diff --git a/src/utils/avltree.c b/src/utils/avltree.c
index 95c004d32ffbe10ae39a31b9a146a80adccd2b41..d8151c8926cb9f443539225eda05514347d4384c 100644 (file)
--- a/src/utils/avltree.c
+++ b/src/utils/avltree.c
# include "config.h"
#endif /* HAVE_CONFIG_H */
+#include "sysdb.h"
#include "utils/avltree.h"
-#include <stdlib.h>
+#include <assert.h>
+#include <stdlib.h>
#include <pthread.h>
/*
node_t *parent;
node_t *left;
node_t *right;
+
+ size_t height;
};
+#define NODE_HEIGHT(n) ((n) ? (n)->height : (size_t)0)
+#define CALC_HEIGHT(n) (SDB_MAX(NODE_HEIGHT((n)->right), \
+ NODE_HEIGHT((n)->left)) + 1)
+
+#define BALANCE(n) \
+ ((n) ? (int)NODE_HEIGHT((n)->left) - (int)NODE_HEIGHT((n)->right) : 0)
+
struct sdb_avltree {
pthread_rwlock_t lock;
sdb_object_ref(obj);
n->obj = obj;
n->parent = n->left = n->right = NULL;
+ n->height = 1;
return n;
} /* node_create */
return next;
} /* node_next */
+static node_t *
+node_smallest(sdb_avltree_t *tree)
+{
+ node_t *n;
+
+ if (! tree)
+ return NULL;
+
+ n = tree->root;
+ while (n && n->left)
+ n = n->left;
+ return n;
+} /* node_smallest */
+
static void
tree_clear(sdb_avltree_t *tree)
{
node_t *n;
- n = tree->root;
+ n = node_smallest(tree);
while (n) {
node_t *tmp = node_next(n);
tree->size = 0;
} /* tree_clear */
+/* Switch node 'n' with its right child, making 'n'
+ * the new left child of that node. */
+static void
+rotate_left(sdb_avltree_t *tree, node_t *n)
+{
+ node_t *n2 = n->right;
+ node_t *c = n2->left;
+
+ n2->parent = n->parent;
+ if (! n2->parent)
+ tree->root = n2;
+ else if (n2->parent->left == n)
+ n2->parent->left = n2;
+ else
+ n2->parent->right = n2;
+
+ n2->left = n;
+ n->parent = n2;
+
+ n->right = c;
+ if (c)
+ c->parent = n;
+
+ n->height = CALC_HEIGHT(n);
+ n2->height = CALC_HEIGHT(n2);
+} /* rotate_left */
+
+/* Switch node 'n' with its left child, making 'n'
+ * the new right child of that node. */
+static void
+rotate_right(sdb_avltree_t *tree, node_t *n)
+{
+ node_t *n2 = n->left;
+ node_t *c = n2->right;
+
+ n2->parent = n->parent;
+ if (! n2->parent)
+ tree->root = n2;
+ else if (n2->parent->left == n)
+ n2->parent->left = n2;
+ else
+ n2->parent->right = n2;
+
+ n2->right = n;
+ n->parent = n2;
+
+ n->left = c;
+ if (c)
+ c->parent = n;
+
+ n->height = CALC_HEIGHT(n);
+ n2->height = CALC_HEIGHT(n2);
+} /* rotate_right */
+
+/* Rebalance a tree starting at node 'n' towards the root;
+ * also, update the node heights all the way up to the root. */
+static void
+rebalance(sdb_avltree_t *tree, node_t *n)
+{
+ for ( ; n; n = n->parent) {
+ int bf = BALANCE(n);
+
+ if (bf == 0)
+ return;
+
+ if ((-1 <= bf) && (bf <= 1)) {
+ n->height = CALC_HEIGHT(n);
+ continue;
+ }
+
+ assert((-2 <= bf) && (bf <= 2));
+
+ if (bf == 2) {
+ if (BALANCE(n->left) == -1)
+ rotate_left(tree, n->left);
+ rotate_right(tree, n);
+ }
+ else {
+ if (BALANCE(n->right) == 1)
+ rotate_right(tree, n->right);
+ rotate_left(tree, n);
+ }
+
+ /* n was moved downwards; get back to the previous level */
+ n = n->parent;
+ }
+} /* rebalance */
+
/*
* public API
*/
if (! n)
return -1;
+ pthread_rwlock_wrlock(&tree->lock);
+
+ if (! tree->root) {
+ tree->root = n;
+ tree->size = 1;
+ pthread_rwlock_unlock(&tree->lock);
+ return 0;
+ }
+
parent = tree->root;
- while (parent) {
+ while (42) {
+ assert(parent);
+
diff = tree->cmp(obj, parent->obj);
if (! diff) {
node_destroy(n);
+ pthread_rwlock_unlock(&tree->lock);
return -1;
}
}
}
- if (! parent) {
- /* new root */
- if (diff < 0)
- n->right = tree->root;
- else
- n->left = tree->root;
- tree->root = n;
- }
-
n->parent = parent;
++tree->size;
- /* XXX: rebalance */
+ rebalance(tree, parent);
+ pthread_rwlock_unlock(&tree->lock);
return 0;
} /* sdb_avltree_insert */
pthread_rwlock_rdlock(&tree->lock);
iter->tree = tree;
- iter->node = tree->root->left;
- while (iter->node && iter->node->left)
- iter->node = iter->node->left;
+ iter->node = node_smallest(tree);
pthread_rwlock_unlock(&tree->lock);
return iter;