webserver: comparison src/ucx/avl.c

-:ddfead6ea863
+:4784c14aa639
 /*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
-* Copyright 2016 Olaf Wintermann. All rights reserved.
+* Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
-#include "avl.h"
+#include "ucx/avl.h"
+#include <limits.h>
 #define ptrcast(ptr) ((void*)(ptr))
 #define alloc_tree(al) (UcxAVLTree*) almalloc((al), sizeof(UcxAVLTree))
 #define alloc_node(al) (UcxAVLNode*) almalloc((al), sizeof(UcxAVLNode))
 UcxAllocator *al = tree->allocator;
 ucx_avl_free_node(al, tree->root);
 alfree(al, tree);
 }
+static void ucx_avl_free_content_node(UcxAllocator *al, UcxAVLNode *node,
+ucx_destructor destr) {
+if (node) {
+ucx_avl_free_content_node(al, node->left, destr);
+ucx_avl_free_content_node(al, node->right, destr);
+if (destr) {
+destr(node->value);
+} else {
+alfree(al, node->value);
+}
+}
+}
+void ucx_avl_free_content(UcxAVLTree *tree, ucx_destructor destr) {
+ucx_avl_free_content_node(tree->allocator, tree->root, destr);
+}
 UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) {
 UcxAVLNode *n = tree->root;
 int cmpresult;
 while (n && (cmpresult = tree->cmpfunc(
 ptrcast(key), ptrcast(n->key), tree->userdata))) {
 return n;
 }
 void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) {
 UcxAVLNode *n = ucx_avl_get_node(tree, key);
+return n ? n->value : NULL;
+}
+UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key,
+distance_func dfnc, int mode) {
+UcxAVLNode *n = tree->root;
+UcxAVLNode *closest = NULL;
+intmax_t cmpresult;
+intmax_t closest_dist;
+closest_dist = mode == UCX_AVL_FIND_LOWER_BOUNDED ? INTMAX_MIN : INTMAX_MAX;
+while (n && (cmpresult = dfnc(
+ptrcast(key), ptrcast(n->key), tree->userdata))) {
+if (mode == UCX_AVL_FIND_CLOSEST) {
+intmax_t dist = cmpresult;
+if (dist < 0) dist *= -1;
+if (dist < closest_dist) {
+closest_dist = dist;
+closest = n;
+}
+} else if (mode == UCX_AVL_FIND_LOWER_BOUNDED && cmpresult <= 0) {
+if (cmpresult > closest_dist) {
+closest_dist = cmpresult;
+closest = n;
+}
+} else if (mode == UCX_AVL_FIND_UPPER_BOUNDED && cmpresult >= 0) {
+if (cmpresult < closest_dist) {
+closest_dist = cmpresult;
+closest = n;
+}
+}
+n = cmpresult > 0 ? n->right : n->left;
+}
+return n ? n : closest;
+}
+void *ucx_avl_find(UcxAVLTree *tree, intptr_t key,
+distance_func dfnc, int mode) {
+UcxAVLNode *n = ucx_avl_find_node(tree, key, dfnc, mode);
 return n ? n->value : NULL;
 }
 int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) {
 return ucx_avl_put_s(tree, key, value, NULL);
 }
 size_t ucx_avl_count(UcxAVLTree *tree) {
 return ucx_avl_countn(tree->root);
 }
+UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
+if (node->left) {
+UcxAVLNode* n = node->left;
+while (n->right) {
+n = n->right;
+}
+return n;
+} else {
+UcxAVLNode* n = node;
+while (n->parent) {
+if (n->parent->right == n) {
+return n->parent;
+} else {
+n = n->parent;
+}
+}
+return NULL;
+}
+}
+UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
+if (node->right) {
+UcxAVLNode* n = node->right;
+while (n->left) {
+n = n->left;
+}
+return n;
+} else {
+UcxAVLNode* n = node;
+while (n->parent) {
+if (n->parent->left == n) {
+return n->parent;
+} else {
+n = n->parent;
+}
+}
+return NULL;
+}
+}

Mercurial > hg > webserver / file comparison

comparison: src/ucx/avl.c

src/ucx/avl.c