git.sur5r.net Git - bacula/bacula/blob - 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 }