2 Bacula® - The Network Backup Solution
4 Copyright (C) 2003-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 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
42 /* ===================================================================
47 * Append an item to the list
49 void dlist::append(void *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)
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 = get_link(where);
84 set_next(item, where);
85 set_prev(item, where_link->prev);
87 if (where_link->prev) {
88 set_next(where_link->prev, item);
90 where_link->prev = item;
97 void dlist::insert_after(void *item, void *where)
99 dlink *where_link = get_link(where);
101 set_next(item, where_link->next);
102 set_prev(item, where);
104 if (where_link->next) {
105 set_prev(where_link->next, 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 = get_link(item); /* item's link */
297 set_prev(head, NULL);
302 } else if (item == tail) {
305 set_next(tail, NULL);
309 set_prev(xitem, ilink->prev);
311 set_next(xitem, ilink->next);
314 if (num_items == 0) {
319 void *dlist::next(void *item)
324 return get_next(item);
327 void *dlist::prev(void *item)
332 return get_prev(item);
336 /* Destroy the list contents */
337 void dlist::destroy()
339 for (void *n=head; n; ) {
340 void *ni = get_next(n);
348 /* String helpers for dlist usage */
350 dlistString *new_dlistString(const char *str)
352 return new_dlistString(str, strlen(str));
355 dlistString *new_dlistString(const char *str, int len)
358 node = (dlistString *)malloc(sizeof(dlink) + len +1);
359 bstrncpy(node->c_str(), str, len + 1);
370 static int my_compare(void *item1, void *item2)
374 jcr1 = (MYJCR *)item1;
375 jcr2 = (MYJCR *)item2;
376 comp = strcmp(jcr1->buf, jcr2->buf);
377 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
387 MYJCR *save_jcr = NULL;
391 jcr_chain = (dlist *)malloc(sizeof(dlist));
392 jcr_chain->init(jcr, &jcr->link);
394 printf("Prepend 20 items 0-19\n");
395 for (int i=0; i<20; i++) {
396 sprintf(buf, "This is dlist item %d", i);
397 jcr = (MYJCR *)malloc(sizeof(MYJCR));
398 jcr->buf = bstrdup(buf);
399 jcr_chain->prepend(jcr);
405 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
406 printf("11th item=%s\n", next_jcr->buf);
407 jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
408 jcr1->buf = save_jcr->buf;
409 printf("Remove 10th item\n");
410 jcr_chain->remove(save_jcr);
412 printf("Re-insert 10th item\n");
413 jcr_chain->insert_before(jcr1, next_jcr);
415 printf("Print remaining list.\n");
416 foreach_dlist(jcr, jcr_chain) {
417 printf("Dlist item = %s\n", jcr->buf);
420 jcr_chain->destroy();
423 /* The following may seem a bit odd, but we create a chaing
424 * of jcr objects. Within a jcr object, there is a buf
425 * that points to a malloced string containing data
427 jcr_chain = New(dlist(jcr, &jcr->link));
428 printf("append 20 items 0-19\n");
429 for (int i=0; i<20; i++) {
430 sprintf(buf, "This is dlist item %d", i);
431 jcr = (MYJCR *)malloc(sizeof(MYJCR));
432 jcr->buf = bstrdup(buf);
433 jcr_chain->append(jcr);
439 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
440 printf("11th item=%s\n", next_jcr->buf);
441 jcr = (MYJCR *)malloc(sizeof(MYJCR));
442 jcr->buf = save_jcr->buf;
443 printf("Remove 10th item\n");
444 jcr_chain->remove(save_jcr);
446 printf("Re-insert 10th item\n");
447 jcr_chain->insert_before(jcr, next_jcr);
449 printf("Print remaining list.\n");
450 foreach_dlist (jcr, jcr_chain) {
451 printf("Dlist item = %s\n", jcr->buf);
458 /* Now do a binary insert for the list */
459 jcr_chain = New(dlist(jcr, &jcr->link));
461 printf("append %d items\n", CNT*CNT*CNT);
464 for (int i=0; i<CNT; i++) {
465 for (int j=0; j<CNT; j++) {
466 for (int k=0; k<CNT; k++) {
468 if ((count & 0x3FF) == 0) {
469 Dmsg1(000, "At %d\n", count);
471 jcr = (MYJCR *)malloc(sizeof(MYJCR));
472 jcr->buf = bstrdup(buf);
473 jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
475 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
486 jcr = (MYJCR *)malloc(sizeof(MYJCR));
488 jcr->buf = bstrdup(buf);
489 if (jcr_chain->binary_search(jcr, my_compare)) {
490 printf("One less failed!!!!\n");
492 printf("One less: OK\n");
495 strcpy(buf, "ZZZZZZZZZZZZZZZZ");
496 jcr->buf = bstrdup(buf);
497 if (jcr_chain->binary_search(jcr, my_compare)) {
498 printf("One greater failed!!!!\n");
500 printf("One greater: OK\n");
506 printf("Find each of %d items in list.\n", count);
507 foreach_dlist (jcr, jcr_chain) {
508 if (!jcr_chain->binary_search(jcr, my_compare)) {
509 printf("Dlist binary_search item not found = %s\n", jcr->buf);
512 printf("Free each of %d items in list.\n", count);
513 foreach_dlist (jcr, jcr_chain) {
519 /* Finally, do a test using the dlistString string helper, which
520 * allocates a dlist node and stores the string directly in
524 chain.append(new_dlistString("This is a long test line"));
526 printf("append %d dlistString items\n", CNT*CNT*CNT);
529 for (int i=0; i<CNT; i++) {
530 for (int j=0; j<CNT; j++) {
531 for (int k=0; k<CNT; k++) {
533 if ((count & 0x3FF) == 0) {
534 Dmsg1(000, "At %d\n", count);
536 chain.append(new_dlistString(buf));
545 printf("dlistString items appended, walking chain\n");
547 foreach_dlist(node, &chain) {
548 printf("%s\n", node->c_str());
550 printf("destroy dlistString chain\n");