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

   1 /*
   2    Bacula(R) - The Network Backup Solution
   3
   4    Copyright (C) 2000-2017 Kern Sibbald
   5
   6    The original author of Bacula is Kern Sibbald, with contributions
   7    from many others, a complete list can be found in the file AUTHORS.
   8
   9    You may use this file and others of this release according to the
  10    license defined in the LICENSE file, which includes the Affero General
  11    Public License, v3.0 ("AGPLv3") and some additional permissions and
  12    terms pursuant to its AGPLv3 Section 7.
  13
  14    This notice must be preserved when any source code is
  15    conveyed and/or propagated.
  16
  17    Bacula(R) is a registered trademark of Kern Sibbald.
  18 */
  19 /*
  20  *  Kern Sibbald, June MMIII
  21  */
  22
  23
  24 extern bool is_null(const void *ptr);
  25
  26 /*
  27  * There is a lot of extra casting here to work around the fact
  28  * that some compilers (Sun and Visual C++) do not accept
  29  * (void *) as an lvalue on the left side of an equal.
  30  *
  31  * Loop var through each member of list
  32  */
  33 #ifdef HAVE_TYPEOF
  34 #define foreach_alist(var, list) \
  35         for((var)=(typeof(var))(list)->first(); (var); (var)=(typeof(var))(list)->next() )
  36 #else
  37 #define foreach_alist(var, list) \
  38     for((*((void **)&(var))=(void*)((list)->first())); \
  39          (var); \
  40          (*((void **)&(var))=(void*)((list)->next())))
  41 #endif
  42
  43 #ifdef HAVE_TYPEOF
  44 #define foreach_alist_index(inx, var, list) \
  45         for(inx=0; ((var)=(typeof(var))(list)->get(inx)); inx++ )
  46 #else
  47 #define foreach_alist_index(inx, var, list) \
  48     for(inx=0; ((*((void **)&(var))=(void*)((list)->get(inx)))); inx++ )
  49 #endif
  50
  51
  52
  53
  54 /* Second arg of init */
  55 enum {
  56   owned_by_alist = true,
  57   not_owned_by_alist = false
  58 };
  59
  60 /*
  61  * Array list -- much like a simplified STL vector
  62  *   array of pointers to inserted items. baselist is
  63  *   the common code between alist and ilist
  64  */
  65 class baselist : public SMARTALLOC {
  66 protected:
  67    void **items;                /* from  0..n-1 */
  68    int num_items;               /* from  1..n   */
  69    int last_item;               /* maximum item index (1..n) */
  70    int max_items;               /* maximum possible items (array size) (1..n) */
  71    int num_grow;
  72    int cur_item;                /* from 1..n */
  73    bool own_items;
  74    void grow_list(void);
  75    void *remove_item(int index);
  76 public:
  77    baselist(int num = 100, bool own=true);
  78    ~baselist();
  79    void init(int num = 100, bool own=true);
  80    void append(void *item);
  81    void *get(int index);
  82    bool empty() const;
  83    int last_index() const { return last_item; };
  84    int max_size() const { return max_items; };
  85    void * operator [](int index) const;
  86    int current() const { return cur_item; };
  87    int size() const;
  88    void destroy();
  89    void grow(int num);
  90
  91    /* Use it as a stack, pushing and poping from the end */
  92    void push(void *item) { append(item); };
  93    void *pop() { return remove_item(num_items-1); };
  94 };
  95
  96 class alist: public baselist
  97 {
  98 public:
  99    alist(int num = 100, bool own=true): baselist(num, own) {};
 100    void *prev();
 101    void *next();
 102    void *last();
 103    void *first();
 104    void prepend(void *item);
 105    void *remove(int index) { return remove_item(index);};
 106 };
 107
 108 /*
 109  * Indexed list -- much like a simplified STL vector
 110  *   array of pointers to inserted items
 111  */
 112 class ilist : public baselist {
 113 public:
 114    ilist(int num = 100, bool own=true): baselist(num, own) {};
 115     /* put() is not compatible with remove(), prepend() or foreach_alist */
 116    void put(int index, void *item);
 117 };
 118
 119 /*
 120  * Define index operator []
 121  */
 122 inline void * baselist::operator [](int index) const {
 123    if (index < 0 || index >= max_items) {
 124       return NULL;
 125    }
 126    return items[index];
 127 }
 128
 129 inline bool baselist::empty() const
 130 {
 131    return num_items == 0;
 132 }
 133
 134 /*
 135  * This allows us to do explicit initialization,
 136  *   allowing us to mix C++ classes inside malloc'ed
 137  *   C structures. Define before called in constructor.
 138  */
 139 inline void baselist::init(int num, bool own)
 140 {
 141    items = NULL;
 142    num_items = 0;
 143    last_item = 0;
 144    max_items = 0;
 145    num_grow = num;
 146    own_items = own;
 147 }
 148
 149 /* Constructor */
 150 inline baselist::baselist(int num, bool own)
 151 {
 152    init(num, own);
 153 }
 154
 155 /* Destructor */
 156 inline baselist::~baselist()
 157 {
 158    destroy();
 159 }
 160
 161 /* Current size of list */
 162 inline int baselist::size() const
 163 {
 164    if (is_null(this)) return 0;
 165    return num_items;
 166 }
 167
 168 /* How much to grow by each time */
 169 inline void baselist::grow(int num)
 170 {
 171    num_grow = num;
 172 }