6 Copyright (C) 2000-2004 Kern Sibbald and John Walker
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of
11 the License, or (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public
19 License along with this program; if not, write to the Free
20 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 /* ========================================================================
27 * Doubly linked list -- dlist
33 /* In case you want to specifically specify the offset to the link */
34 #define OFFSET(item, link) ((char *)(link) - (char *)(item))
36 * There is a lot of extra casting here to work around the fact
37 * that some compilers (Sun and Visual C++) do not accept
38 * (void *) as an lvalue on the left side of an equal.
40 * Loop var through each member of list
42 #define foreach_dlist(var, list) \
43 for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
46 #define foreach_dlist(var, list) \
47 for((var)=NULL; (((void *)(var))=(list)->next(var)); )
56 class dlist : public SMARTALLOC {
62 dlist(void *item, dlink *link);
64 ~dlist() { destroy(); }
65 void init(void *item, dlink *link);
66 void prepend(void *item);
67 void append(void *item);
68 void insert_before(void *item, void *where);
69 void insert_after(void *item, void *where);
70 void *unique_binary_insert(void *item, int compare(void *item1, void *item2));
71 void binary_insert(void *item, int compare(void *item1, void *item2));
72 void remove(void *item);
75 void *next(const void *item) const;
76 void *prev(const void *item) const;
84 * This allows us to do explicit initialization,
85 * allowing us to mix C++ classes inside malloc'ed
86 * C structures. Define before called in constructor.
88 inline void dlist::init(void *item, dlink *link)
91 loffset = (char *)link - (char *)item;
92 if (loffset < 0 || loffset > 5000) {
93 Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
99 * Constructor called with the address of a
100 * member of the list (not the list head), and
101 * the address of the link within that member.
102 * If the link is at the beginning of the list member,
103 * then there is no need to specify the link address
104 * since the offset is zero.
106 inline dlist::dlist(void *item, dlink *link)
111 /* Constructor with link at head of item */
112 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
116 inline bool dlist::empty() const
121 inline int dlist::size() const
128 inline void * dlist::first() const
133 inline void * dlist::last() const