git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/btree.h

   1 /*
   2  *   Version $Id$
   3  */
   4 /*
   5    Copyright (C) 2005 Kern Sibbald
   6
   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.
  11
  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.
  16
  17  */
  18
  19
  20 /* ========================================================================
  21  *
  22  *   red-black binary tree routines -- btree.h
  23  *
  24  *    Kern Sibbald, MMV
  25  *
  26  */
  27
  28 #define M_ABORT 1
  29
  30 /*
  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.
  34  *
  35  * Loop var through each member of list
  36  */
  37 #define foreach_btree(var, tree) \
  38     for(*((bnode **)&(var))=(tree)->first(); (*((bnode **)&(var))=(tree)->next((bnode *)var)); )
  39
  40 #ifdef the_old_way
  41 #define foreach_btree(var, tree) \
  42         for((var)=(tree)->first(); (((bnode *)(var))=(tree)->next((bnode *)var)); )
  43 #endif
  44
  45 struct bnode;
  46 struct bnode {
  47    bnode *left;
  48    bnode *right;
  49    bnode *parent;
  50    bool red;
  51 };
  52
  53 class btree : public SMARTALLOC {
  54    bnode *head;
  55    uint32_t num_items;
  56    bool down;
  57    void left_rotate(bnode *item);
  58    void right_rotate(bnode *item);
  59 public:
  60    btree(void);
  61    ~btree() { destroy(); }
  62    void init(void);
  63    bnode *insert(bnode *item, int compare(bnode *item1, bnode *item2));
  64    bnode *search(bnode *item, int compare(bnode *item1, bnode *item2));
  65    bnode *first(void);
  66    bnode *next(bnode *item);
  67    bnode *any(bnode *item);
  68    void remove(bnode *item);
  69    int  size() const;
  70    void destroy();
  71 };
  72
  73
  74 /*
  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.
  78  */
  79 inline void btree::init()
  80 {
  81    head = NULL;
  82    num_items = 0;
  83 }
  84
  85
  86 /* Constructor with link at head of item */
  87 inline btree::btree(void) : head(0), num_items(0)
  88 {
  89 }
  90
  91 inline int btree::size() const
  92 {
  93    return num_items;
  94 }