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      Ullrich von Bassewitz                                       */
  10 /*               Römerstrasse 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 "hashtab.h"
  38 #include "xmalloc.h"
  39
  40
  41
  42 /*****************************************************************************/
  43 /*                             struct HashTable                              */
  44 /*****************************************************************************/
  45
  46
  47
  48 void FreeHashTable (HashTable* T)
  49 /* Free a hash table. Note: This will not free the entries in the table! */
  50 {
  51     if (T) {
  52         /* Free the contents */
  53         DoneHashTable (T);
  54         /* Free the table structure itself */
  55         xfree (T);
  56     }
  57 }
  58
  59
  60
  61 static void HT_Alloc (HashTable* T)
  62 /* Allocate table memory */
  63 {
  64     unsigned I;
  65
  66     /* Allocate memory */
  67     T->Table = xmalloc (T->Slots * sizeof (T->Table[0]));
  68
  69     /* Initialize the table */
  70     for (I = 0; I < T->Slots; ++I) {
  71         T->Table[I] = 0;
  72     }
  73 }
  74
  75
  76
  77 HashNode* HT_Find (const HashTable* T, const void* Key)
  78 /* Find the node with the given index */
  79 {
  80     unsigned  Hash;
  81     HashNode* N;
  82
  83     /* If we don't have a table, there's nothing to find */
  84     if (T->Table == 0) {
  85         return 0;
  86     }
  87
  88     /* Generate the hash over the index */
  89     Hash = T->Func->GenHash (Key);
  90
  91     /* Search for the entry in the given chain */
  92     N = T->Table[Hash % T->Slots];
  93     while (N) {
  94
  95         /* First compare the full hash, to avoid calling the compare function
  96          * if it is not really necessary.
  97          */
  98         if (N->Hash == Hash &&
  99             T->Func->Compare (Key, T->Func->GetIndex (N->Entry))) {
 100             /* Found */
 101             break;
 102         }
 103
 104         /* Not found, next entry */
 105         N = N->Next;
 106     }
 107
 108     /* Return what we found */
 109     return N;
 110 }
 111
 112
 113
 114 void* HT_FindEntry (const HashTable* T, const void* Key)
 115 /* Find the node with the given index and return the corresponding entry */
 116 {
 117     /* First, search for the hash node */
 118     HashNode* N = HT_Find (T, Key);
 119
 120     /* Convert the node into an entry if necessary */
 121     return N? N->Entry : 0;
 122 }
 123
 124
 125
 126 void HT_Insert (HashTable* T, HashNode* N)
 127 /* Insert a node into the given hash table */
 128 {
 129     unsigned RHash;
 130
 131     /* If we don't have a table, we need to allocate it now */
 132     if (T->Table == 0) {
 133         HT_Alloc (T);
 134     }
 135
 136     /* Generate the hash for the node contents */
 137     N->Hash = T->Func->GenHash (T->Func->GetIndex (N->Entry));
 138
 139     /* Calculate the reduced hash */
 140     RHash = N->Hash % T->Slots;
 141
 142     /* Insert the entry into the correct chain */
 143     N->Next = T->Table[RHash];
 144     T->Table[RHash] = N;
 145
 146     /* One more entry */
 147     ++T->Count;
 148 }
 149
 150
 151
 152 void HT_InsertEntry (HashTable* T, void* Entry)
 153 /* Insert an entry into the given hash table */
 154 {
 155     HT_Insert (T, T->Func->GetHashNode (Entry));
 156 }
 157
 158
 159
 160 void HT_Walk (HashTable* T, void (*F) (void* Entry, void* Data), void* Data)
 161 /* Walk over all nodes of a hash table. For each node, the user supplied
 162  * function F is called, passing a pointer to the entry, and the data pointer
 163  * passed to HT_Walk by the caller.
 164  */
 165 {
 166     unsigned I;
 167
 168     /* If we don't have a table there are no entries to walk over */
 169     if (T->Table == 0) {
 170         return;
 171     }
 172
 173     /* Walk over all chains */
 174     for (I = 0; I < T->Slots; ++I) {
 175
 176         /* Get the pointer to the first entry of the hash chain */
 177         HashNode* N = T->Table[I];
 178
 179         /* Walk over all entries in this chain */
 180         while (N) {
 181             /* Call the user function */
 182             F (N->Entry, Data);
 183             /* Next node in chain */
 184             N = N->Next;
 185         }
 186
 187     }
 188 }
 189
 190
 191