5 Copyright (C) 2004-2005 Kern Sibbald
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.
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.
20 /* ========================================================================
22 * Doubly linked list -- dlist
30 /* In case you want to specifically specify the offset to the link */
31 #define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
33 * There is a lot of extra casting here to work around the fact
34 * that some compilers (Sun and Visual C++) do not accept
35 * (void *) as an lvalue on the left side of an equal.
37 * Loop var through each member of list
39 #define foreach_dlist(var, list) \
40 for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
43 #define foreach_dlist(var, list) \
44 for((var)=NULL; (((void *)(var))=(list)->next(var)); )
53 class dlist : public SMARTALLOC {
59 dlist(void *item, dlink *link);
61 ~dlist() { destroy(); }
62 void init(void *item, dlink *link);
63 void prepend(void *item);
64 void append(void *item);
65 void insert_before(void *item, void *where);
66 void insert_after(void *item, void *where);
67 void *binary_insert(void *item, int compare(void *item1, void *item2));
68 void *binary_search(void *item, int compare(void *item1, void *item2));
69 void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
70 void remove(void *item);
73 void *next(const void *item) const;
74 void *prev(const void *item) const;
82 * This allows us to do explicit initialization,
83 * allowing us to mix C++ classes inside malloc'ed
84 * C structures. Define before called in constructor.
86 inline void dlist::init(void *item, dlink *link)
89 loffset = (int)((char *)link - (char *)item);
90 if (loffset < 0 || loffset > 5000) {
91 Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
97 * Constructor called with the address of a
98 * member of the list (not the list head), and
99 * the address of the link within that member.
100 * If the link is at the beginning of the list member,
101 * then there is no need to specify the link address
102 * since the offset is zero.
104 inline dlist::dlist(void *item, dlink *link)
109 /* Constructor with link at head of item */
110 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
114 inline bool dlist::empty() const
119 inline int dlist::size() const
126 inline void * dlist::first() const
131 inline void * dlist::last() const