1 /*
2
3 AVL tree implementation.
4
5 Copyright (C) 2008 Olaf Klein, o.b.klein@gpsbabel.org
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA
20
21 */
22
23 #include "avltree.h"
24
25 #define MYNAME "avltree"
26
27 #ifdef DEBUG_MEM
28 # define AVLTREE_MAGIC 0x41564c53
29 /* ((((((0L | 'A') << 8) | 'V') << 8) | 'L') << 8) | 'T'; */
30 #endif
31
32 #ifdef MEM_DEBUG
33 void avltree_check_handle(const void* tree);
34 #endif
35 static void avltree_node_free(const avltree_t* tree, avlnode_t* node);
36 static int avltree_node_height(avlnode_t* node);
37 static int avltree_insert_node(avltree_t* tree, avlnode_t** root, const char* key, const void* data);
38 static int avltree_delete_node(avltree_t* tree, const char* key, avlnode_t** root, int* changed);
39 static avlnode_t* avltree_right_rotation(avlnode_t* A);
40 static avlnode_t* avltree_left_rotation(avlnode_t* A);
41 static avlnode_t* avltree_left_right_rotation(avlnode_t* A);
42 static avlnode_t* avltree_right_left_rotation(avlnode_t* A);
43 static avlnode_t* avltree_dupe_node(const avltree_t* tree, const avlnode_t* node);
44 static int avltree_strcmpr(const char* s1, const char* s2);
45 static int avltree_case_ignore_strcmpr(const char* s1, const char* s2);
46 static avlnode_t* avltree_find_next(const avltree_t* tree, avlnode_t* node, const char* key);
47 static void avltree_save_key(avltree_t* tree, const char* key);
48
49
50 #ifdef MEM_DEBUG
51 # define AVLTREE_CHECK_HANDLE(a) avltree_valid_tree(a)
52 #else
53 # define AVLTREE_CHECK_HANDLE(a)
54 #endif
55
56 #define AVLTREE_INVALID_BALANCE "%s/%s.%d: Invalid balance %d at node \"%s\"!\n", \
57 tree->module, MYNAME, __LINE__, node->balance, node->key
58
59
60 /* Allocate and initialize an AVL Tree */
61
62 avltree_t*
avltree_init(const int options,const char * module)63 avltree_init(const int options, const char* module)
64 {
65 avltree_t* tree;
66
67 if ((module == NULL) || (*module == '\0')) {
68 fatal(MYNAME ": 'avltree_init' should be called with a valid module name!\n");
69 }
70
71 tree = (avltree_t*) xcalloc(1, sizeof(*tree));
72 tree->options = options;
73 tree->module = module;
74
75 if (options & AVLTREE_NON_CASE_SENSITIVE) {
76 if (options & AVLTREE_DESCENDING) {
77 tree->compare = avltree_case_ignore_strcmpr; /* descending, non-case-sensitive */
78 } else {
79 tree->compare = case_ignore_strcmp; /* ascending, non-case-sensitive */
80 }
81 } else {
82 if (options & AVLTREE_DESCENDING) {
83 tree->compare = avltree_strcmpr; /* descending, case-sensitive */
84 } else {
85 tree->compare = strcmp; /* ascending, case-sensitive */
86 }
87 }
88
89 return tree;
90 }
91
92 /* Delete all items of tree [tree] */
93
94 int
avltree_clear(avltree_t * tree)95 avltree_clear(avltree_t* tree)
96 {
97 int res;
98
99 AVLTREE_CHECK_HANDLE(tree);
100
101 res = tree->count;
102 avltree_save_key(tree, NULL);
103 if (res) {
104 avltree_node_free(tree, tree->root);
105 /* avltree_node_free doesn't touch 'count' */
106 tree->count = 0;
107 tree->root = NULL;
108 }
109 return res;
110 }
111
112 /* Destroy an AVL Tree */
113
114 void
avltree_done(avltree_t * tree)115 avltree_done(avltree_t* tree)
116 {
117 avltree_clear(tree);
118 xfree(tree);
119 }
120
121
122 /* Get number of items in tree */
123
124 int
avltree_count(const avltree_t * tree)125 avltree_count(const avltree_t* tree)
126 {
127 AVLTREE_CHECK_HANDLE(tree);
128
129 return tree->count;
130 }
131
132
133 /* Delete item with key [key] */
134
135 int
avltree_delete(avltree_t * tree,const char * key)136 avltree_delete(avltree_t* tree, const char* key)
137 {
138 int changed = 0;
139
140 AVLTREE_CHECK_HANDLE(tree);
141
142 if (key == NULL)
143 fatal("%s/%s.%d: Attempt to delete a NULL-pointer!\n",
144 tree->module, MYNAME, __LINE__);
145
146 return avltree_delete_node(tree, key, &tree->root, &changed);
147 }
148
149
150 /* Duplicate an existing tree */
151
152 avltree_t*
avltree_dupe(const avltree_t * tree,const char * module)153 avltree_dupe(const avltree_t* tree, const char* module)
154 {
155 avltree_t* dupe;
156
157 AVLTREE_CHECK_HANDLE(tree);
158
159 dupe = avltree_init(tree->options, module);
160 if ((dupe->count = tree->count)) {
161 dupe->root = avltree_dupe_node(tree, tree->root);
162 }
163
164 return dupe;
165 }
166
167
168 /* Find key [key] in tree */
169
170 int
avltree_find(const avltree_t * tree,const char * key,const void ** data)171 avltree_find(const avltree_t* tree, const char* key, const void** data)
172 {
173 avlnode_t* node;
174
175 AVLTREE_CHECK_HANDLE(tree);
176
177 node = tree->root;
178 while (node) {
179 int compare = tree->compare(key, node->key);
180
181 if (compare < 0) {
182 node = node->left;
183 } else if (compare > 0) {
184 node = node->right;
185 } else {
186 if (data) {
187 (*data) = node->data;
188 }
189 break;
190 }
191 }
192
193 return (node) ? 1 : 0;
194 }
195
196
197 /* Get the first (the MIN-) entry of the tree */
198
199 const char*
avltree_first(const avltree_t * tree,const void ** data)200 avltree_first(const avltree_t* tree, const void** data)
201 {
202 avlnode_t* node;
203
204 AVLTREE_CHECK_HANDLE(tree);
205
206 node = tree->root;
207 if (! node) {
208 return NULL;
209 }
210
211 while (node->left) {
212 node = node->left;
213 }
214 avltree_save_key((avltree_t*)tree, node->key);
215 if (data) {
216 (*data) = node->data;
217 }
218
219 return tree->key;
220 }
221
222
223 /* Get the current height of the tree */
224
225 int
avltree_height(const avltree_t * tree)226 avltree_height(const avltree_t* tree)
227 {
228 AVLTREE_CHECK_HANDLE(tree);
229
230 if (tree->count) {
231 return avltree_node_height(tree->root);
232 } else {
233 return 0;
234 }
235 }
236
237
238 /* Insert key [key] and [data] into tree */
239
240 int
avltree_insert(avltree_t * tree,const char * key,const void * data)241 avltree_insert(avltree_t* tree, const char* key, const void* data)
242 {
243 int count;
244
245 AVLTREE_CHECK_HANDLE(tree);
246
247 if (key == NULL)
248 fatal("%s/%s.%d: Attempt to insert a NULL-pointer!\n",
249 tree->module, MYNAME, __LINE__);
250
251 count = tree->count;
252 avltree_insert_node(tree, &tree->root, key, data);
253 return (count != tree->count) ? 1 : 0;
254 }
255
256
257 /* Get the next (the entry above [key]) */
258
259 const char*
avltree_next(const avltree_t * tree,const char * key,const void ** data)260 avltree_next(const avltree_t* tree, const char* key, const void** data)
261 {
262 avlnode_t* node;
263
264 AVLTREE_CHECK_HANDLE(tree);
265
266 if (key == NULL)
267 fatal("%s/%s.%d: Attempt to look for a NULL-pointer!\n",
268 tree->module, MYNAME, __LINE__);
269
270 node = tree->root;
271 if (! node) {
272 return NULL;
273 }
274
275 if ((node = avltree_find_next(tree, node, key))) {
276 avltree_save_key((avltree_t*)tree, node->key);
277 if (data) {
278 (*data) = node->data;
279 }
280 } else {
281 avltree_save_key((avltree_t*)tree, NULL);
282 }
283
284 return tree->key;
285 }
286
287
288 /* ------------------------------ static stuff ------------------------------ */
289
290
291 #ifdef MEM_DEBUG
292
293 void
avltree_check_handle(const avltree_t * tree)294 avltree_check_handle(const avltree_t* tree)
295 {
296 if (! tree) {
297 fatal(MYNAME ": Invalid (NULL-) pointer!\n");
298 }
299 if (tree->magic != AVLTREE_MAGIC) {
300 fatal(MYNAME ": Invalid (no AVL tree object) pointer!\n");
301 }
302 }
303
304 #endif
305
306
307 static void
avltree_node_free(const avltree_t * tree,avlnode_t * node)308 avltree_node_free(const avltree_t* tree, avlnode_t* node)
309 {
310 if ((!(tree->options & AVLTREE_STATIC_KEYS)) && node->key) {
311 xfree((char*)node->key);
312 }
313 if (node->left) {
314 avltree_node_free(tree, node->left);
315 }
316 if (node->right) {
317 avltree_node_free(tree, node->right);
318 }
319 xfree(node);
320 }
321
322
323 static int
avltree_node_height(avlnode_t * node)324 avltree_node_height(avlnode_t* node)
325 {
326 int height = 1;
327
328 if (node->balance < 0) {
329 height += avltree_node_height(node->left);
330 } else if (node->right) {
331 height += avltree_node_height(node->right);
332 }
333
334 return height;
335 }
336
337
338 static avlnode_t*
avltree_right_rotation(avlnode_t * A)339 avltree_right_rotation(avlnode_t* A)
340 {
341 /*
342 > A B
343 > / \ / \
344 > \ / \
345 > B -->> A .
346 > / \ / \ / \
347 > \
348 > .
349 > / \
350 */
351 avlnode_t* B;
352
353 B = A->right;
354 A->right = B->left;
355 B->left = A;
356
357 /* update balance of all touched nodes */
358 /* reference: <http://cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html> */
359
360 B->balance--;
361 A->balance = -(B->balance);
362
363 return B;
364 }
365
366
367 static avlnode_t*
avltree_left_rotation(avlnode_t * A)368 avltree_left_rotation(avlnode_t* A)
369 {
370 /*
371 > A B
372 > / \ / \
373 > / / \
374 > B -->> . A
375 > / \ / \ / \
376 > /
377 > .
378 > / \
379 */
380 avlnode_t* B;
381
382 B = A->left;
383 A->left = B->right;
384 B->right = A;
385
386 /* update balance of all touched nodes */
387 /* reference: <http://cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html> */
388
389 B->balance++;
390 A->balance = -(B->balance);
391
392 return B;
393 }
394
395
396 static avlnode_t*
avltree_left_right_rotation(avlnode_t * A)397 avltree_left_right_rotation(avlnode_t* A)
398 {
399 /*
400 > A C
401 > / \ / \
402 > / / \
403 > B -->> B A
404 > / \ / \ / \
405 > \
406 > C
407 */
408 avlnode_t* B, *C;
409
410 B = A->left;
411 C = B->right;
412 A->left = C->right;
413 B->right = C->left;
414 C->right = A;
415 C->left = B;
416
417 /* update balance of all touched nodes */
418 /* reference: <http://cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html> */
419
420 A->balance = (C->balance > 0) ? 0 : -(C->balance);
421 B->balance = (C->balance < 0) ? 0 : -(C->balance);
422 C->balance = 0;
423
424 return C;
425 }
426
427
428 static avlnode_t*
avltree_right_left_rotation(avlnode_t * A)429 avltree_right_left_rotation(avlnode_t* A)
430 {
431 /*
432 > A C
433 > / \ / \
434 > \ / \
435 > B -->> B A
436 > / \ / \ / \
437 > /
438 > C
439 */
440 avlnode_t* B, *C;
441
442 B = A->right;
443 C = B->left;
444 A->right = C->left;
445 B->left = C->right;
446 C->left = A;
447 C->right = B;
448
449 /* update balance of all touched nodes */
450 /* reference: <http://cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html> */
451
452 A->balance = (C->balance < 0) ? 0 : -(C->balance);
453 B->balance = (C->balance > 0) ? 0 : -(C->balance);
454 C->balance = 0;
455
456 return C;
457 }
458
459
460 static int
avltree_insert_node(avltree_t * tree,avlnode_t ** root,const char * key,const void * data)461 avltree_insert_node(avltree_t* tree, avlnode_t** root, const char* key, const void* data)
462 {
463 int changed = 0;
464 int compare;
465 avlnode_t* node = (*root);
466
467 if (node == NULL) {
468 (*root) = node = (avlnode_t*) xcalloc(1, sizeof(*node));
469 if (tree->options & AVLTREE_STATIC_KEYS) {
470 node->key = key;
471 } else {
472 node->key = xstrdup(key);
473 }
474 node->data = data;
475 tree->count++;
476 return 1; /* anyway, our tree has been changed */
477 }
478
479 compare = tree->compare(key, node->key);
480
481 if (compare < 0) {
482 if (avltree_insert_node(tree, &node->left, key, data)) {
483 changed = (--node->balance != 0);
484 switch (node->balance) {
485 case -2:
486 if (node->left->balance < 0) {
487 node = avltree_left_rotation(node);
488 } else {
489 node = avltree_left_right_rotation(node);
490 }
491 (*root) = node;
492 case 0:
493 changed = 0;
494 case -1:
495 break;
496 default:
497 /* should be impossible :-) */
498 fatal(AVLTREE_INVALID_BALANCE);
499 }
500 } else {
501 changed = 0;
502 }
503 } else if (compare > 0) {
504 if (avltree_insert_node(tree, &node->right, key, data)) {
505 changed = (++node->balance != 0);
506 switch (node->balance) {
507 case +2:
508 if (node->right->balance > 0) {
509 node = avltree_right_rotation(node);
510 } else {
511 node = avltree_right_left_rotation(node);
512 }
513 (*root) = node;
514 case 0:
515 changed = 0;
516 case +1:
517 break;
518 default:
519 /* should be impossible :-) */
520 fatal(AVLTREE_INVALID_BALANCE);
521 }
522 } else {
523 changed = 0;
524 }
525 } else {
526 if (tree->options & AVLTREE_PARANOIAC)
527 fatal("%s/%s.%d: Duplicate keys are not allowed (\"%s\")!\n",
528 tree->module, MYNAME, __LINE__, key);
529 changed = 0;
530 }
531
532 return changed;
533 }
534
535
536
537 static int
avltree_delete_node(avltree_t * tree,const char * key,avlnode_t ** root,int * changed)538 avltree_delete_node(avltree_t* tree, const char* key, avlnode_t** root, int* changed)
539 {
540 avlnode_t* node = (*root);
541 int deleted = 0;
542 int compare;
543
544 if (node == NULL) {
545 if (tree->options & AVLTREE_PARANOIAC)
546 fatal("%s/%s.%d: Key to delete \"%s\" not found!\n",
547 tree->module, MYNAME, __LINE__, key);
548 return 0;
549 }
550
551 compare = tree->compare(key, node->key);
552
553 if (compare < 0) {
554 deleted = avltree_delete_node(tree, key, &node->left, changed);
555 if (*changed) {
556 node->balance++; /* shift weight to right */
557 switch (node->balance) {
558 case +1:
559 (*changed) = 0; /* stop rebalancing */
560 case 0:
561 break;
562 case +2:
563 if (node->right->balance >= 0) {
564 node = avltree_right_rotation(node);
565 } else {
566 node = avltree_right_left_rotation(node);
567 }
568 (*root) = node;
569 if (node->balance == -1) {
570 (*changed) = 0;
571 }
572 break;
573 default:
574 /* should be impossible :-) */
575 fatal(AVLTREE_INVALID_BALANCE);
576 }
577 }
578 } else if (compare > 0) {
579 deleted = avltree_delete_node(tree, key, &node->right, changed);
580 if (*changed) {
581 node->balance--; /* shift weight to left */
582 switch (node->balance) {
583 case -1:
584 (*changed) = 0; /* stop rebalancing */
585 case 0:
586 break;
587 case -2:
588 if (node->left->balance <= 0) {
589 node = avltree_left_rotation(node);
590 } else {
591 node = avltree_left_right_rotation(node);
592 }
593 (*root) = node;
594 if (node->balance == +1) {
595 (*changed) = 0;
596 }
597 break;
598 default:
599 /* should be impossible :-) */
600 fatal(AVLTREE_INVALID_BALANCE);
601 }
602 }
603 } else {
604 if (node->left) {
605 if (node->right) {
606 const char* temp_key;
607 const void* temp_data;
608 avlnode_t* succ = node->right;
609
610 while (succ->left) {
611 succ = succ->left; /* find successor */
612 }
613
614 temp_key = succ->key; /* swap contents */
615 temp_data = succ->data;
616 succ->key = node->key;
617 succ->data = node->data;
618 node->key = temp_key;
619 node->data = temp_data;
620
621 deleted = avltree_delete_node(tree, key, &node->right, changed);
622
623 if (*changed) {
624 node->balance--; /* shift weight to left */
625 switch (node->balance) {
626 case -1:
627 (*changed) = 0; /* stop rebalancing */
628 case 0:
629 break;
630 case -2:
631 if (node->left->balance <= 0) {
632 node = avltree_left_rotation(node);
633 } else {
634 node = avltree_left_right_rotation(node);
635 }
636 (*root) = node;
637 if (node->balance == +1) {
638 (*changed) = 0;
639 }
640 break;
641 default:
642 /* should be impossible :-) */
643 fatal(AVLTREE_INVALID_BALANCE);
644 }
645 }
646 return deleted;
647 } else { /* only left branch */
648 (*root) = node->left;
649 node->left = NULL;
650 }
651 } else if (node->right) { /* only right branch */
652 (*root) = node->right;
653 node->right = NULL;
654 } else { /* only a simple leaf */
655 (*root) = NULL;
656 }
657
658 avltree_node_free(tree, node);
659 tree->count--;
660 (*changed) = 1;
661 deleted = 1;
662 }
663
664 return deleted;
665 }
666
667
668 static avlnode_t*
avltree_dupe_node(const avltree_t * tree,const avlnode_t * node)669 avltree_dupe_node(const avltree_t* tree, const avlnode_t* node)
670 {
671 avlnode_t* res = (avlnode_t*) xcalloc(1, sizeof(*res));
672
673 if (tree->options & AVLTREE_STATIC_KEYS) {
674 res->key = node->key;
675 } else {
676 res->key = xstrdup(node->key);
677 }
678
679 res->balance = node->balance;
680 if (node->left) {
681 res->left = avltree_dupe_node(tree, node->left);
682 }
683 if (node->right) {
684 res->right = avltree_dupe_node(tree, node->right);
685 }
686
687 return res;
688 }
689
690
691 static int
avltree_strcmpr(const char * s1,const char * s2)692 avltree_strcmpr(const char* s1, const char* s2)
693 {
694 return -(strcmp(s1, s2));
695 }
696
697
698 static int
avltree_case_ignore_strcmpr(const char * s1,const char * s2)699 avltree_case_ignore_strcmpr(const char* s1, const char* s2)
700 {
701 return -(case_ignore_strcmp(s1, s2));
702 }
703
704
705 static avlnode_t*
avltree_find_next(const avltree_t * tree,avlnode_t * node,const char * key)706 avltree_find_next(const avltree_t* tree, avlnode_t* node, const char* key)
707 {
708 avlnode_t* prev = NULL;
709
710 if (key == NULL) {
711 if ((node = tree->root)) {
712 while (node->left) {
713 node = node->left;
714 }
715 }
716 return node;
717 }
718
719 while (node) {
720 int compare = tree->compare(key, node->key);
721
722 if (compare < 0) {
723 prev = node;
724 node = node->left;
725 } else if (compare > 0) {
726 node = node->right;
727 } else {
728 if ((node = node->right))
729 while (node->left) {
730 node = node->left;
731 }
732 else {
733 node = prev;
734 }
735 return node;
736 }
737 }
738 /* The previous node was deleted and we could not find it. */
739 return prev;
740 }
741
742
743 /*
744 Save [key] for a possible delete before next op. Now we have no problem with:
745
746 curr = NULL;
747 while ((curr = avtree_next(tree, curr, NULL))) {
748 avltree_delete(tree, curr);
749 }
750 */
751 static void
avltree_save_key(avltree_t * tree,const char * key)752 avltree_save_key(avltree_t* tree, const char* key)
753 {
754 if (tree->options & AVLTREE_STATIC_KEYS) {
755 tree->key = key;
756 } else {
757 if (key == NULL) {
758 if (tree->key_sz) {
759 xfree((char*)tree->key);
760 tree->key_sz = 0;
761 }
762 tree->key = NULL;
763 } else {
764 int n, n8;
765
766 n = strlen(key) + 1;
767 n8 = ((n + 7) / 8) * 8;
768
769 if (n8 > tree->key_sz) {
770 if (tree->key_sz == 0) {
771 tree->key = (char*) xmalloc(n8);
772 } else {
773 tree->key = (char*) xrealloc((char*)tree->key, n8);
774 }
775 tree->key_sz = n8;
776 }
777 strncpy((char*)tree->key, key, n);
778 }
779 }
780 }
781