/*
- * Bacula doubly linked list routines.
+ * Bacula doubly linked list routines.
*
* dlist is a doubly linked list with the links being in the
* list data item.
- *
+ *
* Kern Sibbald, July MMIII
*
* Version $Id$
*
*/
/*
- Copyright (C) 2000-2004 Kern Sibbald and John Walker
+ Copyright (C) 2003-2005 Kern Sibbald
This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of
- the License, or (at your option) any later version.
+ modify it under the terms of the GNU General Public License
+ version 2 as ammended with additional clauses defined in the
+ file LICENSE in the main source directory.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public
- License along with this program; if not, write to the Free
- Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
- MA 02111-1307, USA.
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ the file LICENSE for additional details.
*/
/*
* Append an item to the list
*/
-void dlist::append(void *item)
+void dlist::append(void *item)
{
((dlink *)(((char *)item)+loffset))->next = NULL;
((dlink *)(((char *)item)+loffset))->prev = tail;
/*
* Append an item to the list
*/
-void dlist::prepend(void *item)
+void dlist::prepend(void *item)
{
((dlink *)(((char *)item)+loffset))->next = head;
((dlink *)(((char *)item)+loffset))->prev = NULL;
((dlink *)(((char *)head)+loffset))->prev = item;
}
head = item;
- if (tail == NULL) { /* if empty list, */
+ if (tail == NULL) { /* if empty list, */
tail = item; /* item is tail too */
}
num_items++;
}
-void dlist::insert_before(void *item, void *where)
+void dlist::insert_before(void *item, void *where)
{
- dlink *where_link = (dlink *)((char *)where+loffset);
+ dlink *where_link = (dlink *)((char *)where+loffset);
((dlink *)(((char *)item)+loffset))->next = where;
((dlink *)(((char *)item)+loffset))->prev = where_link->prev;
num_items++;
}
-void dlist::insert_after(void *item, void *where)
+void dlist::insert_after(void *item, void *where)
{
- dlink *where_link = (dlink *)((char *)where+loffset);
+ dlink *where_link = (dlink *)((char *)where+loffset);
((dlink *)(((char *)item)+loffset))->next = where_link->next;
((dlink *)(((char *)item)+loffset))->prev = where;
* Returns: item if item inserted
* other_item if same value already exists (item not inserted)
*/
-void *dlist::unique_binary_insert(void *item, int compare(void *item1, void *item2))
+void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
{
int comp;
int low, high, cur;
return item;
}
if (num_items == 1) {
- comp = compare(item, first());
+ comp = compare(item, first());
if (comp < 0) {
prepend(item);
//Dmsg0(000, "Insert before first.\n");
cur++;
}
while (nxt < cur) {
- cur_item = prev(cur_item);
+ cur_item = prev(cur_item);
cur--;
}
//Dmsg1(000, "Compare item to %d\n", cur);
return item;
}
-
/*
* Insert an item in the list, regardless if it is unique
* or not.
*/
-void dlist::binary_insert(void *item, int compare(void *item1, void *item2))
+void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
{
- void *ins_item = unique_binary_insert(item, compare);
+ void *ins_item = binary_insert(item, compare);
/* If identical, insert after the one found */
if (ins_item != item) {
insert_after(item, ins_item);
}
}
+/*
+ * Search for item
+ */
+void *dlist::binary_search(void *item, int compare(void *item1, void *item2))
+{
+ int comp;
+ int low, high, cur;
+ void *cur_item;
+
+
+ if (num_items == 0) {
+ return NULL;
+ }
+ cur_item = first();
+ if (num_items == 1) {
+ comp = compare(item, cur_item);
+ if (comp == 0) {
+ return cur_item;
+ } else {
+ return NULL;
+ }
+ }
+ low = 1;
+ high = num_items;
+ cur = 1;
+ cur_item = first();
+ while (low < high) {
+ int nxt;
+ nxt = (low + high) / 2;
+ /* Now get cur pointing to nxt */
+ while (nxt > cur) {
+ cur_item = next(cur_item);
+ cur++;
+ }
+ while (nxt < cur) {
+ cur_item = prev(cur_item);
+ cur--;
+ }
+ comp = compare(item, cur_item);
+ //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
+ if (comp < 0) {
+ high = cur;
+ //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
+ } else if (comp > 0) {
+ low = cur + 1;
+ //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
+ } else {
+ return cur_item;
+ }
+ }
+ /*
+ * low == high can only happen if low just
+ * got incremented from cur, and we have
+ * not yet tested cur+1
+ */
+ if (low == high) {
+ cur_item = next(cur_item);
+ comp = compare(item, cur_item);
+ if (comp == 0) {
+ return cur_item;
+ }
+ }
+ return NULL;
+}
+
void dlist::remove(void *item)
{
jcr_chain = (dlist *)malloc(sizeof(dlist));
jcr_chain->init(jcr, &jcr->link);
-
+
printf("Prepend 20 items 0-19\n");
for (int i=0; i<20; i++) {
sprintf(buf, "This is dlist item %d", i);
next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
printf("11th item=%s\n", next_jcr->buf);
- jcr = (MYJCR *)malloc(sizeof(MYJCR));
- jcr->buf = save_jcr->buf;
+ jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
+ jcr1->buf = save_jcr->buf;
printf("Remove 10th item\n");
jcr_chain->remove(save_jcr);
+ free(save_jcr);
printf("Re-insert 10th item\n");
- jcr_chain->insert_before(jcr, next_jcr);
-
+ jcr_chain->insert_before(jcr1, next_jcr);
+
printf("Print remaining list.\n");
- foreach_dlist (jcr, jcr_chain) {
+ foreach_dlist(jcr, jcr_chain) {
printf("Dlist item = %s\n", jcr->buf);
free(jcr->buf);
}
jcr->buf = save_jcr->buf;
printf("Remove 10th item\n");
jcr_chain->remove(save_jcr);
+ free(save_jcr);
printf("Re-insert 10th item\n");
jcr_chain->insert_before(jcr, next_jcr);
-
+
printf("Print remaining list.\n");
foreach_dlist (jcr, jcr_chain) {
printf("Dlist item = %s\n", jcr->buf);
buf[0]--;
}
- printf("Print sorted list.\n");
+ jcr = (MYJCR *)malloc(sizeof(MYJCR));
+ strcpy(buf, "a");
+ jcr->buf = bstrdup(buf);
+ if (jcr_chain->binary_search(jcr, my_compare)) {
+ printf("One less failed!!!!\n");
+ } else {
+ printf("One less: OK\n");
+ }
+ free(jcr->buf);
+ strcpy(buf, "ZZZZZZZZZZZZZZZZ");
+ jcr->buf = bstrdup(buf);
+ if (jcr_chain->binary_search(jcr, my_compare)) {
+ printf("One greater failed!!!!\n");
+ } else {
+ printf("One greater: OK\n");
+ }
+ free(jcr->buf);
+ free(jcr);
+
+
+ printf("Find each of %d items in list.\n", count);
+ foreach_dlist (jcr, jcr_chain) {
+ if (!jcr_chain->binary_search(jcr, my_compare)) {
+ printf("Dlist binary_search item not found = %s\n", jcr->buf);
+ }
+ }
+ printf("Free each of %d items in list.\n", count);
foreach_dlist (jcr, jcr_chain) {
- printf("Dlist item = %s\n", jcr->buf);
free(jcr->buf);
+ jcr->buf = NULL;
}
-
delete jcr_chain;
projects / bacula / bacula / blobdiff