Removing GBSearchArray from libgtk

[Owen Taylor <otaylor redhat com>]

Here is a patch to remove the usages of GBSearchArray from GTK+.

 * GBSearchArray is replaced with GArray + bsearch

 * I've simplified the code as well by combining various cut-and-paste
    and near-cut-and-paste sections.

 * It's a slight deoptimization in some places because bsearch()
   doesn't provide for lookups for insertion, so I just did them
   linearly but unless people start settting a _lot_ of RC properties
   in their RC styles, this shouldn't be a problem.
   
   If it turns out to be one from profiling, then it will be
   easy to fix ... and there are better algorithms for merging
   two sorted data sets than a insertion sort, even with
   bsearch lookups. :-)

I would consider the new code considerably easier to understand,
though that's mostly because of the general simplification,

Regards,
                                        Owen   

(P.S. - if you start fixing up the private version of GBSearchArray,
I'd suggest making _insert() return a gboolean "did-it-insert" 
value ... a lot of the confusing bits of the original code
are ad-hoc ways to figure out if insertion really happened or not.)


Index: gtkrc.c
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkrc.c,v
retrieving revision 1.86
diff -u -r1.86 gtkrc.c
--- gtkrc.c	2001/08/23 15:26:48	1.86
+++ gtkrc.c	2001/08/30 04:10:57
@@ -1071,14 +1071,14 @@
     {
       guint i;
 
-      for (i = 0; i < rc_style->rc_properties->n_nodes; i++)
+      for (i = 0; i < rc_style->rc_properties->len; i++)
 	{
-	  GtkRcProperty *node = g_bsearch_array_get_nth (rc_style->rc_properties, i);
+	  GtkRcProperty *node = &g_array_index (rc_style->rc_properties, GtkRcProperty, i);
 
 	  g_free (node->origin);
 	  g_value_unset (&node->value);
 	}
-      g_bsearch_array_destroy (rc_style->rc_properties);
+      g_array_free (rc_style->rc_properties, TRUE);
       rc_style->rc_properties = NULL;
     }
 
@@ -1155,13 +1155,63 @@
 {
   const GtkRcProperty *prop1 = bsearch_node1;
   const GtkRcProperty *prop2 = bsearch_node2;
-  gint cmp;
 
-  cmp = G_BSEARCH_ARRAY_CMP (prop1->type_name, prop2->type_name);
-  if (cmp == 0)
-    cmp = G_BSEARCH_ARRAY_CMP (prop1->property_name, prop2->property_name);
+  if (prop1->type_name == prop2->type_name)
+    return prop1->property_name < prop2->property_name ? -1 : prop1->property_name == prop2->property_name ? 0 : 1;
+  else
+    return prop1->type_name < prop2->type_name ? -1 : 1;
+}
+
+static void
+insert_rc_property (GtkRcStyle    *style,
+		    GtkRcProperty *property,
+		    gboolean       replace)
+{
+  guint i;
+  GtkRcProperty *new_property = NULL;
+  GtkRcProperty key = { 0, 0, NULL, { 0, }, };
+
+  key.type_name = property->type_name;
+  key.property_name = property->property_name;
+
+  if (!style->rc_properties)
+    style->rc_properties = g_array_new (FALSE, FALSE, sizeof (GtkRcProperty));
+
+  i = 0;
+  while (i < style->rc_properties->len)
+    {
+      gint cmp = gtk_rc_properties_cmp (&key, &g_array_index (style->rc_properties, GtkRcProperty, i));
+      if (cmp == 0)
+	
+	{
+	  if (replace)
+	    {
+	      new_property = &g_array_index (style->rc_properties, GtkRcProperty, i);
+	      
+	      g_free (new_property->origin);
+	      g_value_unset (&new_property->value);
+	      
+	      *new_property = key;
+	      break;
+	    }
+	  else
+	    return;
+	}
+      else if (cmp > 0)
+	break;
+
+      i++;
+    }
 
-  return cmp;
+  if (!new_property)
+    {
+      g_array_insert_val (style->rc_properties, i, key);
+      new_property = &g_array_index (style->rc_properties, GtkRcProperty, i);
+    }
+
+  new_property->origin = g_strdup (property->origin);
+  g_value_init (&new_property->value, G_VALUE_TYPE (&property->value));
+  g_value_copy (&property->value, &new_property->value);
 }
 
 static void
@@ -1213,25 +1263,10 @@
     {
       guint i;
 
-      if (!dest->rc_properties)
-	dest->rc_properties = g_bsearch_array_new (sizeof (GtkRcProperty),
-						   gtk_rc_properties_cmp,
-						   0);
-      for (i = 0; i < src->rc_properties->n_nodes; i++)
-	{
-	  GtkRcProperty *node = g_bsearch_array_get_nth (src->rc_properties, i);
-	  GtkRcProperty *prop, key = { 0, 0, NULL, { 0, }, };
-
-	  key.type_name = node->type_name;
-	  key.property_name = node->property_name;
-	  prop = g_bsearch_array_insert (dest->rc_properties, &key, FALSE);
-	  if (!prop->origin)
-	    {
-	      prop->origin = g_strdup (node->origin);
-	      g_value_init (&prop->value, G_VALUE_TYPE (&node->value));
-	      g_value_copy (&node->value, &prop->value);
-	    }
-	}
+      for (i = 0; i < src->rc_properties->len; i++)
+	insert_rc_property (dest,
+			    &g_array_index (src->rc_properties, GtkRcProperty, i),
+			    FALSE);
     }
 }
 
@@ -2318,27 +2353,10 @@
 	    {
 	      guint i;
 
-	      if (!rc_style->rc_properties)
-		rc_style->rc_properties = g_bsearch_array_new (sizeof (GtkRcProperty),
-							       gtk_rc_properties_cmp,
-							       0);
-	      for (i = 0; i < parent_style->rc_properties->n_nodes; i++)
-		{
-		  GtkRcProperty *node = g_bsearch_array_get_nth (parent_style->rc_properties, i);
-		  GtkRcProperty *prop, key = { 0, 0, NULL, { 0, }, };
-
-		  key.type_name = node->type_name;
-		  key.property_name = node->property_name;
-		  prop = g_bsearch_array_insert (rc_style->rc_properties, &key, FALSE);
-		  if (prop->origin)
-		    {
-		      g_free (prop->origin);
-		      g_value_unset (&prop->value);
-		    }
-		  prop->origin = g_strdup (node->origin);
-		  g_value_init (&prop->value, G_VALUE_TYPE (&node->value));
-		  g_value_copy (&node->value, &prop->value);
-		}
+	      for (i = 0; i < parent_style->rc_properties->len; i++)
+		insert_rc_property (rc_style,
+				    &g_array_index (parent_style->rc_properties, GtkRcProperty, i),
+				    TRUE);
 	    }
 	  
 	  for (i = 0; i < 5; i++)
@@ -2464,29 +2482,13 @@
 	      token = gtk_rc_parse_assignment (scanner, &prop);
 	      if (token == G_TOKEN_NONE)
 		{
-		  GtkRcProperty *tmp;
-
 		  g_return_val_if_fail (prop.origin != NULL && G_VALUE_TYPE (&prop.value) != 0, G_TOKEN_ERROR);
-
-		  if (!rc_style->rc_properties)
-		    rc_style->rc_properties = g_bsearch_array_new (sizeof (GtkRcProperty),
-								   gtk_rc_properties_cmp,
-								   0);
-		  tmp = g_bsearch_array_insert (rc_style->rc_properties, &prop, FALSE);
-		  if (prop.origin != tmp->origin)
-		    {
-		      g_free (tmp->origin);
-		      g_value_unset (&tmp->value);
-		      tmp->origin = prop.origin;
-		      memcpy (&tmp->value, &prop.value, sizeof (prop.value));
-		    }
-		}
-	      else
-		{
-		  g_free (prop.origin);
-		  if (G_VALUE_TYPE (&prop.value))
-		    g_value_unset (&prop.value);
+		  insert_rc_property (rc_style, &prop, TRUE);
 		}
+	      
+	      g_free (prop.origin);
+	      if (G_VALUE_TYPE (&prop.value))
+		g_value_unset (&prop.value);
 	    }
 	  else
 	    {
@@ -2555,7 +2557,9 @@
       key.type_name = type_name;
       key.property_name = property_name;
 
-      node = g_bsearch_array_lookup (rc_style->rc_properties, &key);
+      node = bsearch (&key,
+		      rc_style->rc_properties->data, rc_style->rc_properties->len,
+		      sizeof (GtkRcProperty), gtk_rc_properties_cmp);
     }
 
   return node;
Index: gtkrc.h
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkrc.h,v
retrieving revision 1.31
diff -u -r1.31 gtkrc.h
--- gtkrc.h	2001/06/30 16:08:24	1.31
+++ gtkrc.h	2001/08/30 04:10:57
@@ -76,7 +76,7 @@
   gint ythickness;
 
   /*< private >*/
-  GBSearchArray *rc_properties;
+  GArray *rc_properties;
   
   /* list of RC style lists including this RC style */
   GSList *rc_style_lists;
Index: gtkstyle.c
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkstyle.c,v
retrieving revision 1.75
diff -u -r1.75 gtkstyle.c
--- gtkstyle.c	2001/08/29 21:30:20	1.75
+++ gtkstyle.c	2001/08/30 04:10:58
@@ -25,6 +25,7 @@
  */
 
 #include <math.h>
+#include <stdlib.h>
 #include <string.h>
 #include "gtkgc.h"
 #include "gtkrc.h"
@@ -563,26 +564,32 @@
 }
 
 static void
-gtk_style_finalize (GObject *object)
+clear_property_cache (GtkStyle *style)
 {
-  GtkStyle *style = GTK_STYLE (object);
-
-  g_return_if_fail (style->attach_count == 0);
-
   if (style->property_cache)
     {
       guint i;
 
-      for (i = 0; i < style->property_cache->n_nodes; i++)
+      for (i = 0; i < style->property_cache->len; i++)
 	{
-	  PropertyValue *node = g_bsearch_array_get_nth (style->property_cache, i);
+	  PropertyValue *node = &g_array_index (style->property_cache, PropertyValue, i);
 
 	  g_param_spec_unref (node->pspec);
 	  g_value_unset (&node->value);
 	}
-      g_bsearch_array_destroy (style->property_cache);
+      g_array_free (style->property_cache, TRUE);
       style->property_cache = NULL;
     }
+}
+
+static void
+gtk_style_finalize (GObject *object)
+{
+  GtkStyle *style = GTK_STYLE (object);
+
+  g_return_if_fail (style->attach_count == 0);
+
+  clear_property_cache (style);
   
   if (style->styles)
     {
@@ -1206,20 +1213,7 @@
     gtk_rc_style_ref (src->rc_style);
 
   /* don't copy, just clear cache */
-  if (style->property_cache)
-    {
-      guint i;
-
-      for (i = 0; i < style->property_cache->n_nodes; i++)
-	{
-	  PropertyValue *node = g_bsearch_array_get_nth (style->property_cache, i);
-
-	  g_param_spec_unref (node->pspec);
-	  g_value_unset (&node->value);
-	}
-      g_bsearch_array_destroy (style->property_cache);
-      style->property_cache = NULL;
-    }
+  clear_property_cache (style);
 }
 
 static void
@@ -1230,20 +1224,7 @@
   gint i;
 
   /* cache _should_ be still empty */
-  if (style->property_cache)
-    {
-      guint i;
-
-      for (i = 0; i < style->property_cache->n_nodes; i++)
-	{
-	  PropertyValue *node = g_bsearch_array_get_nth (style->property_cache, i);
-
-	  g_param_spec_unref (node->pspec);
-	  g_value_unset (&node->value);
-	}
-      g_bsearch_array_destroy (style->property_cache);
-      style->property_cache = NULL;
-    }
+  clear_property_cache (style);
 
   if (rc_style->font_desc)
     {
@@ -1297,13 +1278,11 @@
 {
   const PropertyValue *val1 = bsearch_node1;
   const PropertyValue *val2 = bsearch_node2;
-  gint cmp;
 
-  cmp = G_BSEARCH_ARRAY_CMP (val1->widget_type, val2->widget_type);
-  if (cmp == 0)
-    cmp = G_BSEARCH_ARRAY_CMP (val1->pspec, val2->pspec);
-
-  return cmp;
+  if (val1->widget_type == val2->widget_type)
+    return val1->pspec < val2->pspec ? -1 : val1->pspec == val2->pspec ? 0 : 1;
+  else
+    return val1->widget_type < val2->widget_type ? -1 : 1;
 }
 
 const GValue*
@@ -1314,6 +1293,7 @@
 {
   PropertyValue *pcache, key = { 0, NULL, { 0, } };
   const GtkRcProperty *rcprop = NULL;
+  guint i;
 
   g_return_val_if_fail (GTK_IS_STYLE (style), NULL);
   g_return_val_if_fail (G_IS_PARAM_SPEC (pspec), NULL);
@@ -1322,15 +1302,24 @@
 
   /* need value cache array */
   if (!style->property_cache)
-    style->property_cache = g_bsearch_array_new (sizeof (PropertyValue),
-						 style_property_values_cmp,
-						 0);
+    style->property_cache = g_array_new (FALSE, FALSE, sizeof (PropertyValue));
+
   /* lookup, or insert value if not yet present */
   key.widget_type = widget_type;
   key.pspec = pspec;
-  pcache = g_bsearch_array_insert (style->property_cache, &key, FALSE);
-  if (G_VALUE_TYPE (&pcache->value))
+  pcache = bsearch (&key,
+		    style->property_cache->data, style->property_cache->len,
+		    sizeof (PropertyValue), style_property_values_cmp);
+  if (pcache)
     return &pcache->value;
+
+  i = 0;
+  while (i < style->property_cache->len &&
+	 style_property_values_cmp (&key, &g_array_index (style->property_cache, PropertyValue, i)) >= 0)
+    i++;
+
+  g_array_insert_val (style->property_cache, i, key);
+  pcache = &g_array_index (style->property_cache, PropertyValue, i);
 
   /* cache miss, initialize value type, then set contents */
   g_param_spec_ref (pcache->pspec);
Index: gtkstyle.h
===================================================================
RCS file: /cvs/gnome/gtk+/gtk/gtkstyle.h,v
retrieving revision 1.29
diff -u -r1.29 gtkstyle.h
--- gtkstyle.h	2001/08/23 15:26:48	1.29
+++ gtkstyle.h	2001/08/30 04:10:58
@@ -117,7 +117,7 @@
   GtkRcStyle	 *rc_style;
 
   GSList	 *styles;	  /* of type GtkStyle* */
-  GBSearchArray	 *property_cache;
+  GArray	 *property_cache;
   GSList         *icon_factories; /* of type GtkIconFactory* */
 };