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-2011, 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. NOTE: This structure must be the first member of a struct
  54 ** that is hashed by the module. Having it first allows to omit a pointer to
  55 ** the entry itself, because the C standard guarantees that a pointer to a
  56 ** struct can be converted to its first member.
  57 */
  58 typedef struct HashNode HashNode;
  59 struct HashNode {
  60     HashNode*           Next;           /* Next entry in hash list */
  61     unsigned            Hash;           /* The full hash value */
  62 };
  63
  64 #define STATIC_HASHNODE_INITIALIZER     { 0, 0, 0 }
  65
  66 /* Hash table functions */
  67 typedef struct HashFunctions HashFunctions;
  68 struct HashFunctions {
  69
  70     unsigned (*GenHash) (const void* Key);
  71     /* Generate the hash over a key. */
  72
  73     const void* (*GetKey) (const void* Entry);
  74     /* Given a pointer to the user entry data, return a pointer to the key */
  75
  76     int (*Compare) (const void* Key1, const void* Key2);
  77     /* Compare two keys. The function must return a value less than zero if
  78     ** Key1 is smaller than Key2, zero if both are equal, and a value greater
  79     ** than zero if Key1 is greater then Key2.
  80     */
  81 };
  82
  83 /* Hash table */
  84 typedef struct HashTable HashTable;
  85 struct HashTable {
  86     unsigned                    Slots;  /* Number of table slots */
  87     unsigned                    Count;  /* Number of table entries */
  88     HashNode**                  Table;  /* Table, dynamically allocated */
  89     const HashFunctions*        Func;   /* Table functions */
  90 };
  91
  92 #define STATIC_HASHTABLE_INITIALIZER(Slots, Func)   { Slots, 0, 0, Func }
  93
  94
  95
  96 /*****************************************************************************/
  97 /*                              struct HashNode                              */
  98 /*****************************************************************************/
  99
 100
 101
 102 #if defined(HAVE_INLINE)
 103 INLINE void InitHashNode (HashNode* N)
 104 /* Initialize a hash node. */
 105 {
 106     N->Next     = 0;
 107 }
 108 #else
 109 #define InitHashNode(N)         do { (N)->Next   = 0; } while (0)
 110 #endif
 111
 112
 113
 114 /*****************************************************************************/
 115 /*                             struct HashTable                              */
 116 /*****************************************************************************/
 117
 118
 119
 120 HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func);
 121 /* Initialize a hash table and return it */
 122
 123 void DoneHashTable (HashTable* T);
 124 /* Destroy the contents of a hash table. Note: This will not free the entries
 125 ** in the table!
 126 */
 127
 128 #if defined(HAVE_INLINE)
 129 INLINE HashTable* NewHashTable (unsigned Slots, const HashFunctions* Func)
 130 /* Create a new hash table and return it. */
 131 {
 132     /* Allocate memory, initialize and return it */
 133     return InitHashTable (xmalloc (sizeof (HashTable)), Slots, Func);
 134 }
 135 #else
 136 #define NewHashTable(Slots, Func) InitHashTable(xmalloc (sizeof (HashTable)), Slots, Func)
 137 #endif
 138
 139 void FreeHashTable (HashTable* T);
 140 /* Free a hash table. Note: This will not free the entries in the table! */
 141
 142 #if defined(HAVE_INLINE)
 143 INLINE unsigned HT_GetCount (const HashTable* T)
 144 /* Return the number of items in the table. */
 145 {
 146     return T->Count;
 147 }
 148 #else
 149 #define HT_GetCount(T)  ((T)->Count)
 150 #endif
 151
 152 HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash);
 153 /* Find the node with the given key. Differs from HT_Find in that the hash
 154 ** for the key is precalculated and passed to the function.
 155 */
 156
 157 void* HT_Find (const HashTable* T, const void* Key);
 158 /* Find the entry with the given key and return it */
 159
 160 void HT_Insert (HashTable* T, void* Entry);
 161 /* Insert an entry into the given hash table */
 162
 163 void HT_Remove (HashTable* T, void* Entry);
 164 /* Remove an entry from the given hash table */
 165
 166 void HT_Walk (HashTable* T, int (*F) (void* Entry, void* Data), void* Data);
 167 /* Walk over all nodes of a hash table, optionally deleting entries from the
 168 ** table. For each node, the user supplied function F is called, passing a
 169 ** pointer to the entry, and the data pointer passed to HT_Walk by the caller.
 170 ** If F returns true, the node is deleted from the hash table otherwise it's
 171 ** left in place. While deleting the node, the node is not accessed, so it is
 172 ** safe for F to free the memory associcated with the entry.
 173 */
 174
 175
 176
 177 /* End of hashtab.h */
 178
 179 #endif