mono/utils/mono-internal-hash.h

   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 #ifndef __MONO_UTILS_MONO_INTERNAL_HASH__
  12 #define __MONO_UTILS_MONO_INTERNAL_HASH__
  13
  14 /* A MonoInternalHashTable is a hash table that does not allocate hash
  15    nodes.  It can be used if the following conditions are fulfilled:
  16
  17    * The key is contained (directly or indirectly) in the value.
  18
  19    * Each value is in at most one internal hash table at the same
  20      time.
  21
  22    The value data structure must then be extended to contain a
  23    pointer, used by the internal hash table to chain values in the
  24    same bucket.
  25
  26    Apart from the hash function, two other functions must be provided,
  27    namely for extracting the key out of a value, and for getting the
  28    next value pointer.  The latter must actually return a pointer to
  29    the next value pointer, because the internal hash table must be
  30    able to modify it.
  31
  32    See the class_cache internal hash table in MonoImage for an
  33    example.
  34 */
  35
  36 typedef struct _MonoInternalHashTable MonoInternalHashTable;
  37
  38 typedef gpointer (*MonoInternalHashKeyExtractFunc) (gpointer value);
  39 typedef gpointer* (*MonoInternalHashNextValueFunc) (gpointer value);
  40
  41 struct _MonoInternalHashTable
  42 {
  43         GHashFunc hash_func;
  44         MonoInternalHashKeyExtractFunc key_extract;
  45         MonoInternalHashNextValueFunc next_value;
  46         gint size;
  47         gint num_entries;
  48         gpointer *table;
  49 };
  50
  51 void
  52 mono_internal_hash_table_init (MonoInternalHashTable *table,
  53                                GHashFunc hash_func,
  54                                MonoInternalHashKeyExtractFunc key_extract,
  55                                MonoInternalHashNextValueFunc next_value);
  56
  57 void
  58 mono_internal_hash_table_destroy (MonoInternalHashTable *table);
  59
  60 gpointer
  61 mono_internal_hash_table_lookup (MonoInternalHashTable *table, gpointer key);
  62
  63 /* mono_internal_hash_table_insert requires that there is no entry for
  64    key in the hash table.  If you want to change the value for a key
  65    already in the hash table, remove it first and then insert the new
  66    one.
  67
  68    The key pointer is actually only passed here to check a debugging
  69    assertion and to make the API look more familiar. */
  70 void
  71 mono_internal_hash_table_insert (MonoInternalHashTable *table,
  72                                  gpointer key, gpointer value);
  73
  74 void
  75 mono_internal_hash_table_remove (MonoInternalHashTable *table, gpointer key);
  76
  77 #endif