1.1 --- a/ucx/avl.c Mon May 18 20:39:04 2015 +0200
1.2 +++ b/ucx/avl.c Tue May 19 16:47:54 2015 +0200
1.3 @@ -132,17 +132,27 @@
1.4 alfree(al, tree);
1.5 }
1.6
1.7 -void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
1.8 +UcxAVLNode *ucx_avl_getn(UcxAVLTree *tree, intptr_t key) {
1.9 UcxAVLNode *n = tree->root;
1.10 int cmpresult;
1.11 while (n && (cmpresult = tree->cmpfunc(
1.12 ptrcast(key), ptrcast(n->key), tree->userdata))) {
1.13 n = cmpresult > 0 ? n->right : n->left;
1.14 }
1.15 + return n;
1.16 +}
1.17 +
1.18 +void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
1.19 + UcxAVLNode *n = ucx_avl_getn(tree, key);
1.20 return n ? n->value : NULL;
1.21 }
1.22
1.23 -void* ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
1.24 +int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
1.25 + return ucx_avl_put_s(tree, key, value, NULL);
1.26 +}
1.27 +
1.28 +int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value,
1.29 + void **oldvalue) {
1.30 if (tree->root) {
1.31 UcxAVLNode *n = tree->root;
1.32 int cmpresult;
1.33 @@ -158,26 +168,51 @@
1.34
1.35 if (cmpresult) {
1.36 UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode));
1.37 - e->key = key; e->value = value; e->height = 1;
1.38 - e->parent = e->left = e->right = NULL;
1.39 - ucx_avl_connect(tree, n, e, 0);
1.40 - ucx_avl_balance(tree, n);
1.41 - return NULL;
1.42 + if (e) {
1.43 + e->key = key; e->value = value; e->height = 1;
1.44 + e->parent = e->left = e->right = NULL;
1.45 + ucx_avl_connect(tree, n, e, 0);
1.46 + ucx_avl_balance(tree, n);
1.47 + return 0;
1.48 + } else {
1.49 + return 1;
1.50 + }
1.51 } else {
1.52 - void *prevval = n->value;
1.53 + if (oldvalue) {
1.54 + *oldvalue = n->value;
1.55 + }
1.56 n->value = value;
1.57 - return prevval;
1.58 + return 0;
1.59 }
1.60 } else {
1.61 tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode));
1.62 - tree->root->key = key; tree->root->value = value;
1.63 - tree->root->height = 1;
1.64 - tree->root->parent = tree->root->left = tree->root->right = NULL;
1.65 - return NULL;
1.66 + if (tree->root) {
1.67 + tree->root->key = key; tree->root->value = value;
1.68 + tree->root->height = 1;
1.69 + tree->root->parent = tree->root->left = tree->root->right = NULL;
1.70 +
1.71 + if (oldvalue) {
1.72 + *oldvalue = NULL;
1.73 + }
1.74 +
1.75 + return 0;
1.76 + } else {
1.77 + return 1;
1.78 + }
1.79 }
1.80 }
1.81
1.82 -void* ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
1.83 +int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) {
1.84 + return ucx_avl_remove_s(tree, key, NULL, NULL);
1.85 +}
1.86 +
1.87 +int ucx_avl_remove_n(UcxAVLTree *tree, UcxAVLNode *node) {
1.88 + return ucx_avl_remove_s(tree, node->key, NULL, NULL);
1.89 +}
1.90 +
1.91 +int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key,
1.92 + intptr_t *oldkey, void **oldvalue) {
1.93 +
1.94 UcxAVLNode *n = tree->root;
1.95 int cmpresult;
1.96 while (n && (cmpresult = tree->cmpfunc(
1.97 @@ -185,7 +220,13 @@
1.98 n = cmpresult > 0 ? n->right : n->left;
1.99 }
1.100 if (n) {
1.101 - void *prevval = n->value;
1.102 + if (oldkey) {
1.103 + *oldkey = n->key;
1.104 + }
1.105 + if (oldvalue) {
1.106 + *oldvalue = n->value;
1.107 + }
1.108 +
1.109 UcxAVLNode *p = n->parent;
1.110 if (n->left && n->right) {
1.111 UcxAVLNode *s = n->right;
1.112 @@ -211,9 +252,10 @@
1.113 if (p) {
1.114 ucx_avl_balance(tree, p);
1.115 }
1.116 - return prevval;
1.117 +
1.118 + return 0;
1.119 } else {
1.120 - return NULL;
1.121 + return 1;
1.122 }
1.123 }
1.124
