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