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_FindHash (const HashTable* T, const void* Key, unsigned Hash)
 105 /* Find the node with the given key. Differs from HT_Find in that the hash
 106  * for the key is precalculated and passed to the function.
 107  */
 108 {
 109     HashNode* N;
 110
 111     /* If we don't have a table, there's nothing to find */
 112     if (T->Table == 0) {
 113         return 0;
 114     }
 115
 116     /* Search for the entry in the given chain */
 117     N = T->Table[Hash % T->Slots];
 118     while (N) {
 119
 120         /* First compare the full hash, to avoid calling the compare function
 121          * if it is not really necessary.
 122          */
 123         if (N->Hash == Hash &&
 124             T->Func->Compare (Key, T->Func->GetKey (N)) == 0) {
 125             /* Found */
 126             break;
 127         }
 128
 129         /* Not found, next entry */
 130         N = N->Next;
 131     }
 132
 133     /* Return what we found */
 134     return N;
 135 }
 136
 137
 138
 139 void* HT_Find (const HashTable* T, const void* Key)
 140 /* Find the entry with the given key and return it */
 141 {
 142     /* Search for the entry */
 143     return HT_FindHash (T, Key, T->Func->GenHash (Key));
 144 }
 145
 146
 147
 148 void HT_Insert (HashTable* T, void* Entry)
 149 /* Insert an entry into the given hash table */
 150 {
 151     HashNode* N;
 152     unsigned RHash;
 153
 154     /* If we don't have a table, we need to allocate it now */
 155     if (T->Table == 0) {
 156         HT_Alloc (T);
 157     }
 158
 159     /* The first member of Entry is also the hash node */
 160     N = Entry;
 161
 162     /* Generate the hash over the node key. */
 163     N->Hash = T->Func->GenHash (T->Func->GetKey (N));
 164
 165     /* Calculate the reduced hash */
 166     RHash = N->Hash % T->Slots;
 167
 168     /* Insert the entry into the correct chain */
 169     N->Next = T->Table[RHash];
 170     T->Table[RHash] = N;
 171
 172     /* One more entry */
 173     ++T->Count;
 174 }
 175
 176
 177
 178 void HT_Remove (HashTable* T, void* Entry)
 179 /* Remove an entry from the given hash table */
 180 {
 181     /* The first member of Entry is also the hash node */
 182     HashNode* N = Entry;
 183
 184     /* Calculate the reduced hash, which is also the slot number */
 185     unsigned Slot = N->Hash % T->Slots;
 186
 187     /* Remove the entry from the single linked list */
 188     HashNode** Q = &T->Table[Slot];
 189     while (1) {
 190         /* If the pointer is NULL, the node is not in the table which we will
 191          * consider a serious error.
 192          */
 193         CHECK (*Q != 0);
 194         if (*Q == N) {
 195             /* Found - remove it */
 196             *Q = N->Next;
 197             --T->Count;
 198             break;
 199         }
 200         /* Next node */
 201         Q = &(*Q)->Next;
 202     }
 203 }
 204
 205
 206
 207 void HT_Walk (HashTable* T, int (*F) (void* Entry, void* Data), void* Data)
 208 /* Walk over all nodes of a hash table, optionally deleting entries from the
 209  * table. For each node, the user supplied function F is called, passing a
 210  * pointer to the entry, and the data pointer passed to HT_Walk by the caller.
 211  * If F returns true, the node is deleted from the hash table otherwise it's
 212  * left in place. While deleting the node, the node is not accessed, so it is
 213  * safe for F to free the memory associcated with the entry.
 214  */
 215 {
 216     unsigned I;
 217
 218     /* If we don't have a table there are no entries to walk over */
 219     if (T->Table == 0) {
 220         return;
 221     }
 222
 223     /* Walk over all chains */
 224     for (I = 0; I < T->Slots; ++I) {
 225
 226         /* Get the pointer to the first entry of the hash chain */
 227         HashNode** Cur = &T->Table[I];
 228
 229         /* Walk over all entries in this chain */
 230         while (*Cur) {
 231             /* Fetch the next node in chain now, because F() may delete it */
 232             HashNode* Next = (*Cur)->Next;
 233             /* Call the user function. N is also the pointer to the entry. If
 234              * the function returns true, the entry is to be deleted.
 235              */
 236             if (F (*Cur, Data)) {
 237                 /* Delete the node from the chain */
 238                 *Cur = Next;
 239                 --T->Count;
 240             } else {
 241                 /* Next node in chain */
 242                 Cur = &(*Cur)->Next;
 243             }
 244         }
 245     }
 246 }