From bf42cc28795ebc8f3158d99f66b0e5d79d9b4251 Mon Sep 17 00:00:00 2001 From: Kern Sibbald Date: Wed, 23 Nov 2005 15:40:44 +0000 Subject: [PATCH] Add new files git-svn-id: https://bacula.svn.sourceforge.net/svnroot/bacula/trunk@2623 91ce42f0-d328-0410-95d8-f526ca767f89 --- bacula/kes-1.39 | 2 + bacula/projects | 21 +- bacula/src/lib/btree.c | 457 +++++++++++++++++++++++++++++++++++++++++ bacula/src/lib/btree.h | 94 +++++++++ 4 files changed, 571 insertions(+), 3 deletions(-) create mode 100644 bacula/src/lib/btree.c create mode 100644 bacula/src/lib/btree.h diff --git a/bacula/kes-1.39 b/bacula/kes-1.39 index e04221ec3a..9daab4d782 100644 --- a/bacula/kes-1.39 +++ b/bacula/kes-1.39 @@ -4,6 +4,8 @@ General: Changes to 1.39.0: +23Nov05 +- Add red-black btree routines 21Nov05 - Remove abs() in bfile.c so that it compiles on Solaris. Bug #491. diff --git a/bacula/projects b/bacula/projects index 55fec7bf02..fde0368db2 100644 --- a/bacula/projects +++ b/bacula/projects @@ -488,11 +488,26 @@ Item 19: Implement new {Client}Run{Before|After}Job feature. if that specific RunBefore fails. Notes: By Kern: I would prefer to have a single new Resource called - RunScript, and within that resource an additional directive: + RunScript. More notes from Phil: - RunBeforeJob = Yes|No + RunsWhen = Before|After + RunsAtJobLevels = All|Full|Diff|Inc - If no, it runs it after the job. + The AbortJobOnError, RunsOnSuccess and RunsOnFailure directives + could be optional, and possibly RunsWhen as well. + + If omitted, RunsWhen would default to Before. + + AbortJobOnError would be ignored unless RunsWhen was set to Before + (or RunsBefore Job set to Yes), and would default to Yes if + omitted. If AbortJobOnError was set to No, failure of the script + would still generate a warning. + + RunsOnSuccess would be ignored unless RunsWhen was set to After + (or RunsBeforeJob set to No), and default to Yes. + + RunsOnFailure would be ignored unless RunsWhen was set to After, + and default to No. ============= Empty RFC form =========== diff --git a/bacula/src/lib/btree.c b/bacula/src/lib/btree.c new file mode 100644 index 0000000000..f419823eaf --- /dev/null +++ b/bacula/src/lib/btree.c @@ -0,0 +1,457 @@ +/* + * Bacula red-black binary tree routines. + * + * btree is a binary tree with the links being in the data item. + * + * Developped in part from ideas obtained from several online University + * courses. + * + * Kern Sibbald, November MMV + * + * Version $Id$ + * + */ +/* + Copyright (C) 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 + version 2 as amended 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 + the file LICENSE for additional details. + + */ + +#include "bacula.h" +#include "btree.h" + +/* =================================================================== + * btree + */ + +/* + * Insert an item in the tree, but only if it is unique + * otherwise, the item is returned non inserted + * The big trick is keeping the tree balanced after the + * insert. We use a parent pointer to make it simpler and + * to avoid recursion. + * + * Returns: item if item inserted + * other_item if same value already exists (item not inserted) + */ +bnode *btree::insert(bnode *item, int compare(bnode *item1, bnode *item2)) +{ + bnode *x, *y; + bnode *last = NULL; /* last leaf if not found */ + bnode *found = NULL; + int comp = 0; + + /* Search */ + x = head; + while (x && !found) { + last = x; + comp = compare(item, x); + if (comp < 0) { + x = x->left; + } else if (comp > 0) { + x = x->right; + } else { + found = x; + } + } + + if (found) { /* found? */ + return found; /* yes, return item found */ + } + /* Handle empty tree */ + if (num_items == 0) { + head = item; + num_items++; + return item; + } + x = last; + /* Not found, so insert it on appropriate side of tree */ + if (comp < 0) { + last->left = item; + } else { + last->right = item; + } + last->red = true; + item->parent = last; + num_items++; + + /* Now we must walk up the tree balancing it */ + x = last; + while (x != head && x->parent->red) { + if (x->parent == x->parent->parent->left) { + /* Look at the right side of our grandparent */ + y = x->parent->parent->right; + if (y && y->red) { + /* our parent must be black */ + x->parent->red = false; + y->red = false; + x->parent->parent->red = true; + x = x->parent->parent; /* move up to grandpa */ + } else { + if (x == x->parent->right) { /* right side of parent? */ + x = x->parent; + left_rotate(x); + } + /* make parent black too */ + x->parent->red = false; + x->parent->parent->red = true; + right_rotate(x->parent->parent); + } + } else { + /* Look at left side of our grandparent */ + y = x->parent->parent->left; + if (y && y->red) { + x->parent->red = false; + y->red = false; + x->parent->parent->red = true; + x = x->parent->parent; /* move up to grandpa */ + } else { + if (x == x->parent->left) { + x = x->parent; + right_rotate(x); + } + /* make parent black too */ + x->parent->red = false; + x->parent->parent->red = true; + left_rotate(x->parent->parent); + } + } + } + /* Make sure the head is always black */ + head->red = false; + return item; +} + + +/* + * Search for item + */ +bnode *btree::search(bnode *item, int compare(bnode *item1, bnode *item2)) +{ + bnode *found = NULL; + bnode *x; + int comp; + + x = head; + while (x && !found) { + comp = compare(item, x); + if (comp < 0) { + x = x->left; + } else if (comp > 0) { + x = x->right; + } else { + found = x; + } + } + return found; +} + +/* + * Get first item (i.e. lowest value) + */ +bnode *btree::first(void) +{ + bnode *x; + + x = head; + down = true; + while (x) { + if (x->left) { + x = x->left; + continue; + } + return x; + } + /* Tree is empty */ + return NULL; +} + +/* + * This is a non-recursive btree walk routine that returns + * the items one at a time in order. I've never seen a + * non-recursive tree walk routine published that returns + * one item at a time rather than doing a callback. + * + * Return the next item in sorted order. We assume first() + * was called once before calling this routine. + * We always go down as far as we can to the left, then up, and + * down one to the right, and again down as far as we can to the + * left. etc. + * + * Returns: pointer to next larger item + * NULL when no more items in tree + */ +bnode *btree::next(bnode *item) +{ + bnode *x; + + x = item; + if ((down && !x->left && x->right) || (!down && x->right)) { + /* Move down to right one */ + down = true; + x = x->right; + /* Then all the way down left */ + while (x->left) { + x = x->left; + } + return x; + } + + /* We have gone down all we can, so now go up */ + for ( ;; ) { + /* If at head, we are done */ + if (!x->parent) { + return NULL; + } + /* Move up in tree */ + down = false; + /* if coming from right, continue up */ + if (x->parent->right == x) { + x = x->parent; + continue; + } + /* Coming from left, go up one -- ie. return parent */ + return x->parent; + } +} + +/* + * Similer to next(), but visits all right nodes when + * coming up the tree. + */ +bnode *btree::any(bnode *item) +{ + bnode *x; + + x = item; + if ((down && !x->left && x->right) || (!down && x->right)) { + /* Move down to right one */ + down = true; + x = x->right; + /* Then all the way down left */ + while (x->left) { + x = x->left; + } + return x; + } + + /* We have gone down all we can, so now go up */ + for ( ;; ) { + /* If at head, we are done */ + if (!x->parent) { + return NULL; + } + /* Move up in tree */ + down = false; + /* Go up one and return parent */ + return x->parent; + } +} + + +/* x is item, y is below and to right, then rotated to below left */ +void btree::left_rotate(bnode *item) +{ + bnode *y; + bnode *x; + + x = item; + y = x->right; + x->right = y->left; + if (y->left) { + y->left->parent = x; + } + y->parent = x->parent; + /* if no parent then we have a new head */ + if (!x->parent) { + head = y; + } else if (x == x->parent->left) { + x->parent->left = y; + } else { + x->parent->right = y; + } + y->left = x; + x->parent = y; +} + +void btree::right_rotate(bnode *item) +{ + bnode *x, *y; + + y = item; + x = y->left; + y->left = x->right; + if (x->right) { + x->right->parent = y; + } + x->parent = y->parent; + /* if no parent then we have a new head */ + if (!y->parent) { + head = x; + } else if (y == y->parent->left) { + y->parent->left = x; + } else { + y->parent->right = x; + } + x->right = y; + y->parent = x; +} + + +void btree::remove(bnode *item) +{ +} + +/* Destroy the tree contents. Not totally working */ +void btree::destroy() +{ + bnode *x, *y = NULL; + + for (x=first(); (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->left && !x->right) { + free((void *)x); /* free previous node */ + } + x = y; /* save last node */ + } + if (x) { + free((void *)x); + } + if (y) { + free((void *)y); + } + + num_items = 0; + head = NULL; +} + + + +#ifdef TEST_PROGRAM + +struct MYJCR { + bnode link; + char *buf; +}; + +static int my_compare(bnode *item1, bnode *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]; + btree *jcr_chain; + MYJCR *jcr = NULL; + MYJCR *jcr1; + + + /* Now do a binary insert for the tree */ + jcr_chain = New(btree()); +#define CNT 26 + printf("append %d items\n", CNT*CNT*CNT); + strcpy(buf, "ZZZ"); + int count = 0; + for (int i=0; ibuf = bstrdup(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[1]--; + } + buf[1] = 'Z'; + buf[2]--; + } + buf[2] = 'Z'; + buf[0]--; + } + printf("%d items appended\n", CNT*CNT*CNT); + 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"); + } 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"); + } 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"); + } else { + printf("AAA: OK\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"); + } else { + printf("ZZZ: OK\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)); ) { +// 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)); ) { + free(jcr->buf); + jcr->buf = NULL; + } + delete jcr_chain; + + + sm_dump(true); + +} +#endif diff --git a/bacula/src/lib/btree.h b/bacula/src/lib/btree.h new file mode 100644 index 0000000000..df25085341 --- /dev/null +++ b/bacula/src/lib/btree.h @@ -0,0 +1,94 @@ +/* + * Version $Id$ + */ +/* + Copyright (C) 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 + version 2 as amended 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 + the file LICENSE for additional details. + + */ + + +/* ======================================================================== + * + * red-black binary tree routines -- btree.h + * + * Kern Sibbald, MMV + * + */ + +#define M_ABORT 1 + +/* + * There is a lot of extra casting here to work around the fact + * that some compilers (Sun and Visual C++) do not accept + * (bnode *) as an lvalue on the left side of an equal. + * + * Loop var through each member of list + */ +#define foreach_btree(var, tree) \ + for(*((bnode **)&(var))=(tree)->first(); (*((bnode **)&(var))=(tree)->next((bnode *)var)); ) + +#ifdef the_old_way +#define foreach_btree(var, tree) \ + for((var)=(tree)->first(); (((bnode *)(var))=(tree)->next((bnode *)var)); ) +#endif + +struct bnode; +struct bnode { + bnode *left; + bnode *right; + bnode *parent; + bool red; +}; + +class btree : public SMARTALLOC { + bnode *head; + uint32_t num_items; + bool down; + void left_rotate(bnode *item); + void right_rotate(bnode *item); +public: + btree(void); + ~btree() { destroy(); } + void init(void); + bnode *insert(bnode *item, int compare(bnode *item1, bnode *item2)); + bnode *search(bnode *item, int compare(bnode *item1, bnode *item2)); + bnode *first(void); + bnode *next(bnode *item); + bnode *any(bnode *item); + void remove(bnode *item); + int size() const; + void destroy(); +}; + + +/* + * This allows us to do explicit initialization, + * allowing us to mix C++ classes inside malloc'ed + * C structures. Define before called in constructor. + */ +inline void btree::init() +{ + head = NULL; + num_items = 0; +} + + +/* Constructor with link at head of item */ +inline btree::btree(void) : head(0), num_items(0) +{ +} + +inline int btree::size() const +{ + return num_items; +} -- 2.39.5