]> git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/btree.h
ebl add Error status in update volume=xxx status=yyyy
[bacula/bacula] / bacula / src / lib / btree.h
1 /*
2  *   Version $Id$
3  */
4 /*
5    Bacula® - The Network Backup Solution
6
7    Copyright (C) 2005-2006 Free Software Foundation Europe e.V.
8
9    The main author of Bacula is Kern Sibbald, with contributions from
10    many others, a complete list can be found in the file AUTHORS.
11    This program is Free Software; you can redistribute it and/or
12    modify it under the terms of version two of the GNU General Public
13    License as published by the Free Software Foundation plus additions
14    that are listed in the file LICENSE.
15
16    This program is distributed in the hope that it will be useful, but
17    WITHOUT ANY WARRANTY; without even the implied warranty of
18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19    General Public License for more details.
20
21    You should have received a copy of the GNU General Public License
22    along with this program; if not, write to the Free Software
23    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
24    02110-1301, USA.
25
26    Bacula® is a registered trademark of John Walker.
27    The licensor of Bacula is the Free Software Foundation Europe
28    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
29    Switzerland, email:ftf@fsfeurope.org.
30 */
31
32
33 /* ========================================================================
34  *
35  *   red-black binary tree routines -- btree.h
36  *
37  *    Kern Sibbald, MMV
38  *
39  */
40
41 #define M_ABORT 1
42
43 /*
44  * There is a lot of extra casting here to work around the fact
45  * that some compilers (Sun and Visual C++) do not accept
46  * (bnode *) as an lvalue on the left side of an equal.
47  *
48  * Loop var through each member of list
49  */
50 #define foreach_btree(var, tree) \
51     for(*((bnode **)&(var))=(tree)->first(); (*((bnode **)&(var))=(tree)->next((bnode *)var)); )
52
53 #ifdef the_old_way
54 #define foreach_btree(var, tree) \
55         for((var)=(tree)->first(); (((bnode *)(var))=(tree)->next((bnode *)var)); )
56 #endif
57
58 struct bnode;
59 struct bnode {
60    bnode *left;
61    bnode *right;
62    bnode *parent;
63    bool red;
64 };
65
66 class btree : public SMARTALLOC {
67    bnode *head;
68    uint32_t num_items;
69    bool down;
70    void left_rotate(bnode *item);
71    void right_rotate(bnode *item);
72 public:
73    btree(void);
74    ~btree() { destroy(); }
75    void init(void);
76    bnode *insert(bnode *item, int compare(bnode *item1, bnode *item2));
77    bnode *search(bnode *item, int compare(bnode *item1, bnode *item2));
78    bnode *first(void);
79    bnode *next(bnode *item);
80    bnode *any(bnode *item);
81    void remove(bnode *item);
82    int  size() const;
83    void destroy();
84 };
85
86
87 /*
88  * This allows us to do explicit initialization,
89  *   allowing us to mix C++ classes inside malloc'ed
90  *   C structures. Define before called in constructor.
91  */
92 inline void btree::init()
93 {
94    head = NULL;
95    num_items = 0;
96 }
97
98
99 /* Constructor with link at head of item */
100 inline btree::btree(void) : head(0), num_items(0)
101 {
102 }
103
104 inline int btree::size() const
105 {
106    return num_items;
107 }