5 Copyright (C) 2005-2006 Kern Sibbald
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License
9 version 2 as amended with additional clauses defined in the
10 file LICENSE in the main source directory.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 the file LICENSE for additional details.
20 /* ========================================================================
22 * red-black binary tree routines -- btree.h
31 * There is a lot of extra casting here to work around the fact
32 * that some compilers (Sun and Visual C++) do not accept
33 * (bnode *) as an lvalue on the left side of an equal.
35 * Loop var through each member of list
37 #define foreach_btree(var, tree) \
38 for(*((bnode **)&(var))=(tree)->first(); (*((bnode **)&(var))=(tree)->next((bnode *)var)); )
41 #define foreach_btree(var, tree) \
42 for((var)=(tree)->first(); (((bnode *)(var))=(tree)->next((bnode *)var)); )
53 class btree : public SMARTALLOC {
57 void left_rotate(bnode *item);
58 void right_rotate(bnode *item);
61 ~btree() { destroy(); }
63 bnode *insert(bnode *item, int compare(bnode *item1, bnode *item2));
64 bnode *search(bnode *item, int compare(bnode *item1, bnode *item2));
66 bnode *next(bnode *item);
67 bnode *any(bnode *item);
68 void remove(bnode *item);
75 * This allows us to do explicit initialization,
76 * allowing us to mix C++ classes inside malloc'ed
77 * C structures. Define before called in constructor.
79 inline void btree::init()
86 /* Constructor with link at head of item */
87 inline btree::btree(void) : head(0), num_items(0)
91 inline int btree::size() const