2 * Written by Kern Sibbald MMIV
7 Bacula® - The Network Backup Solution
9 Copyright (C) 2004-2006 Free Software Foundation Europe e.V.
11 The main author of Bacula is Kern Sibbald, with contributions from
12 many others, a complete list can be found in the file AUTHORS.
13 This program is Free Software; you can redistribute it and/or
14 modify it under the terms of version two of the GNU General Public
15 License as published by the Free Software Foundation plus additions
16 that are listed in the file LICENSE.
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
28 Bacula® is a registered trademark of John Walker.
29 The licensor of Bacula is the Free Software Foundation Europe
30 (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
31 Switzerland, email:ftf@fsfeurope.org.
35 /* ========================================================================
37 * Doubly linked list -- dlist
45 /* In case you want to specifically specify the offset to the link */
46 #define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
48 * There is a lot of extra casting here to work around the fact
49 * that some compilers (Sun and Visual C++) do not accept
50 * (void *) as an lvalue on the left side of an equal.
52 * Loop var through each member of list
55 #define foreach_dlist(var, list) \
56 for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); )
58 #define foreach_dlist(var, list) \
59 for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
69 class dlist : public SMARTALLOC {
75 dlist(void *item, dlink *link);
77 ~dlist() { destroy(); }
78 void init(void *item, dlink *link);
79 void prepend(void *item);
80 void append(void *item);
81 void insert_before(void *item, void *where);
82 void insert_after(void *item, void *where);
83 void *binary_insert(void *item, int compare(void *item1, void *item2));
84 void *binary_search(void *item, int compare(void *item1, void *item2));
85 void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
86 void remove(void *item);
89 void *next(const void *item) const;
90 void *prev(const void *item) const;
98 * This allows us to do explicit initialization,
99 * allowing us to mix C++ classes inside malloc'ed
100 * C structures. Define before called in constructor.
102 inline void dlist::init(void *item, dlink *link)
105 loffset = (int)((char *)link - (char *)item);
106 if (loffset < 0 || loffset > 5000) {
107 Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
113 * Constructor called with the address of a
114 * member of the list (not the list head), and
115 * the address of the link within that member.
116 * If the link is at the beginning of the list member,
117 * then there is no need to specify the link address
118 * since the offset is zero.
120 inline dlist::dlist(void *item, dlink *link)
125 /* Constructor with link at head of item */
126 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
130 inline bool dlist::empty() const
135 inline int dlist::size() const
142 inline void * dlist::first() const
147 inline void * dlist::last() const