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