2 Bacula(R) - The Network Backup Solution
4 Copyright (C) 2000-2016 Kern Sibbald
6 The original author of Bacula is Kern Sibbald, with contributions
7 from many others, a complete list can be found in the file AUTHORS.
9 You may use this file and others of this release according to the
10 license defined in the LICENSE file, which includes the Affero General
11 Public License, v3.0 ("AGPLv3") and some additional permissions and
12 terms pursuant to its AGPLv3 Section 7.
14 This notice must be preserved when any source code is
15 conveyed and/or propagated.
17 Bacula(R) is a registered trademark of Kern Sibbald.
20 * Bacula doubly linked list routines.
22 * dlist is a doubly linked list with the links being in the
25 * Kern Sibbald, July MMIII
31 /* ===================================================================
36 * Append an item to the list
38 void dlist::append(void *item)
46 if (head == NULL) { /* if empty list, */
47 head = item; /* item is head as well */
53 * Append an item to the list
55 void dlist::prepend(void *item)
63 if (tail == NULL) { /* if empty list, */
64 tail = item; /* item is tail too */
69 void dlist::insert_before(void *item, void *where)
71 dlink *where_link = get_link(where);
73 set_next(item, where);
74 set_prev(item, where_link->prev);
76 if (where_link->prev) {
77 set_next(where_link->prev, item);
79 where_link->prev = item;
86 void dlist::insert_after(void *item, void *where)
88 dlink *where_link = get_link(where);
90 set_next(item, where_link->next);
91 set_prev(item, where);
93 if (where_link->next) {
94 set_prev(where_link->next, item);
96 where_link->next = item;
104 * Insert an item in the list, but only if it is unique
105 * otherwise, the item is returned non inserted
107 * Returns: item if item inserted
108 * other_item if same value already exists (item not inserted)
110 void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
116 if (num_items == 0) {
117 //Dmsg0(000, "Append first.\n");
121 if (num_items == 1) {
122 comp = compare(item, first());
125 //Dmsg0(000, "Insert before first.\n");
127 } else if (comp > 0) {
128 insert_after(item, first());
129 //Dmsg0(000, "Insert after first.\n");
132 //Dmsg0(000, "Same as first.\n");
136 /* Check against last item */
137 comp = compare(item, last());
140 //Dmsg0(000, "Appended item.\n");
142 } else if (comp == 0) {
143 //Dmsg0(000, "Same as last.\n");
146 /* Check against first item */
147 comp = compare(item, first());
150 //Dmsg0(000, "Inserted item before.\n");
152 } else if (comp == 0) {
153 //Dmsg0(000, "Same as first.\n");
156 if (num_items == 2) {
157 insert_after(item, first());
158 //Dmsg0(000, "Inserted item after.\n");
167 nxt = (low + high) / 2;
169 cur_item = next(cur_item);
173 cur_item = prev(cur_item);
176 //Dmsg1(000, "Compare item to %d\n", cur);
177 comp = compare(item, cur_item);
178 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
181 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
182 } else if (comp > 0) {
184 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
186 //Dmsg1(000, "Same as item %d\n", cur);
191 insert_before(item, cur_item);
192 //Dmsg1(000, "Insert before item %d\n", cur);
194 insert_after(item, cur_item);
195 //Dmsg1(000, "Insert after item %d\n", cur);
201 * Insert an item in the list, regardless if it is unique
204 void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
206 void *ins_item = binary_insert(item, compare);
207 /* If identical, insert after the one found */
208 if (ins_item != item) {
209 insert_after(item, ins_item);
216 void *dlist::binary_search(void *item, int compare(void *item1, void *item2))
223 if (num_items == 0) {
227 if (num_items == 1) {
228 comp = compare(item, cur_item);
241 nxt = (low + high) / 2;
242 /* Now get cur pointing to nxt */
244 cur_item = next(cur_item);
248 cur_item = prev(cur_item);
251 comp = compare(item, cur_item);
252 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
255 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
256 } else if (comp > 0) {
258 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
264 * low == high can only happen if low just
265 * got incremented from cur, and we have
266 * not yet tested cur+1
269 cur_item = next(cur_item);
270 comp = compare(item, cur_item);
279 void dlist::remove(void *item)
282 dlink *ilink = get_link(item); /* item's link */
286 set_prev(head, NULL);
291 } else if (item == tail) {
294 set_next(tail, NULL);
298 set_prev(xitem, ilink->prev);
300 set_next(xitem, ilink->next);
303 if (num_items == 0) {
306 ilink->prev = ilink->next = NULL;
309 void *dlist::next(void *item)
314 return get_next(item);
317 void *dlist::prev(void *item)
322 return get_prev(item);
326 /* Destroy the list contents */
327 void dlist::destroy()
329 for (void *n=head; n; ) {
330 void *ni = get_next(n);
338 /* String helpers for dlist usage */
340 dlistString *new_dlistString(const char *str)
342 return new_dlistString(str, strlen(str));
345 dlistString *new_dlistString(const char *str, int len)
348 node = (dlistString *)malloc(sizeof(dlink) + len +1);
349 bstrncpy(node->c_str(), str, len + 1);
360 static int my_compare(void *item1, void *item2)
364 jcr1 = (MYJCR *)item1;
365 jcr2 = (MYJCR *)item2;
366 comp = strcmp(jcr1->buf, jcr2->buf);
367 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
377 MYJCR *save_jcr = NULL;
381 jcr_chain = (dlist *)malloc(sizeof(dlist));
382 jcr_chain->init(jcr, &jcr->link);
384 printf("Prepend 20 items 0-19\n");
385 for (int i=0; i<20; i++) {
386 sprintf(buf, "This is dlist item %d", i);
387 jcr = (MYJCR *)malloc(sizeof(MYJCR));
388 jcr->buf = bstrdup(buf);
389 jcr_chain->prepend(jcr);
395 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
396 printf("11th item=%s\n", next_jcr->buf);
397 jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
398 jcr1->buf = save_jcr->buf;
399 printf("Remove 10th item\n");
400 jcr_chain->remove(save_jcr);
402 printf("Re-insert 10th item\n");
403 jcr_chain->insert_before(jcr1, next_jcr);
405 printf("Print remaining list.\n");
406 foreach_dlist(jcr, jcr_chain) {
407 printf("Dlist item = %s\n", jcr->buf);
410 jcr_chain->destroy();
413 /* The following may seem a bit odd, but we create a chaing
414 * of jcr objects. Within a jcr object, there is a buf
415 * that points to a malloced string containing data
417 jcr_chain = New(dlist(jcr, &jcr->link));
418 printf("append 20 items 0-19\n");
419 for (int i=0; i<20; i++) {
420 sprintf(buf, "This is dlist item %d", i);
421 jcr = (MYJCR *)malloc(sizeof(MYJCR));
422 jcr->buf = bstrdup(buf);
423 jcr_chain->append(jcr);
429 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
430 printf("11th item=%s\n", next_jcr->buf);
431 jcr = (MYJCR *)malloc(sizeof(MYJCR));
432 jcr->buf = save_jcr->buf;
433 printf("Remove 10th item\n");
434 jcr_chain->remove(save_jcr);
436 printf("Re-insert 10th item\n");
437 jcr_chain->insert_before(jcr, next_jcr);
439 printf("Print remaining list.\n");
440 foreach_dlist (jcr, jcr_chain) {
441 printf("Dlist item = %s\n", jcr->buf);
448 /* Now do a binary insert for the list */
449 jcr_chain = New(dlist(jcr, &jcr->link));
451 printf("append %d items\n", CNT*CNT*CNT);
454 for (int i=0; i<CNT; i++) {
455 for (int j=0; j<CNT; j++) {
456 for (int k=0; k<CNT; k++) {
458 if ((count & 0x3FF) == 0) {
459 Dmsg1(000, "At %d\n", count);
461 jcr = (MYJCR *)malloc(sizeof(MYJCR));
462 jcr->buf = bstrdup(buf);
463 jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
465 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
476 jcr = (MYJCR *)malloc(sizeof(MYJCR));
478 jcr->buf = bstrdup(buf);
479 if (jcr_chain->binary_search(jcr, my_compare)) {
480 printf("One less failed!!!!\n");
482 printf("One less: OK\n");
485 strcpy(buf, "ZZZZZZZZZZZZZZZZ");
486 jcr->buf = bstrdup(buf);
487 if (jcr_chain->binary_search(jcr, my_compare)) {
488 printf("One greater failed!!!!\n");
490 printf("One greater: OK\n");
496 printf("Find each of %d items in list.\n", count);
497 foreach_dlist (jcr, jcr_chain) {
498 if (!jcr_chain->binary_search(jcr, my_compare)) {
499 printf("Dlist binary_search item not found = %s\n", jcr->buf);
502 printf("Free each of %d items in list.\n", count);
503 foreach_dlist (jcr, jcr_chain) {
509 /* Finally, do a test using the dlistString string helper, which
510 * allocates a dlist node and stores the string directly in
514 chain.append(new_dlistString("This is a long test line"));
516 printf("append %d dlistString items\n", CNT*CNT*CNT);
519 for (int i=0; i<CNT; i++) {
520 for (int j=0; j<CNT; j++) {
521 for (int k=0; k<CNT; k++) {
523 if ((count & 0x3FF) == 0) {
524 Dmsg1(000, "At %d\n", count);
526 chain.append(new_dlistString(buf));
535 printf("dlistString items appended, walking chain\n");
537 foreach_dlist(node, &chain) {
538 printf("%s\n", node->c_str());
540 printf("destroy dlistString chain\n");
543 sm_dump(false); /* unit test */