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, int numbucks, void *mem)
  13 {
  14         table->numbuckets = numbucks;
  15         table->bucket = (bucket_t **)mem;
  16 }
  17
  18 int Hash_Key(const char *name, 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 (int)(key%modulus);
  25 }
  26 int Hash_KeyInsensative(const char *name, 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 (int)(key%modulus);
  38 }
  39
  40 void *Hash_Get(hashtable_t *table, const char *name)
  41 {
  42         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         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, int key)
  73 {
  74         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 void *Hash_GetNext(hashtable_t *table, char *name, void *old)
  89 {
  90         int bucknum = Hash_Key(name, table->numbuckets);
  91         bucket_t *buck;
  92
  93         buck = table->bucket[bucknum];
  94
  95         while(buck)
  96         {
  97                 if (!STRCMP(name, buck->key.string))
  98                 {
  99                         if (buck->data == old)  //found the old one
 100                                 break;
 101                 }
 102
 103                 buck = buck->next;
 104         }
 105         if (!buck)
 106                 return NULL;
 107
 108         buck = buck->next;//don't return old
 109         while(buck)
 110         {
 111                 if (!STRCMP(name, buck->key.string))
 112                         return buck->data;
 113
 114                 buck = buck->next;
 115         }
 116         return NULL;
 117 }
 118 void *Hash_GetNextInsensative(hashtable_t *table, char *name, void *old)
 119 {
 120         int bucknum = Hash_KeyInsensative(name, table->numbuckets);
 121         bucket_t *buck;
 122
 123         buck = table->bucket[bucknum];
 124
 125         while(buck)
 126         {
 127                 if (!STRCMP(name, buck->key.string))
 128                 {
 129                         if (buck->data == old)  //found the old one
 130                                 break;
 131                 }
 132
 133                 buck = buck->next;
 134         }
 135         if (!buck)
 136                 return NULL;
 137
 138         buck = buck->next;//don't return old
 139         while(buck)
 140         {
 141                 if (!STRCMP(name, buck->key.string))
 142                         return buck->data;
 143
 144                 buck = buck->next;
 145         }
 146         return NULL;
 147 }
 148
 149
 150 void *Hash_Add(hashtable_t *table, char *name, void *data, bucket_t *buck)
 151 {
 152         int bucknum = Hash_Key(name, table->numbuckets);
 153
 154         buck->data = data;
 155         buck->key.string = name;
 156         buck->next = table->bucket[bucknum];
 157         table->bucket[bucknum] = buck;
 158
 159         return buck;
 160 }
 161 void *Hash_AddInsensative(hashtable_t *table, char *name, void *data, bucket_t *buck)
 162 {
 163         int bucknum = Hash_KeyInsensative(name, table->numbuckets);
 164
 165         buck->data = data;
 166         buck->key.string = name;
 167         buck->next = table->bucket[bucknum];
 168         table->bucket[bucknum] = buck;
 169
 170         return buck;
 171 }
 172 void *Hash_AddKey(hashtable_t *table, int key, void *data, bucket_t *buck)
 173 {
 174         int bucknum = key%table->numbuckets;
 175
 176         buck->data = data;
 177         buck->key.value = key;
 178         buck->next = table->bucket[bucknum];
 179         table->bucket[bucknum] = buck;
 180
 181         return buck;
 182 }
 183
 184 void Hash_Remove(hashtable_t *table, char *name)
 185 {
 186         int bucknum = Hash_Key(name, table->numbuckets);
 187         bucket_t *buck;
 188
 189         buck = table->bucket[bucknum];
 190         if(!buck)
 191                 return;
 192
 193         if (!STRCMP(name, buck->key.string))
 194         {
 195                 table->bucket[bucknum] = buck->next;
 196                 return;
 197         }
 198
 199
 200         while(buck->next)
 201         {
 202                 if (!STRCMP(name, buck->next->key.string))
 203                 {
 204                         buck->next = buck->next->next;
 205                         return;
 206                 }
 207
 208                 buck = buck->next;
 209         }
 210         return;
 211 }
 212
 213 void Hash_RemoveData(hashtable_t *table, char *name, void *data)
 214 {
 215         int bucknum = Hash_Key(name, table->numbuckets);
 216         bucket_t *buck;
 217
 218         buck = table->bucket[bucknum];
 219         if(!buck)
 220                 return;
 221
 222         if (buck->data == data)
 223                 if (!STRCMP(name, buck->key.string))
 224                 {
 225                         table->bucket[bucknum] = buck->next;
 226                         return;
 227                 }
 228
 229
 230         while(buck->next)
 231         {
 232                 if (buck->next->data == data)
 233                         if (!STRCMP(name, buck->next->key.string))
 234                         {
 235                                 buck->next = buck->next->next;
 236                                 return;
 237                         }
 238
 239                 buck = buck->next;
 240         }
 241         return;
 242 }
 243
 244
 245 void Hash_RemoveKey(hashtable_t *table, int key)
 246 {
 247         int bucknum = key%table->numbuckets;
 248         bucket_t *buck;
 249
 250         buck = table->bucket[bucknum];
 251         if(!buck)
 252                 return;
 253
 254         if (buck->key.value == key)
 255         {
 256                 table->bucket[bucknum] = buck->next;
 257                 return;
 258         }
 259
 260
 261         while(buck->next)
 262         {
 263                 if (buck->next->key.value == key)
 264                 {
 265                         buck->next = buck->next->next;
 266                         return;
 267                 }
 268
 269                 buck = buck->next;
 270         }
 271         return;
 272 }