git.sur5r.net Git - cc65/blob - src/common/hashtab.h

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 hashtab.h                                 */
   4 /*                                                                           */
   5 /*                            Generic hash table                             */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2003-2008 Ullrich von Bassewitz                                       */
  10 /*               Roemerstrasse 52                                            */
  11 /*               D-70794 Filderstadt                                         */
  12 /* EMail:        uz@cc65.org                                                 */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 #ifndef HASHTAB_H
  37 #define HASHTAB_H
  38
  39
  40
  41 /* common */
  42 #include "inline.h"
  43 #include "xmalloc.h"
  44
  45
  46
  47 /*****************************************************************************/
  48 /*                                   Data                                    */
  49 /*****************************************************************************/
  50
  51
  52
  53 /* Hash table node */
  54 typedef struct HashNode HashNode;
  55 struct HashNode {
  56     HashNode*           Next;           /* Next entry in hash list */
  57     struct HashTable*   Owner;          /* Owner table */
  58     unsigned            Hash;           /* The full hash value */
  59     void*               Entry;          /* Pointer to user entry data */
  60 };
  61
  62 #define STATIC_HASHNODE_INITIALIZER(Entry) { 0, 0, 0, Entry }
  63
  64 /* Hash table functions */
  65 typedef struct HashFunctions HashFunctions;
  66 struct HashFunctions {
  67
  68     unsigned (*GenHash) (const void* Key);
  69     /* Generate the hash over a key. */
  70
  71     const void* (*GetKey) (void* Entry);
  72     /* Given a pointer to the user entry data, return a pointer to the key */
  73
  74     HashNode* (*GetHashNode) (void* Entry);
  75     /* Given a pointer to the user entry data, return a pointer to the hash node */
  76
  77     int (*Compare) (const void* Key1, const void* Key2);
  78     /* Compare two keys. The function must return a value less than zero if
  79      * Key1 is smaller than Key2, zero if both are equal, and a value greater
  80      * than zero if Key1 is greater then Key2.
  81      */
  82 };
  83
  84 /* Hash table */
  85 typedef struct HashTable HashTable;
  86 struct HashTable {
  87     unsigned                    Slots;  /* Number of table slots */
  88     unsigned                    Count;  /* Number of table entries */
  89     HashNode**                  Table;  /* Table, dynamically allocated */
  90     const HashFunctions*        Func;   /* Table functions */
  91 };
  92
  93 #define STATIC_HASHTABLE_INITIALIZER(Slots, Func)   { Slots, 0, 0, Func }
  94
  95
  96
  97 /*****************************************************************************/
  98 /*                              struct HashNode                              */
  99 /*****************************************************************************/
 100
 101
 102
 103 #if defined(HAVE_INLINE)
 104 INLINE void InitHashNode (HashNode* N, void* Entry)
 105 /* Initialize a hash node. */
 106 {
 107     N->Next     = 0;
 108     N->Owner    = 0;
 109     N->Entry    = Entry;
 110 }
 111 #else
 112 #define InitHashNode(N, E)      \
 113     (N)->Next   = 0,            \
 114     (N)->Owner  = 0,            \
 115     (N)->Entry  = (E)
 116 #endif
 117
 118 #if defined(HAVE_INLINE)
 119 INLINE void* HN_GetEntry (HashNode* N)
 120 /* Get the entry from a hash node */
 121 {
 122     return N->Entry;
 123 }
 124 #else
 125 #define HN_GetEntry(N)          (N)->Entry
 126 #endif
 127
 128
 129
 130 /*****************************************************************************/
 131 /*                             struct HashTable                              */
 132 /*****************************************************************************/
 133
 134
 135
 136 #if defined(HAVE_INLINE)
 137 INLINE HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
 138 /* Initialize a hash table and return it */
 139 {
 140     /* Initialize the fields */
 141     T->Slots    = Slots;
 142     T->Count    = 0;
 143     T->Table    = 0;
 144     T->Func     = Func;
 145
 146     /* Return the initialized table */
 147     return T;
 148 }
 149 #else
 150 #define InitHashTable(T, Slots, Func)   \
 151     (T)->Slots  = (Slots),              \
 152     (T)->Count  = 0,                    \
 153     (T)->Table  = 0,                    \
 154     (T)->Func   = (Func),               \
 155     (T)
 156 #endif
 157
 158 #if defined(HAVE_INLINE)
 159 INLINE void DoneHashTable (HashTable* T)
 160 /* Destroy the contents of a hash table. Note: This will not free the entries
 161  * in the table!
 162  */
 163 {
 164     /* Just free the array with the table pointers */
 165     xfree (T->Table);
 166 }
 167 #else
 168 #define DoneHashTable(T)        xfree ((T)->Table)
 169 #endif
 170
 171 #if defined(HAVE_INLINE)
 172 INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func)
 173 /* Create a new hash table and return it. */
 174 {
 175     /* Allocate memory, initialize and return it */
 176     return InitHashTable (xmalloc (sizeof (HashTable)), Slots, Func);
 177 }
 178 #else
 179 #define NewHashTable(Slots, Func) InitHashTable(xmalloc (sizeof (HashTable)), Slots, Func)
 180 #endif
 181
 182 void FreeHashTable (HashTable* T);
 183 /* Free a hash table. Note: This will not free the entries in the table! */
 184
 185 HashNode* HT_Find (const HashTable* T, const void* Key);
 186 /* Find the node with the given key*/
 187
 188 HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash);
 189 /* Find the node with the given key. Differs from HT_Find in that the hash
 190  * for the key is precalculated and passed to the function.
 191  */
 192
 193 void* HT_FindEntry (const HashTable* T, const void* Key);
 194 /* Find the node with the given key and return the corresponding entry */
 195
 196 void HT_Insert (HashTable* T, HashNode* N);
 197 /* Insert a node into the given hash table */
 198
 199 void HT_InsertEntry (HashTable* T, void* Entry);
 200 /* Insert an entry into the given hash table */
 201
 202 void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data);
 203 /* Walk over all nodes of a hash table. For each node, the user supplied
 204  * function F is called, passing a pointer to the entry, and the data pointer
 205  * passed to HT_Walk by the caller.
 206  */
 207
 208
 209
 210 /* End of hashtab.h */
 211
 212 #endif
 213
 214
 215