red_black_tree.h 1.78 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
/* 
 * Copyright (c) 2012 Christoph Mueller <ruunhb@googlemail.com>
 * 
 * Crystal is free software: you can redistribute it and/or modify
 * it under the terms of the Lesser GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * Crystal 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
 * Lesser GNU General Public License for more details.
 *
 * You should have received a copy of the Lesser GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifndef CRYSTAL_STRUCTURES_REDBLACKTREE_H
#define CRYSTAL_STRUCTURES_REDBLACKTREE_H

#include "structures.h"

enum RBNodeColor { RED, BLACK };

struct RBNode {
27
    const_pointer entry;
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
    enum RBNodeColor color;
    struct RBNode* parent;
    struct RBNode* left;
    struct RBNode* right;
};


struct RBTree {
    struct RBNode* root;
    cry_ordering_funptr compare;
    size_t nodes;
};


#define RB_PARENT(node) node->parent
#define RB_GRAND_PARENT(node) node->parent->parent


struct RBTree*          rb_tree_new(cry_ordering_funptr compare);
47
void			rb_tree_clear(struct RBTree* tree, cry_free_funptr free_key);
48

49 50 51
struct RBNode*          rb_tree_lookup(struct RBTree* tree, const_pointer entry);
struct RBNode*          rb_tree_insert(struct RBTree* tree, const_pointer entry);
struct RBNode*          rb_tree_remove(struct RBTree* tree, const_pointer entry);
52

53 54
struct RBNode*          rb_node_new(enum RBNodeColor color, struct RBNode* parent, const_pointer entry);
void			rb_node_free(struct RBNode* node, cry_free_funptr entry_key);
55 56 57 58 59 60





#endif // CRYSTAL_STRUCTURES_REDBLACKTREE_H