added a GNode test.
[platform/upstream/glib.git] / gtree.c
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19 #include "glib.h"
20
21
22 typedef struct _GRealTree  GRealTree;
23 typedef struct _GTreeNode  GTreeNode;
24
25 struct _GRealTree
26 {
27   GTreeNode *root;
28   GCompareFunc key_compare;
29 };
30
31 struct _GTreeNode
32 {
33   gint balance;      /* height (left) - height (right) */
34   GTreeNode *left;   /* left subtree */
35   GTreeNode *right;  /* right subtree */
36   gpointer key;      /* key for this node */
37   gpointer value;    /* value stored at this node */
38 };
39
40
41 static GTreeNode* g_tree_node_new                   (gpointer        key,
42                                                      gpointer        value);
43 static void       g_tree_node_destroy               (GTreeNode      *node);
44 static GTreeNode* g_tree_node_insert                (GTreeNode      *node,
45                                                      GCompareFunc    compare,
46                                                      gpointer        key,
47                                                      gpointer        value,
48                                                      gint           *inserted);
49 static GTreeNode* g_tree_node_remove                (GTreeNode      *node,
50                                                      GCompareFunc    compare,
51                                                      gpointer        key);
52 static GTreeNode* g_tree_node_balance               (GTreeNode      *node);
53 static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode      *node,
54                                                      GTreeNode     **leftmost);
55 static GTreeNode* g_tree_node_restore_left_balance  (GTreeNode      *node,
56                                                      gint            old_balance);
57 static GTreeNode* g_tree_node_restore_right_balance (GTreeNode      *node,
58                                                      gint            old_balance);
59 static gpointer   g_tree_node_lookup                (GTreeNode      *node,
60                                                      GCompareFunc    compare,
61                                                      gpointer        key);
62 static gint       g_tree_node_count                 (GTreeNode      *node);
63 static gint       g_tree_node_pre_order             (GTreeNode      *node,
64                                                      GTraverseFunc   traverse_func,
65                                                      gpointer        data);
66 static gint       g_tree_node_in_order              (GTreeNode      *node,
67                                                      GTraverseFunc   traverse_func,
68                                                      gpointer        data);
69 static gint       g_tree_node_post_order            (GTreeNode      *node,
70                                                      GTraverseFunc   traverse_func,
71                                                      gpointer        data);
72 static gpointer   g_tree_node_search                (GTreeNode      *node,
73                                                      GSearchFunc     search_func,
74                                                      gpointer        data);
75 static gint       g_tree_node_height                (GTreeNode      *node);
76 static GTreeNode* g_tree_node_rotate_left           (GTreeNode      *node);
77 static GTreeNode* g_tree_node_rotate_right          (GTreeNode      *node);
78 static void       g_tree_node_check                 (GTreeNode      *node);
79
80
81 static GMemChunk *node_mem_chunk = NULL;
82 static GSList *node_free_list = NULL;
83
84
85 GTree*
86 g_tree_new (GCompareFunc key_compare_func)
87 {
88   GRealTree *rtree;
89
90   rtree = g_new (GRealTree, 1);
91   rtree->root = NULL;
92   rtree->key_compare = key_compare_func;
93
94   return (GTree*) rtree;
95 }
96
97 void
98 g_tree_destroy (GTree *tree)
99 {
100   GRealTree *rtree;
101
102   g_return_if_fail (tree != NULL);
103
104   rtree = (GRealTree*) tree;
105
106   g_tree_node_destroy (rtree->root);
107   g_free (rtree);
108 }
109
110 void
111 g_tree_insert (GTree    *tree,
112                gpointer  key,
113                gpointer  value)
114 {
115   GRealTree *rtree;
116   gint inserted;
117
118   g_return_if_fail (tree != NULL);
119
120   rtree = (GRealTree*) tree;
121
122   inserted = FALSE;
123   rtree->root = g_tree_node_insert (rtree->root, rtree->key_compare,
124                                     key, value, &inserted);
125 }
126
127 void
128 g_tree_remove (GTree    *tree,
129                gpointer  key)
130 {
131   GRealTree *rtree;
132
133   g_return_if_fail (tree != NULL);
134
135   rtree = (GRealTree*) tree;
136
137   rtree->root = g_tree_node_remove (rtree->root, rtree->key_compare, key);
138 }
139
140 gpointer
141 g_tree_lookup (GTree    *tree,
142                gpointer  key)
143 {
144   GRealTree *rtree;
145
146   g_return_val_if_fail (tree != NULL, NULL);
147
148   rtree = (GRealTree*) tree;
149
150   return g_tree_node_lookup (rtree->root, rtree->key_compare, key);
151 }
152
153 void
154 g_tree_traverse (GTree         *tree,
155                  GTraverseFunc  traverse_func,
156                  GTraverseType  traverse_type,
157                  gpointer       data)
158 {
159   GRealTree *rtree;
160
161   g_return_if_fail (tree != NULL);
162
163   rtree = (GRealTree*) tree;
164
165   g_return_if_fail (rtree->root != NULL);
166
167   switch (traverse_type)
168     {
169     case G_PRE_ORDER:
170       g_tree_node_pre_order (rtree->root, traverse_func, data);
171       break;
172
173     case G_IN_ORDER:
174       g_tree_node_in_order (rtree->root, traverse_func, data);
175       break;
176
177     case G_POST_ORDER:
178       g_tree_node_post_order (rtree->root, traverse_func, data);
179       break;
180     
181     case G_LEVEL_ORDER:
182       g_warning ("g_tree_traverse(): traverse type G_LEVEL_ORDER isn't implemented.");
183       break;
184     }
185 }
186
187 gpointer
188 g_tree_search (GTree       *tree,
189                GSearchFunc  search_func,
190                gpointer     data)
191 {
192   GRealTree *rtree;
193
194   g_return_val_if_fail (tree != NULL, NULL);
195
196   rtree = (GRealTree*) tree;
197
198   if (rtree->root)
199     return g_tree_node_search (rtree->root, search_func, data);
200   return NULL;
201 }
202
203 gint
204 g_tree_height (GTree *tree)
205 {
206   GRealTree *rtree;
207
208   g_return_val_if_fail (tree != NULL, 0);
209
210   rtree = (GRealTree*) tree;
211
212   if (rtree->root)
213     return g_tree_node_height (rtree->root);
214   return 0;
215 }
216
217 gint
218 g_tree_nnodes (GTree *tree)
219 {
220   GRealTree *rtree;
221
222   g_return_val_if_fail (tree != NULL, 0);
223
224   rtree = (GRealTree*) tree;
225
226   if (rtree->root)
227     return g_tree_node_count (rtree->root);
228   return 0;
229 }
230
231
232 static GTreeNode*
233 g_tree_node_new (gpointer key,
234                  gpointer value)
235 {
236   GTreeNode *node;
237   GSList *tmp_list;
238
239   if (node_free_list)
240     {
241       tmp_list = node_free_list;
242       node_free_list = node_free_list->next;
243
244       node = tmp_list->data;
245
246       {
247         GListAllocator *tmp_allocator = g_list_set_allocator (NULL);
248         g_slist_free_1 (tmp_list);
249         g_list_set_allocator (tmp_allocator);
250       }
251     }
252   else
253     {
254       if (!node_mem_chunk)
255         node_mem_chunk = g_mem_chunk_new ("tree node mem chunk", sizeof (GTreeNode), 1024, G_ALLOC_ONLY);
256
257       node = g_chunk_new (GTreeNode, node_mem_chunk);
258     }
259
260   node->balance = 0;
261   node->left = NULL;
262   node->right = NULL;
263   node->key = key;
264   node->value = value;
265
266   return node;
267 }
268
269 static void
270 g_tree_node_destroy (GTreeNode *node)
271 {
272   if (node)
273     {
274       node_free_list = g_slist_prepend (node_free_list, node);
275       g_tree_node_destroy (node->right);
276       g_tree_node_destroy (node->left);
277     }
278 }
279
280 static GTreeNode*
281 g_tree_node_insert (GTreeNode    *node,
282                     GCompareFunc  compare,
283                     gpointer      key,
284                     gpointer      value,
285                     gint         *inserted)
286 {
287   gint old_balance;
288   gint cmp;
289
290   if (!node)
291     {
292       *inserted = TRUE;
293       return g_tree_node_new (key, value);
294     }
295
296   cmp = (* compare) (key, node->key);
297   if (cmp == 0)
298     {
299       *inserted = FALSE;
300       node->value = value;
301       return node;
302     }
303
304   if (cmp < 0)
305     {
306       if (node->left)
307         {
308           old_balance = node->left->balance;
309           node->left = g_tree_node_insert (node->left, compare, key, value, inserted);
310
311           if ((old_balance != node->left->balance) && node->left->balance)
312             node->balance -= 1;
313         }
314       else
315         {
316           *inserted = TRUE;
317           node->left = g_tree_node_new (key, value);
318           node->balance -= 1;
319         }
320     }
321   else if (cmp > 0)
322     {
323       if (node->right)
324         {
325           old_balance = node->right->balance;
326           node->right = g_tree_node_insert (node->right, compare, key, value, inserted);
327
328           if ((old_balance != node->right->balance) && node->right->balance)
329             node->balance += 1;
330         }
331       else
332         {
333           *inserted = TRUE;
334           node->right = g_tree_node_new (key, value);
335           node->balance += 1;
336         }
337     }
338
339   if (*inserted)
340     {
341       if ((node->balance < -1) || (node->balance > 1))
342         node = g_tree_node_balance (node);
343     }
344
345   return node;
346 }
347
348 static GTreeNode*
349 g_tree_node_remove (GTreeNode    *node,
350                     GCompareFunc  compare,
351                     gpointer      key)
352 {
353   GTreeNode *garbage;
354   GTreeNode *new_root;
355   gint old_balance;
356   gint cmp;
357
358   if (!node)
359     return NULL;
360
361   cmp = (* compare) (key, node->key);
362   if (cmp == 0)
363     {
364       garbage = node;
365
366       if (!node->right)
367         {
368           node = node->left;
369         }
370       else
371         {
372           old_balance = node->right->balance;
373           node->right = g_tree_node_remove_leftmost (node->right, &new_root);
374           new_root->left = node->left;
375           new_root->right = node->right;
376           new_root->balance = node->balance;
377           node = g_tree_node_restore_right_balance (new_root, old_balance);
378         }
379
380       node_free_list = g_slist_prepend (node_free_list, garbage);
381     }
382   else if (cmp < 0)
383     {
384       if (node->left)
385         {
386           old_balance = node->left->balance;
387           node->left = g_tree_node_remove (node->left, compare, key);
388           node = g_tree_node_restore_left_balance (node, old_balance);
389         }
390     }
391   else if (cmp > 0)
392     {
393       if (node->right)
394         {
395           old_balance = node->right->balance;
396           node->right = g_tree_node_remove (node->right, compare, key);
397           node = g_tree_node_restore_right_balance (node, old_balance);
398         }
399     }
400
401   return node;
402 }
403
404 static GTreeNode*
405 g_tree_node_balance (GTreeNode *node)
406 {
407   if (node->balance < -1)
408     {
409       if (node->left->balance > 0)
410         node->left = g_tree_node_rotate_left (node->left);
411       node = g_tree_node_rotate_right (node);
412     }
413   else if (node->balance > 1)
414     {
415       if (node->right->balance < 0)
416         node->right = g_tree_node_rotate_right (node->right);
417       node = g_tree_node_rotate_left (node);
418     }
419
420   return node;
421 }
422
423 static GTreeNode*
424 g_tree_node_remove_leftmost (GTreeNode  *node,
425                              GTreeNode **leftmost)
426 {
427   gint old_balance;
428
429   if (!node->left)
430     {
431       *leftmost = node;
432       return node->right;
433     }
434
435   old_balance = node->left->balance;
436   node->left = g_tree_node_remove_leftmost (node->left, leftmost);
437   return g_tree_node_restore_left_balance (node, old_balance);
438 }
439
440 static GTreeNode*
441 g_tree_node_restore_left_balance (GTreeNode *node,
442                                   gint       old_balance)
443 {
444   if (!node->left)
445     node->balance += 1;
446   else if ((node->left->balance != old_balance) &&
447            (node->left->balance == 0))
448     node->balance += 1;
449
450   if (node->balance > 1)
451     return g_tree_node_balance (node);
452   return node;
453 }
454
455 static GTreeNode*
456 g_tree_node_restore_right_balance (GTreeNode *node,
457                                    gint       old_balance)
458 {
459   if (!node->right)
460     node->balance -= 1;
461   else if ((node->right->balance != old_balance) &&
462            (node->right->balance == 0))
463     node->balance -= 1;
464
465   if (node->balance < -1)
466     return g_tree_node_balance (node);
467   return node;
468 }
469
470 static gpointer
471 g_tree_node_lookup (GTreeNode    *node,
472                     GCompareFunc  compare,
473                     gpointer      key)
474 {
475   gint cmp;
476
477   if (!node)
478     return NULL;
479
480   cmp = (* compare) (key, node->key);
481   if (cmp == 0)
482     return node->value;
483
484   if (cmp < 0)
485     {
486       if (node->left)
487         return g_tree_node_lookup (node->left, compare, key);
488     }
489   else if (cmp > 0)
490     {
491       if (node->right)
492         return g_tree_node_lookup (node->right, compare, key);
493     }
494
495   return NULL;
496 }
497
498 static gint
499 g_tree_node_count (GTreeNode *node)
500 {
501   gint count;
502
503   count = 1;
504   if (node->left)
505     count += g_tree_node_count (node->left);
506   if (node->right)
507     count += g_tree_node_count (node->right);
508
509   return count;
510 }
511
512 static gint
513 g_tree_node_pre_order (GTreeNode     *node,
514                        GTraverseFunc  traverse_func,
515                        gpointer       data)
516 {
517   if ((*traverse_func) (node->key, node->value, data))
518     return TRUE;
519   if (node->left)
520     {
521       if (g_tree_node_pre_order (node->left, traverse_func, data))
522         return TRUE;
523     }
524   if (node->right)
525     {
526       if (g_tree_node_pre_order (node->right, traverse_func, data))
527         return TRUE;
528     }
529
530   return FALSE;
531 }
532
533 static gint
534 g_tree_node_in_order (GTreeNode     *node,
535                       GTraverseFunc  traverse_func,
536                       gpointer       data)
537 {
538   if (node->left)
539     {
540       if (g_tree_node_in_order (node->left, traverse_func, data))
541         return TRUE;
542     }
543   if ((*traverse_func) (node->key, node->value, data))
544     return TRUE;
545   if (node->right)
546     {
547       if (g_tree_node_in_order (node->right, traverse_func, data))
548         return TRUE;
549     }
550
551   return FALSE;
552 }
553
554 static gint
555 g_tree_node_post_order (GTreeNode     *node,
556                         GTraverseFunc  traverse_func,
557                         gpointer       data)
558 {
559   if (node->left)
560     {
561       if (g_tree_node_post_order (node->left, traverse_func, data))
562         return TRUE;
563     }
564   if (node->right)
565     {
566       if (g_tree_node_post_order (node->right, traverse_func, data))
567         return TRUE;
568     }
569   if ((*traverse_func) (node->key, node->value, data))
570     return TRUE;
571
572   return FALSE;
573 }
574
575 static gpointer
576 g_tree_node_search (GTreeNode   *node,
577                     GSearchFunc  search_func,
578                     gpointer     data)
579 {
580   gint dir;
581
582   if (!node)
583     return NULL;
584
585   do {
586     dir = (* search_func) (node->key, data);
587     if (dir == 0)
588       return node->value;
589
590     if (dir < 0)
591       node = node->left;
592     else if (dir > 0)
593       node = node->right;
594   } while (node && (dir != 0));
595
596   return NULL;
597 }
598
599 static gint
600 g_tree_node_height (GTreeNode *node)
601 {
602   gint left_height;
603   gint right_height;
604
605   if (node)
606     {
607       left_height = 0;
608       right_height = 0;
609
610       if (node->left)
611         left_height = g_tree_node_height (node->left);
612
613       if (node->right)
614         right_height = g_tree_node_height (node->right);
615
616       return MAX (left_height, right_height) + 1;
617     }
618
619   return 0;
620 }
621
622 static GTreeNode*
623 g_tree_node_rotate_left (GTreeNode *node)
624 {
625   GTreeNode *left;
626   GTreeNode *right;
627   gint a_bal;
628   gint b_bal;
629
630   left = node->left;
631   right = node->right;
632
633   node->right = right->left;
634   right->left = node;
635
636   a_bal = node->balance;
637   b_bal = right->balance;
638
639   if (b_bal <= 0)
640     {
641       if (a_bal >= 1)
642         right->balance = b_bal - 1;
643       else
644         right->balance = a_bal + b_bal - 2;
645       node->balance = a_bal - 1;
646     }
647   else
648     {
649       if (a_bal <= b_bal)
650         right->balance = a_bal - 2;
651       else
652         right->balance = b_bal - 1;
653       node->balance = a_bal - b_bal - 1;
654     }
655
656   return right;
657 }
658
659 static GTreeNode*
660 g_tree_node_rotate_right (GTreeNode *node)
661 {
662   GTreeNode *left;
663   GTreeNode *right;
664   gint a_bal;
665   gint b_bal;
666
667   left = node->left;
668   right = node->right;
669
670   node->left = left->right;
671   left->right = node;
672
673   a_bal = node->balance;
674   b_bal = left->balance;
675
676   if (b_bal <= 0)
677     {
678       if (b_bal > a_bal)
679         left->balance = b_bal + 1;
680       else
681         left->balance = a_bal + 2;
682       node->balance = a_bal - b_bal + 1;
683     }
684   else
685     {
686       if (a_bal <= -1)
687         left->balance = b_bal + 1;
688       else
689         left->balance = a_bal + b_bal + 2;
690       node->balance = a_bal + 1;
691     }
692
693   return left;
694 }
695
696 static void
697 g_tree_node_check (GTreeNode *node)
698 {
699   gint left_height;
700   gint right_height;
701   gint balance;
702
703   if (node)
704     {
705       left_height = 0;
706       right_height = 0;
707
708       if (node->left)
709         left_height = g_tree_node_height (node->left);
710       if (node->right)
711         right_height = g_tree_node_height (node->right);
712
713       balance = right_height - left_height;
714       if (balance != node->balance)
715         g_print ("g_tree_node_check: failed: %d ( %d )\n",
716                  balance, node->balance);
717
718       if (node->left)
719         g_tree_node_check (node->left);
720       if (node->right)
721         g_tree_node_check (node->right);
722     }
723 }