rosapps/smartpdf/fitz/base/base_hash.c

   1 /* Linear probe hash table.
   2  * 2004 (C) Tor Andersson.
   3  * BSD license.
   4  *
   5  * Simple hashtable with open adressing linear probe.
   6  * Unlike text book examples, removing entries works
   7  * correctly in this implementation so it wont start
   8  * exhibiting bad behaviour if entries are inserted
   9  * and removed frequently.
  10  */
  11
  12 #include "fitz-base.h"
  13
  14 enum { MAXKEYLEN = 16 };
  15
  16 typedef struct fz_hashentry_s fz_hashentry;
  17
  18 struct fz_hashentry_s
  19 {
  20         unsigned char key[MAXKEYLEN];
  21         void *val;
  22 };
  23
  24 struct fz_hashtable_s
  25 {
  26         int keylen;
  27         int size;
  28         int load;
  29         fz_hashentry *ents;
  30 };
  31
  32 static unsigned hash(unsigned char *s, int len)
  33 {
  34         unsigned hash = 0;
  35         int i;
  36         for (i = 0; i < len; i++)
  37         {
  38                 hash += s[i];
  39                 hash += (hash << 10);
  40                 hash ^= (hash >> 6);
  41         }
  42         hash += (hash << 3);
  43         hash ^= (hash >> 11);
  44         hash += (hash << 15);
  45         return hash;
  46 }
  47
  48 fz_error *
  49 fz_newhash(fz_hashtable **tablep, int initialsize, int keylen)
  50 {
  51         fz_hashtable *table;
  52
  53         assert(keylen <= MAXKEYLEN);
  54
  55         table = *tablep = fz_malloc(sizeof(fz_hashtable));
  56         if (!table)
  57                 return fz_outofmem;
  58
  59         table->keylen = keylen;
  60         table->size = initialsize;
  61         table->load = 0;
  62
  63         table->ents = fz_malloc(sizeof(fz_hashentry) * table->size);
  64         if (!table->ents)
  65         {
  66                 fz_free(table);
  67                 *tablep = nil;
  68                 return fz_outofmem;
  69         }
  70
  71         memset(table->ents, 0, sizeof(fz_hashentry) * table->size);
  72
  73         return nil;
  74 }
  75
  76 void
  77 fz_emptyhash(fz_hashtable *table)
  78 {
  79         table->load = 0;
  80         memset(table->ents, 0, sizeof(fz_hashentry) * table->size);
  81 }
  82
  83 int
  84 fz_hashlen(fz_hashtable *table)
  85 {
  86         return table->size;
  87 }
  88
  89 void *
  90 fz_hashgetkey(fz_hashtable *table, int idx)
  91 {
  92         return table->ents[idx].key;
  93 }
  94
  95 void *
  96 fz_hashgetval(fz_hashtable *table, int idx)
  97 {
  98         return table->ents[idx].val;
  99 }
 100
 101 void
 102 fz_drophash(fz_hashtable *table)
 103 {
 104         fz_free(table->ents);
 105         fz_free(table);
 106 }
 107
 108 fz_error *
 109 fz_resizehash(fz_hashtable *table, int newsize)
 110 {
 111         fz_error *error;
 112         fz_hashentry *newents;
 113         fz_hashentry *oldents;
 114         int oldload;
 115         int oldsize;
 116         int i;
 117
 118         oldsize = table->size;
 119         oldload = table->load;
 120         oldents = table->ents;
 121
 122         if (newsize < oldload * 8 / 10)
 123                 return fz_throw("rangecheck: resize hash too small");
 124
 125         newents = fz_malloc(sizeof(fz_hashentry) * newsize);
 126         if (!newents)
 127                 return fz_outofmem;
 128
 129         table->size = newsize;
 130         table->load = 0;
 131         table->ents = newents;
 132         memset(table->ents, 0, sizeof(fz_hashentry) * table->size);
 133
 134         for (i = 0; i < oldsize; i++)
 135         {
 136                 if (oldents[i].val)
 137                 {
 138                         error = fz_hashinsert(table, oldents[i].key, oldents[i].val);
 139                         if (error)
 140                         {
 141                                 table->size = oldsize;
 142                                 table->load = oldload;
 143                                 table->ents = oldents;
 144                                 fz_free(newents);
 145                                 return error;
 146                         }
 147                 }
 148         }
 149
 150         fz_free(oldents);
 151         return nil;
 152 }
 153
 154 void *
 155 fz_hashfind(fz_hashtable *table, void *key)
 156 {
 157         fz_hashentry *ents = table->ents;
 158         unsigned size = table->size;
 159         unsigned pos = hash(key, table->keylen) % size;
 160
 161         while (1)
 162         {
 163                 if (!ents[pos].val)
 164                         return nil;
 165
 166                 if (memcmp(key, &ents[pos].key, table->keylen) == 0)
 167                         return ents[pos].val;
 168
 169                 pos = (pos + 1) % size;
 170         }
 171 }
 172
 173 fz_error *
 174 fz_hashinsert(fz_hashtable *table, void *key, void *val)
 175 {
 176         fz_error *error;
 177         fz_hashentry *ents;
 178         unsigned size;
 179         unsigned pos;
 180
 181         if (table->load > table->size * 8 / 10)
 182         {
 183                 error = fz_resizehash(table, table->size * 2);
 184                 if (error)
 185                         return error;
 186         }
 187
 188         ents = table->ents;
 189         size = table->size;
 190         pos = hash(key, table->keylen) % size;
 191
 192         while (1)
 193         {
 194                 if (!ents[pos].val)
 195                 {
 196                         memcpy(ents[pos].key, key, table->keylen);
 197                         ents[pos].val = val;
 198                         table->load ++;
 199                         return nil;
 200                 }
 201
 202                 if (memcmp(key, &ents[pos].key, table->keylen) == 0)
 203                         return fz_throw("rangecheck: overwrite hash slot");
 204
 205                 pos = (pos + 1) % size;
 206         }
 207
 208         return nil;
 209 }
 210
 211 fz_error *
 212 fz_hashremove(fz_hashtable *table, void *key)
 213 {
 214         fz_hashentry *ents = table->ents;
 215         unsigned size = table->size;
 216         unsigned pos = hash(key, table->keylen) % size;
 217         unsigned hole, look, code;
 218
 219         while (1)
 220         {
 221                 if (!ents[pos].val)
 222                         return fz_throw("rangecheck: remove inexistant hash entry");
 223
 224                 if (memcmp(key, &ents[pos].key, table->keylen) == 0)
 225                 {
 226                         ents[pos].val = nil;
 227
 228                         hole = pos;
 229                         look = (hole + 1) % size;
 230
 231                         while (ents[look].val)
 232                         {
 233                                 code = hash(ents[look].key, table->keylen) % size;
 234                                 if ((code <= hole && hole < look) ||
 235                                         (look < code && code <= hole) ||
 236                                         (hole < look && look < code))
 237                                 {
 238                                         ents[hole] = ents[look];
 239                                         ents[look].val = nil;
 240                                         hole = look;
 241                                 }
 242
 243                                 look = (look + 1) % size;
 244                         }
 245
 246                         table->load --;
 247                         return nil;
 248                 }
 249
 250                 pos = (pos + 1) % size;
 251         }
 252 }
 253
 254 void
 255 fz_debughash(fz_hashtable *table)
 256 {
 257         int i, k;
 258
 259         printf("cache load %d / %d\n", table->load, table->size);
 260
 261         for (i = 0; i < table->size; i++)
 262         {
 263                 if (!table->ents[i].val)
 264                         printf("table % 4d: empty\n", i);
 265                 else
 266                 {
 267                         printf("table % 4d: key=", i);
 268                         for (k = 0; k < MAXKEYLEN; k++)
 269                                 printf("%02x", ((char*)table->ents[i].key)[k]);
 270                         printf(" val=$%p\n", table->ents[i].val);
 271                 }
 272         }
 273 }
 274