Generic hash cleanup, added a function (g_hash_table_lookup_full).

1 files changed, 167 insertions, 247 deletions

diff --git a/ghash.c b/ghash.c
index ee364c9c2..a3ce08a29 100644
--- a/ghash.c
+++ b/ghash.c
@@ -24,7 +24,6 @@
 
 
 typedef struct _GHashNode      GHashNode;
-typedef struct _GRealHashTable GRealHashTable;
 
 struct _GHashNode
 {
@@ -33,7 +32,7 @@ struct _GHashNode
   GHashNode *next;
 };
 
-struct _GRealHashTable
+struct _GHashTable
 {
   gint size;
   gint nnodes;
@@ -44,17 +43,16 @@ struct _GRealHashTable
 };
 
 
-static void       g_hash_table_resize  (GHashTable *hash_table);
-static gint       g_hash_closest_prime (gint        num);
-static GHashNode* g_hash_node_new      (gpointer    key,
-					gpointer    value);
-static void       g_hash_node_destroy  (GHashNode  *hash_node);
-static void       g_hash_nodes_destroy (GHashNode  *hash_node);
+static void		g_hash_table_resize	(GHashTable	*hash_table);
+static GHashNode**	g_hash_table_lookup_node(GHashTable	*hash_table,
+						 gconstpointer	 key);
+static gint		g_hash_closest_prime	(gint		 num);
+static GHashNode*	g_hash_node_new		(gpointer	 key,
+						 gpointer	 value);
+static void		g_hash_node_destroy	(GHashNode	*hash_node);
+static void		g_hash_nodes_destroy	(GHashNode	*hash_node);
 
 
-extern gint g_primes[];
-extern gint g_nprimes;
-
 static GMemChunk *node_mem_chunk = NULL;
 static GHashNode *node_free_list = NULL;
 
@@ -63,38 +61,35 @@ GHashTable*
 g_hash_table_new (GHashFunc    hash_func,
 		  GCompareFunc key_compare_func)
 {
-  GRealHashTable *hash_table;
-
-  g_return_val_if_fail (hash_func != NULL, NULL);
-
-  hash_table = g_new (GRealHashTable, 1);
-  hash_table->size = 0;
+  GHashTable *hash_table;
+  gint i;
+  
+  hash_table = g_new (GHashTable, 1);
+  hash_table->size = HASH_TABLE_MIN_SIZE;
   hash_table->nnodes = 0;
   hash_table->frozen = FALSE;
-  hash_table->nodes = NULL;
-  hash_table->hash_func = hash_func;
+  hash_table->hash_func = hash_func ? hash_func : g_direct_hash;
   hash_table->key_compare_func = key_compare_func;
+  hash_table->nodes = g_new (GHashNode*, hash_table->size);
+  
+  for (i = 0; i < hash_table->size; i++)
+    hash_table->nodes[i] = NULL;
 
-  return ((GHashTable*) hash_table);
+  return hash_table;
 }
 
 void
 g_hash_table_destroy (GHashTable *hash_table)
 {
-  GRealHashTable *rhash_table;
   gint i;
 
-  if (hash_table)
-    {
-      rhash_table = (GRealHashTable*) hash_table;
-
-      for (i = 0; i < rhash_table->size; i++)
-	g_hash_nodes_destroy (rhash_table->nodes[i]);
-
-      if (rhash_table->nodes)
-	g_free (rhash_table->nodes);
-      g_free (rhash_table);
-    }
+  g_return_if_fail (hash_table);
+  
+  for (i = 0; i < hash_table->size; i++)
+    g_hash_nodes_destroy (hash_table->nodes[i]);
+  
+  g_free (hash_table->nodes);
+  g_free (hash_table);
 }
 
 void
@@ -102,45 +97,28 @@ g_hash_table_insert (GHashTable *hash_table,
 		     gpointer    key,
 		     gpointer    value)
 {
-  GRealHashTable *rhash_table;
-  GHashNode *node;
-  guint hash_val;
+  GHashNode **node;
 
-  if (hash_table)
-    {
-      rhash_table = (GRealHashTable*) hash_table;
+  g_return_if_fail (hash_table);
+  
+  node = g_hash_table_lookup_node (hash_table, key);
 
-      if (rhash_table->size == 0)
+  if (*node)
+    {
+      /* do not reset node->key in this place, keeping
+       * the old key might be intended.
+       * a g_hash_table_remove/g_hash_table_insert pair
+       * can be used otherwise.
+       *
+       * node->key = key; */
+      (*node)->value = value;
+    }
+  else
+    {
+      *node = g_hash_node_new (key, value);
+      hash_table->nnodes++;
+      if (!hash_table->frozen)
 	g_hash_table_resize (hash_table);
-
-      hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
-
-      node = rhash_table->nodes[hash_val];
-      while (node)
-	{
-	  if ((rhash_table->key_compare_func &&
-	       (* rhash_table->key_compare_func) (node->key, key)) ||
-	      (node->key == key))
-	    {
-	      /* do not reset node->key in this place, keeping
-	       * the old key might be intended.
-	       * a g_hash_table_remove/g_hash_table_insert pair
-	       * can be used otherwise.
-	       *
-	       * node->key = key;
-	       */
-	      node->value = value;
-	      return;
-	    }
-	  node = node->next;
-	}
-
-      node = g_hash_node_new (key, value);
-      node->next = rhash_table->nodes[hash_val];
-      rhash_table->nodes[hash_val] = node;
-
-      rhash_table->nnodes += 1;
-      g_hash_table_resize (hash_table);
     }
 }
 
@@ -148,110 +126,73 @@ void
 g_hash_table_remove (GHashTable      *hash_table,
 		     gconstpointer    key)
 {
-  GRealHashTable *rhash_table;
-  GHashNode *node;
-  GHashNode *prev;
-  guint hash_val;
+  GHashNode **node, *dest;
+
+  g_return_if_fail (hash_table);
 
-  rhash_table = (GRealHashTable*) hash_table;
-  if (hash_table && rhash_table->size)
+  while (*(node = g_hash_table_lookup_node (hash_table, key)))
     {
-      hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
-
-      prev = NULL;
-      node = rhash_table->nodes[hash_val];
-
-      while (node)
-	{
-	  if ((rhash_table->key_compare_func &&
-	       (* rhash_table->key_compare_func) (node->key, key)) ||
-	      (node->key == key))
-	    {
-	      if (prev)
-		prev->next = node->next;
-	      if (node == rhash_table->nodes[hash_val])
-		rhash_table->nodes[hash_val] = node->next;
-
-	      g_hash_node_destroy (node);
-
-	      rhash_table->nnodes -= 1;
-	      g_hash_table_resize (hash_table);
-	      break;
-	    }
-
-	  prev = node;
-	  node = node->next;
-	}
+      dest = *node;
+      (*node) = dest->next;
+      g_hash_node_destroy (dest);
+      hash_table->nnodes--;
     }
+  if (!hash_table->frozen)
+    g_hash_table_resize (hash_table);
 }
 
 gpointer
 g_hash_table_lookup (GHashTable   *hash_table,
 		     gconstpointer key)
 {
-  GRealHashTable *rhash_table;
   GHashNode *node;
-  guint hash_val;
+	
+  g_return_val_if_fail (hash_table, NULL);
+
+  node = *g_hash_table_lookup_node (hash_table, key);
+  return node ? node->value : NULL;
+}
 
-  rhash_table = (GRealHashTable*) hash_table;
-  if (hash_table && rhash_table->size)
+gboolean
+g_hash_table_lookup_full (GHashTable	*hash_table,
+			  gconstpointer	 lookup_key,
+			  gpointer	*orig_key,
+			  gpointer	*value)
+{
+  GHashNode *node;
+  
+  g_return_val_if_fail (hash_table, FALSE);
+
+  node = *g_hash_table_lookup_node (hash_table, lookup_key);
+
+  if (node)
     {
-      hash_val = (* rhash_table->hash_func) (key) % rhash_table->size;
-
-      node = rhash_table->nodes[hash_val];
-
-      /* Hash table lookup needs to be fast.
-       *  We therefore remove the extra conditional of testing
-       *  whether to call the key_compare_func or not from
-       *  the inner loop.
-       */
-      if (rhash_table->key_compare_func)
-	{
-	  while (node)
-	    {
-	      if ((* rhash_table->key_compare_func) (node->key, key))
-		return node->value;
-	      node = node->next;
-	    }
-	}
-      else
-	{
-	  while (node)
-	    {
-	      if (node->key == key)
-		return node->value;
-	      node = node->next;
-	    }
-	}
+      if (orig_key)
+	*orig_key = node->key;
+      if (value)
+	*value = node->value;
+      return TRUE;
     }
-
-  return NULL;
+  else
+    return FALSE;
 }
 
 void
 g_hash_table_freeze (GHashTable *hash_table)
 {
-  GRealHashTable *rhash_table;
+  g_return_if_fail (hash_table);
 
-  if (hash_table)
-    {
-      rhash_table = (GRealHashTable*) hash_table;
-      rhash_table->frozen = TRUE;
-    }
+  hash_table->frozen = TRUE;
 }
 
 void
 g_hash_table_thaw (GHashTable *hash_table)
 {
-  GRealHashTable *rhash_table;
+  g_return_if_fail (hash_table);
 
-  if (hash_table)
-    {
-      rhash_table = (GRealHashTable*) hash_table;
-      rhash_table->frozen = FALSE;
+  hash_table->frozen = FALSE;
 
-      g_hash_table_resize (hash_table);
-    }
+  g_hash_table_resize (hash_table);
 }
 
 void
@@ -259,110 +200,96 @@ g_hash_table_foreach (GHashTable *hash_table,
 		      GHFunc      func,
 		      gpointer    user_data)
 {
-  GRealHashTable *rhash_table;
   GHashNode *node;
   gint i;
 
-  if (hash_table)
-    {
-      rhash_table = (GRealHashTable*) hash_table;
-
-      for (i = 0; i < rhash_table->size; i++)
-	{
-	  node = rhash_table->nodes[i];
-
-	  while (node)
-	    {
-	      (* func) (node->key, node->value, user_data);
-	      node = node->next;
-	    }
-	}
-    }
+  g_return_if_fail (hash_table);
+
+  for (i = 0; i < hash_table->size; i++)
+    for (node = hash_table->nodes[i]; node; node = node->next)
+      (* func) (node->key, node->value, user_data);
 }
 
+/* Returns the number of elements contained in the hash table. */
+gint g_hash_table_size (GHashTable *hash_table)
+{
+  g_return_val_if_fail (hash_table, 0);
+
+  return hash_table->nnodes;
+}
 
 static void
 g_hash_table_resize (GHashTable *hash_table)
 {
-  GRealHashTable *rhash_table;
   GHashNode **new_nodes;
   GHashNode *node;
   GHashNode *next;
   gfloat nodes_per_list;
   guint hash_val;
   gint new_size;
-  gint need_resize;
   gint i;
 
-  if (hash_table)
-    {
-      rhash_table = (GRealHashTable*) hash_table;
-
-      if (rhash_table->size == 0)
-	{
-	  rhash_table->size = HASH_TABLE_MIN_SIZE;
-	  rhash_table->nodes = g_new (GHashNode*, rhash_table->size);
-
-	  for (i = 0; i < rhash_table->size; i++)
-	    rhash_table->nodes[i] = NULL;
-	}
-      else if (!rhash_table->frozen)
-	{
-	  need_resize = FALSE;
-	  nodes_per_list = (gfloat) rhash_table->nnodes / (gfloat) rhash_table->size;
-
-	  if (nodes_per_list < 0.3)
-	    {
-	      if (rhash_table->size > HASH_TABLE_MIN_SIZE)
-		need_resize = TRUE;
-	    }
-	  else if (nodes_per_list > 3.0)
-	    {
-	      if (rhash_table->size < HASH_TABLE_MAX_SIZE)
-		need_resize = TRUE;
-	    }
-
-	  if (need_resize)
-	    {
-	      new_size = g_hash_closest_prime (rhash_table->nnodes);
-	      if (new_size < HASH_TABLE_MIN_SIZE)
-		new_size = HASH_TABLE_MIN_SIZE;
-	      else if (new_size > HASH_TABLE_MAX_SIZE)
-		new_size = HASH_TABLE_MAX_SIZE;
-
-	      new_nodes = g_new (GHashNode*, new_size);
-
-	      for (i = 0; i < new_size; i++)
-		new_nodes[i] = NULL;
-
-	      for (i = 0; i < rhash_table->size; i++)
-		{
-		  node = rhash_table->nodes[i];
-
-		  while (node)
-		    {
-		      next = node->next;
-
-		      hash_val = (* rhash_table->hash_func) (node->key) % new_size;
-		      node->next = new_nodes[hash_val];
-		      new_nodes[hash_val] = node;
-
-		      node = next;
-		    }
-		}
-
-	      g_free (rhash_table->nodes);
-
-	      rhash_table->nodes = new_nodes;
-	      rhash_table->size = new_size;
-	    }
-	}
-    }
+  g_return_if_fail (hash_table);
+
+  nodes_per_list = (gfloat) hash_table->nnodes / (gfloat) hash_table->size;
+      
+  if ((nodes_per_list > 0.3 || hash_table->size <= HASH_TABLE_MIN_SIZE) &&
+      (nodes_per_list < 3.0 || hash_table->size >= HASH_TABLE_MAX_SIZE))
+    return;
+
+  new_size = CLAMP(g_hash_closest_prime (hash_table->nnodes),
+		   HASH_TABLE_MIN_SIZE,
+		   HASH_TABLE_MAX_SIZE);
+  new_nodes = g_new (GHashNode*, new_size);
+	  
+  for (i = 0; i < new_size; i++)
+    new_nodes[i] = NULL;
+      
+  for (i = 0; i < hash_table->size; i++)
+    for (node = hash_table->nodes[i]; node; node = next)
+      {
+	next = node->next;
+	hash_val = (* hash_table->hash_func) (node->key) % new_size;
+	node->next = new_nodes[hash_val];
+	new_nodes[hash_val] = node;
+      }
+      
+  g_free (hash_table->nodes);
+  hash_table->nodes = new_nodes;
+  hash_table->size = new_size;
+}
+
+static GHashNode **
+g_hash_table_lookup_node (GHashTable	*hash_table,
+			  gconstpointer	 key)
+{
+  GHashNode **node;
+  
+  g_return_val_if_fail (hash_table, NULL);
+
+  node = &hash_table->nodes
+    [(* hash_table->hash_func) (key) % hash_table->size];
+
+  /* Hash table lookup needs to be fast.
+   *  We therefore remove the extra conditional of testing
+   *  whether to call the key_compare_func or not from
+   *  the inner loop.
+   */
+  if (hash_table->key_compare_func)
+    while (*node && !(*hash_table->key_compare_func) ((*node)->key, key))
+      node = &(*node)->next;
+  else
+    while (*node && (*node)->key != key)
+      node = &(*node)->next;
+  
+  return node;
 }
 
 static gint
 g_hash_closest_prime (gint num)
 {
+  extern gint g_primes[];
+  extern gint g_nprimes;
   gint i;
 
   for (i = 0; i < g_nprimes; i++)
@@ -403,11 +330,10 @@ g_hash_node_new (gpointer key,
 static void
 g_hash_node_destroy (GHashNode *hash_node)
 {
-  if (hash_node)
-    {
-      hash_node->next = node_free_list;
-      node_free_list = hash_node;
-    }
+  g_return_if_fail (hash_node);
+
+  hash_node->next = node_free_list;
+  node_free_list = hash_node;
 }
 
 static void
@@ -415,20 +341,14 @@ g_hash_nodes_destroy (GHashNode *hash_node)
 {
   GHashNode *node;
 
-  if (hash_node)
-    {
-      node = hash_node;
-      while (node->next)
-	node = node->next;
-      node->next = node_free_list;
-      node_free_list = hash_node;
-    }
-}
+  if (!hash_node)
+    return;
 
-/* Returns the number of elements contained in the hash table. */
-gint g_hash_table_size (GHashTable *hash_table)
-{
-  g_return_val_if_fail (hash_table, 0);
+  node = hash_node;
+
+  while (node->next)
+    node = node->next;
 
-  return ((GRealHashTable *) hash_table)->nnodes;
+  node->next = node_free_list;
+  node_free_list = hash_node;
 }