1 /*
2 * avl package
3 *
4 * Copyright (c) 1988-1993, The Regents of the University of California.
5 *
6 * Permission to use, copy, modify, and distribute this software and its
7 * documentation for any purpose and without fee is hereby granted, provided
8 * that the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation, and that the name of the University of California not
11 * be used in advertising or publicity pertaining to distribution of
12 * the software without specific, written prior permission. The University
13 * of California makes no representations about the suitability of this
14 * software for any purpose. It is provided "as is" without express or
15 * implied warranty.
16 *
17 * THE UNIVERSITY OF CALIFORNIA DISCLAIMS ALL WARRANTIES WITH REGARD TO
18 * THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
19 * FITNESS, IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE FOR
20 * ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
21 * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
22 * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
23 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 */
25
26 // Modified for Gmsh (C++ and 64 bit compatibility)
27
28 #include "GmshConfig.h"
29 #if !defined(HAVE_NO_STDINT_H)
30 #include <stdint.h>
31 #elif defined(HAVE_NO_INTPTR_T)
32 typedef unsigned long intptr_t;
33 #endif
34 #include <stdio.h>
35 #include "avl.h"
36 #include "MallocUtils.h"
37
38 #define ALLOC(type, number) (type *) Malloc((unsigned) sizeof(type) * number)
39 #define FREE(item) (void) Free(item)
40 #define XRNMAX(a,b) ((a) > (b) ? (a) : (b))
41 #define HEIGHT(node) (node == NIL(avl_node) ? -1 : (node)->height)
42 #define BALANCE(node) (HEIGHT((node)->right) - HEIGHT((node)->left))
43
44 #define compute_height(node) { \
45 int x=HEIGHT(node->left), y=HEIGHT(node->right); \
46 (node)->height = XRNMAX(x,y) + 1; \
47 }
48
49 #define COMPARE(key, nodekey, compare) \
50 ((compare == avl_numcmp) ? \
51 (intptr_t) key - (intptr_t) nodekey : \
52 (*compare)(key, nodekey))
53
54 static void avl_record_gen_forward(avl_node *node, avl_generator *gen);
55 static void avl_record_gen_backward(avl_node *node, avl_generator *gen);
56 static avl_node *find_rightmost(avl_node **node_p);
57 static void do_rebalance(avl_node ***stack_nodep, int stack_n);
58 static void rotate_left(avl_node **node_p);
59 static void rotate_right(avl_node **node_p);
60 static void free_entry(avl_node *node, void (*key_free)(void *key),
61 void (*value_free)(void *value));
62 static avl_node *new_node(void *key, void *value);
63 static int do_check_tree(avl_node *node, int (*compar)(const void *key1, const void *key2),
64 int *error);
65
66
avl_init_table(int (* compar)(const void * key1,const void * key2))67 avl_tree *avl_init_table(int (*compar)(const void *key1, const void *key2))
68 {
69 avl_tree *tree;
70
71 tree = ALLOC(avl_tree, 1);
72 tree->root = NIL(avl_node);
73 tree->compar = compar;
74 tree->num_entries = 0;
75 return tree;
76 }
77
avl_lookup(avl_tree * tree,void * key,void ** value_p)78 int avl_lookup(avl_tree *tree, void *key, void **value_p)
79 {
80 avl_node *node;
81 int (*compare)(const void*, const void *) = tree->compar, diff;
82
83 node = tree->root;
84 while (node != NIL(avl_node)) {
85 diff = COMPARE(key, node->key, compare);
86 if (diff == 0) {
87 /* got a match, give the user a 'value' only if non-null */
88 if (value_p != NIL(void *)) *value_p = node->value;
89 return 1;
90 }
91 node = (diff < 0) ? node->left : node->right;
92 }
93 return 0;
94 }
95
avl_insert(avl_tree * tree,void * key,void * value)96 int avl_insert(avl_tree *tree, void *key, void *value)
97 {
98 avl_node **node_p, *node;
99 int stack_n = 0;
100 int (*compare)(const void*, const void *) = tree->compar;
101 avl_node **stack_nodep[32];
102 int diff, status;
103
104 node_p = &tree->root;
105
106 /* walk down the tree (saving the path); stop at insertion point */
107 status = 0;
108 while ((node = *node_p) != NIL(avl_node)) {
109 stack_nodep[stack_n++] = node_p;
110 diff = COMPARE(key, node->key, compare);
111 if (diff == 0) status = 1;
112 node_p = (diff < 0) ? &node->left : &node->right;
113 }
114
115 /* insert the item and re-balance the tree */
116 *node_p = new_node(key, value);
117 do_rebalance(stack_nodep, stack_n);
118 tree->num_entries++;
119 tree->modified = 1;
120 return status;
121 }
122
avl_delete(avl_tree * tree,void ** key_p,void ** value_p)123 int avl_delete(avl_tree *tree, void **key_p, void **value_p)
124 {
125 avl_node **node_p, *node, *rightmost;
126 int stack_n = 0;
127 void *key = *key_p;
128 int (*compare)(const void*, const void*) = tree->compar, diff;
129 avl_node **stack_nodep[32];
130
131 node_p = &tree->root;
132
133 /* Walk down the tree saving the path; return if not found */
134 while ((node = *node_p) != NIL(avl_node)) {
135 diff = COMPARE(key, node->key, compare);
136 if (diff == 0) goto delete_item;
137 stack_nodep[stack_n++] = node_p;
138 node_p = (diff < 0) ? &node->left : &node->right;
139 }
140 return 0; /* not found */
141
142 /* prepare to delete node and replace it with rightmost of left tree */
143 delete_item:
144 *key_p = node->key;
145 if (value_p != nullptr) *value_p = node->value;
146 if (node->left == NIL(avl_node)) {
147 *node_p = node->right;
148 } else {
149 rightmost = find_rightmost(&node->left);
150 rightmost->left = node->left;
151 rightmost->right = node->right;
152 rightmost->height = -2; /* mark bogus height for do_rebal */
153 *node_p = rightmost;
154 stack_nodep[stack_n++] = node_p;
155 }
156 FREE(node);
157
158 /* work our way back up, re-balancing the tree */
159 do_rebalance(stack_nodep, stack_n);
160 tree->num_entries--;
161 tree->modified = 1;
162 return 1;
163 }
164
avl_record_gen_forward(avl_node * node,avl_generator * gen)165 static void avl_record_gen_forward(avl_node *node, avl_generator *gen)
166 {
167 if (node != NIL(avl_node)) {
168 avl_record_gen_forward(node->left, gen);
169 gen->nodelist[gen->count++] = node;
170 avl_record_gen_forward(node->right, gen);
171 }
172 }
173
avl_record_gen_backward(avl_node * node,avl_generator * gen)174 static void avl_record_gen_backward(avl_node *node, avl_generator *gen)
175 {
176 if (node != NIL(avl_node)) {
177 avl_record_gen_backward(node->right, gen);
178 gen->nodelist[gen->count++] = node;
179 avl_record_gen_backward(node->left, gen);
180 }
181 }
182
avl_init_gen(avl_tree * tree,int dir)183 avl_generator *avl_init_gen(avl_tree *tree, int dir)
184 {
185 avl_generator *gen;
186
187 /* what a hack */
188 gen = ALLOC(avl_generator, 1);
189 gen->tree = tree;
190 gen->nodelist = ALLOC(avl_node *, avl_count(tree));
191 gen->count = 0;
192 if (dir == AVL_FORWARD) {
193 avl_record_gen_forward(tree->root, gen);
194 } else {
195 avl_record_gen_backward(tree->root, gen);
196 }
197 gen->count = 0;
198
199 /* catch any attempt to modify the tree while we generate */
200 tree->modified = 0;
201 return gen;
202 }
203
avl_gen(avl_generator * gen,void ** key_p,void ** value_p)204 int avl_gen(avl_generator *gen, void **key_p, void **value_p)
205 {
206 avl_node *node;
207
208 if (gen->count == gen->tree->num_entries) {
209 return 0;
210 } else {
211 node = gen->nodelist[gen->count++];
212 if (key_p != NIL(void *)) *key_p = node->key;
213 if (value_p != NIL(void *)) *value_p = node->value;
214 return 1;
215 }
216 }
217
avl_free_gen(avl_generator * gen)218 void avl_free_gen(avl_generator *gen)
219 {
220 FREE(gen->nodelist);
221 FREE(gen);
222 }
223
find_rightmost(avl_node ** node_p)224 static avl_node *find_rightmost(avl_node **node_p)
225 {
226 avl_node *node;
227 int stack_n = 0;
228 avl_node **stack_nodep[32];
229
230 node = *node_p;
231 while (node->right != NIL(avl_node)) {
232 stack_nodep[stack_n++] = node_p;
233 node_p = &node->right;
234 node = *node_p;
235 }
236 *node_p = node->left;
237
238 do_rebalance(stack_nodep, stack_n);
239 return node;
240 }
241
do_rebalance(avl_node *** stack_nodep,int stack_n)242 static void do_rebalance(avl_node ***stack_nodep, int stack_n)
243 {
244 avl_node **node_p, *node;
245 int hl, hr;
246 int height;
247
248 /* work our way back up, re-balancing the tree */
249 while (--stack_n >= 0) {
250 node_p = stack_nodep[stack_n];
251 node = *node_p;
252 hl = HEIGHT(node->left); /* watch for NIL */
253 hr = HEIGHT(node->right); /* watch for NIL */
254 if ((hr - hl) < -1) {
255 rotate_right(node_p);
256 } else if ((hr - hl) > 1) {
257 rotate_left(node_p);
258 } else {
259 height = XRNMAX(hl, hr) + 1;
260 if (height == node->height) break;
261 node->height = height;
262 }
263 }
264 }
265
rotate_left(avl_node ** node_p)266 static void rotate_left(avl_node **node_p)
267 {
268 avl_node *old_root = *node_p, *new_root, *new_right;
269
270 if (BALANCE(old_root->right) >= 0) {
271 *node_p = new_root = old_root->right;
272 old_root->right = new_root->left;
273 new_root->left = old_root;
274 } else {
275 new_right = old_root->right;
276 *node_p = new_root = new_right->left;
277 old_root->right = new_root->left;
278 new_right->left = new_root->right;
279 new_root->right = new_right;
280 new_root->left = old_root;
281 compute_height(new_right);
282 }
283 compute_height(old_root);
284 compute_height(new_root);
285 }
286
rotate_right(avl_node ** node_p)287 static void rotate_right(avl_node **node_p)
288 {
289 avl_node *old_root = *node_p, *new_root, *new_left;
290
291 if (BALANCE(old_root->left) <= 0) {
292 *node_p = new_root = old_root->left;
293 old_root->left = new_root->right;
294 new_root->right = old_root;
295 } else {
296 new_left = old_root->left;
297 *node_p = new_root = new_left->right;
298 old_root->left = new_root->right;
299 new_left->right = new_root->left;
300 new_root->left = new_left;
301 new_root->right = old_root;
302 compute_height(new_left);
303 }
304 compute_height(old_root);
305 compute_height(new_root);
306 }
307
308
avl_extremum(avl_tree * tree,int side,void ** value_p)309 int avl_extremum(avl_tree *tree, int side, void **value_p)
310 {
311 avl_node *node;
312
313 node = tree->root;
314 if (node == NIL(avl_node)) return 0;
315
316 if (side == AVL_MOST_LEFT)
317 while (node->left != NIL(avl_node)) node = node->left;
318 else
319 while (node->right != NIL(avl_node)) node = node->right;
320
321 if (value_p != NIL(void *)) {
322 *value_p = node->value;
323 return 1;
324 }
325 return 0;
326 }
327
free_entry(avl_node * node,void (* key_free)(void * key),void (* value_free)(void * value))328 static void free_entry(avl_node *node, void (*key_free)(void *key), void (*value_free)(void *value))
329 {
330 if (node != NIL(avl_node)) {
331 free_entry(node->left, key_free, value_free);
332 free_entry(node->right, key_free, value_free);
333 if (key_free != nullptr) (*key_free)(node->key);
334 if (value_free != nullptr) (*value_free)(node->value);
335 FREE(node);
336 }
337 }
338
avl_free_table(avl_tree * tree,void (* key_free)(void * key),void (* value_free)(void * value))339 void avl_free_table(avl_tree *tree, void (*key_free)(void *key), void (*value_free)(void *value))
340 {
341 free_entry(tree->root, key_free, value_free);
342 FREE(tree);
343 }
344
avl_count(avl_tree * tree)345 int avl_count(avl_tree *tree)
346 {
347 return tree->num_entries;
348 }
349
new_node(void * key,void * value)350 static avl_node *new_node(void *key, void *value)
351 {
352 avl_node *newn;
353
354 newn = ALLOC(avl_node, 1);
355 newn->key = key;
356 newn->value = value;
357 newn->height = 0;
358 newn->left = newn->right = NIL(avl_node);
359 return newn;
360 }
361
avl_numcmp(const void * x,const void * y)362 int avl_numcmp(const void *x, const void*y)
363 {
364 return (intptr_t) x - (intptr_t) y;
365 }
366
avl_check_tree(avl_tree * tree)367 int avl_check_tree(avl_tree *tree)
368 {
369 int error = 0;
370 (void) do_check_tree(tree->root, tree->compar, &error);
371 return error;
372 }
373
do_check_tree(avl_node * node,int (* compar)(const void * key1,const void * key2),int * error)374 static int do_check_tree(avl_node *node,
375 int (*compar)(const void *key1, const void *key2), int *error)
376 {
377 int l_height, r_height, comp_height, bal;
378
379 if (node == NIL(avl_node)) {
380 return -1;
381 }
382
383 r_height = do_check_tree(node->right, compar, error);
384 l_height = do_check_tree(node->left, compar, error);
385
386 comp_height = XRNMAX(l_height, r_height) + 1;
387 bal = r_height - l_height;
388
389 if (comp_height != node->height) {
390 (void) printf("Bad height for %p: computed=%d stored=%d\n",
391 (void*)node, comp_height, node->height);
392 ++*error;
393 }
394
395 if (bal > 1 || bal < -1) {
396 (void) printf("Out of balance at node %p, balance = %d\n",
397 (void*)node, bal);
398 ++*error;
399 }
400
401 if (node->left != NIL(avl_node) &&
402 (*compar)(node->left->key, node->key) > 0) {
403 (void) printf("Bad ordering between %p and %p",
404 (void*)node, (void*)node->left);
405 ++*error;
406 }
407
408 if (node->right != NIL(avl_node) &&
409 (*compar)(node->key, node->right->key) > 0) {
410 (void) printf("Bad ordering between %p and %p",
411 (void*)node, (void*)node->right);
412 ++*error;
413 }
414
415 return comp_height;
416 }
417