ghash.c

嵌入式下基于MiniGUI的Web Browser

      (*node)->key   = key;
      (*node)->value = value;
    }
  else
    {
      *node = g_hash_node_new (key, value);
      hash_table->nnodes++;
      G_HASH_TABLE_RESIZE (hash_table);
    }
}

/**
 * g_hash_table_remove:
 * @hash_table: a #GHashTable.
 * @key: the key to remove.
 * 
 * Removes a key and its associated value from a #GHashTable.
 *
 * If the #GHashTable was created using g_hash_table_new_full(), the
 * key and value are freed using the supplied destroy functions, otherwise
 * you have to make sure that any dynamically allocated values are freed 
 * yourself.
 * 
 * Return value: %TRUE if the key was found and removed from the #GHashTable.
 **/
gboolean
g_hash_table_remove (GHashTable	   *hash_table,
		     gconstpointer  key)
{
  GHashNode **node, *dest;
  
  g_return_val_if_fail (hash_table != NULL, FALSE);
  
  node = g_hash_table_lookup_node (hash_table, key);
  if (*node)
    {
      dest = *node;
      (*node) = dest->next;
      g_hash_node_destroy (dest, 
			   hash_table->key_destroy_func,
			   hash_table->value_destroy_func);
      hash_table->nnodes--;
  
      G_HASH_TABLE_RESIZE (hash_table);

      return TRUE;
    }

  return FALSE;
}

/**
 * g_hash_table_steal:
 * @hash_table: a #GHashTable.
 * @key: the key to remove.
 * 
 * Removes a key and its associated value from a #GHashTable without
 * calling the key and value destroy functions.
 *
 * Return value: %TRUE if the key was found and removed from the #GHashTable.
 **/
gboolean
g_hash_table_steal (GHashTable    *hash_table,
                    gconstpointer  key)
{
  GHashNode **node, *dest;
  
  g_return_val_if_fail (hash_table != NULL, FALSE);
  
  node = g_hash_table_lookup_node (hash_table, key);
  if (*node)
    {
      dest = *node;
      (*node) = dest->next;
      g_hash_node_destroy (dest, NULL, NULL);
      hash_table->nnodes--;
  
      G_HASH_TABLE_RESIZE (hash_table);

      return TRUE;
    }

  return FALSE;
}

/**
 * g_hash_table_foreach_remove:
 * @hash_table: a #GHashTable.
 * @func: the function to call for each key/value pair.
 * @user_data: user data to pass to the function.
 * 
 * Calls the given function for each key/value pair in the #GHashTable.
 * If the function returns %TRUE, then the key/value pair is removed from the
 * #GHashTable. If you supplied key or value destroy functions when creating
 * the #GHashTable, they are used to free the memory allocated for the removed
 * keys and values.
 * 
 * Return value: the number of key/value pairs removed.
 **/
guint
g_hash_table_foreach_remove (GHashTable	*hash_table,
			     GHRFunc	 func,
			     gpointer	 user_data)
{
  g_return_val_if_fail (hash_table != NULL, 0);
  g_return_val_if_fail (func != NULL, 0);
  
  return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);
}

/**
 * g_hash_table_foreach_steal:
 * @hash_table: a #GHashTable.
 * @func: the function to call for each key/value pair.
 * @user_data: user data to pass to the function.
 * 
 * Calls the given function for each key/value pair in the #GHashTable.
 * If the function returns %TRUE, then the key/value pair is removed from the
 * #GHashTable, but no key or value destroy functions are called.
 * 
 * Return value: the number of key/value pairs removed.
 **/
guint
g_hash_table_foreach_steal (GHashTable *hash_table,
                            GHRFunc	func,
                            gpointer	user_data)
{
  g_return_val_if_fail (hash_table != NULL, 0);
  g_return_val_if_fail (func != NULL, 0);
  
  return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);
}

static guint
g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,
                                      GHRFunc	  func,
                                      gpointer	  user_data,
                                      gboolean    notify)
{
  GHashNode *node, *prev;
  guint i;
  guint deleted = 0;
  
  for (i = 0; i < hash_table->size; i++)
    {
    restart:
      
      prev = NULL;
      
      for (node = hash_table->nodes[i]; node; prev = node, node = node->next)
	{
	  if ((* func) (node->key, node->value, user_data))
	    {
	      deleted += 1;
	      
	      hash_table->nnodes -= 1;
	      
	      if (prev)
		{
		  prev->next = node->next;
		  g_hash_node_destroy (node,
				       notify ? hash_table->key_destroy_func : NULL,
				       notify ? hash_table->value_destroy_func : NULL);
		  node = prev;
		}
	      else
		{
		  hash_table->nodes[i] = node->next;
		  g_hash_node_destroy (node,
				       notify ? hash_table->key_destroy_func : NULL,
				       notify ? hash_table->value_destroy_func : NULL);
		  goto restart;
		}
	    }
	}
    }
  
  G_HASH_TABLE_RESIZE (hash_table);
  
  return deleted;
}

/**
 * g_hash_table_foreach:
 * @hash_table: a #GHashTable.
 * @func: the function to call for each key/value pair.
 * @user_data: user data to pass to the function.
 * 
 * Calls the given function for each of the key/value pairs in the
 * #GHashTable.  The function is passed the key and value of each
 * pair, and the given @user_data parameter.  The hash table may not
 * be modified while iterating over it (you can't add/remove
 * items). To remove all items matching a predicate, use
 * g_hash_table_remove().
 **/
void
g_hash_table_foreach (GHashTable *hash_table,
		      GHFunc	  func,
		      gpointer	  user_data)
{
  GHashNode *node;
  gint i;
  
  g_return_if_fail (hash_table != NULL);
  g_return_if_fail (func != NULL);
  
  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);
}

/**
 * g_hash_table_size:
 * @hash_table: a #GHashTable.
 * 
 * Returns the number of elements contained in the #GHashTable.
 * 
 * Return value: the number of key/value pairs in the #GHashTable.
 **/
guint
g_hash_table_size (GHashTable *hash_table)
{
  g_return_val_if_fail (hash_table != NULL, 0);
  
  return hash_table->nnodes;
}

static void
g_hash_table_resize (GHashTable *hash_table)
{
  GHashNode **new_nodes;
  GHashNode *node;
  GHashNode *next;
  guint hash_val;
  gint new_size;
  gint i;

  new_size = g_spaced_primes_closest (hash_table->nnodes);
  new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);
 
  new_nodes = g_new0 (GHashNode*, new_size);
  
  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_node_new (gpointer key,
		 gpointer value)
{
  GHashNode *hash_node;
  
  G_LOCK (g_hash_global);
  if (node_free_list)
    {
      hash_node = node_free_list;
      node_free_list = node_free_list->next;
    }
  else
    {
      if (!node_mem_chunk)
	node_mem_chunk = g_mem_chunk_new ("hash node mem chunk",
					  sizeof (GHashNode),
					  1024, G_ALLOC_ONLY);
      
      hash_node = g_chunk_new (GHashNode, node_mem_chunk);
    }
  G_UNLOCK (g_hash_global);
  
  hash_node->key = key;
  hash_node->value = value;
  hash_node->next = NULL;
  
  return hash_node;
}

static void
g_hash_node_destroy (GHashNode      *hash_node,
		     GDestroyNotify  key_destroy_func,
		     GDestroyNotify  value_destroy_func)
{
  if (key_destroy_func)
    key_destroy_func (hash_node->key);
  if (value_destroy_func)
    value_destroy_func (hash_node->value);
  
#ifdef ENABLE_GC_FRIENDLY
  hash_node->key = NULL;
  hash_node->value = NULL;
#endif /* ENABLE_GC_FRIENDLY */

  G_LOCK (g_hash_global);
  hash_node->next = node_free_list;
  node_free_list = hash_node;
  G_UNLOCK (g_hash_global);
}

static void
g_hash_nodes_destroy (GHashNode *hash_node,
		      GFreeFunc  key_destroy_func,
		      GFreeFunc  value_destroy_func)
{
  if (hash_node)
    {
      GHashNode *node = hash_node;
  
      while (node->next)
	{
	  if (key_destroy_func)
	    key_destroy_func (node->key);
	  if (value_destroy_func)
	    value_destroy_func (node->value);

#ifdef ENABLE_GC_FRIENDLY
	  node->key = NULL;
	  node->value = NULL;
#endif /* ENABLE_GC_FRIENDLY */

	  node = node->next;
	}

  if (key_destroy_func)
    key_destroy_func (node->key);
  if (value_destroy_func)
    value_destroy_func (node->value);

#ifdef ENABLE_GC_FRIENDLY
      node->key = NULL;
      node->value = NULL;
#endif /* ENABLE_GC_FRIENDLY */
 
      G_LOCK (g_hash_global);
      node->next = node_free_list;
      node_free_list = hash_node;
      G_UNLOCK (g_hash_global);
    }
}