mono/utils/mono-internal-hash.c

   1 /*
   2  * mono-internal-hash.c: A hash table which uses the values themselves as nodes.
   3  *
   4  * Author:
   5  *   Mark Probst (mark.probst@gmail.com)
   6  *
   7  * (C) 2007 Novell, Inc.
   8  *
   9  */
  10
  11 #include <config.h>
  12 #include <glib.h>
  13 #include <mono/utils/mono-compiler.h>
  14 #include <mono/utils/mono-internal-hash.h>
  15
  16 #define MIN_SIZE        11
  17 #define HASH(k,f,s)     ((f)((k)) % (s))
  18
  19 void
  20 mono_internal_hash_table_init (MonoInternalHashTable *table,
  21                                GHashFunc hash_func,
  22                                MonoInternalHashKeyExtractFunc key_extract,
  23                                MonoInternalHashNextValueFunc next_value)
  24 {
  25         table->hash_func = hash_func;
  26         table->key_extract = key_extract;
  27         table->next_value = next_value;
  28
  29         table->size = MIN_SIZE;
  30         table->num_entries = 0;
  31         table->table = g_new0 (gpointer, table->size);
  32 }
  33
  34 void
  35 mono_internal_hash_table_destroy (MonoInternalHashTable *table)
  36 {
  37         g_free (table->table);
  38         table->table = NULL;
  39 }
  40
  41 gpointer
  42 mono_internal_hash_table_lookup (MonoInternalHashTable *table, gpointer key)
  43 {
  44         gpointer value;
  45
  46         g_assert (table->table != NULL);
  47
  48         for (value = table->table [HASH (key, table->hash_func, table->size)];
  49              value != NULL;
  50              value = *(table->next_value (value))) {
  51                 if (table->key_extract (value) == key)
  52                         return value;
  53         }
  54         return NULL;
  55 }
  56
  57 static void
  58 resize_if_needed (MonoInternalHashTable *table)
  59 {
  60         gpointer *new_table;
  61         gint new_size;
  62         gint i;
  63
  64         if (table->num_entries < table->size * 3)
  65                 return;
  66
  67         new_size = g_spaced_primes_closest (table->num_entries);
  68         new_table = g_new0 (gpointer, new_size);
  69
  70         for (i = 0; i < table->size; ++i) {
  71                 while (table->table[i] != NULL) {
  72                         gpointer value;
  73                         gint hash;
  74
  75                         value = table->table [i];
  76                         table->table [i] = *(table->next_value (value));
  77
  78                         hash = HASH (table->key_extract (value), table->hash_func, new_size);
  79                         *(table->next_value (value)) = new_table [hash];
  80                         new_table [hash] = value;
  81                 }
  82         }
  83
  84         g_free (table->table);
  85
  86         table->size = new_size;
  87         table->table = new_table;
  88 }
  89
  90 void
  91 mono_internal_hash_table_insert (MonoInternalHashTable *table,
  92                                  gpointer key, gpointer value)
  93 {
  94         gint hash = HASH (key, table->hash_func, table->size);
  95
  96         g_assert (table->key_extract(value) == key);
  97         g_assert (*(table->next_value (value)) == NULL);
  98         g_assert (mono_internal_hash_table_lookup (table, key) == NULL);
  99
 100         *(table->next_value (value)) = table->table[hash];
 101         table->table [hash] = value;
 102
 103         ++table->num_entries;
 104
 105         resize_if_needed (table);
 106 }
 107
 108 void
 109 mono_internal_hash_table_remove (MonoInternalHashTable *table, gpointer key)
 110 {
 111         gint hash = HASH (key, table->hash_func, table->size);
 112         gpointer *value;
 113
 114         for (value = &table->table [hash];
 115              *value != NULL;
 116              value = table->next_value (*value)) {
 117                 if (table->key_extract (*value) == key)
 118                 {
 119                         *value = *(table->next_value (*value));
 120                         --table->num_entries;
 121                         return;
 122                 }
 123         }
 124
 125         g_assert (0);
 126 }