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 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
  46 {
  47         struct isl_hash_table *table = NULL;
  48
  49         table = isl_alloc_type(ctx, struct isl_hash_table);
  50         if (isl_hash_table_init(ctx, table, min_size))
  51                 goto error;
  52         return table;
  53 error:
  54         isl_hash_table_free(ctx, table);
  55         return NULL;
  56 }
  57
  58 void isl_hash_table_clear(struct isl_hash_table *table)
  59 {
  60         if (!table)
  61                 return;
  62         free(table->entries);
  63 }
  64
  65 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
  66 {
  67         if (!table)
  68                 return;
  69         isl_hash_table_clear(table);
  70         free(table);
  71 }
  72
  73 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
  74                                 struct isl_hash_table *table,
  75                                 uint32_t key_hash,
  76                                 int (*eq)(const void *entry, const void *val),
  77                                 const void *val, int reserve)
  78 {
  79         size_t size;
  80         uint32_t h, key_bits;
  81
  82         key_bits = isl_hash_bits(key_hash, table->bits);
  83         size = 2 << table->bits;
  84         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
  85                 if (table->entries[h].hash == key_hash &&
  86                     eq(table->entries[h].data, val))
  87                         return &table->entries[h];
  88
  89         if (!reserve)
  90                 return NULL;
  91
  92         assert(4 * table->n < 3 * size); /* XXX */
  93         table->n++;
  94         table->entries[h].hash = key_hash;
  95
  96         return &table->entries[h];
  97 }
  98
  99 void isl_hash_table_remove(struct isl_ctx *ctx,
 100                                 struct isl_hash_table *table,
 101                                 struct isl_hash_table_entry *entry)
 102 {
 103         int h, h2;
 104         size_t size;
 105
 106         if (!table || !entry)
 107                 return;
 108
 109         size = 2 << table->bits;
 110         h = entry - table->entries;
 111         isl_assert(ctx, h >= 0 && h < size, return);
 112
 113         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
 114                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
 115                                                 table->bits);
 116                 uint32_t offset = (size + bits - (h+1)) % size;
 117                 if (offset <= h2 - (h+1))
 118                         continue;
 119                 *entry = table->entries[h2 % size];
 120                 h = h2;
 121                 entry = &table->entries[h % size];
 122         }
 123
 124         entry->hash = 0;
 125         entry->data = NULL;
 126         table->n--;
 127 }