2 Bacula® - The Network Backup Solution
4 Copyright (C) 2003-2010 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 three of the GNU Affero 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 Affero 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 Kern Sibbald.
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 * Bacula doubly linked list routines.
31 * dlist is a doubly linked list with the links being in the
34 * Kern Sibbald, July MMIII
40 /* ===================================================================
45 * Append an item to the list
47 void dlist::append(void *item)
55 if (head == NULL) { /* if empty list, */
56 head = item; /* item is head as well */
62 * Append an item to the list
64 void dlist::prepend(void *item)
72 if (tail == NULL) { /* if empty list, */
73 tail = item; /* item is tail too */
78 void dlist::insert_before(void *item, void *where)
80 dlink *where_link = get_link(where);
82 set_next(item, where);
83 set_prev(item, where_link->prev);
85 if (where_link->prev) {
86 set_next(where_link->prev, item);
88 where_link->prev = item;
95 void dlist::insert_after(void *item, void *where)
97 dlink *where_link = get_link(where);
99 set_next(item, where_link->next);
100 set_prev(item, where);
102 if (where_link->next) {
103 set_prev(where_link->next, item);
105 where_link->next = item;
113 * Insert an item in the list, but only if it is unique
114 * otherwise, the item is returned non inserted
116 * Returns: item if item inserted
117 * other_item if same value already exists (item not inserted)
119 void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
125 if (num_items == 0) {
126 //Dmsg0(000, "Append first.\n");
130 if (num_items == 1) {
131 comp = compare(item, first());
134 //Dmsg0(000, "Insert before first.\n");
136 } else if (comp > 0) {
137 insert_after(item, first());
138 //Dmsg0(000, "Insert after first.\n");
141 //Dmsg0(000, "Same as first.\n");
145 /* Check against last item */
146 comp = compare(item, last());
149 //Dmsg0(000, "Appended item.\n");
151 } else if (comp == 0) {
152 //Dmsg0(000, "Same as last.\n");
155 /* Check against first item */
156 comp = compare(item, first());
159 //Dmsg0(000, "Inserted item before.\n");
161 } else if (comp == 0) {
162 //Dmsg0(000, "Same as first.\n");
165 if (num_items == 2) {
166 insert_after(item, first());
167 //Dmsg0(000, "Inserted item after.\n");
176 nxt = (low + high) / 2;
178 cur_item = next(cur_item);
182 cur_item = prev(cur_item);
185 //Dmsg1(000, "Compare item to %d\n", cur);
186 comp = compare(item, cur_item);
187 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
190 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
191 } else if (comp > 0) {
193 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
195 //Dmsg1(000, "Same as item %d\n", cur);
200 insert_before(item, cur_item);
201 //Dmsg1(000, "Insert before item %d\n", cur);
203 insert_after(item, cur_item);
204 //Dmsg1(000, "Insert after item %d\n", cur);
210 * Insert an item in the list, regardless if it is unique
213 void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
215 void *ins_item = binary_insert(item, compare);
216 /* If identical, insert after the one found */
217 if (ins_item != item) {
218 insert_after(item, ins_item);
225 void *dlist::binary_search(void *item, int compare(void *item1, void *item2))
232 if (num_items == 0) {
236 if (num_items == 1) {
237 comp = compare(item, cur_item);
250 nxt = (low + high) / 2;
251 /* Now get cur pointing to nxt */
253 cur_item = next(cur_item);
257 cur_item = prev(cur_item);
260 comp = compare(item, cur_item);
261 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
264 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
265 } else if (comp > 0) {
267 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
273 * low == high can only happen if low just
274 * got incremented from cur, and we have
275 * not yet tested cur+1
278 cur_item = next(cur_item);
279 comp = compare(item, cur_item);
288 void dlist::remove(void *item)
291 dlink *ilink = get_link(item); /* item's link */
295 set_prev(head, NULL);
300 } else if (item == tail) {
303 set_next(tail, NULL);
307 set_prev(xitem, ilink->prev);
309 set_next(xitem, ilink->next);
312 if (num_items == 0) {
317 void *dlist::next(void *item)
322 return get_next(item);
325 void *dlist::prev(void *item)
330 return get_prev(item);
334 /* Destroy the list contents */
335 void dlist::destroy()
337 for (void *n=head; n; ) {
338 void *ni = get_next(n);
346 /* String helpers for dlist usage */
348 dlistString *new_dlistString(const char *str)
350 return new_dlistString(str, strlen(str));
353 dlistString *new_dlistString(const char *str, int len)
356 node = (dlistString *)malloc(sizeof(dlink) + len +1);
357 bstrncpy(node->c_str(), str, len + 1);
368 static int my_compare(void *item1, void *item2)
372 jcr1 = (MYJCR *)item1;
373 jcr2 = (MYJCR *)item2;
374 comp = strcmp(jcr1->buf, jcr2->buf);
375 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
385 MYJCR *save_jcr = NULL;
389 jcr_chain = (dlist *)malloc(sizeof(dlist));
390 jcr_chain->init(jcr, &jcr->link);
392 printf("Prepend 20 items 0-19\n");
393 for (int i=0; i<20; i++) {
394 sprintf(buf, "This is dlist item %d", i);
395 jcr = (MYJCR *)malloc(sizeof(MYJCR));
396 jcr->buf = bstrdup(buf);
397 jcr_chain->prepend(jcr);
403 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
404 printf("11th item=%s\n", next_jcr->buf);
405 jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
406 jcr1->buf = save_jcr->buf;
407 printf("Remove 10th item\n");
408 jcr_chain->remove(save_jcr);
410 printf("Re-insert 10th item\n");
411 jcr_chain->insert_before(jcr1, next_jcr);
413 printf("Print remaining list.\n");
414 foreach_dlist(jcr, jcr_chain) {
415 printf("Dlist item = %s\n", jcr->buf);
418 jcr_chain->destroy();
421 /* The following may seem a bit odd, but we create a chaing
422 * of jcr objects. Within a jcr object, there is a buf
423 * that points to a malloced string containing data
425 jcr_chain = New(dlist(jcr, &jcr->link));
426 printf("append 20 items 0-19\n");
427 for (int i=0; i<20; i++) {
428 sprintf(buf, "This is dlist item %d", i);
429 jcr = (MYJCR *)malloc(sizeof(MYJCR));
430 jcr->buf = bstrdup(buf);
431 jcr_chain->append(jcr);
437 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
438 printf("11th item=%s\n", next_jcr->buf);
439 jcr = (MYJCR *)malloc(sizeof(MYJCR));
440 jcr->buf = save_jcr->buf;
441 printf("Remove 10th item\n");
442 jcr_chain->remove(save_jcr);
444 printf("Re-insert 10th item\n");
445 jcr_chain->insert_before(jcr, next_jcr);
447 printf("Print remaining list.\n");
448 foreach_dlist (jcr, jcr_chain) {
449 printf("Dlist item = %s\n", jcr->buf);
456 /* Now do a binary insert for the list */
457 jcr_chain = New(dlist(jcr, &jcr->link));
459 printf("append %d items\n", CNT*CNT*CNT);
462 for (int i=0; i<CNT; i++) {
463 for (int j=0; j<CNT; j++) {
464 for (int k=0; k<CNT; k++) {
466 if ((count & 0x3FF) == 0) {
467 Dmsg1(000, "At %d\n", count);
469 jcr = (MYJCR *)malloc(sizeof(MYJCR));
470 jcr->buf = bstrdup(buf);
471 jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
473 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
484 jcr = (MYJCR *)malloc(sizeof(MYJCR));
486 jcr->buf = bstrdup(buf);
487 if (jcr_chain->binary_search(jcr, my_compare)) {
488 printf("One less failed!!!!\n");
490 printf("One less: OK\n");
493 strcpy(buf, "ZZZZZZZZZZZZZZZZ");
494 jcr->buf = bstrdup(buf);
495 if (jcr_chain->binary_search(jcr, my_compare)) {
496 printf("One greater failed!!!!\n");
498 printf("One greater: OK\n");
504 printf("Find each of %d items in list.\n", count);
505 foreach_dlist (jcr, jcr_chain) {
506 if (!jcr_chain->binary_search(jcr, my_compare)) {
507 printf("Dlist binary_search item not found = %s\n", jcr->buf);
510 printf("Free each of %d items in list.\n", count);
511 foreach_dlist (jcr, jcr_chain) {
517 /* Finally, do a test using the dlistString string helper, which
518 * allocates a dlist node and stores the string directly in
522 chain.append(new_dlistString("This is a long test line"));
524 printf("append %d dlistString items\n", CNT*CNT*CNT);
527 for (int i=0; i<CNT; i++) {
528 for (int j=0; j<CNT; j++) {
529 for (int k=0; k<CNT; k++) {
531 if ((count & 0x3FF) == 0) {
532 Dmsg1(000, "At %d\n", count);
534 chain.append(new_dlistString(buf));
543 printf("dlistString items appended, walking chain\n");
545 foreach_dlist(node, &chain) {
546 printf("%s\n", node->c_str());
548 printf("destroy dlistString chain\n");
551 sm_dump(false); /* unit test */