rbtree.h

Go to the documentation of this file.

/***************************************************************************
    begin........: May 2012
    copyright....: Sebastian Fedrau
    email........: sebastian.fedrau@gmail.com
 ***************************************************************************/
 
/***************************************************************************
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License v3 as published by
    the Free Software Foundation.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    General Public License v3 for more details.
 ***************************************************************************/
#ifndef RBTREE_H
#define RBTREE_H
 
#include <stdbool.h>
#include <stdint.h>
 
#include "datatypes.h"
#include "pool.h"
 
typedef struct _rbnode
{
    void *key;
    void *value;
    struct _rbnode *left;
    struct _rbnode *right;
    bool black;
} RBNode;
 
typedef struct
{
    CompareFunc compare_keys;
    FreeFunc free_key;
    FreeFunc free_value;
    RBNode *root;
    RBNode **stack;
    RBNode **sp;
    size_t stack_size;
    Pool *pool;
    size_t count;
    struct _RBTreePair
    {
        FreeFunc free_value;
        RBNode *node;
    } pair;
} RBTree;
 
typedef struct _RBTreePair RBTreePair;
 
typedef enum
{
    RBTREE_INSERT_RESULT_NEW,
    RBTREE_INSERT_RESULT_REPLACED,
    RBTREE_INSERT_RESULT_FAILED
} RBTreeInsertResult;
 
typedef struct
{
    RBNode *node;
    int state;
} RBTreeIterStackItem;
 
typedef struct
{
    const RBTree *tree;
    RBTreeIterStackItem *stack;
    RBTreeIterStackItem *sp;
    size_t stack_size;
    bool finished;
} RBTreeIter;
 
RBTree *rbtree_new(CompareFunc compare_keys, FreeFunc free_key, FreeFunc free_value, Pool *pool);
 
void rbtree_init(RBTree *tree, CompareFunc compare_keys, FreeFunc free_key, FreeFunc free_value, Pool *pool);
 
void rbtree_free(RBTree *tree);
 
void rbtree_destroy(RBTree *tree);
 
void rbtree_clear(RBTree *tree);
 
RBTreeInsertResult rbtree_set(RBTree *tree, void *key, void *value, bool replace_key);
 
size_t rbtree_count(const RBTree *tree);
 
RBTreePair *rbtree_lookup(RBTree *tree, const void *key);
 
void *rbtree_pair_get_key(const RBTreePair *pair);
 
#define rbtree_pair_key(p) p->node->key
 
void *rbtree_pair_get_value(const RBTreePair *pair);
 
#define rbtree_pair_value(p) p->node->value
 
void rbtree_pair_set_value(RBTreePair *pair, void *value);
 
bool rbtree_key_exists(const RBTree *tree, const void *key);
 
bool rbtree_remove(RBTree *tree, const void *key);
 
void rbtree_iter_init(const RBTree *tree, RBTreeIter *iter);
 
void rbtree_iter_free(RBTreeIter *iter);
 
void rbtree_iter_reuse(const RBTree *tree, RBTreeIter *iter);
 
bool rbtree_iter_next(RBTreeIter *iter);
 
void *rbtree_iter_get_key(const RBTreeIter *iter);
 
#define rbtree_iter_key(iter) iter.sp->node->key
 
void *rbtree_iter_get_value(const RBTreeIter *iter);
 
#define rbtree_iter_value(iter) iter.sp->node->value
 
#endif