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 static unsigned int round_up(unsigned int v)
  13 {
  14         int old_v = v;
  15
  16         while (v) {
  17                 old_v = v;
  18                 v ^= v & -v;
  19         }
  20         return old_v << 1;
  21 }
  22
  23 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
  24                         int min_size)
  25 {
  26         size_t size;
  27
  28         if (!table)
  29                 return -1;
  30
  31         if (min_size < 2)
  32                 min_size = 2;
  33         table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
  34         table->n = 0;
  35
  36         size = 2 << table->bits;
  37         table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
  38                                           size);
  39         if (!table->entries)
  40                 return -1;
  41
  42         return 0;
  43 }
  44
  45 void isl_hash_table_clear(struct isl_hash_table *table)
  46 {
  47         if (!table)
  48                 return;
  49         free(table->entries);
  50 }
  51
  52 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
  53                                 struct isl_hash_table *table,
  54                                 uint32_t key_hash,
  55                                 int (*eq)(const void *entry, const void *val),
  56                                 const void *val, int reserve)
  57 {
  58         size_t size;
  59         uint32_t h, key_bits;
  60
  61         key_bits = isl_hash_bits(key_hash, table->bits);
  62         size = 2 << table->bits;
  63         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
  64                 if (table->entries[h].hash == key_hash &&
  65                     eq(table->entries[h].data, val))
  66                         return &table->entries[h];
  67
  68         if (!reserve)
  69                 return NULL;
  70
  71         assert(4 * table->n < 3 * size); /* XXX */
  72         table->n++;
  73         table->entries[h].hash = key_hash;
  74
  75         return &table->entries[h];
  76 }
  77
  78 void isl_hash_table_remove(struct isl_ctx *ctx,
  79                                 struct isl_hash_table *table,
  80                                 struct isl_hash_table_entry *entry)
  81 {
  82         int h, h2, last_h;
  83         size_t size;
  84
  85         if (!table || !entry)
  86                 return;
  87
  88         size = 2 << table->bits;
  89         h = entry - table->entries;
  90         isl_assert(ctx, h >= 0 && h < size, return);
  91
  92         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
  93                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
  94                                                 table->bits);
  95                 uint32_t offset = (size + bits - (h+1)) % size;
  96                 if (offset <= h2 - (h+1))
  97                         continue;
  98                 *entry = table->entries[h2 % size];
  99                 h = h2;
 100                 entry = &table->entries[h % size];
 101         }
 102
 103         entry->hash = 0;
 104         entry->data = NULL;
 105         table->n--;
 106 }