*
*/
/*
- Copyright (C) 2005 Kern Sibbald
+ Bacula® - The Network Backup Solution
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License
- version 2 as amended with additional clauses defined in the
- file LICENSE in the main source directory.
+ Copyright (C) 2005-2006 Free Software Foundation Europe e.V.
- 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
- the file LICENSE for additional details.
+ 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
+ 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., 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.
+*/
#include "bacula.h"
#include "btree.h"
int comp;
x = head;
- while (x && !found) {
+ while (x) {
comp = compare(item, x);
if (comp < 0) {
x = x->left;
x = x->right;
} else {
found = x;
+ break;
}
}
return found;
if (!x->parent) {
return NULL;
}
- /* Move up in tree */
down = false;
/* Go up one and return parent */
return x->parent;
{
bnode *x, *y = NULL;
- for (x=first(); (y=any(x)); ) {
+ x = first();
+// printf("head=%p first=%p left=%p right=%p\n", head, x, x->left, x->right);
+
+ for ( ; (y=any(x)); ) {
/* Prune the last item */
- if (!x->parent) {
- head = x;
- } else if (x == x->parent->left) {
- x->parent->left = NULL;
- } else if (x == x->parent->right) {
- x->parent->right = NULL;
+ if (x->parent) {
+ if (x == x->parent->left) {
+ x->parent->left = NULL;
+ } else if (x == x->parent->right) {
+ x->parent->right = NULL;
+ }
}
if (!x->left && !x->right) {
+ if (head == x) {
+ head = NULL;
+ }
+// if (num_items<30) {
+// printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
+// }
free((void *)x); /* free previous node */
+ num_items--;
}
x = y; /* save last node */
}
if (x) {
+ if (x == head) {
+ head = NULL;
+ }
+// printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
free((void *)x);
+ num_items--;
}
- if (y) {
- free((void *)y);
+ if (head) {
+// printf("Free head\n");
+ free((void *)head);
}
+// printf("free nitems=%d\n", num_items);
- num_items = 0;
head = NULL;
}
jcr = (MYJCR *)malloc(sizeof(MYJCR));
memset(jcr, 0, sizeof(MYJCR));
jcr->buf = bstrdup(buf);
+// printf("buf=%p %s\n", jcr, jcr->buf);
jcr1 = (MYJCR *)jcr_chain->insert((bnode *)jcr, my_compare);
if (jcr != jcr1) {
Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
buf[0]--;
}
printf("%d items appended\n", CNT*CNT*CNT);
+ printf("num_items=%d\n", jcr_chain->size());
+
+ foreach_btree(jcr, jcr_chain) {
+// printf("%s\n", jcr->buf); /* turn on if you want lots of output */
+ }
+
jcr = (MYJCR *)malloc(sizeof(MYJCR));
memset(jcr, 0, sizeof(MYJCR));
- strcpy(buf, "a");
- jcr->buf = bstrdup(buf);
- if (jcr_chain->search((bnode *)jcr, my_compare)) {
- printf("One less failed!!!!\n");
+
+ jcr->buf = bstrdup("a");
+ if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
+ printf("One less failed!!!! Got: %s\n", jcr1->buf);
} else {
printf("One less: OK\n");
}
free(jcr->buf);
- strcpy(buf, "ZZZZZZZZZZZZZZZZ");
- jcr->buf = bstrdup(buf);
- if (jcr_chain->search((bnode *)jcr, my_compare)) {
- printf("One greater failed!!!!\n");
+
+ jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
+ if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
+ printf("One greater failed!!!! Got:%s\n", jcr1->buf);
} else {
printf("One greater: OK\n");
}
free(jcr->buf);
- strcpy(buf, "AAA");
- jcr->buf = bstrdup(buf);
- if (jcr_chain->search((bnode *)jcr, my_compare)) {
- printf("Search for AAA failed!!!!\n");
+
+ jcr->buf = bstrdup("AAA");
+ if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
+ printf("Search for AAA got %s\n", jcr1->buf);
} else {
- printf("AAA: OK\n");
+ printf("Search for AAA not found\n");
}
free(jcr->buf);
- strcpy(buf, "ZZZ");
- jcr->buf = bstrdup(buf);
- if (jcr_chain->search((bnode *)jcr, my_compare)) {
- printf("Search for ZZZ failed!!!!\n");
+
+ jcr->buf = bstrdup("ZZZ");
+ if ((jcr1 = (MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
+ printf("Search for ZZZ got %s\n", jcr1->buf);
} else {
- printf("ZZZ: OK\n");
+ printf("Search for ZZZ not found\n");
}
free(jcr->buf);
-
free(jcr);
printf("Find each of %d items in tree.\n", count);
- for (jcr=(MYJCR *)jcr_chain->first(); (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)); ) {
+ for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
// printf("Got: %s\n", jcr->buf);
if (!jcr_chain->search((bnode *)jcr, my_compare)) {
printf("btree binary_search item not found = %s\n", jcr->buf);
}
}
printf("Free each of %d items in tree.\n", count);
- for (jcr=(MYJCR *)jcr_chain->first(); (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)); ) {
+ for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
+// printf("Free: %p %s\n", jcr, jcr->buf);
free(jcr->buf);
jcr->buf = NULL;
}
+ printf("num_items=%d\n", jcr_chain->size());
delete jcr_chain;