applied patch from Andreas Persenius <ndap@swipnet.se> that updates the

[platform/upstream/glib.git] / glib / gtree.c

diff --git a/glib/gtree.c b/glib/gtree.c
index 4d9e98a..23b3fed 100644 (file)
--- a/glib/gtree.c
+++ b/glib/gtree.c
@@ -2,20 +2,32 @@
  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
  *
  * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Library General Public
+ * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- * Library General Public License for more details.
+ * Lesser General Public License for more details.
  *
- * You should have received a copy of the GNU Library General Public
+ * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
+
+/*
+ * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
+ * file for a list of people on the GLib Team.  See the ChangeLog
+ * files for a list of changes.  These files are distributed with
+ * GLib at ftp://ftp.gtk.org/pub/gtk/. 
+ */
+
+/* 
+ * MT safe
+ */
+
 #include "glib.h"
 
 
@@ -48,7 +60,7 @@ static GTreeNode* g_tree_node_insert                (GTreeNode      *node,
                                                     gint           *inserted);
 static GTreeNode* g_tree_node_remove                (GTreeNode      *node,
                                                     GCompareFunc    compare,
-                                                    gpointer        key);
+                                                    gconstpointer   key);
 static GTreeNode* g_tree_node_balance               (GTreeNode      *node);
 static GTreeNode* g_tree_node_remove_leftmost       (GTreeNode      *node,
                                                     GTreeNode     **leftmost);
@@ -58,7 +70,7 @@ static GTreeNode* g_tree_node_restore_right_balance (GTreeNode      *node,
                                                     gint            old_balance);
 static gpointer   g_tree_node_lookup                (GTreeNode      *node,
                                                     GCompareFunc    compare,
-                                                    gpointer        key);
+                                                    gconstpointer   key);
 static gint       g_tree_node_count                 (GTreeNode      *node);
 static gint       g_tree_node_pre_order             (GTreeNode      *node,
                                                     GTraverseFunc   traverse_func,
@@ -70,14 +82,15 @@ static gint       g_tree_node_post_order            (GTreeNode      *node,
                                                     GTraverseFunc   traverse_func,
                                                     gpointer        data);
 static gpointer   g_tree_node_search                (GTreeNode      *node,
-                                                    GSearchFunc     search_func,
-                                                    gpointer        data);
+                                                    GCompareFunc    search_func,
+                                                    gconstpointer   data);
 static gint       g_tree_node_height                (GTreeNode      *node);
 static GTreeNode* g_tree_node_rotate_left           (GTreeNode      *node);
 static GTreeNode* g_tree_node_rotate_right          (GTreeNode      *node);
 static void       g_tree_node_check                 (GTreeNode      *node);
 
 
+G_LOCK_DEFINE_STATIC (g_tree_global);
 static GMemChunk *node_mem_chunk = NULL;
 static GTreeNode *node_free_list = NULL;
 
@@ -88,6 +101,7 @@ g_tree_node_new (gpointer key,
 {
   GTreeNode *node;
 
+  G_LOCK (g_tree_global);
   if (node_free_list)
     {
       node = node_free_list;
@@ -102,7 +116,8 @@ g_tree_node_new (gpointer key,
                                          G_ALLOC_ONLY);
 
       node = g_chunk_new (GTreeNode, node_mem_chunk);
-    }
+   }
+  G_UNLOCK (g_tree_global);
 
   node->balance = 0;
   node->left = NULL;
@@ -120,9 +135,18 @@ g_tree_node_destroy (GTreeNode *node)
     {
       g_tree_node_destroy (node->right);
       g_tree_node_destroy (node->left);
+
+#ifdef ENABLE_GC_FRIENDLY
+      node->left = NULL;
+      node->key = NULL;
+      node->value = NULL;
+#endif /* ENABLE_GC_FRIENDLY */
+
+      G_LOCK (g_tree_global);
       node->right = node_free_list;
       node_free_list = node;
-    }
+      G_UNLOCK (g_tree_global);
+   }
 }
 
 
@@ -171,8 +195,8 @@ g_tree_insert (GTree    *tree,
 }
 
 void
-g_tree_remove (GTree    *tree,
-              gpointer  key)
+g_tree_remove (GTree         *tree,
+              gconstpointer  key)
 {
   GRealTree *rtree;
 
@@ -184,8 +208,8 @@ g_tree_remove (GTree    *tree,
 }
 
 gpointer
-g_tree_lookup (GTree    *tree,
-              gpointer  key)
+g_tree_lookup (GTree         *tree,
+              gconstpointer  key)
 {
   GRealTree *rtree;
 
@@ -208,7 +232,8 @@ g_tree_traverse (GTree         *tree,
 
   rtree = (GRealTree*) tree;
 
-  g_return_if_fail (rtree->root != NULL);
+  if (!rtree->root)
+    return;
 
   switch (traverse_type)
     {
@@ -231,9 +256,9 @@ g_tree_traverse (GTree         *tree,
 }
 
 gpointer
-g_tree_search (GTree       *tree,
-              GSearchFunc  search_func,
-              gpointer     data)
+g_tree_search (GTree            *tree,
+              GCompareFunc      search_func,
+              gconstpointer     data)
 {
   GRealTree *rtree;
 
@@ -243,7 +268,8 @@ g_tree_search (GTree       *tree,
 
   if (rtree->root)
     return g_tree_node_search (rtree->root, search_func, data);
-  return NULL;
+  else
+    return NULL;
 }
 
 gint
@@ -257,7 +283,8 @@ g_tree_height (GTree *tree)
 
   if (rtree->root)
     return g_tree_node_height (rtree->root);
-  return 0;
+  else
+    return 0;
 }
 
 gint
@@ -271,7 +298,8 @@ g_tree_nnodes (GTree *tree)
 
   if (rtree->root)
     return g_tree_node_count (rtree->root);
-  return 0;
+  else
+    return 0;
 }
 
 static GTreeNode*
@@ -343,9 +371,9 @@ g_tree_node_insert (GTreeNode    *node,
 }
 
 static GTreeNode*
-g_tree_node_remove (GTreeNode    *node,
-                   GCompareFunc  compare,
-                   gpointer      key)
+g_tree_node_remove (GTreeNode     *node,
+                   GCompareFunc   compare,
+                   gconstpointer  key)
 {
   GTreeNode *new_root;
   gint old_balance;
@@ -375,9 +403,17 @@ g_tree_node_remove (GTreeNode    *node,
          node = g_tree_node_restore_right_balance (new_root, old_balance);
        }
 
+#ifdef ENABLE_GC_FRIENDLY
+      garbage->left = NULL;
+      garbage->key = NULL;
+      garbage->value = NULL;
+#endif /* ENABLE_GC_FRIENDLY */
+
+      G_LOCK (g_tree_global);
       garbage->right = node_free_list;
       node_free_list = garbage;
-    }
+      G_UNLOCK (g_tree_global);
+   }
   else if (cmp < 0)
     {
       if (node->left)
@@ -467,9 +503,9 @@ g_tree_node_restore_right_balance (GTreeNode *node,
 }
 
 static gpointer
-g_tree_node_lookup (GTreeNode    *node,
-                   GCompareFunc  compare,
-                   gpointer      key)
+g_tree_node_lookup (GTreeNode     *node,
+                   GCompareFunc   compare,
+                   gconstpointer  key)
 {
   gint cmp;
 
@@ -572,9 +608,9 @@ g_tree_node_post_order (GTreeNode     *node,
 }
 
 static gpointer
-g_tree_node_search (GTreeNode   *node,
-                   GSearchFunc  search_func,
-                   gpointer     data)
+g_tree_node_search (GTreeNode     *node,
+                   GCompareFunc   search_func,
+                   gconstpointer  data)
 {
   gint dir;
 
@@ -621,12 +657,10 @@ g_tree_node_height (GTreeNode *node)
 static GTreeNode*
 g_tree_node_rotate_left (GTreeNode *node)
 {
-  GTreeNode *left;
   GTreeNode *right;
   gint a_bal;
   gint b_bal;
 
-  left = node->left;
   right = node->right;
 
   node->right = right->left;
@@ -659,12 +693,10 @@ static GTreeNode*
 g_tree_node_rotate_right (GTreeNode *node)
 {
   GTreeNode *left;
-  GTreeNode *right;
   gint a_bal;
   gint b_bal;
 
   left = node->left;
-  right = node->right;
 
   node->left = left->right;
   left->right = node;