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