1/* 2 * Copyright 2008-2009 Katholieke Universiteit Leuven 3 * 4 * Use of this software is governed by the MIT 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 <strings.h> 12#include <isl/hash.h> 13#include <isl/ctx.h> 14#include "isl_config.h" 15 16uint32_t isl_hash_string(uint32_t hash, const char *s) 17{ 18 for (; *s; s++) 19 isl_hash_byte(hash, *s); 20 return hash; 21} 22 23uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len) 24{ 25 int i; 26 const char *s = p; 27 for (i = 0; i < len; ++i) 28 isl_hash_byte(hash, s[i]); 29 return hash; 30} 31 32static unsigned int round_up(unsigned int v) 33{ 34 int old_v = v; 35 36 while (v) { 37 old_v = v; 38 v ^= v & -v; 39 } 40 return old_v << 1; 41} 42 43int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table, 44 int min_size) 45{ 46 size_t size; 47 48 if (!table) 49 return -1; 50 51 if (min_size < 2) 52 min_size = 2; 53 table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1; 54 table->n = 0; 55 56 size = 1 << table->bits; 57 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry, 58 size); 59 if (!table->entries) 60 return -1; 61 62 return 0; 63} 64 65/* Dummy comparison function that always returns false. 66 */ 67static int no(const void *entry, const void *val) 68{ 69 return 0; 70} 71 72/* Extend "table" to twice its size. 73 * Return 0 on success and -1 on error. 74 * 75 * We reuse isl_hash_table_find to create entries in the extended table. 76 * Since all entries in the original table are assumed to be different, 77 * there is no need to compare them against each other. 78 */ 79static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table) 80{ 81 int n; 82 size_t old_size, size; 83 struct isl_hash_table_entry *entries; 84 uint32_t h; 85 86 entries = table->entries; 87 old_size = 1 << table->bits; 88 size = 2 * old_size; 89 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry, 90 size); 91 if (!table->entries) { 92 table->entries = entries; 93 return -1; 94 } 95 96 n = table->n; 97 table->n = 0; 98 table->bits++; 99 100 for (h = 0; h < old_size; ++h) { 101 struct isl_hash_table_entry *entry; 102 103 if (!entries[h].data) 104 continue; 105 106 entry = isl_hash_table_find(ctx, table, entries[h].hash, 107 &no, NULL, 1); 108 if (!entry) { 109 table->bits--; 110 free(table->entries); 111 table->entries = entries; 112 table->n = n; 113 return -1; 114 } 115 116 *entry = entries[h]; 117 } 118 119 free(entries); 120 121 return 0; 122} 123 124struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size) 125{ 126 struct isl_hash_table *table = NULL; 127 128 table = isl_alloc_type(ctx, struct isl_hash_table); 129 if (isl_hash_table_init(ctx, table, min_size)) 130 goto error; 131 return table; 132error: 133 isl_hash_table_free(ctx, table); 134 return NULL; 135} 136 137void isl_hash_table_clear(struct isl_hash_table *table) 138{ 139 if (!table) 140 return; 141 free(table->entries); 142} 143 144void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table) 145{ 146 if (!table) 147 return; 148 isl_hash_table_clear(table); 149 free(table); 150} 151 152struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx, 153 struct isl_hash_table *table, 154 uint32_t key_hash, 155 int (*eq)(const void *entry, const void *val), 156 const void *val, int reserve) 157{ 158 size_t size; 159 uint32_t h, key_bits; 160 161 key_bits = isl_hash_bits(key_hash, table->bits); 162 size = 1 << table->bits; 163 for (h = key_bits; table->entries[h].data; h = (h+1) % size) 164 if (table->entries[h].hash == key_hash && 165 eq(table->entries[h].data, val)) 166 return &table->entries[h]; 167 168 if (!reserve) 169 return NULL; 170 171 if (4 * table->n >= 3 * size) { 172 if (grow_table(ctx, table) < 0) 173 return NULL; 174 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1); 175 } 176 177 table->n++; 178 table->entries[h].hash = key_hash; 179 180 return &table->entries[h]; 181} 182 183int isl_hash_table_foreach(struct isl_ctx *ctx, 184 struct isl_hash_table *table, 185 int (*fn)(void **entry, void *user), void *user) 186{ 187 size_t size; 188 uint32_t h; 189 190 size = 1 << table->bits; 191 for (h = 0; h < size; ++ h) 192 if (table->entries[h].data && 193 fn(&table->entries[h].data, user) < 0) 194 return -1; 195 196 return 0; 197} 198 199void isl_hash_table_remove(struct isl_ctx *ctx, 200 struct isl_hash_table *table, 201 struct isl_hash_table_entry *entry) 202{ 203 int h, h2; 204 size_t size; 205 206 if (!table || !entry) 207 return; 208 209 size = 1 << table->bits; 210 h = entry - table->entries; 211 isl_assert(ctx, h >= 0 && h < size, return); 212 213 for (h2 = h+1; table->entries[h2 % size].data; h2++) { 214 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash, 215 table->bits); 216 uint32_t offset = (size + bits - (h+1)) % size; 217 if (offset <= h2 - (h+1)) 218 continue; 219 *entry = table->entries[h2 % size]; 220 h = h2; 221 entry = &table->entries[h % size]; 222 } 223 224 entry->hash = 0; 225 entry->data = NULL; 226 table->n--; 227} 228