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 Bacula® - The Network Backup Solution
15 Copyright (C) 2003-2006 Free Software Foundation Europe e.V.
17 The main author of Bacula is Kern Sibbald, with contributions from
18 many others, a complete list can be found in the file AUTHORS.
19 This program is Free Software; you can redistribute it and/or
20 modify it under the terms of version two of the GNU General Public
21 License as published by the Free Software Foundation plus additions
22 that are listed in the file LICENSE.
24 This program is distributed in the hope that it will be useful, but
25 WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 General Public License for more details.
29 You should have received a copy of the GNU General Public License
30 along with this program; if not, write to the Free Software
31 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
34 Bacula® is a registered trademark of John Walker.
35 The licensor of Bacula is the Free Software Foundation Europe
36 (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
37 Switzerland, email:ftf@fsfeurope.org.
42 /* ===================================================================
47 * Append an item to the list
49 void dlist::append(void *item)
51 ((dlink *)(((char *)item)+loffset))->next = NULL;
52 ((dlink *)(((char *)item)+loffset))->prev = tail;
54 ((dlink *)(((char *)tail)+loffset))->next = item;
57 if (head == NULL) { /* if empty list, */
58 head = item; /* item is head as well */
64 * Append an item to the list
66 void dlist::prepend(void *item)
68 ((dlink *)(((char *)item)+loffset))->next = head;
69 ((dlink *)(((char *)item)+loffset))->prev = NULL;
71 ((dlink *)(((char *)head)+loffset))->prev = item;
74 if (tail == NULL) { /* if empty list, */
75 tail = item; /* item is tail too */
80 void dlist::insert_before(void *item, void *where)
82 dlink *where_link = (dlink *)((char *)where+loffset);
84 ((dlink *)(((char *)item)+loffset))->next = where;
85 ((dlink *)(((char *)item)+loffset))->prev = where_link->prev;
87 if (where_link->prev) {
88 ((dlink *)(((char *)(where_link->prev))+loffset))->next = item;
90 where_link->prev = item;
97 void dlist::insert_after(void *item, void *where)
99 dlink *where_link = (dlink *)((char *)where+loffset);
101 ((dlink *)(((char *)item)+loffset))->next = where_link->next;
102 ((dlink *)(((char *)item)+loffset))->prev = where;
104 if (where_link->next) {
105 ((dlink *)(((char *)(where_link->next))+loffset))->prev = item;
107 where_link->next = item;
115 * Insert an item in the list, but only if it is unique
116 * otherwise, the item is returned non inserted
118 * Returns: item if item inserted
119 * other_item if same value already exists (item not inserted)
121 void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
127 if (num_items == 0) {
128 //Dmsg0(000, "Append first.\n");
132 if (num_items == 1) {
133 comp = compare(item, first());
136 //Dmsg0(000, "Insert before first.\n");
138 } else if (comp > 0) {
139 insert_after(item, first());
140 //Dmsg0(000, "Insert after first.\n");
143 //Dmsg0(000, "Same as first.\n");
147 /* Check against last item */
148 comp = compare(item, last());
151 //Dmsg0(000, "Appended item.\n");
153 } else if (comp == 0) {
154 //Dmsg0(000, "Same as last.\n");
157 /* Check against first item */
158 comp = compare(item, first());
161 //Dmsg0(000, "Inserted item before.\n");
163 } else if (comp == 0) {
164 //Dmsg0(000, "Same as first.\n");
167 if (num_items == 2) {
168 insert_after(item, first());
169 //Dmsg0(000, "Inserted item after.\n");
178 nxt = (low + high) / 2;
180 cur_item = next(cur_item);
184 cur_item = prev(cur_item);
187 //Dmsg1(000, "Compare item to %d\n", cur);
188 comp = compare(item, cur_item);
189 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
192 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
193 } else if (comp > 0) {
195 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
197 //Dmsg1(000, "Same as item %d\n", cur);
202 insert_before(item, cur_item);
203 //Dmsg1(000, "Insert before item %d\n", cur);
205 insert_after(item, cur_item);
206 //Dmsg1(000, "Insert after item %d\n", cur);
212 * Insert an item in the list, regardless if it is unique
215 void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
217 void *ins_item = binary_insert(item, compare);
218 /* If identical, insert after the one found */
219 if (ins_item != item) {
220 insert_after(item, ins_item);
227 void *dlist::binary_search(void *item, int compare(void *item1, void *item2))
234 if (num_items == 0) {
238 if (num_items == 1) {
239 comp = compare(item, cur_item);
252 nxt = (low + high) / 2;
253 /* Now get cur pointing to nxt */
255 cur_item = next(cur_item);
259 cur_item = prev(cur_item);
262 comp = compare(item, cur_item);
263 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
266 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
267 } else if (comp > 0) {
269 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
275 * low == high can only happen if low just
276 * got incremented from cur, and we have
277 * not yet tested cur+1
280 cur_item = next(cur_item);
281 comp = compare(item, cur_item);
290 void dlist::remove(void *item)
293 dlink *ilink = (dlink *)(((char *)item)+loffset); /* item's link */
297 ((dlink *)(((char *)head)+loffset))->prev = NULL;
302 } else if (item == tail) {
305 ((dlink *)(((char *)tail)+loffset))->next = NULL;
309 ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
311 ((dlink *)(((char *)xitem)+loffset))->next = ilink->next;
314 if (num_items == 0) {
319 void * dlist::next(const void *item) const
324 return ((dlink *)(((char *)item)+loffset))->next;
327 void * dlist::prev(const void *item) const
332 return ((dlink *)(((char *)item)+loffset))->prev;
336 /* Destroy the list contents */
337 void dlist::destroy()
339 for (void *n=head; n; ) {
340 void *ni = ((dlink *)(((char *)n)+loffset))->next;
357 static int my_compare(void *item1, void *item2)
361 jcr1 = (MYJCR *)item1;
362 jcr2 = (MYJCR *)item2;
363 comp = strcmp(jcr1->buf, jcr2->buf);
364 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
374 MYJCR *save_jcr = NULL;
377 jcr_chain = (dlist *)malloc(sizeof(dlist));
378 jcr_chain->init(jcr, &jcr->link);
380 printf("Prepend 20 items 0-19\n");
381 for (int i=0; i<20; i++) {
382 sprintf(buf, "This is dlist item %d", i);
383 jcr = (MYJCR *)malloc(sizeof(MYJCR));
384 jcr->buf = bstrdup(buf);
385 jcr_chain->prepend(jcr);
391 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
392 printf("11th item=%s\n", next_jcr->buf);
393 jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
394 jcr1->buf = save_jcr->buf;
395 printf("Remove 10th item\n");
396 jcr_chain->remove(save_jcr);
398 printf("Re-insert 10th item\n");
399 jcr_chain->insert_before(jcr1, next_jcr);
401 printf("Print remaining list.\n");
402 foreach_dlist(jcr, jcr_chain) {
403 printf("Dlist item = %s\n", jcr->buf);
406 jcr_chain->destroy();
409 jcr_chain = New(dlist(jcr, &jcr->link));
410 printf("append 20 items 0-19\n");
411 for (int i=0; i<20; i++) {
412 sprintf(buf, "This is dlist item %d", i);
413 jcr = (MYJCR *)malloc(sizeof(MYJCR));
414 jcr->buf = bstrdup(buf);
415 jcr_chain->append(jcr);
421 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
422 printf("11th item=%s\n", next_jcr->buf);
423 jcr = (MYJCR *)malloc(sizeof(MYJCR));
424 jcr->buf = save_jcr->buf;
425 printf("Remove 10th item\n");
426 jcr_chain->remove(save_jcr);
428 printf("Re-insert 10th item\n");
429 jcr_chain->insert_before(jcr, next_jcr);
431 printf("Print remaining list.\n");
432 foreach_dlist (jcr, jcr_chain) {
433 printf("Dlist item = %s\n", jcr->buf);
440 /* Now do a binary insert for the list */
441 jcr_chain = New(dlist(jcr, &jcr->link));
443 printf("append %d items\n", CNT*CNT*CNT);
446 for (int i=0; i<CNT; i++) {
447 for (int j=0; j<CNT; j++) {
448 for (int k=0; k<CNT; k++) {
450 if ((count & 0x3FF) == 0) {
451 Dmsg1(000, "At %d\n", count);
453 jcr = (MYJCR *)malloc(sizeof(MYJCR));
454 jcr->buf = bstrdup(buf);
455 jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
457 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
468 jcr = (MYJCR *)malloc(sizeof(MYJCR));
470 jcr->buf = bstrdup(buf);
471 if (jcr_chain->binary_search(jcr, my_compare)) {
472 printf("One less failed!!!!\n");
474 printf("One less: OK\n");
477 strcpy(buf, "ZZZZZZZZZZZZZZZZ");
478 jcr->buf = bstrdup(buf);
479 if (jcr_chain->binary_search(jcr, my_compare)) {
480 printf("One greater failed!!!!\n");
482 printf("One greater: OK\n");
488 printf("Find each of %d items in list.\n", count);
489 foreach_dlist (jcr, jcr_chain) {
490 if (!jcr_chain->binary_search(jcr, my_compare)) {
491 printf("Dlist binary_search item not found = %s\n", jcr->buf);
494 printf("Free each of %d items in list.\n", count);
495 foreach_dlist (jcr, jcr_chain) {