/******************************************************************************
 * qLibc
 *
 * Copyright (c) 2010-2015 Seungyoung Kim.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *****************************************************************************/

/**
 * Tree Table container that implements "Left-Leaning Red-Black" Binary Search Tree algorithm.
 *
 * @file qtreetbl.h
 */

#ifndef QTREETBL_H
#define QTREETBL_H

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

/* types */
typedef struct qtreetbl_s qtreetbl_t;
typedef struct qtreetbl_obj_s qtreetbl_obj_t;

/* public functions */
enum {
    QTREETBL_THREADSAFE = (0x01) /*!< make it thread-safe */
};

extern qtreetbl_t *qtreetbl(int options); /*!< qtreetbl constructor */

/* member functions
 *
 * All the member functions can be accessed in both ways:
 *  - tbl->put(tbl, ...);      // easier to switch the container type to other kinds.
 *  - qtreetbl_put(tbl, ...);  // where avoiding pointer overhead is preferred.
 */
extern void qtreetbl_set_compare(qtreetbl_t *tbl,
                                 int (*cmp)(const void *name1, size_t namesize1,
                                            const void *name2, size_t namesize2));

extern bool qtreetbl_put(qtreetbl_t *tbl, const char *name, const void *data,
                         size_t datasize);
extern bool qtreetbl_putstr(qtreetbl_t *tbl, const char *name, const char *str);
extern bool qtreetbl_putstrf(qtreetbl_t *tbl, const char *name,
                             const char *format, ...);
extern bool qtreetbl_putobj(qtreetbl_t *tbl, const void *name, size_t namesize,
                            const void *data, size_t datasize);

extern void *qtreetbl_get(qtreetbl_t *tbl,
                          const char *name, size_t *datasize, bool newmem);
extern char *qtreetbl_getstr(qtreetbl_t *tbl, const char *name, const bool newmem);
extern void *qtreetbl_getobj(qtreetbl_t *tbl, const void *name, size_t namesize,
                             size_t *datasize, bool newmem);

extern bool qtreetbl_remove(qtreetbl_t *tbl, const char *name);
extern bool qtreetbl_removeobj(qtreetbl_t *tbl, const void *name, size_t namesize);

extern bool qtreetbl_getnext(qtreetbl_t *tbl, qtreetbl_obj_t *obj, const bool newmem);

extern void *qtreetbl_find_min(qtreetbl_t *tbl, size_t *namesize);
extern void *qtreetbl_find_max(qtreetbl_t *tbl, size_t *namesize);
extern qtreetbl_obj_t qtreetbl_find_nearest(qtreetbl_t *tbl, const void *name,
                                            size_t namesize, bool newmem);

extern size_t qtreetbl_size(qtreetbl_t *tbl);
extern void qtreetbl_clear(qtreetbl_t *tbl);

extern void qtreetbl_lock(qtreetbl_t *tbl);
extern void qtreetbl_unlock(qtreetbl_t *tbl);

extern void qtreetbl_free(qtreetbl_t *tbl);

extern int qtreetbl_byte_cmp(const void *name1, size_t namesize1,
                             const void *name2, size_t namesize2);
extern bool qtreetbl_debug(qtreetbl_t *tbl, FILE *out);
extern int qtreetbl_check(qtreetbl_t *tbl);

/**
 * qtreetbl container object
 */
struct qtreetbl_s {
    /* encapsulated member functions */
    void (*set_compare)(qtreetbl_t *tbl,
        int (*cmp)(const void *name1, size_t namesize1, const void *name2,
        size_t namesize2));
    bool (*put)(qtreetbl_t *tbl, const char *name, const void *data, size_t size);
    bool (*putstr)(qtreetbl_t *tbl, const char *name, const char *str);
    bool (*putstrf)(qtreetbl_t *tbl, const char *name, const char *format, ...);
    bool (*putobj)(qtreetbl_t *tbl, const void *name, size_t namesize,
                   const void *data, size_t datasize);

    void *(*get)(qtreetbl_t *tbl, const char *name, size_t *datasize,
    bool newmem);
    char *(*getstr)(qtreetbl_t *tbl, const char *name, bool newmem);
    void *(*getobj)(qtreetbl_t *tbl, const void *name, size_t namesize,
                    size_t *datasize, bool newmem);

    bool (*remove)(qtreetbl_t *tbl, const char *name);
    bool (*removeobj)(qtreetbl_t *tbl, const void *name, size_t namesize);

    bool (*getnext)(qtreetbl_t *tbl, qtreetbl_obj_t *obj, const bool newmem);

    void *(*find_min)(qtreetbl_t *tbl, size_t *namesize);
    void *(*find_max)(qtreetbl_t *tbl, size_t *namesize);
    qtreetbl_obj_t (*find_nearest)(qtreetbl_t *tbl, const void *name,
                                   size_t namesize, bool newmem);

    size_t (*size)(qtreetbl_t *tbl);
    void (*clear)(qtreetbl_t *tbl);
    bool (*debug)(qtreetbl_t *tbl, FILE *out);

    void (*lock)(qtreetbl_t *tbl);
    void (*unlock)(qtreetbl_t *tbl);

    void (*free)(qtreetbl_t *tbl);

    /* private member functions */
    int (*compare)(const void *name1, size_t namesize1, const void *name2,
                   size_t namesize2);

    /* private variables - do not access directly */
    void *qmutex;           /*!< initialized when QTREETBL_THREADSAFE is given */
    qtreetbl_obj_t *root;   /*!< root node */
    size_t num;             /*!< number of objects */
    uint8_t tid;            /*!< travel id sequencer */
};

/**
 * qtreetbl object data structure
 */
struct qtreetbl_obj_s {
    void *name;             /*!< name of key */
    size_t namesize;        /*!< name size */
    void *data;             /*!< data */
    size_t datasize;        /*!< data size */

    bool red;               /*!< true if upper link is red */
    qtreetbl_obj_t *left;   /*!< left node */
    qtreetbl_obj_t *right;  /*!< right node */

    qtreetbl_obj_t *next;   /*!< temporary use for tree traversal */
    uint8_t tid;            /*!< temporary use for tree traversal */
};

#ifdef __cplusplus
}
#endif

#endif /* QTREETBL_H */
