mono/utils/mono-internal-hash.c

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