/*
- * 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-2003 Kern Sibbald and John Walker
+ Bacula® - The Network Backup Solution
+
+ Copyright (C) 2003-2007 Free Software Foundation Europe e.V.
- 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.
+ The main author of Bacula is Kern Sibbald, with contributions from
+ many others, a complete list can be found in the file AUTHORS.
+ This program is Free Software; you can redistribute it and/or
+ modify it under the terms of version two of the GNU General Public
+ License as published by the Free Software Foundation plus additions
+ that are listed in the file LICENSE.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
+ 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.
+ 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., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.
+ Bacula® is a registered trademark of John Walker.
+ The licensor of Bacula is the Free Software Foundation Europe
+ (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
+ Switzerland, email:ftf@fsfeurope.org.
+*/
+/*
+ * 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$
+ *
*/
#include "bacula.h"
/* ===================================================================
* dlist
*/
+
/*
* 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;
+ set_next(item, NULL);
+ set_prev(item, tail);
if (tail) {
- ((dlink *)((char *)tail+loffset))->next = item;
+ set_next(tail, item);
}
tail = item;
- if (head == NULL) { /* if empty list, */
- head = item; /* item is head as well */
+ if (head == NULL) { /* if empty list, */
+ head = item; /* item is head as well */
}
num_items++;
}
/*
* 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;
+ set_next(item, head);
+ set_prev(item, NULL);
if (head) {
- ((dlink *)((char *)head+loffset))->prev = item;
+ set_prev(head, item);
}
head = item;
- if (tail == NULL) { /* if empty list, */
- tail = item; /* item is tail too */
+ 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;
+ set_next(item, where);
+ set_prev(item, where_link->prev);
if (where_link->prev) {
- ((dlink *)((char *)(where_link->prev)+loffset))->next = item;
- where_link->prev = item;
+ set_next(where_link->prev, item);
}
+ where_link->prev = item;
if (head == where) {
head = item;
}
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;
+ set_next(item, where_link->next);
+ set_prev(item, where);
if (where_link->next) {
- ((dlink *)((char *)(where_link->next)+loffset))->prev = item;
- where_link->next = item;
+ set_prev(where_link->next, item);
}
+ where_link->next = item;
if (tail == where) {
tail = item;
}
num_items++;
}
+/*
+ * Insert an item in the list, but only if it is unique
+ * otherwise, the item is returned non inserted
+ *
+ * Returns: item if item inserted
+ * other_item if same value already exists (item not inserted)
+ */
+void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
+{
+ int comp;
+ int low, high, cur;
+ void *cur_item;
+
+ if (num_items == 0) {
+ //Dmsg0(000, "Append first.\n");
+ append(item);
+ return item;
+ }
+ if (num_items == 1) {
+ comp = compare(item, first());
+ if (comp < 0) {
+ prepend(item);
+ //Dmsg0(000, "Insert before first.\n");
+ return item;
+ } else if (comp > 0) {
+ insert_after(item, first());
+ //Dmsg0(000, "Insert after first.\n");
+ return item;
+ } else {
+ //Dmsg0(000, "Same as first.\n");
+ return first();
+ }
+ }
+ /* Check against last item */
+ comp = compare(item, last());
+ if (comp > 0) {
+ append(item);
+ //Dmsg0(000, "Appended item.\n");
+ return item;
+ } else if (comp == 0) {
+ //Dmsg0(000, "Same as last.\n");
+ return last();
+ }
+ /* Check against first item */
+ comp = compare(item, first());
+ if (comp < 0) {
+ prepend(item);
+ //Dmsg0(000, "Inserted item before.\n");
+ return item;
+ } else if (comp == 0) {
+ //Dmsg0(000, "Same as first.\n");
+ return first();
+ }
+ if (num_items == 2) {
+ insert_after(item, first());
+ //Dmsg0(000, "Inserted item after.\n");
+ return item;
+ }
+ low = 1;
+ high = num_items;
+ cur = 1;
+ cur_item = first();
+ while (low < high) {
+ int nxt;
+ nxt = (low + high) / 2;
+ while (nxt > cur) {
+ cur_item = next(cur_item);
+ cur++;
+ }
+ while (nxt < cur) {
+ cur_item = prev(cur_item);
+ cur--;
+ }
+ //Dmsg1(000, "Compare item to %d\n", 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 {
+ //Dmsg1(000, "Same as item %d\n", cur);
+ return cur_item;
+ }
+ }
+ if (high == cur) {
+ insert_before(item, cur_item);
+ //Dmsg1(000, "Insert before item %d\n", cur);
+ } else {
+ insert_after(item, cur_item);
+ //Dmsg1(000, "Insert after item %d\n", cur);
+ }
+ return item;
+}
+
+/*
+ * Insert an item in the list, regardless if it is unique
+ * or not.
+ */
+void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
+{
+ 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)
{
void *xitem;
- dlink *ilink = (dlink *)((char *)item+loffset); /* item's link */
+ dlink *ilink = (dlink *)(((char *)item)+loffset); /* item's link */
if (item == head) {
head = ilink->next;
if (head) {
- ((dlink *)((char *)head+loffset))->prev = NULL;
+ set_prev(head, NULL);
}
if (item == tail) {
- tail = ilink->prev;
+ tail = ilink->prev;
}
} else if (item == tail) {
tail = ilink->prev;
if (tail) {
- ((dlink *)((char *)tail+loffset))->next = NULL;
+ set_next(tail, NULL);
}
} else {
xitem = ilink->next;
- ((dlink *)((char *)xitem+loffset))->prev = ilink->prev;
+ set_prev(xitem, ilink->prev);
xitem = ilink->prev;
- ((dlink *)((char *)xitem+loffset))->next = ilink->next;
+ set_next(xitem, ilink->next);
}
num_items--;
+ if (num_items == 0) {
+ head = tail = NULL;
+ }
}
-void * dlist::next(void *item)
+void * dlist::next(const void *item) const
{
if (item == NULL) {
return head;
}
- return ((dlink *)((char *)item+loffset))->next;
+ return ((dlink *)(((char *)item)+loffset))->next;
}
-void * dlist::prev(void *item)
+void * dlist::prev(const void *item) const
{
if (item == NULL) {
return tail;
}
- return ((dlink *)((char *)item+loffset))->prev;
+ return ((dlink *)(((char *)item)+loffset))->prev;
}
void dlist::destroy()
{
for (void *n=head; n; ) {
- void *ni = ((dlink *)((char *)n+loffset))->next;
+ void *ni = ((dlink *)(((char *)n)+loffset))->next;
free(n);
n = ni;
}
num_items = 0;
+ head = tail = NULL;
}
+/* String helpers for dlist usage */
+dlistString *new_dlistString(const char *str)
+{
+ return new_dlistString(str, strlen(str));
+}
+
+dlistString *new_dlistString(const char *str, int len)
+{
+ dlistString *node;
+ node = (dlistString *)malloc(sizeof(dlistString) + len);
+ bstrncpy(node->c_str(), str, len);
+ return node;
+}
#ifdef TEST_PROGRAM
dlink link;
};
+static int my_compare(void *item1, void *item2)
+{
+ MYJCR *jcr1, *jcr2;
+ int comp;
+ jcr1 = (MYJCR *)item1;
+ jcr2 = (MYJCR *)item2;
+ comp = strcmp(jcr1->buf, jcr2->buf);
+ //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
+ return comp;
+}
+
int main()
{
char buf[30];
dlist *jcr_chain;
MYJCR *jcr = NULL;
+ MYJCR *jcr1;
MYJCR *save_jcr = NULL;
MYJCR *next_jcr;
+ int count;
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);
jcr->buf = bstrdup(buf);
jcr_chain->prepend(jcr);
if (i == 10) {
- save_jcr = jcr;
+ save_jcr = jcr;
}
}
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_chain->destroy();
free(jcr_chain);
- jcr_chain = new dlist(jcr, &jcr->link);
+ /* The following may seem a bit odd, but we create a chaing
+ * of jcr objects. Within a jcr object, there is a buf
+ * that points to a malloced string containing data
+ */
+ jcr_chain = New(dlist(jcr, &jcr->link));
printf("append 20 items 0-19\n");
for (int i=0; i<20; i++) {
sprintf(buf, "This is dlist item %d", i);
jcr->buf = bstrdup(buf);
jcr_chain->append(jcr);
if (i == 10) {
- save_jcr = jcr;
+ save_jcr = jcr;
}
}
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);
delete jcr_chain;
- sm_dump(False);
+
+ /* Now do a binary insert for the list */
+ jcr_chain = New(dlist(jcr, &jcr->link));
+#define CNT 26
+ printf("append %d items\n", CNT*CNT*CNT);
+ strcpy(buf, "ZZZ");
+ count = 0;
+ for (int i=0; i<CNT; i++) {
+ for (int j=0; j<CNT; j++) {
+ for (int k=0; k<CNT; k++) {
+ count++;
+ if ((count & 0x3FF) == 0) {
+ Dmsg1(000, "At %d\n", count);
+ }
+ jcr = (MYJCR *)malloc(sizeof(MYJCR));
+ jcr->buf = bstrdup(buf);
+ jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
+ if (jcr != jcr1) {
+ Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
+ }
+ buf[1]--;
+ }
+ buf[1] = 'Z';
+ buf[2]--;
+ }
+ buf[2] = 'Z';
+ buf[0]--;
+ }
+
+ 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) {
+ free(jcr->buf);
+ jcr->buf = NULL;
+ }
+ delete jcr_chain;
+
+ /* Finally, do a test using the dlistString string helper, which
+ * allocates a dlist node and stores the string directly in
+ * it.
+ */
+ dlist chain;
+ dlistString *node;
+#define CNT 26
+ printf("append %d dlistString items\n", CNT*CNT*CNT);
+ strcpy(buf, "ZZZ");
+ count = 0;
+ for (int i=0; i<CNT; i++) {
+ for (int j=0; j<CNT; j++) {
+ for (int k=0; k<CNT; k++) {
+ count++;
+ if ((count & 0x3FF) == 0) {
+ Dmsg1(000, "At %d\n", count);
+ }
+ node = new_dlistString(buf);
+ chain.append(node);
+ buf[1]--;
+ }
+ buf[1] = 'Z';
+ buf[2]--;
+ }
+ buf[2] = 'Z';
+ buf[0]--;
+ }
+ printf("dlistString items appended, walking chain\n");
+ foreach_dlist(node, &chain) {
+ printf("%s\n", node->c_str());
+ }
+ printf("destroy dlistString chain\n");
+ chain.destroy();
+
+ sm_dump(false);
}
#endif
projects / bacula / bacula / blobdiff