QRScanner/mobile/jni/fitz/hash.c

   1 #include "mupdf/fitz.h"
   2
   3 /*
   4 Simple hashtable with open addressing linear probe.
   5 Unlike text book examples, removing entries works
   6 correctly in this implementation, so it wont start
   7 exhibiting bad behaviour if entries are inserted
   8 and removed frequently.
   9 */
  10
  11 enum { MAX_KEY_LEN = 48 };
  12 typedef struct fz_hash_entry_s fz_hash_entry;
  13
  14 struct fz_hash_entry_s
  15 {
  16         unsigned char key[MAX_KEY_LEN];
  17         void *val;
  18 };
  19
  20 struct fz_hash_table_s
  21 {
  22         int keylen;
  23         int size;
  24         int load;
  25         int lock; /* -1 or the lock used to protect this hash table */
  26         fz_hash_entry *ents;
  27 };
  28
  29 static unsigned hash(const unsigned char *s, int len)
  30 {
  31         unsigned val = 0;
  32         int i;
  33         for (i = 0; i < len; i++)
  34         {
  35                 val += s[i];
  36                 val += (val << 10);
  37                 val ^= (val >> 6);
  38         }
  39         val += (val << 3);
  40         val ^= (val >> 11);
  41         val += (val << 15);
  42         return val;
  43 }
  44
  45 fz_hash_table *
  46 fz_new_hash_table(fz_context *ctx, int initialsize, int keylen, int lock)
  47 {
  48         fz_hash_table *table;
  49
  50         assert(keylen <= MAX_KEY_LEN);
  51
  52         table = fz_malloc_struct(ctx, fz_hash_table);
  53         table->keylen = keylen;
  54         table->size = initialsize;
  55         table->load = 0;
  56         table->lock = lock;
  57         fz_try(ctx)
  58         {
  59                 table->ents = fz_malloc_array(ctx, table->size, sizeof(fz_hash_entry));
  60                 memset(table->ents, 0, sizeof(fz_hash_entry) * table->size);
  61         }
  62         fz_catch(ctx)
  63         {
  64                 fz_free(ctx, table);
  65                 fz_rethrow(ctx);
  66         }
  67
  68         return table;
  69 }
  70
  71 void
  72 fz_empty_hash(fz_context *ctx, fz_hash_table *table)
  73 {
  74         table->load = 0;
  75         memset(table->ents, 0, sizeof(fz_hash_entry) * table->size);
  76 }
  77
  78 int
  79 fz_hash_len(fz_context *ctx, fz_hash_table *table)
  80 {
  81         return table->size;
  82 }
  83
  84 void *
  85 fz_hash_get_key(fz_context *ctx, fz_hash_table *table, int idx)
  86 {
  87         return table->ents[idx].key;
  88 }
  89
  90 void *
  91 fz_hash_get_val(fz_context *ctx, fz_hash_table *table, int idx)
  92 {
  93         return table->ents[idx].val;
  94 }
  95
  96 void
  97 fz_free_hash(fz_context *ctx, fz_hash_table *table)
  98 {
  99         fz_free(ctx, table->ents);
 100         fz_free(ctx, table);
 101 }
 102
 103 static void *
 104 do_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *val, unsigned *pos_ptr)
 105 {
 106         fz_hash_entry *ents;
 107         unsigned size;
 108         unsigned pos;
 109
 110         ents = table->ents;
 111         size = table->size;
 112         pos = hash(key, table->keylen) % size;
 113
 114         if (table->lock >= 0)
 115                 fz_assert_lock_held(ctx, table->lock);
 116
 117         while (1)
 118         {
 119                 if (!ents[pos].val)
 120                 {
 121                         memcpy(ents[pos].key, key, table->keylen);
 122                         ents[pos].val = val;
 123                         table->load ++;
 124                         if (pos_ptr)
 125                                 *pos_ptr = pos;
 126                         return NULL;
 127                 }
 128
 129                 if (memcmp(key, ents[pos].key, table->keylen) == 0)
 130                 {
 131                         /* This is legal, but should happen rarely in the non
 132                          * pos_ptr case. */
 133                         if (pos_ptr)
 134                                 *pos_ptr = pos;
 135                         else
 136                                 fz_warn(ctx, "assert: overwrite hash slot");
 137                         return ents[pos].val;
 138                 }
 139
 140                 pos = (pos + 1) % size;
 141         }
 142 }
 143
 144 /* Entered with the lock taken, held throughout and at exit, UNLESS the lock
 145  * is the alloc lock in which case it may be momentarily dropped. */
 146 static void
 147 fz_resize_hash(fz_context *ctx, fz_hash_table *table, int newsize)
 148 {
 149         fz_hash_entry *oldents = table->ents;
 150         fz_hash_entry *newents;
 151         int oldsize = table->size;
 152         int oldload = table->load;
 153         int i;
 154
 155         if (newsize < oldload * 8 / 10)
 156         {
 157                 fz_warn(ctx, "assert: resize hash too small");
 158                 return;
 159         }
 160
 161         if (table->lock == FZ_LOCK_ALLOC)
 162                 fz_unlock(ctx, FZ_LOCK_ALLOC);
 163         newents = fz_malloc_array_no_throw(ctx, newsize, sizeof(fz_hash_entry));
 164         if (table->lock == FZ_LOCK_ALLOC)
 165                 fz_lock(ctx, FZ_LOCK_ALLOC);
 166         if (table->lock >= 0)
 167         {
 168                 if (table->size >= newsize)
 169                 {
 170                         /* Someone else fixed it before we could lock! */
 171                         if (table->lock == FZ_LOCK_ALLOC)
 172                                 fz_unlock(ctx, table->lock);
 173                         fz_free(ctx, newents);
 174                         if (table->lock == FZ_LOCK_ALLOC)
 175                                 fz_lock(ctx, table->lock);
 176                         return;
 177                 }
 178         }
 179         if (newents == NULL)
 180                 fz_throw(ctx, FZ_ERROR_GENERIC, "hash table resize failed; out of memory (%d entries)", newsize);
 181         table->ents = newents;
 182         memset(table->ents, 0, sizeof(fz_hash_entry) * newsize);
 183         table->size = newsize;
 184         table->load = 0;
 185
 186         for (i = 0; i < oldsize; i++)
 187         {
 188                 if (oldents[i].val)
 189                 {
 190                         do_hash_insert(ctx, table, oldents[i].key, oldents[i].val, NULL);
 191                 }
 192         }
 193
 194         if (table->lock == FZ_LOCK_ALLOC)
 195                 fz_unlock(ctx, FZ_LOCK_ALLOC);
 196         fz_free(ctx, oldents);
 197         if (table->lock == FZ_LOCK_ALLOC)
 198                 fz_lock(ctx, FZ_LOCK_ALLOC);
 199 }
 200
 201 void *
 202 fz_hash_find(fz_context *ctx, fz_hash_table *table, const void *key)
 203 {
 204         fz_hash_entry *ents = table->ents;
 205         unsigned size = table->size;
 206         unsigned pos = hash(key, table->keylen) % size;
 207
 208         if (table->lock >= 0)
 209                 fz_assert_lock_held(ctx, table->lock);
 210
 211         while (1)
 212         {
 213                 if (!ents[pos].val)
 214                         return NULL;
 215
 216                 if (memcmp(key, ents[pos].key, table->keylen) == 0)
 217                         return ents[pos].val;
 218
 219                 pos = (pos + 1) % size;
 220         }
 221 }
 222
 223 void *
 224 fz_hash_insert(fz_context *ctx, fz_hash_table *table, const void *key, void *val)
 225 {
 226         if (table->load > table->size * 8 / 10)
 227         {
 228                 fz_resize_hash(ctx, table, table->size * 2);
 229         }
 230
 231         return do_hash_insert(ctx, table, key, val, NULL);
 232 }
 233
 234 void *
 235 fz_hash_insert_with_pos(fz_context *ctx, fz_hash_table *table, const void *key, void *val, unsigned *pos)
 236 {
 237         if (table->load > table->size * 8 / 10)
 238         {
 239                 fz_resize_hash(ctx, table, table->size * 2);
 240         }
 241
 242         return do_hash_insert(ctx, table, key, val, pos);
 243 }
 244
 245 static void
 246 do_removal(fz_context *ctx, fz_hash_table *table, const void *key, unsigned hole)
 247 {
 248         fz_hash_entry *ents = table->ents;
 249         unsigned size = table->size;
 250         unsigned look, code;
 251
 252         if (table->lock >= 0)
 253                 fz_assert_lock_held(ctx, table->lock);
 254
 255         ents[hole].val = NULL;
 256
 257         look = hole + 1;
 258         if (look == size)
 259                 look = 0;
 260
 261         while (ents[look].val)
 262         {
 263                 code = hash(ents[look].key, table->keylen) % size;
 264                 if ((code <= hole && hole < look) ||
 265                         (look < code && code <= hole) ||
 266                         (hole < look && look < code))
 267                 {
 268                         ents[hole] = ents[look];
 269                         ents[look].val = NULL;
 270                         hole = look;
 271                 }
 272
 273                 look++;
 274                 if (look == size)
 275                         look = 0;
 276         }
 277
 278         table->load --;
 279 }
 280
 281 void
 282 fz_hash_remove(fz_context *ctx, fz_hash_table *table, const void *key)
 283 {
 284         fz_hash_entry *ents = table->ents;
 285         unsigned size = table->size;
 286         unsigned pos = hash(key, table->keylen) % size;
 287
 288         if (table->lock >= 0)
 289                 fz_assert_lock_held(ctx, table->lock);
 290
 291         while (1)
 292         {
 293                 if (!ents[pos].val)
 294                 {
 295                         fz_warn(ctx, "assert: remove non-existent hash entry");
 296                         return;
 297                 }
 298
 299                 if (memcmp(key, ents[pos].key, table->keylen) == 0)
 300                 {
 301                         do_removal(ctx, table, key, pos);
 302                         return;
 303                 }
 304
 305                 pos++;
 306                 if (pos == size)
 307                         pos = 0;
 308         }
 309 }
 310
 311 void
 312 fz_hash_remove_fast(fz_context *ctx, fz_hash_table *table, const void *key, unsigned pos)
 313 {
 314         fz_hash_entry *ents = table->ents;
 315
 316         if (ents[pos].val == NULL || memcmp(key, ents[pos].key, table->keylen) != 0)
 317         {
 318                 /* The value isn't there, or the key didn't match! The table
 319                  * must have been rebuilt (or the contents moved) in the
 320                  * meantime. Do the removal the slow way. */
 321                 fz_hash_remove(ctx, table, key);
 322         }
 323         else
 324                 do_removal(ctx, table, key, pos);
 325 }
 326
 327 #ifndef NDEBUG
 328 void
 329 fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table)
 330 {
 331         fz_print_hash_details(ctx, out, table, NULL);
 332 }
 333
 334 void
 335 fz_print_hash_details(fz_context *ctx, FILE *out, fz_hash_table *table, void (*details)(FILE *,void*))
 336 {
 337         int i, k;
 338
 339         fprintf(out, "cache load %d / %d\n", table->load, table->size);
 340
 341         for (i = 0; i < table->size; i++)
 342         {
 343                 if (!table->ents[i].val)
 344                         fprintf(out, "table % 4d: empty\n", i);
 345                 else
 346                 {
 347                         fprintf(out, "table % 4d: key=", i);
 348                         for (k = 0; k < MAX_KEY_LEN; k++)
 349                                 fprintf(out, "%02x", ((char*)table->ents[i].key)[k]);
 350                         if (details)
 351                                 details(out, table->ents[i].val);
 352                         else
 353                                 fprintf(out, " val=$%p\n", table->ents[i].val);
 354                 }
 355         }
 356 }
 357 #endif