isl_hash.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include <stdlib.h>
  11 #include "isl_hash.h"
  12 #include "isl_ctx.h"
  13
  14 uint32_t isl_hash_string(uint32_t hash, const char *s)
  15 {
  16         for (; *s; s++)
  17                 isl_hash_byte(hash, *s);
  18         return hash;
  19 }
  20
  21 static unsigned int round_up(unsigned int v)
  22 {
  23         int old_v = v;
  24
  25         while (v) {
  26                 old_v = v;
  27                 v ^= v & -v;
  28         }
  29         return old_v << 1;
  30 }
  31
  32 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
  33                         int min_size)
  34 {
  35         size_t size;
  36
  37         if (!table)
  38                 return -1;
  39
  40         if (min_size < 2)
  41                 min_size = 2;
  42         table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
  43         table->n = 0;
  44
  45         size = 2 << table->bits;
  46         table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
  47                                           size);
  48         if (!table->entries)
  49                 return -1;
  50
  51         return 0;
  52 }
  53
  54 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
  55 {
  56         struct isl_hash_table *table = NULL;
  57
  58         table = isl_alloc_type(ctx, struct isl_hash_table);
  59         if (isl_hash_table_init(ctx, table, min_size))
  60                 goto error;
  61         return table;
  62 error:
  63         isl_hash_table_free(ctx, table);
  64         return NULL;
  65 }
  66
  67 void isl_hash_table_clear(struct isl_hash_table *table)
  68 {
  69         if (!table)
  70                 return;
  71         free(table->entries);
  72 }
  73
  74 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
  75 {
  76         if (!table)
  77                 return;
  78         isl_hash_table_clear(table);
  79         free(table);
  80 }
  81
  82 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
  83                                 struct isl_hash_table *table,
  84                                 uint32_t key_hash,
  85                                 int (*eq)(const void *entry, const void *val),
  86                                 const void *val, int reserve)
  87 {
  88         size_t size;
  89         uint32_t h, key_bits;
  90
  91         key_bits = isl_hash_bits(key_hash, table->bits);
  92         size = 2 << table->bits;
  93         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
  94                 if (table->entries[h].hash == key_hash &&
  95                     eq(table->entries[h].data, val))
  96                         return &table->entries[h];
  97
  98         if (!reserve)
  99                 return NULL;
 100
 101         assert(4 * table->n < 3 * size); /* XXX */
 102         table->n++;
 103         table->entries[h].hash = key_hash;
 104
 105         return &table->entries[h];
 106 }
 107
 108 void isl_hash_table_remove(struct isl_ctx *ctx,
 109                                 struct isl_hash_table *table,
 110                                 struct isl_hash_table_entry *entry)
 111 {
 112         int h, h2;
 113         size_t size;
 114
 115         if (!table || !entry)
 116                 return;
 117
 118         size = 2 << table->bits;
 119         h = entry - table->entries;
 120         isl_assert(ctx, h >= 0 && h < size, return);
 121
 122         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
 123                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
 124                                                 table->bits);
 125                 uint32_t offset = (size + bits - (h+1)) % size;
 126                 if (offset <= h2 - (h+1))
 127                         continue;
 128                 *entry = table->entries[h2 % size];
 129                 h = h2;
 130                 entry = &table->entries[h % size];
 131         }
 132
 133         entry->hash = 0;
 134         entry->data = NULL;
 135         table->n--;
 136 }