2 Bacula® - The Network Backup Solution
4 Copyright (C) 2004-2007 Free Software Foundation Europe e.V.
6 The main author of Bacula is Kern Sibbald, with contributions from
7 many others, a complete list can be found in the file AUTHORS.
8 This program is Free Software; you can redistribute it and/or
9 modify it under the terms of version two of the GNU General Public
10 License as published by the Free Software Foundation and included
13 This program is distributed in the hope that it will be useful, but
14 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 License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
23 Bacula® is a registered trademark of John Walker.
24 The licensor of Bacula is the Free Software Foundation Europe
25 (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
26 Switzerland, email:ftf@fsfeurope.org.
29 * Written by Kern Sibbald MMIV
35 /* ========================================================================
37 * Doubly linked list -- dlist
39 * See the end of the file for the dlistString class which
40 * facilitates storing strings in a dlist.
42 * Kern Sibbald, MMIV and MMVII
48 /* In case you want to specifically specify the offset to the link */
49 #define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
51 * There is a lot of extra casting here to work around the fact
52 * that some compilers (Sun and Visual C++) do not accept
53 * (void *) as an lvalue on the left side of an equal.
55 * Loop var through each member of list
58 #define foreach_dlist(var, list) \
59 for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); )
61 #define foreach_dlist(var, list) \
62 for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
70 class dlist : public SMARTALLOC {
76 dlist(void *item, dlink *link);
78 ~dlist() { destroy(); }
79 void init(void *item, dlink *link);
81 void prepend(void *item);
82 void append(void *item);
83 void set_prev(void *item, void *prev);
84 void set_next(void *item, void *next);
85 void *get_prev(void *item);
86 void *get_next(void *item);
87 dlink *get_link(void *item);
88 void insert_before(void *item, void *where);
89 void insert_after(void *item, void *where);
90 void *binary_insert(void *item, int compare(void *item1, void *item2));
91 void *binary_search(void *item, int compare(void *item1, void *item2));
92 void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
93 void remove(void *item);
96 void *next(void *item);
97 void *prev(void *item);
105 * This allows us to do explicit initialization,
106 * allowing us to mix C++ classes inside malloc'ed
107 * C structures. Define before called in constructor.
109 inline void dlist::init(void *item, dlink *link)
112 loffset = (int)((char *)link - (char *)item);
113 if (loffset < 0 || loffset > 5000) {
114 Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
119 inline void dlist::init()
128 * Constructor called with the address of a
129 * member of the list (not the list head), and
130 * the address of the link within that member.
131 * If the link is at the beginning of the list member,
132 * then there is no need to specify the link address
133 * since the offset is zero.
135 inline dlist::dlist(void *item, dlink *link)
140 /* Constructor with link at head of item */
141 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
145 inline void dlist::set_prev(void *item, void *prev)
147 ((dlink *)(((char *)item)+loffset))->prev = prev;
150 inline void dlist::set_next(void *item, void *next)
152 ((dlink *)(((char *)item)+loffset))->next = next;
155 inline void *dlist::get_prev(void *item)
157 return ((dlink *)(((char *)item)+loffset))->prev;
160 inline void *dlist::get_next(void *item)
162 return ((dlink *)(((char *)item)+loffset))->next;
166 inline dlink *dlist::get_link(void *item)
168 return (dlink *)(((char *)item)+loffset);
173 inline bool dlist::empty() const
178 inline int dlist::size() const
185 inline void * dlist::first() const
190 inline void * dlist::last() const
196 * C string helper routines for dlist
197 * The string (char *) is kept in the node
199 * Kern Sibbald, February 2007
205 char *c_str() { return m_str; };
210 /* !!! Don't put anything after this as this space is used
211 * to hold the string in inline
215 extern dlistString *new_dlistString(const char *str, int len);
216 extern dlistString *new_dlistString(const char *str);