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

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                 hashtab.c                                 */
   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 /* common */
  37 #include "check.h"
  38 #include "hashtab.h"
  39 #include "xmalloc.h"
  40
  41
  42
  43 /*****************************************************************************/
  44 /*                             struct HashTable                              */
  45 /*****************************************************************************/
  46
  47
  48
  49 HashTable* InitHashTable (HashTable* T, unsigned Slots, const HashFunctions* Func)
  50 /* Initialize a hash table and return it */
  51 {
  52     /* Initialize the fields */
  53     T->Slots    = Slots;
  54     T->Count    = 0;
  55     T->Table    = 0;
  56     T->Func     = Func;
  57
  58     /* Return the initialized table */
  59     return T;
  60 }
  61
  62
  63
  64 void DoneHashTable (HashTable* T)
  65 /* Destroy the contents of a hash table. Note: This will not free the entries
  66  * in the table!
  67  */
  68 {
  69     /* Just free the array with the table pointers */
  70     xfree (T->Table);
  71 }
  72
  73
  74
  75 void FreeHashTable (HashTable* T)
  76 /* Free a hash table. Note: This will not free the entries in the table! */
  77 {
  78     if (T) {
  79         /* Free the contents */
  80         DoneHashTable (T);
  81         /* Free the table structure itself */
  82         xfree (T);
  83     }
  84 }
  85
  86
  87
  88 static void HT_Alloc (HashTable* T)
  89 /* Allocate table memory */
  90 {
  91     unsigned I;
  92
  93     /* Allocate memory */
  94     T->Table = xmalloc (T->Slots * sizeof (T->Table[0]));
  95
  96     /* Initialize the table */
  97     for (I = 0; I < T->Slots; ++I) {
  98         T->Table[I] = 0;
  99     }
 100 }
 101
 102
 103
 104 HashNode* HT_Find (const HashTable* T, const void* Key)
 105 /* Find the node with the given index */
 106 {
 107     /* If we don't have a table, there's nothing to find */
 108     if (T->Table == 0) {
 109         return 0;
 110     }
 111
 112     /* Search for the entry */
 113     return HT_FindHash (T, Key, T->Func->GenHash (Key));
 114 }
 115
 116
 117
 118 HashNode* HT_FindHash (const HashTable* T, const void* Key, unsigned Hash)
 119 /* Find the node with the given key. Differs from HT_Find in that the hash
 120  * for the key is precalculated and passed to the function.
 121  */
 122 {
 123     HashNode* N;
 124
 125     /* If we don't have a table, there's nothing to find */
 126     if (T->Table == 0) {
 127         return 0;
 128     }
 129
 130     /* Search for the entry in the given chain */
 131     N = T->Table[Hash % T->Slots];
 132     while (N) {
 133
 134         /* First compare the full hash, to avoid calling the compare function
 135          * if it is not really necessary.
 136          */
 137         if (N->Hash == Hash &&
 138             T->Func->Compare (Key, T->Func->GetKey (N)) == 0) {
 139             /* Found */
 140             break;
 141         }
 142
 143         /* Not found, next entry */
 144         N = N->Next;
 145     }
 146
 147     /* Return what we found */
 148     return N;
 149 }
 150
 151
 152
 153 void* HT_FindEntry (const HashTable* T, const void* Key)
 154 /* Find the node with the given index and return the corresponding entry */
 155 {
 156     /* Since the HashEntry must be first member, we can use HT_Find here */
 157     return HT_Find (T, Key);
 158 }
 159
 160
 161
 162 void HT_Insert (HashTable* T, HashNode* N)
 163 /* Insert a node into the given hash table */
 164 {
 165     unsigned RHash;
 166
 167     /* If we don't have a table, we need to allocate it now */
 168     if (T->Table == 0) {
 169         HT_Alloc (T);
 170     }
 171
 172     /* Generate the hash over the node key. */
 173     N->Hash = T->Func->GenHash (T->Func->GetKey (N));
 174
 175     /* Calculate the reduced hash */
 176     RHash = N->Hash % T->Slots;
 177
 178     /* Insert the entry into the correct chain */
 179     N->Next = T->Table[RHash];
 180     T->Table[RHash] = N;
 181
 182     /* One more entry */
 183     ++T->Count;
 184 }
 185
 186
 187
 188 void HT_Remove (HashTable* T, HashNode* N)
 189 /* Remove a node from a hash table. */
 190 {
 191     /* Calculate the reduced hash, which is also the slot number */
 192     unsigned Slot = N->Hash % T->Slots;
 193
 194     /* Remove the entry from the single linked list */
 195     HashNode** Q = &T->Table[Slot];
 196     while (1) {
 197         /* If the pointer is NULL, the node is not in the table which we will
 198          * consider a serious error.
 199          */
 200         CHECK (*Q != 0);
 201         if (*Q == N) {
 202             /* Found - remove it */
 203             *Q = N->Next;
 204             break;
 205         }
 206         /* Next node */
 207         Q = &(*Q)->Next;
 208     }
 209 }
 210
 211
 212
 213 void HT_InsertEntry (HashTable* T, void* Entry)
 214 /* Insert an entry into the given hash table */
 215 {
 216     /* Since the hash node must be first member, Entry is also the pointer to
 217      * the hash node.
 218      */
 219     HT_Insert (T, Entry);
 220 }
 221
 222
 223
 224 void HT_RemoveEntry (HashTable* T, void* Entry)
 225 /* Remove an entry from the given hash table */
 226 {
 227     /* The entry is the first member, so we can just convert the pointer */
 228     HT_Remove (T, Entry);
 229 }
 230
 231
 232
 233 void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data)
 234 /* Walk over all nodes of a hash table. For each node, the user supplied
 235  * function F is called, passing a pointer to the entry, and the data pointer
 236  * passed to HT_Walk by the caller.
 237  */
 238 {
 239     unsigned I;
 240
 241     /* If we don't have a table there are no entries to walk over */
 242     if (T->Table == 0) {
 243         return;
 244     }
 245
 246     /* Walk over all chains */
 247     for (I = 0; I < T->Slots; ++I) {
 248
 249         /* Get the pointer to the first entry of the hash chain */
 250         HashNode* N = T->Table[I];
 251
 252         /* Walk over all entries in this chain */
 253         while (N) {
 254             /* Call the user function. N is also the pointer to the entry */
 255             F (N, Data);
 256             /* Next node in chain */
 257             N = N->Next;
 258         }
 259
 260     }
 261 }
 262
 263
 264