isl_hash.c

   1 #include <stdlib.h>
   2 #include "isl_hash.h"
   3 #include "isl_ctx.h"
   4
   5 uint32_t isl_hash_string(uint32_t hash, const char *s)
   6 {
   7         for (; *s; s++)
   8                 isl_hash_byte(hash, *s);
   9         return hash;
  10 }
  11
  12 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
  13                         int init_bits)
  14 {
  15         size_t size;
  16
  17         if (!table)
  18                 return -1;
  19
  20         if (init_bits < 2)
  21                 init_bits = 2;
  22         table->bits = init_bits;
  23         table->n = 0;
  24
  25         size = 2 << table->bits;
  26         table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
  27                                           size);
  28         if (!table->entries)
  29                 return -1;
  30
  31         return 0;
  32 }
  33
  34 void isl_hash_table_clear(struct isl_hash_table *table)
  35 {
  36         if (!table)
  37                 return;
  38         free(table->entries);
  39 }
  40
  41 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
  42                                 struct isl_hash_table *table,
  43                                 uint32_t key_hash,
  44                                 int (*eq)(const void *entry, const void *val),
  45                                 const void *val, int reserve)
  46 {
  47         size_t size;
  48         uint32_t h, key_bits;
  49
  50         key_bits = isl_hash_bits(key_hash, table->bits);
  51         size = 2 << table->bits;
  52         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
  53                 if (table->entries[h].hash == key_hash &&
  54                     eq(table->entries[h].data, val))
  55                         return &table->entries[h];
  56
  57         if (!reserve)
  58                 return NULL;
  59
  60         assert(4 * table->n < 3 * size); /* XXX */
  61         table->n++;
  62         table->entries[h].hash = key_hash;
  63
  64         return &table->entries[h];
  65 }
  66
  67 void isl_hash_table_remove(struct isl_ctx *ctx,
  68                                 struct isl_hash_table *table,
  69                                 struct isl_hash_table_entry *entry)
  70 {
  71         int h, h2, last_h;
  72         size_t size;
  73
  74         if (!table || !entry)
  75                 return;
  76
  77         size = 2 << table->bits;
  78         h = entry - table->entries;
  79         isl_assert(ctx, h >= 0 && h < size, return);
  80
  81         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
  82                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
  83                                                 table->bits);
  84                 uint32_t offset = (size + bits - (h+1)) % size;
  85                 if (offset <= h2 - (h+1))
  86                         continue;
  87                 *entry = table->entries[h2 % size];
  88                 h = h2;
  89                 entry = &table->entries[h % size];
  90         }
  91
  92         entry->hash = 0;
  93         entry->data = NULL;
  94         table->n--;
  95 }