misc/source/fteqcc-src/hash.c

   1 #include "hash.h"
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #ifndef _WIN32
   6 #ifndef stricmp
   7 #define stricmp strcasecmp
   8 #endif
   9 #endif
  10
  11 // hash init assumes we get clean memory
  12 void Hash_InitTable(hashtable_t *table, unsigned int numbucks, void *mem)
  13 {
  14         table->numbuckets = numbucks;
  15         table->bucket = (bucket_t **)mem;
  16 }
  17
  18 unsigned int Hash_Key(const char *name, unsigned int modulus)
  19 {       //fixme: optimize.
  20         unsigned int key;
  21         for (key=0;*name; name++)
  22                 key += ((key<<3) + (key>>28) + *name);
  23
  24         return (key%modulus);
  25 }
  26 unsigned int Hash_KeyInsensative(const char *name, unsigned int modulus)
  27 {       //fixme: optimize.
  28         unsigned int key;
  29         for (key=0;*name; name++)
  30         {
  31                 if (*name >= 'A' && *name <= 'Z')
  32                         key += ((key<<3) + (key>>28) + (*name-'A'+'a'));
  33                 else
  34                         key += ((key<<3) + (key>>28) + *name);
  35         }
  36
  37         return (key%modulus);
  38 }
  39
  40 void *Hash_Get(hashtable_t *table, const char *name)
  41 {
  42         unsigned int bucknum = Hash_Key(name, table->numbuckets);
  43         bucket_t *buck;
  44
  45         buck = table->bucket[bucknum];
  46
  47         while(buck)
  48         {
  49                 if (!STRCMP(name, buck->key.string))
  50                         return buck->data;
  51
  52                 buck = buck->next;
  53         }
  54         return NULL;
  55 }
  56 void *Hash_GetInsensative(hashtable_t *table, const char *name)
  57 {
  58         unsigned int bucknum = Hash_KeyInsensative(name, table->numbuckets);
  59         bucket_t *buck;
  60
  61         buck = table->bucket[bucknum];
  62
  63         while(buck)
  64         {
  65                 if (!stricmp(name, buck->key.string))
  66                         return buck->data;
  67
  68                 buck = buck->next;
  69         }
  70         return NULL;
  71 }
  72 void *Hash_GetKey(hashtable_t *table, unsigned int key)
  73 {
  74         unsigned int bucknum = key%table->numbuckets;
  75         bucket_t *buck;
  76
  77         buck = table->bucket[bucknum];
  78
  79         while(buck)
  80         {
  81                 if (buck->key.value == key)
  82                         return buck->data;
  83
  84                 buck = buck->next;
  85         }
  86         return NULL;
  87 }
  88 /*Does _NOT_ support items that are added with two names*/
  89 void *Hash_GetNextKey(hashtable_t *table, unsigned int key, void *old)
  90 {
  91         unsigned int bucknum = key%table->numbuckets;
  92         bucket_t *buck;
  93
  94         buck = table->bucket[bucknum];
  95
  96         while(buck)
  97         {
  98                 if (buck->data == old)  //found the old one
  99                         break;
 100                 buck = buck->next;
 101         }
 102         if (!buck)
 103                 return NULL;
 104
 105         buck = buck->next;//don't return old
 106         while(buck)
 107         {
 108                 if (buck->key.value == key)
 109                         return buck->data;
 110
 111                 buck = buck->next;
 112         }
 113         return NULL;
 114 }
 115 /*Does _NOT_ support items that are added with two names*/
 116 void *Hash_GetNext(hashtable_t *table, const char *name, void *old)
 117 {
 118         unsigned int bucknum = Hash_Key(name, table->numbuckets);
 119         bucket_t *buck;
 120
 121         buck = table->bucket[bucknum];
 122
 123         while(buck)
 124         {
 125                 if (buck->data == old)  //found the old one
 126 //                      if (!STRCMP(name, buck->key.string))
 127                                 break;
 128                 buck = buck->next;
 129         }
 130         if (!buck)
 131                 return NULL;
 132
 133         buck = buck->next;//don't return old
 134         while(buck)
 135         {
 136                 if (!STRCMP(name, buck->key.string))
 137                         return buck->data;
 138
 139                 buck = buck->next;
 140         }
 141         return NULL;
 142 }
 143 /*Does _NOT_ support items that are added with two names*/
 144 void *Hash_GetNextInsensative(hashtable_t *table, const char *name, void *old)
 145 {
 146         unsigned int bucknum = Hash_KeyInsensative(name, table->numbuckets);
 147         bucket_t *buck;
 148
 149         buck = table->bucket[bucknum];
 150
 151         while(buck)
 152         {
 153                 if (buck->data == old)  //found the old one
 154                 {
 155 //                      if (!stricmp(name, buck->key.string))
 156                                 break;
 157                 }
 158
 159                 buck = buck->next;
 160         }
 161         if (!buck)
 162                 return NULL;
 163
 164         buck = buck->next;//don't return old
 165         while(buck)
 166         {
 167                 if (!stricmp(name, buck->key.string))
 168                         return buck->data;
 169
 170                 buck = buck->next;
 171         }
 172         return NULL;
 173 }
 174
 175
 176 void *Hash_Add(hashtable_t *table, const char *name, void *data, bucket_t *buck)
 177 {
 178         unsigned int bucknum = Hash_Key(name, table->numbuckets);
 179
 180         buck->data = data;
 181         buck->key.string = name;
 182         buck->next = table->bucket[bucknum];
 183         table->bucket[bucknum] = buck;
 184
 185         return buck;
 186 }
 187 void *Hash_AddInsensative(hashtable_t *table, const char *name, void *data, bucket_t *buck)
 188 {
 189         unsigned int bucknum = Hash_KeyInsensative(name, table->numbuckets);
 190
 191         buck->data = data;
 192         buck->key.string = name;
 193         buck->next = table->bucket[bucknum];
 194         table->bucket[bucknum] = buck;
 195
 196         return buck;
 197 }
 198 void *Hash_AddKey(hashtable_t *table, unsigned int key, void *data, bucket_t *buck)
 199 {
 200         unsigned int bucknum = key%table->numbuckets;
 201
 202         buck->data = data;
 203         buck->key.value = key;
 204         buck->next = table->bucket[bucknum];
 205         table->bucket[bucknum] = buck;
 206
 207         return buck;
 208 }
 209
 210 void Hash_Remove(hashtable_t *table, const char *name)
 211 {
 212         unsigned int bucknum = Hash_Key(name, table->numbuckets);
 213         bucket_t *buck;
 214
 215         buck = table->bucket[bucknum];
 216
 217         if (!STRCMP(name, buck->key.string))
 218         {
 219                 table->bucket[bucknum] = buck->next;
 220                 return;
 221         }
 222
 223
 224         while(buck->next)
 225         {
 226                 if (!STRCMP(name, buck->next->key.string))
 227                 {
 228                         buck->next = buck->next->next;
 229                         return;
 230                 }
 231
 232                 buck = buck->next;
 233         }
 234         return;
 235 }
 236
 237 void Hash_RemoveData(hashtable_t *table, const char *name, void *data)
 238 {
 239         unsigned int bucknum = Hash_Key(name, table->numbuckets);
 240         bucket_t *buck;
 241
 242         buck = table->bucket[bucknum];
 243
 244         if (buck->data == data)
 245                 if (!STRCMP(name, buck->key.string))
 246                 {
 247                         table->bucket[bucknum] = buck->next;
 248                         return;
 249                 }
 250
 251
 252         while(buck->next)
 253         {
 254                 if (buck->next->data == data)
 255                         if (!STRCMP(name, buck->next->key.string))
 256                         {
 257                                 buck->next = buck->next->next;
 258                                 return;
 259                         }
 260
 261                 buck = buck->next;
 262         }
 263         return;
 264 }
 265
 266
 267 void Hash_RemoveKey(hashtable_t *table, unsigned int key)
 268 {
 269         unsigned int bucknum = key%table->numbuckets;
 270         bucket_t *buck;
 271
 272         buck = table->bucket[bucknum];
 273
 274         if (buck->key.value == key)
 275         {
 276                 table->bucket[bucknum] = buck->next;
 277                 return;
 278         }
 279
 280
 281         while(buck->next)
 282         {
 283                 if (buck->next->key.value == key)
 284                 {
 285                         buck->next = buck->next->next;
 286                         return;
 287                 }
 288
 289                 buck = buck->next;
 290         }
 291         return;
 292 }