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) 2003-2005 Kern Sibbald
15 This program is free software; you can redistribute it and/or
16 modify it under the terms of the GNU General Public License
17 version 2 as amended with additional clauses defined in the
18 file LICENSE in the main source directory.
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
23 the file LICENSE for additional details.
29 /* ===================================================================
34 * Append an item to the list
36 void dlist::append(void *item)
38 ((dlink *)(((char *)item)+loffset))->next = NULL;
39 ((dlink *)(((char *)item)+loffset))->prev = tail;
41 ((dlink *)(((char *)tail)+loffset))->next = item;
44 if (head == NULL) { /* if empty list, */
45 head = item; /* item is head as well */
51 * Append an item to the list
53 void dlist::prepend(void *item)
55 ((dlink *)(((char *)item)+loffset))->next = head;
56 ((dlink *)(((char *)item)+loffset))->prev = NULL;
58 ((dlink *)(((char *)head)+loffset))->prev = item;
61 if (tail == NULL) { /* if empty list, */
62 tail = item; /* item is tail too */
67 void dlist::insert_before(void *item, void *where)
69 dlink *where_link = (dlink *)((char *)where+loffset);
71 ((dlink *)(((char *)item)+loffset))->next = where;
72 ((dlink *)(((char *)item)+loffset))->prev = where_link->prev;
74 if (where_link->prev) {
75 ((dlink *)(((char *)(where_link->prev))+loffset))->next = item;
77 where_link->prev = item;
84 void dlist::insert_after(void *item, void *where)
86 dlink *where_link = (dlink *)((char *)where+loffset);
88 ((dlink *)(((char *)item)+loffset))->next = where_link->next;
89 ((dlink *)(((char *)item)+loffset))->prev = where;
91 if (where_link->next) {
92 ((dlink *)(((char *)(where_link->next))+loffset))->prev = item;
94 where_link->next = item;
102 * Insert an item in the list, but only if it is unique
103 * otherwise, the item is returned non inserted
105 * Returns: item if item inserted
106 * other_item if same value already exists (item not inserted)
108 void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
114 if (num_items == 0) {
115 //Dmsg0(000, "Append first.\n");
119 if (num_items == 1) {
120 comp = compare(item, first());
123 //Dmsg0(000, "Insert before first.\n");
125 } else if (comp > 0) {
126 insert_after(item, first());
127 //Dmsg0(000, "Insert after first.\n");
130 //Dmsg0(000, "Same as first.\n");
134 /* Check against last item */
135 comp = compare(item, last());
138 //Dmsg0(000, "Appended item.\n");
140 } else if (comp == 0) {
141 //Dmsg0(000, "Same as last.\n");
144 /* Check against first item */
145 comp = compare(item, first());
148 //Dmsg0(000, "Inserted item before.\n");
150 } else if (comp == 0) {
151 //Dmsg0(000, "Same as first.\n");
154 if (num_items == 2) {
155 insert_after(item, first());
156 //Dmsg0(000, "Inserted item after.\n");
165 nxt = (low + high) / 2;
167 cur_item = next(cur_item);
171 cur_item = prev(cur_item);
174 //Dmsg1(000, "Compare item to %d\n", cur);
175 comp = compare(item, cur_item);
176 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
179 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
180 } else if (comp > 0) {
182 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
184 //Dmsg1(000, "Same as item %d\n", cur);
189 insert_before(item, cur_item);
190 //Dmsg1(000, "Insert before item %d\n", cur);
192 insert_after(item, cur_item);
193 //Dmsg1(000, "Insert after item %d\n", cur);
199 * Insert an item in the list, regardless if it is unique
202 void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
204 void *ins_item = binary_insert(item, compare);
205 /* If identical, insert after the one found */
206 if (ins_item != item) {
207 insert_after(item, ins_item);
214 void *dlist::binary_search(void *item, int compare(void *item1, void *item2))
221 if (num_items == 0) {
225 if (num_items == 1) {
226 comp = compare(item, cur_item);
239 nxt = (low + high) / 2;
240 /* Now get cur pointing to nxt */
242 cur_item = next(cur_item);
246 cur_item = prev(cur_item);
249 comp = compare(item, cur_item);
250 //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
253 //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
254 } else if (comp > 0) {
256 //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
262 * low == high can only happen if low just
263 * got incremented from cur, and we have
264 * not yet tested cur+1
267 cur_item = next(cur_item);
268 comp = compare(item, cur_item);
277 void dlist::remove(void *item)
280 dlink *ilink = (dlink *)(((char *)item)+loffset); /* item's link */
284 ((dlink *)(((char *)head)+loffset))->prev = NULL;
289 } else if (item == tail) {
292 ((dlink *)(((char *)tail)+loffset))->next = NULL;
296 ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
298 ((dlink *)(((char *)xitem)+loffset))->next = ilink->next;
301 if (num_items == 0) {
306 void * dlist::next(const void *item) const
311 return ((dlink *)(((char *)item)+loffset))->next;
314 void * dlist::prev(const void *item) const
319 return ((dlink *)(((char *)item)+loffset))->prev;
323 /* Destroy the list contents */
324 void dlist::destroy()
326 for (void *n=head; n; ) {
327 void *ni = ((dlink *)(((char *)n)+loffset))->next;
344 static int my_compare(void *item1, void *item2)
348 jcr1 = (MYJCR *)item1;
349 jcr2 = (MYJCR *)item2;
350 comp = strcmp(jcr1->buf, jcr2->buf);
351 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
361 MYJCR *save_jcr = NULL;
364 jcr_chain = (dlist *)malloc(sizeof(dlist));
365 jcr_chain->init(jcr, &jcr->link);
367 printf("Prepend 20 items 0-19\n");
368 for (int i=0; i<20; i++) {
369 sprintf(buf, "This is dlist item %d", i);
370 jcr = (MYJCR *)malloc(sizeof(MYJCR));
371 jcr->buf = bstrdup(buf);
372 jcr_chain->prepend(jcr);
378 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
379 printf("11th item=%s\n", next_jcr->buf);
380 jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
381 jcr1->buf = save_jcr->buf;
382 printf("Remove 10th item\n");
383 jcr_chain->remove(save_jcr);
385 printf("Re-insert 10th item\n");
386 jcr_chain->insert_before(jcr1, next_jcr);
388 printf("Print remaining list.\n");
389 foreach_dlist(jcr, jcr_chain) {
390 printf("Dlist item = %s\n", jcr->buf);
393 jcr_chain->destroy();
396 jcr_chain = New(dlist(jcr, &jcr->link));
397 printf("append 20 items 0-19\n");
398 for (int i=0; i<20; i++) {
399 sprintf(buf, "This is dlist item %d", i);
400 jcr = (MYJCR *)malloc(sizeof(MYJCR));
401 jcr->buf = bstrdup(buf);
402 jcr_chain->append(jcr);
408 next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
409 printf("11th item=%s\n", next_jcr->buf);
410 jcr = (MYJCR *)malloc(sizeof(MYJCR));
411 jcr->buf = save_jcr->buf;
412 printf("Remove 10th item\n");
413 jcr_chain->remove(save_jcr);
415 printf("Re-insert 10th item\n");
416 jcr_chain->insert_before(jcr, next_jcr);
418 printf("Print remaining list.\n");
419 foreach_dlist (jcr, jcr_chain) {
420 printf("Dlist item = %s\n", jcr->buf);
427 /* Now do a binary insert for the list */
428 jcr_chain = New(dlist(jcr, &jcr->link));
430 printf("append %d items\n", CNT*CNT*CNT);
433 for (int i=0; i<CNT; i++) {
434 for (int j=0; j<CNT; j++) {
435 for (int k=0; k<CNT; k++) {
437 if ((count & 0x3FF) == 0) {
438 Dmsg1(000, "At %d\n", count);
440 jcr = (MYJCR *)malloc(sizeof(MYJCR));
441 jcr->buf = bstrdup(buf);
442 jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
444 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
455 jcr = (MYJCR *)malloc(sizeof(MYJCR));
457 jcr->buf = bstrdup(buf);
458 if (jcr_chain->binary_search(jcr, my_compare)) {
459 printf("One less failed!!!!\n");
461 printf("One less: OK\n");
464 strcpy(buf, "ZZZZZZZZZZZZZZZZ");
465 jcr->buf = bstrdup(buf);
466 if (jcr_chain->binary_search(jcr, my_compare)) {
467 printf("One greater failed!!!!\n");
469 printf("One greater: OK\n");
475 printf("Find each of %d items in list.\n", count);
476 foreach_dlist (jcr, jcr_chain) {
477 if (!jcr_chain->binary_search(jcr, my_compare)) {
478 printf("Dlist binary_search item not found = %s\n", jcr->buf);
481 printf("Free each of %d items in list.\n", count);
482 foreach_dlist (jcr, jcr_chain) {