2 * Bacula doubly linked list routines.
4 * dlist is a doubly linked list with the links being in the
7 * Kern Sibbald, July MMIII
13 Copyright (C) 2000-2004 Kern Sibbald and John Walker
15 This program is free software; you can redistribute it and/or
16 modify it under the terms of the GNU General Public License as
17 published by the Free Software Foundation; either version 2 of
18 the License, or (at your option) any later version.
20 This program is distributed in the hope that it will be useful,
21 but WITHOUT ANY WARRANTY; without even the implied warranty of
22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 General Public License for more details.
25 You should have received a copy of the GNU General Public
26 License along with this program; if not, write to the Free
27 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
34 /* ===================================================================
39 * Append an item to the list
41 void dlist::append(void *item)
43 ((dlink *)(((char *)item)+loffset))->next = NULL;
44 ((dlink *)(((char *)item)+loffset))->prev = tail;
46 ((dlink *)(((char *)tail)+loffset))->next = item;
49 if (head == NULL) { /* if empty list, */
50 head = item; /* item is head as well */
56 * Append an item to the list
58 void dlist::prepend(void *item)
60 ((dlink *)(((char *)item)+loffset))->next = head;
61 ((dlink *)(((char *)item)+loffset))->prev = NULL;
63 ((dlink *)(((char *)head)+loffset))->prev = item;
66 if (tail == NULL) { /* if empty list, */
67 tail = item; /* item is tail too */
72 void dlist::insert_before(void *item, void *where)
74 dlink *where_link = (dlink *)((char *)where+loffset);
76 ((dlink *)(((char *)item)+loffset))->next = where;
77 ((dlink *)(((char *)item)+loffset))->prev = where_link->prev;
79 if (where_link->prev) {
80 ((dlink *)(((char *)(where_link->prev))+loffset))->next = item;
82 where_link->prev = item;
89 void dlist::insert_after(void *item, void *where)
91 dlink *where_link = (dlink *)((char *)where+loffset);
93 ((dlink *)(((char *)item)+loffset))->next = where_link->next;
94 ((dlink *)(((char *)item)+loffset))->prev = where;
96 if (where_link->next) {
97 ((dlink *)(((char *)(where_link->next))+loffset))->prev = item;
99 where_link->next = item;
107 * Insert an item in the list, but only if it is unique
108 * otherwise, the item is returned non inserted
110 * Returns: item if item inserted
111 * other_item if same value already exists (item not inserted)
113 void *dlist::unique_binary_insert(void *item, int compare(void *item1, void *item2))
119 if (num_items == 0) {
120 //Dmsg0(000, "Append first.\n");
124 if (num_items == 1) {
125 comp = compare(item, first());
128 //Dmsg0(000, "Insert before first.\n");
130 } else if (comp > 0) {
131 insert_after(item, first());
132 //Dmsg0(000, "Insert after first.\n");
135 //Dmsg0(000, "Same as first.\n");
139 /* Check against last item */
140 comp = compare(item, last());
143 //Dmsg0(000, "Appended item.\n");
145 } else if (comp == 0) {
146 //Dmsg0(000, "Same as last.\n");
149 /* Check against first item */
150 comp = compare(item, first());
153 //Dmsg0(000, "Inserted item before.\n");
155 } else if (comp == 0) {
156 //Dmsg0(000, "Same as first.\n");
159 if (num_items == 2) {
160 insert_after(item, first());
161 //Dmsg0(000, "Inserted item after.\n");
170 nxt = (low + high) / 2;
172 cur_item = next(cur_item);
176 cur_item = prev(cur_item);
179 //Dmsg1(000, "Compare item to %d\n", cur);
180 comp = compare(item, cur_item);
181 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
184 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
185 } else if (comp > 0) {
187 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
189 //Dmsg1(000, "Same as item %d\n", cur);
194 insert_before(item, cur_item);
195 //Dmsg1(000, "Insert before item %d\n", cur);
197 insert_after(item, cur_item);
198 //Dmsg1(000, "Insert after item %d\n", cur);
205 * Insert an item in the list, regardless if it is unique
208 void dlist::binary_insert(void *item, int compare(void *item1, void *item2))
210 void *ins_item = unique_binary_insert(item, compare);
211 /* If identical, insert after the one found */
212 if (ins_item != item) {
213 insert_after(item, ins_item);
218 void dlist::remove(void *item)
221 dlink *ilink = (dlink *)(((char *)item)+loffset); /* item's link */
225 ((dlink *)(((char *)head)+loffset))->prev = NULL;
230 } else if (item == tail) {
233 ((dlink *)(((char *)tail)+loffset))->next = NULL;
237 ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
239 ((dlink *)(((char *)xitem)+loffset))->next = ilink->next;
242 if (num_items == 0) {
247 void * dlist::next(const void *item) const
252 return ((dlink *)(((char *)item)+loffset))->next;
255 void * dlist::prev(const void *item) const
260 return ((dlink *)(((char *)item)+loffset))->prev;
264 /* Destroy the list contents */
265 void dlist::destroy()
267 for (void *n=head; n; ) {
268 void *ni = ((dlink *)(((char *)n)+loffset))->next;
285 static int my_compare(void *item1, void *item2)
289 jcr1 = (MYJCR *)item1;
290 jcr2 = (MYJCR *)item2;
291 comp = strcmp(jcr1->buf, jcr2->buf);
292 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
302 MYJCR *save_jcr = NULL;
305 jcr_chain = (dlist *)malloc(sizeof(dlist));
306 jcr_chain->init(jcr, &jcr->link);
308 printf("Prepend 20 items 0-19\n");
309 for (int i=0; i<20; i++) {
310 sprintf(buf, "This is dlist item %d", i);
311 jcr = (MYJCR *)malloc(sizeof(MYJCR));
312 jcr->buf = bstrdup(buf);
313 jcr_chain->prepend(jcr);
319 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
320 printf("11th item=%s\n", next_jcr->buf);
321 jcr = (MYJCR *)malloc(sizeof(MYJCR));
322 jcr->buf = save_jcr->buf;
323 printf("Remove 10th item\n");
324 jcr_chain->remove(save_jcr);
325 printf("Re-insert 10th item\n");
326 jcr_chain->insert_before(jcr, next_jcr);
328 printf("Print remaining list.\n");
329 foreach_dlist (jcr, jcr_chain) {
330 printf("Dlist item = %s\n", jcr->buf);
333 jcr_chain->destroy();
336 jcr_chain = New(dlist(jcr, &jcr->link));
337 printf("append 20 items 0-19\n");
338 for (int i=0; i<20; i++) {
339 sprintf(buf, "This is dlist item %d", i);
340 jcr = (MYJCR *)malloc(sizeof(MYJCR));
341 jcr->buf = bstrdup(buf);
342 jcr_chain->append(jcr);
348 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
349 printf("11th item=%s\n", next_jcr->buf);
350 jcr = (MYJCR *)malloc(sizeof(MYJCR));
351 jcr->buf = save_jcr->buf;
352 printf("Remove 10th item\n");
353 jcr_chain->remove(save_jcr);
354 printf("Re-insert 10th item\n");
355 jcr_chain->insert_before(jcr, next_jcr);
357 printf("Print remaining list.\n");
358 foreach_dlist (jcr, jcr_chain) {
359 printf("Dlist item = %s\n", jcr->buf);
366 /* Now do a binary insert for the list */
367 jcr_chain = New(dlist(jcr, &jcr->link));
369 printf("append %d items\n", CNT*CNT*CNT);
372 for (int i=0; i<CNT; i++) {
373 for (int j=0; j<CNT; j++) {
374 for (int k=0; k<CNT; k++) {
376 if ((count & 0x3FF) == 0) {
377 Dmsg1(000, "At %d\n", count);
379 jcr = (MYJCR *)malloc(sizeof(MYJCR));
380 jcr->buf = bstrdup(buf);
381 jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
383 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
394 printf("Print sorted list.\n");
395 foreach_dlist (jcr, jcr_chain) {
396 printf("Dlist item = %s\n", jcr->buf);