Wed, 14 Oct 2015 14:37:08 +0200
reimplemented redirects for propfind requests
128
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1 | /* |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
3 | * |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
4 | * Copyright 2015 Olaf Wintermann. All rights reserved. |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
5 | * |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
6 | * Redistribution and use in source and binary forms, with or without |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
7 | * modification, are permitted provided that the following conditions are met: |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
8 | * |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
9 | * 1. Redistributions of source code must retain the above copyright |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
10 | * notice, this list of conditions and the following disclaimer. |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
11 | * |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
12 | * 2. Redistributions in binary form must reproduce the above copyright |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
13 | * notice, this list of conditions and the following disclaimer in the |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
14 | * documentation and/or other materials provided with the distribution. |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
15 | * |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
26 | * POSSIBILITY OF SUCH DAMAGE. |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
27 | */ |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
28 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
29 | #include "avl.h" |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
30 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31 | #define ptrcast(ptr) ((void*)(ptr)) |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
32 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
33 | static void ucx_avl_connect(UcxAVLTree *tree, |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
34 | UcxAVLNode *node, UcxAVLNode *child, intptr_t nullkey) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
35 | if (child) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
36 | child->parent = node; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
37 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
38 | // if child is NULL, nullkey decides if left or right pointer is cleared |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
39 | if (tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
40 | ptrcast(child ? child->key : nullkey), |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
41 | ptrcast(node->key), tree->userdata) > 0) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
42 | node->right = child; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
43 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
44 | node->left = child; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
45 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | size_t lh = node->left ? node->left->height : 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
47 | size_t rh = node->right ? node->right->height : 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
48 | node->height = 1 + (lh > rh ? lh : rh); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
49 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
50 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51 | #define avlheight(node) ((node) ? (node)->height : 0) |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
53 | static UcxAVLNode* avl_rotright(UcxAVLTree *tree, UcxAVLNode *l0) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
54 | UcxAVLNode *p = l0->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55 | UcxAVLNode *l1 = l0->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
56 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57 | ucx_avl_connect(tree, p, l1, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
59 | l1->parent = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61 | ucx_avl_connect(tree, l0, l1->right, l1->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62 | ucx_avl_connect(tree, l1, l0, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
63 | return l1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
64 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
65 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
66 | static UcxAVLNode* avl_rotleft(UcxAVLTree *tree, UcxAVLNode *l0) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
67 | UcxAVLNode *p = l0->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
68 | UcxAVLNode *l1 = l0->right; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
69 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70 | ucx_avl_connect(tree, p, l1, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
71 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
72 | l1->parent = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
73 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
74 | ucx_avl_connect(tree, l0, l1->left, l1->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
75 | ucx_avl_connect(tree, l1, l0, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76 | return l1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79 | static void ucx_avl_balance(UcxAVLTree *tree, UcxAVLNode *n) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
80 | int lh = avlheight(n->left); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
81 | int rh = avlheight(n->right); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
82 | n->height = 1 + (lh > rh ? lh : rh); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
83 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84 | if (lh - rh == 2) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85 | UcxAVLNode *c = n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86 | if (avlheight(c->right) - avlheight(c->left) == 1) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
87 | avl_rotleft(tree, c); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
88 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
89 | n = avl_rotright(tree, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
90 | } else if (rh - lh == 2) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
91 | UcxAVLNode *c = n->right; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
92 | if (avlheight(c->left) - avlheight(c->right) == 1) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
93 | avl_rotright(tree, c); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
94 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
95 | n = avl_rotleft(tree, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
96 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
97 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
98 | if (n->parent) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
99 | ucx_avl_balance(tree, n->parent); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
100 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
101 | tree->root = n; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
102 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
103 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
104 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
105 | UcxAVLTree *ucx_avl_new(cmp_func cmpfunc) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
106 | return ucx_avl_new_a(cmpfunc, ucx_default_allocator()); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
107 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
108 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
109 | UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
110 | UcxAVLTree *tree = almalloc(allocator, sizeof(UcxAVLTree)); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
111 | if (tree) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
112 | tree->allocator = allocator; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
113 | tree->cmpfunc = cmpfunc; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
114 | tree->root = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
115 | tree->userdata = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
116 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
117 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
118 | return tree; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
119 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
120 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
121 | static void ucx_avl_free_node(UcxAllocator *al, UcxAVLNode *node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
122 | if (node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
123 | ucx_avl_free_node(al, node->left); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
124 | ucx_avl_free_node(al, node->right); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
125 | alfree(al, node); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
126 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
127 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
128 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
129 | void ucx_avl_free(UcxAVLTree *tree) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
130 | UcxAllocator *al = tree->allocator; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
131 | ucx_avl_free_node(al, tree->root); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
132 | alfree(al, tree); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
133 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
134 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
135 | UcxAVLNode *ucx_avl_get_node(UcxAVLTree *tree, intptr_t key) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
136 | UcxAVLNode *n = tree->root; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
137 | int cmpresult; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
138 | while (n && (cmpresult = tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
139 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
140 | n = cmpresult > 0 ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
141 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
142 | return n; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
143 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
144 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
145 | void *ucx_avl_get(UcxAVLTree *tree, intptr_t key) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
146 | UcxAVLNode *n = ucx_avl_get_node(tree, key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
147 | return n ? n->value : NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
148 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
149 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
150 | int ucx_avl_put(UcxAVLTree *tree, intptr_t key, void *value) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
151 | return ucx_avl_put_s(tree, key, value, NULL); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
152 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
153 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
154 | int ucx_avl_put_s(UcxAVLTree *tree, intptr_t key, void *value, |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
155 | void **oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
156 | if (tree->root) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
157 | UcxAVLNode *n = tree->root; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
158 | int cmpresult; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
159 | while ((cmpresult = tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
160 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
161 | UcxAVLNode *m = cmpresult > 0 ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
162 | if (m) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
163 | n = m; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
164 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
165 | break; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
166 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
167 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
168 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
169 | if (cmpresult) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
170 | UcxAVLNode *e = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
171 | if (e) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
172 | e->key = key; e->value = value; e->height = 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
173 | e->parent = e->left = e->right = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
174 | ucx_avl_connect(tree, n, e, 0); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
175 | ucx_avl_balance(tree, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
176 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
177 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
178 | return 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
179 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
180 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
181 | if (oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
182 | *oldvalue = n->value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
183 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
184 | n->value = value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
185 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
186 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
187 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
188 | tree->root = almalloc(tree->allocator, sizeof(UcxAVLNode)); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
189 | if (tree->root) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
190 | tree->root->key = key; tree->root->value = value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
191 | tree->root->height = 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
192 | tree->root->parent = tree->root->left = tree->root->right = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
193 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
194 | if (oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
195 | *oldvalue = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
196 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
197 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
198 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
199 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
200 | return 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
201 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
202 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
203 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
204 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
205 | int ucx_avl_remove(UcxAVLTree *tree, intptr_t key) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
206 | return ucx_avl_remove_s(tree, key, NULL, NULL); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
207 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
208 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
209 | int ucx_avl_remove_node(UcxAVLTree *tree, UcxAVLNode *node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
210 | return ucx_avl_remove_s(tree, node->key, NULL, NULL); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
211 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
212 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
213 | int ucx_avl_remove_s(UcxAVLTree *tree, intptr_t key, |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
214 | intptr_t *oldkey, void **oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
215 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
216 | UcxAVLNode *n = tree->root; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
217 | int cmpresult; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
218 | while (n && (cmpresult = tree->cmpfunc( |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
219 | ptrcast(key), ptrcast(n->key), tree->userdata))) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
220 | n = cmpresult > 0 ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
221 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
222 | if (n) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
223 | if (oldkey) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
224 | *oldkey = n->key; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
225 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
226 | if (oldvalue) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
227 | *oldvalue = n->value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
228 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
229 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
230 | UcxAVLNode *p = n->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
231 | if (n->left && n->right) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
232 | UcxAVLNode *s = n->right; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
233 | while (s->left) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
234 | s = s->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
235 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
236 | ucx_avl_connect(tree, s->parent, s->right, s->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
237 | n->key = s->key; n->value = s->value; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
238 | p = s->parent; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
239 | alfree(tree->allocator, s); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
240 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
241 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
242 | ucx_avl_connect(tree, p, n->right ? n->right:n->left, n->key); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
243 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
244 | tree->root = n->right ? n->right : n->left; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
245 | if (tree->root) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
246 | tree->root->parent = NULL; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
247 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
248 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
249 | alfree(tree->allocator, n); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
250 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
251 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
252 | if (p) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
253 | ucx_avl_balance(tree, p); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
254 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
255 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
256 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
257 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
258 | return 1; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
259 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
260 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
261 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
262 | static size_t ucx_avl_countn(UcxAVLNode *node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
263 | if (node) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
264 | return 1 + ucx_avl_countn(node->left) + ucx_avl_countn(node->right); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
265 | } else { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
266 | return 0; |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
267 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
268 | } |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
269 | |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
270 | size_t ucx_avl_count(UcxAVLTree *tree) { |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
271 | return ucx_avl_countn(tree->root); |
649eb328674a
implemented minimal executor features and added missing ucx files
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
272 | } |