17Mar06

[bacula/bacula] / bacula / src / lib / dlist.h

diff --git a/bacula/src/lib/dlist.h b/bacula/src/lib/dlist.h
index 0b4a154789a049cc3553c47558f639f83a628ff7..40c54f013379ee396a81b902b6bd5c9afa2599d2 100644 (file)
--- a/bacula/src/lib/dlist.h
+++ b/bacula/src/lib/dlist.h
@@ -1,111 +1,134 @@
 /*
  *   Version $Id$
  */
-
 /*
-   Copyright (C) 2000-2003 Kern Sibbald and John Walker
+   Copyright (C) 2004-2006 Kern Sibbald
 
    This program is free software; you can redistribute it and/or
-   modify it under the terms of the GNU General Public License as
-   published by the Free Software Foundation; either version 2 of
-   the License, or (at your option) any later version.
+   modify it under the terms of the GNU General Public License
+   version 2 as amended with additional clauses defined in the
+   file LICENSE in the main source directory.
 
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-   General Public License for more details.
-
-   You should have received a copy of the GNU General Public
-   License along with this program; if not, write to the Free
-   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
-   MA 02111-1307, USA.
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
+   the file LICENSE for additional details.
 
  */
 
+
 /* ========================================================================
- * 
+ *
  *   Doubly linked list  -- dlist
  *
+ *    Kern Sibbald, MMIV
+ *
  */
 
-#define OFFSET(item,link) ((char *)link - (char *)item)
+#define M_ABORT 1
+
+/* In case you want to specifically specify the offset to the link */
+#define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
+/*
+ * There is a lot of extra casting here to work around the fact
+ * that some compilers (Sun and Visual C++) do not accept
+ * (void *) as an lvalue on the left side of an equal.
+ *
+ * Loop var through each member of list
+ */
+#define foreach_dlist(var, list) \
+    for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
+
+#ifdef the_old_way
+#define foreach_dlist(var, list) \
+        for((var)=NULL; (((void *)(var))=(list)->next(var)); )
+#endif
+
 
 struct dlink {
    void *next;
    void *prev;
 };
 
-class dlist {
+class dlist : public SMARTALLOC {
    void *head;
    void *tail;
-   int loffset;
-   int num_items;
+   int16_t loffset;
+   uint32_t num_items;
 public:
-   dlist(void *item, void *link);
-   void init(void *item, void *link);
+   dlist(void *item, dlink *link);
+   dlist(void);
+   ~dlist() { destroy(); }
+   void init(void *item, dlink *link);
    void prepend(void *item);
    void append(void *item);
    void insert_before(void *item, void *where);
    void insert_after(void *item, void *where);
+   void *binary_insert(void *item, int compare(void *item1, void *item2));
+   void *binary_search(void *item, int compare(void *item1, void *item2));
+   void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
    void remove(void *item);
-   bool empty();
-   int  size();
-   void *next(void *item);
-   void *prev(void *item);
+   bool empty() const;
+   int  size() const;
+   void *next(const void *item) const;
+   void *prev(const void *item) const;
    void destroy();
-   void *first();
-   void *last();
-   void * operator new(size_t);
-   void operator delete(void *);
+   void *first() const;
+   void *last() const;
 };
 
-/*                            
+
+/*
  * This allows us to do explicit initialization,
  *   allowing us to mix C++ classes inside malloc'ed
  *   C structures. Define before called in constructor.
  */
-inline void dlist::init(void *item, void *link) 
+inline void dlist::init(void *item, dlink *link)
 {
    head = tail = NULL;
-   loffset = (char *)link - (char *)item;
+   loffset = (int)((char *)link - (char *)item);
+   if (loffset < 0 || loffset > 5000) {
+      Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
+   }
    num_items = 0;
 }
 
-/* Constructor */
-inline dlist::dlist(void *item, void *link)
+/*
+ * Constructor called with the address of a
+ *   member of the list (not the list head), and
+ *   the address of the link within that member.
+ * If the link is at the beginning of the list member,
+ *   then there is no need to specify the link address
+ *   since the offset is zero.
+ */
+inline dlist::dlist(void *item, dlink *link)
 {
-   this->init(item, link);
+   init(item, link);
 }
 
-inline bool dlist::empty()
+/* Constructor with link at head of item */
+inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 {
-   return head == NULL;
 }
 
-inline int dlist::size()
+inline bool dlist::empty() const
 {
-   return num_items;
+   return head == NULL;
 }
 
-   
-inline void * dlist::operator new(size_t)
+inline int dlist::size() const
 {
-   return malloc(sizeof(dlist));
+   return num_items;
 }
 
-inline void dlist::operator delete(void  *item)
-{
-   ((dlist *)item)->destroy();
-   free(item);
-}
- 
 
-inline void * dlist::first()
+
+inline void * dlist::first() const
 {
    return head;
 }
 
-inline void * dlist::last()
+inline void * dlist::last() const
 {
    return tail;
 }