1 /* GLIB - Library of useful routines for C programming

     2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald

     3  * Portions copyright (c) 2006 Nokia Corporation.  All rights reserved.

     4  *

     5  * This library is free software; you can redistribute it and/or

     6  * modify it under the terms of the GNU Lesser General Public

     7  * License as published by the Free Software Foundation; either

     8  * version 2 of the License, or (at your option) any later version.

     9  *

    10  * This library is distributed in the hope that it will be useful,

    11  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU

    13  * Lesser General Public License for more details.

    14  *

    15  * You should have received a copy of the GNU Lesser General Public

    16  * License along with this library; if not, write to the

    17  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,

    18  * Boston, MA 02111-1307, USA.

    19  */

    20 

    21 /*

    22  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS

    23  * file for a list of people on the GLib Team.  See the ChangeLog

    24  * files for a list of changes.  These files are distributed with

    25  * GLib at ftp://ftp.gtk.org/pub/gtk/. 

    26  */

    27 

    28 /* 

    29  * MT safe

    30  */

    31 

    32 #include "config.h"

    33 

    34 #include "glib.h"

    35 #include "galias.h"

    36 

    37 

    38 #define HASH_TABLE_MIN_SIZE 11

    39 #define HASH_TABLE_MAX_SIZE 13845163

    40 

    41 

    42 typedef struct _GHashNode      GHashNode;

    43 

    44 struct _GHashNode

    45 {

    46   gpointer   key;

    47   gpointer   value;

    48   GHashNode *next;

    49 };

    50 

    51 struct _GHashTable

    52 {

    53   gint             size;

    54   gint             nnodes;

    55   GHashNode      **nodes;

    56   GHashFunc        hash_func;

    57   GEqualFunc       key_equal_func;

    58   volatile guint   ref_count;

    59   GDestroyNotify   key_destroy_func;

    60   GDestroyNotify   value_destroy_func;

    61 };

    62 

    63 #define G_HASH_TABLE_RESIZE(hash_table)				\

    64    G_STMT_START {						\

    65      if ((hash_table->size >= 3 * hash_table->nnodes &&	        \

    66 	  hash_table->size > HASH_TABLE_MIN_SIZE) ||		\

    67 	 (3 * hash_table->size <= hash_table->nnodes &&	        \

    68 	  hash_table->size < HASH_TABLE_MAX_SIZE))		\

    69 	   g_hash_table_resize (hash_table);			\

    70    } G_STMT_END

    71 

    72 static void		g_hash_table_resize	  (GHashTable	  *hash_table);

    73 static GHashNode**	g_hash_table_lookup_node  (GHashTable     *hash_table,

    74                                                    gconstpointer   key);

    75 static GHashNode*	g_hash_node_new		  (gpointer	   key,

    76                                                    gpointer        value);

    77 static void		g_hash_node_destroy	  (GHashNode	  *hash_node,

    78                                                    GDestroyNotify  key_destroy_func,

    79                                                    GDestroyNotify  value_destroy_func);

    80 static void		g_hash_nodes_destroy	  (GHashNode	  *hash_node,

    81 						  GDestroyNotify   key_destroy_func,

    82 						  GDestroyNotify   value_destroy_func);

    83 static guint g_hash_table_foreach_remove_or_steal (GHashTable     *hash_table,

    84                                                    GHRFunc	   func,

    85                                                    gpointer	   user_data,

    86                                                    gboolean        notify);

    87 

    88 

    89 /**

    90  * g_hash_table_new:

    91  * @hash_func: a function to create a hash value from a key.

    92  *   Hash values are used to determine where keys are stored within the

    93  *   #GHashTable data structure. The g_direct_hash(), g_int_hash() and 

    94  *   g_str_hash() functions are provided for some common types of keys. 

    95  *   If hash_func is %NULL, g_direct_hash() is used.

    96  * @key_equal_func: a function to check two keys for equality.  This is

    97  *   used when looking up keys in the #GHashTable.  The g_direct_equal(),

    98  *   g_int_equal() and g_str_equal() functions are provided for the most

    99  *   common types of keys. If @key_equal_func is %NULL, keys are compared

   100  *   directly in a similar fashion to g_direct_equal(), but without the

   101  *   overhead of a function call.

   102  *

   103  * Creates a new #GHashTable with a reference count of 1.

   104  * 

   105  * Return value: a new #GHashTable.

   106  **/

   107 EXPORT_C GHashTable*

   108 g_hash_table_new (GHashFunc    hash_func,

   109 		  GEqualFunc   key_equal_func)

   110 {

   111   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);

   112 }

   113 

   114 

   115 /**

   116  * g_hash_table_new_full:

   117  * @hash_func: a function to create a hash value from a key.

   118  * @key_equal_func: a function to check two keys for equality.

   119  * @key_destroy_func: a function to free the memory allocated for the key 

   120  *   used when removing the entry from the #GHashTable or %NULL if you 

   121  *   don't want to supply such a function.

   122  * @value_destroy_func: a function to free the memory allocated for the 

   123  *   value used when removing the entry from the #GHashTable or %NULL if 

   124  *   you don't want to supply such a function.

   125  * 

   126  * Creates a new #GHashTable like g_hash_table_new() with a reference count

   127  * of 1 and allows to specify functions to free the memory allocated for the

   128  * key and value that get called when removing the entry from the #GHashTable.

   129  * 

   130  * Return value: a new #GHashTable.

   131  **/

   132 EXPORT_C GHashTable*

   133 g_hash_table_new_full (GHashFunc       hash_func,

   134 		       GEqualFunc      key_equal_func,

   135 		       GDestroyNotify  key_destroy_func,

   136 		       GDestroyNotify  value_destroy_func)

   137 {

   138   GHashTable *hash_table;

   139 

   140   hash_table = g_slice_new (GHashTable);

   141   hash_table->size               = HASH_TABLE_MIN_SIZE;

   142   hash_table->nnodes             = 0;

   143   hash_table->hash_func          = hash_func ? hash_func : g_direct_hash;

   144   hash_table->key_equal_func     = key_equal_func;

   145   hash_table->ref_count          = 1;

   146   hash_table->key_destroy_func   = key_destroy_func;

   147   hash_table->value_destroy_func = value_destroy_func;

   148   hash_table->nodes              = g_new0 (GHashNode*, hash_table->size);

   149   return hash_table;

   150 }

   151 

   152 

   153 /**

   154  * g_hash_table_ref:

   155  * @hash_table: a valid #GHashTable.

   156  * 

   157  * Atomically increments the reference count of @hash_table by one.

   158  * This function is MT-safe and may be called from any thread.

   159  * 

   160  * Return value: the passed in #GHashTable.

   161  * 

   162  * Since: 2.10

   163  **/

   164 EXPORT_C GHashTable*

   165 g_hash_table_ref (GHashTable *hash_table)

   166 {

   167   g_return_val_if_fail (hash_table != NULL, NULL);

   168   g_return_val_if_fail (hash_table->ref_count > 0, hash_table);

   169 

   170   g_atomic_int_add (FIX_CASTING(volatile int *)&hash_table->ref_count, 1);

   171   return hash_table;

   172 }

   173 

   174 /**

   175  * g_hash_table_unref:

   176  * @hash_table: a valid #GHashTable.

   177  * 

   178  * Atomically decrements the reference count of @hash_table by one.

   179  * If the reference count drops to 0, all keys and values will be

   180  * destroyed, and all memory allocated by the hash table is released.

   181  * This function is MT-safe and may be called from any thread.

   182  * 

   183  * Since: 2.10

   184  **/

   185 EXPORT_C void

   186 g_hash_table_unref (GHashTable *hash_table)

   187 {

   188   g_return_if_fail (hash_table != NULL);

   189   g_return_if_fail (hash_table->ref_count > 0);

   190 

   191   if (g_atomic_int_exchange_and_add (FIX_CASTING(volatile int *)&hash_table->ref_count, -1) - 1 == 0)

   192     {

   193       gint i;

   194 

   195       for (i = 0; i < hash_table->size; i++)

   196         g_hash_nodes_destroy (hash_table->nodes[i], 

   197                               hash_table->key_destroy_func,

   198                               hash_table->value_destroy_func);

   199       g_free (hash_table->nodes);

   200       g_slice_free (GHashTable, hash_table);

   201     }

   202 }

   203 

   204 /**

   205  * g_hash_table_destroy:

   206  * @hash_table: a #GHashTable.

   207  * 

   208  * Destroys all keys and values in the #GHashTable and decrements its

   209  * reference count by 1. If keys and/or values are dynamically allocated,

   210  * you should either free them first or create the #GHashTable with destroy

   211  * notifiers using g_hash_table_new_full(). In the latter case the destroy

   212  * functions you supplied will be called on all keys and values during the

   213  * destruction phase.

   214  **/

   215 EXPORT_C void

   216 g_hash_table_destroy (GHashTable *hash_table)

   217 {

   218   gint i;

   219   

   220   g_return_if_fail (hash_table != NULL);

   221   g_return_if_fail (hash_table->ref_count > 0);

   222   

   223   for (i = 0; i < hash_table->size; i++)

   224     {

   225       g_hash_nodes_destroy (hash_table->nodes[i], 

   226                             hash_table->key_destroy_func,

   227                             hash_table->value_destroy_func);

   228       hash_table->nodes[i] = NULL;

   229     }

   230   hash_table->nnodes = 0;

   231   hash_table->size = HASH_TABLE_MIN_SIZE;

   232 

   233   g_hash_table_unref (hash_table);

   234 }

   235 

   236 static inline GHashNode**

   237 g_hash_table_lookup_node (GHashTable	*hash_table,

   238 			  gconstpointer	 key)

   239 {

   240   GHashNode **node;

   241   

   242   node = &hash_table->nodes

   243     [(* hash_table->hash_func) (key) % hash_table->size];

   244   

   245   /* Hash table lookup needs to be fast.

   246    *  We therefore remove the extra conditional of testing

   247    *  whether to call the key_equal_func or not from

   248    *  the inner loop.

   249    */

   250   if (hash_table->key_equal_func)

   251     while (*node && !(*hash_table->key_equal_func) ((*node)->key, key))

   252       node = &(*node)->next;

   253   else

   254     while (*node && (*node)->key != key)

   255       node = &(*node)->next;

   256   

   257   return node;

   258 }

   259 

   260 /**

   261  * g_hash_table_lookup:

   262  * @hash_table: a #GHashTable.

   263  * @key: the key to look up.

   264  * 

   265  * Looks up a key in a #GHashTable. Note that this function cannot

   266  * distinguish between a key that is not present and one which is present

   267  * and has the value %NULL. If you need this distinction, use

   268  * g_hash_table_lookup_extended().

   269  * 

   270  * Return value: the associated value, or %NULL if the key is not found.

   271  **/

   272 EXPORT_C gpointer

   273 g_hash_table_lookup (GHashTable	  *hash_table,

   274 		     gconstpointer key)

   275 {

   276   GHashNode *node;

   277   

   278   g_return_val_if_fail (hash_table != NULL, NULL);

   279   

   280   node = *g_hash_table_lookup_node (hash_table, key);

   281   

   282   return node ? node->value : NULL;

   283 }

   284 

   285 /**

   286  * g_hash_table_lookup_extended:

   287  * @hash_table: a #GHashTable.

   288  * @lookup_key: the key to look up.

   289  * @orig_key: returns the original key.

   290  * @value: returns the value associated with the key.

   291  * 

   292  * Looks up a key in the #GHashTable, returning the original key and the

   293  * associated value and a #gboolean which is %TRUE if the key was found. This 

   294  * is useful if you need to free the memory allocated for the original key, 

   295  * for example before calling g_hash_table_remove().

   296  * 

   297  * Return value: %TRUE if the key was found in the #GHashTable.

   298  **/

   299 EXPORT_C gboolean

   300 g_hash_table_lookup_extended (GHashTable    *hash_table,

   301 			      gconstpointer  lookup_key,

   302 			      gpointer	    *orig_key,

   303 			      gpointer	    *value)

   304 {

   305   GHashNode *node;

   306   

   307   g_return_val_if_fail (hash_table != NULL, FALSE);

   308   

   309   node = *g_hash_table_lookup_node (hash_table, lookup_key);

   310   

   311   if (node)

   312     {

   313       if (orig_key)

   314 	*orig_key = node->key;

   315       if (value)

   316 	*value = node->value;

   317       return TRUE;

   318     }

   319   else

   320     return FALSE;

   321 }

   322 

   323 /**

   324  * g_hash_table_insert:

   325  * @hash_table: a #GHashTable.

   326  * @key: a key to insert.

   327  * @value: the value to associate with the key.

   328  * 

   329  * Inserts a new key and value into a #GHashTable.

   330  * 

   331  * If the key already exists in the #GHashTable its current value is replaced

   332  * with the new value. If you supplied a @value_destroy_func when creating the 

   333  * #GHashTable, the old value is freed using that function. If you supplied

   334  * a @key_destroy_func when creating the #GHashTable, the passed key is freed 

   335  * using that function.

   336  **/

   337 EXPORT_C void

   338 g_hash_table_insert (GHashTable *hash_table,

   339 		     gpointer	 key,

   340 		     gpointer	 value)

   341 {

   342   GHashNode **node;

   343   

   344   g_return_if_fail (hash_table != NULL);

   345   g_return_if_fail (hash_table->ref_count > 0);

   346   

   347   node = g_hash_table_lookup_node (hash_table, key);

   348   

   349   if (*node)

   350     {

   351       /* do not reset node->key in this place, keeping

   352        * the old key is the intended behaviour. 

   353        * g_hash_table_replace() can be used instead.

   354        */

   355 

   356       /* free the passed key */

   357       if (hash_table->key_destroy_func)

   358 	hash_table->key_destroy_func (key);

   359       

   360       if (hash_table->value_destroy_func)

   361 	hash_table->value_destroy_func ((*node)->value);

   362 

   363       (*node)->value = value;

   364     }

   365   else

   366     {

   367       *node = g_hash_node_new (key, value);

   368       hash_table->nnodes++;

   369       G_HASH_TABLE_RESIZE (hash_table);

   370     }

   371 }

   372 

   373 /**

   374  * g_hash_table_replace:

   375  * @hash_table: a #GHashTable.

   376  * @key: a key to insert.

   377  * @value: the value to associate with the key.

   378  * 

   379  * Inserts a new key and value into a #GHashTable similar to 

   380  * g_hash_table_insert(). The difference is that if the key already exists 

   381  * in the #GHashTable, it gets replaced by the new key. If you supplied a 

   382  * @value_destroy_func when creating the #GHashTable, the old value is freed 

   383  * using that function. If you supplied a @key_destroy_func when creating the 

   384  * #GHashTable, the old key is freed using that function. 

   385  **/

   386 EXPORT_C void

   387 g_hash_table_replace (GHashTable *hash_table,

   388 		      gpointer	  key,

   389 		      gpointer	  value)

   390 {

   391   GHashNode **node;

   392   

   393   g_return_if_fail (hash_table != NULL);

   394   g_return_if_fail (hash_table->ref_count > 0);

   395   

   396   node = g_hash_table_lookup_node (hash_table, key);

   397   

   398   if (*node)

   399     {

   400       if (hash_table->key_destroy_func)

   401 	hash_table->key_destroy_func ((*node)->key);

   402       

   403       if (hash_table->value_destroy_func)

   404 	hash_table->value_destroy_func ((*node)->value);

   405 

   406       (*node)->key   = key;

   407       (*node)->value = value;

   408     }

   409   else

   410     {

   411       *node = g_hash_node_new (key, value);

   412       hash_table->nnodes++;

   413       G_HASH_TABLE_RESIZE (hash_table);

   414     }

   415 }

   416 

   417 /**

   418  * g_hash_table_remove:

   419  * @hash_table: a #GHashTable.

   420  * @key: the key to remove.

   421  * 

   422  * Removes a key and its associated value from a #GHashTable.

   423  *

   424  * If the #GHashTable was created using g_hash_table_new_full(), the

   425  * key and value are freed using the supplied destroy functions, otherwise

   426  * you have to make sure that any dynamically allocated values are freed 

   427  * yourself.

   428  * 

   429  * Return value: %TRUE if the key was found and removed from the #GHashTable.

   430  **/

   431 EXPORT_C gboolean

   432 g_hash_table_remove (GHashTable	   *hash_table,

   433 		     gconstpointer  key)

   434 {

   435   GHashNode **node, *dest;

   436   

   437   g_return_val_if_fail (hash_table != NULL, FALSE);

   438   

   439   node = g_hash_table_lookup_node (hash_table, key);

   440   if (*node)

   441     {

   442       dest = *node;

   443       (*node) = dest->next;

   444       g_hash_node_destroy (dest, 

   445 			   hash_table->key_destroy_func,

   446 			   hash_table->value_destroy_func);

   447       hash_table->nnodes--;

   448   

   449       G_HASH_TABLE_RESIZE (hash_table);

   450 

   451       return TRUE;

   452     }

   453 

   454   return FALSE;

   455 }

   456 

   457 /**

   458  * g_hash_table_steal:

   459  * @hash_table: a #GHashTable.

   460  * @key: the key to remove.

   461  * 

   462  * Removes a key and its associated value from a #GHashTable without

   463  * calling the key and value destroy functions.

   464  *

   465  * Return value: %TRUE if the key was found and removed from the #GHashTable.

   466  **/

   467 EXPORT_C gboolean

   468 g_hash_table_steal (GHashTable    *hash_table,

   469                     gconstpointer  key)

   470 {

   471   GHashNode **node, *dest;

   472   

   473   g_return_val_if_fail (hash_table != NULL, FALSE);

   474   

   475   node = g_hash_table_lookup_node (hash_table, key);

   476   if (*node)

   477     {

   478       dest = *node;

   479       (*node) = dest->next;

   480       g_hash_node_destroy (dest, NULL, NULL);

   481       hash_table->nnodes--;

   482   

   483       G_HASH_TABLE_RESIZE (hash_table);

   484 

   485       return TRUE;

   486     }

   487 

   488   return FALSE;

   489 }

   490 

   491 /**

   492  * g_hash_table_foreach_remove:

   493  * @hash_table: a #GHashTable.

   494  * @func: the function to call for each key/value pair.

   495  * @user_data: user data to pass to the function.

   496  * 

   497  * Calls the given function for each key/value pair in the #GHashTable.

   498  * If the function returns %TRUE, then the key/value pair is removed from the

   499  * #GHashTable. If you supplied key or value destroy functions when creating

   500  * the #GHashTable, they are used to free the memory allocated for the removed

   501  * keys and values.

   502  * 

   503  * Return value: the number of key/value pairs removed.

   504  **/

   505 EXPORT_C guint

   506 g_hash_table_foreach_remove (GHashTable	*hash_table,

   507 			     GHRFunc	 func,

   508 			     gpointer	 user_data)

   509 {

   510   g_return_val_if_fail (hash_table != NULL, 0);

   511   g_return_val_if_fail (func != NULL, 0);

   512   

   513   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, TRUE);

   514 }

   515 

   516 /**

   517  * g_hash_table_foreach_steal:

   518  * @hash_table: a #GHashTable.

   519  * @func: the function to call for each key/value pair.

   520  * @user_data: user data to pass to the function.

   521  * 

   522  * Calls the given function for each key/value pair in the #GHashTable.

   523  * If the function returns %TRUE, then the key/value pair is removed from the

   524  * #GHashTable, but no key or value destroy functions are called.

   525  * 

   526  * Return value: the number of key/value pairs removed.

   527  **/

   528 EXPORT_C guint

   529 g_hash_table_foreach_steal (GHashTable *hash_table,

   530                             GHRFunc	func,

   531                             gpointer	user_data)

   532 {

   533   g_return_val_if_fail (hash_table != NULL, 0);

   534   g_return_val_if_fail (func != NULL, 0);

   535   

   536   return g_hash_table_foreach_remove_or_steal (hash_table, func, user_data, FALSE);

   537 }

   538 

   539 static guint

   540 g_hash_table_foreach_remove_or_steal (GHashTable *hash_table,

   541                                       GHRFunc	  func,

   542                                       gpointer	  user_data,

   543                                       gboolean    notify)

   544 {

   545   GHashNode *node, *prev;

   546   gint i;

   547   guint deleted = 0;

   548   

   549   for (i = 0; i < hash_table->size; i++)

   550     {

   551     restart:

   552       

   553       prev = NULL;

   554       

   555       for (node = hash_table->nodes[i]; node; prev = node, node = node->next)

   556 	{

   557 	  if ((* func) (node->key, node->value, user_data))

   558 	    {

   559 	      deleted += 1;

   560 	      

   561 	      hash_table->nnodes -= 1;

   562 	      

   563 	      if (prev)

   564 		{

   565 		  prev->next = node->next;

   566 		  g_hash_node_destroy (node,

   567 				       notify ? hash_table->key_destroy_func : NULL,

   568 				       notify ? hash_table->value_destroy_func : NULL);

   569 		  node = prev;

   570 		}

   571 	      else

   572 		{

   573 		  hash_table->nodes[i] = node->next;

   574 		  g_hash_node_destroy (node,

   575 				       notify ? hash_table->key_destroy_func : NULL,

   576 				       notify ? hash_table->value_destroy_func : NULL);

   577 		  goto restart;

   578 		}

   579 	    }

   580 	}

   581     }

   582   

   583   G_HASH_TABLE_RESIZE (hash_table);

   584   

   585   return deleted;

   586 }

   587 

   588 /**

   589  * g_hash_table_foreach:

   590  * @hash_table: a #GHashTable.

   591  * @func: the function to call for each key/value pair.

   592  * @user_data: user data to pass to the function.

   593  * 

   594  * Calls the given function for each of the key/value pairs in the

   595  * #GHashTable.  The function is passed the key and value of each

   596  * pair, and the given @user_data parameter.  The hash table may not

   597  * be modified while iterating over it (you can't add/remove

   598  * items). To remove all items matching a predicate, use

   599  * g_hash_table_foreach_remove().

   600  **/

   601 EXPORT_C void

   602 g_hash_table_foreach (GHashTable *hash_table,

   603 		      GHFunc	  func,

   604 		      gpointer	  user_data)

   605 {

   606   GHashNode *node;

   607   gint i;

   608   

   609   g_return_if_fail (hash_table != NULL);

   610   g_return_if_fail (func != NULL);

   611   

   612   for (i = 0; i < hash_table->size; i++)

   613     for (node = hash_table->nodes[i]; node; node = node->next)

   614       (* func) (node->key, node->value, user_data);

   615 }

   616 

   617 /**

   618  * g_hash_table_find:

   619  * @hash_table: a #GHashTable.

   620  * @predicate:  function to test the key/value pairs for a certain property.

   621  * @user_data:  user data to pass to the function.

   622  * 

   623  * Calls the given function for key/value pairs in the #GHashTable until 

   624  * @predicate returns %TRUE.  The function is passed the key and value of 

   625  * each pair, and the given @user_data parameter. The hash table may not

   626  * be modified while iterating over it (you can't add/remove items). 

   627  *

   628  * Return value: The value of the first key/value pair is returned, for which 

   629  * func evaluates to %TRUE. If no pair with the requested property is found, 

   630  * %NULL is returned.

   631  *

   632  * Since: 2.4

   633  **/

   634 EXPORT_C gpointer

   635 g_hash_table_find (GHashTable	   *hash_table,

   636                    GHRFunc	    predicate,

   637                    gpointer	    user_data)

   638 {

   639   GHashNode *node;

   640   gint i;

   641   

   642   g_return_val_if_fail (hash_table != NULL, NULL);

   643   g_return_val_if_fail (predicate != NULL, NULL);

   644   

   645   for (i = 0; i < hash_table->size; i++)

   646     for (node = hash_table->nodes[i]; node; node = node->next)

   647       if (predicate (node->key, node->value, user_data))

   648         return node->value;       

   649   return NULL;

   650 }

   651 

   652 /**

   653  * g_hash_table_size:

   654  * @hash_table: a #GHashTable.

   655  * 

   656  * Returns the number of elements contained in the #GHashTable.

   657  * 

   658  * Return value: the number of key/value pairs in the #GHashTable.

   659  **/

   660 EXPORT_C guint

   661 g_hash_table_size (GHashTable *hash_table)

   662 {

   663   g_return_val_if_fail (hash_table != NULL, 0);

   664   

   665   return hash_table->nnodes;

   666 }

   667 

   668 static void

   669 g_hash_table_resize (GHashTable *hash_table)

   670 {

   671   GHashNode **new_nodes;

   672   GHashNode *node;

   673   GHashNode *next;

   674   guint hash_val;

   675   gint new_size;

   676   gint i;

   677 

   678   new_size = g_spaced_primes_closest (hash_table->nnodes);

   679   new_size = CLAMP (new_size, HASH_TABLE_MIN_SIZE, HASH_TABLE_MAX_SIZE);

   680   new_nodes = g_new0 (GHashNode*, new_size);

   681   

   682   for (i = 0; i < hash_table->size; i++)

   683     for (node = hash_table->nodes[i]; node; node = next)

   684       {

   685 	next = node->next;

   686 

   687 	hash_val = (* hash_table->hash_func) (node->key) % new_size;

   688 

   689 	node->next = new_nodes[hash_val];

   690 	new_nodes[hash_val] = node;

   691       }

   692   

   693   g_free (hash_table->nodes);

   694   hash_table->nodes = new_nodes;

   695   hash_table->size = new_size;

   696 }

   697 

   698 static GHashNode*

   699 g_hash_node_new (gpointer key,

   700 		 gpointer value)

   701 {

   702   GHashNode *hash_node = g_slice_new (GHashNode);

   703   

   704   hash_node->key = key;

   705   hash_node->value = value;

   706   hash_node->next = NULL;

   707   

   708   return hash_node;

   709 }

   710 

   711 static void

   712 g_hash_node_destroy (GHashNode      *hash_node,

   713 		     GDestroyNotify  key_destroy_func,

   714 		     GDestroyNotify  value_destroy_func)

   715 {

   716   if (key_destroy_func)

   717     key_destroy_func (hash_node->key);

   718   if (value_destroy_func)

   719     value_destroy_func (hash_node->value);

   720   g_slice_free (GHashNode, hash_node);

   721 }

   722 

   723 static void

   724 g_hash_nodes_destroy (GHashNode *hash_node,

   725 		      GFreeFunc  key_destroy_func,

   726 		      GFreeFunc  value_destroy_func)

   727 {

   728   while (hash_node)

   729     {

   730       GHashNode *next = hash_node->next;

   731       if (key_destroy_func)

   732 	key_destroy_func (hash_node->key);

   733       if (value_destroy_func)

   734 	value_destroy_func (hash_node->value);

   735       g_slice_free (GHashNode, hash_node);

   736       hash_node = next;

   737     }

   738 }

   739 

   740 

   741 #define __G_HASH_C__

   742 #include "galiasdef.c"