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