mono/utils/mono-internal-hash.h

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