1 /* $NetBSD: hash.c,v 1.1.1.2 2009/12/02 00:26:11 haad Exp $ */ 2 3 /* 4 * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved. 5 * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved. 6 * 7 * This file is part of the device-mapper userspace tools. 8 * 9 * This copyrighted material is made available to anyone wishing to use, 10 * modify, copy, or redistribute it subject to the terms and conditions 11 * of the GNU Lesser General Public License v.2.1. 12 * 13 * You should have received a copy of the GNU Lesser General Public License 14 * along with this program; if not, write to the Free Software Foundation, 15 * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 16 */ 17 18 #include "dmlib.h" 19 20 struct dm_hash_node { 21 struct dm_hash_node *next; 22 void *data; 23 unsigned keylen; 24 char key[0]; 25 }; 26 27 struct dm_hash_table { 28 unsigned num_nodes; 29 unsigned num_slots; 30 struct dm_hash_node **slots; 31 }; 32 33 /* Permutation of the Integers 0 through 255 */ 34 static unsigned char _nums[] = { 35 1, 14, 110, 25, 97, 174, 132, 119, 138, 170, 125, 118, 27, 233, 140, 51, 36 87, 197, 177, 107, 234, 169, 56, 68, 30, 7, 173, 73, 188, 40, 36, 65, 37 49, 213, 104, 190, 57, 211, 148, 223, 48, 115, 15, 2, 67, 186, 210, 28, 38 12, 181, 103, 70, 22, 58, 75, 78, 183, 167, 238, 157, 124, 147, 172, 39 144, 40 176, 161, 141, 86, 60, 66, 128, 83, 156, 241, 79, 46, 168, 198, 41, 254, 41 178, 85, 253, 237, 250, 154, 133, 88, 35, 206, 95, 116, 252, 192, 54, 42 221, 43 102, 218, 255, 240, 82, 106, 158, 201, 61, 3, 89, 9, 42, 155, 159, 93, 44 166, 80, 50, 34, 175, 195, 100, 99, 26, 150, 16, 145, 4, 33, 8, 189, 45 121, 64, 77, 72, 208, 245, 130, 122, 143, 55, 105, 134, 29, 164, 185, 46 194, 47 193, 239, 101, 242, 5, 171, 126, 11, 74, 59, 137, 228, 108, 191, 232, 48 139, 49 6, 24, 81, 20, 127, 17, 91, 92, 251, 151, 225, 207, 21, 98, 113, 112, 50 84, 226, 18, 214, 199, 187, 13, 32, 94, 220, 224, 212, 247, 204, 196, 51 43, 52 249, 236, 45, 244, 111, 182, 153, 136, 129, 90, 217, 202, 19, 165, 231, 53 71, 54 230, 142, 96, 227, 62, 179, 246, 114, 162, 53, 160, 215, 205, 180, 47, 55 109, 56 44, 38, 31, 149, 135, 0, 216, 52, 63, 23, 37, 69, 39, 117, 146, 184, 57 163, 200, 222, 235, 248, 243, 219, 10, 152, 131, 123, 229, 203, 76, 120, 58 209 59 }; 60 61 static struct dm_hash_node *_create_node(const char *str, unsigned len) 62 { 63 struct dm_hash_node *n = dm_malloc(sizeof(*n) + len); 64 65 if (n) { 66 memcpy(n->key, str, len); 67 n->keylen = len; 68 } 69 70 return n; 71 } 72 73 static unsigned long _hash(const char *str, unsigned len) 74 { 75 unsigned long h = 0, g; 76 unsigned i; 77 78 for (i = 0; i < len; i++) { 79 h <<= 4; 80 h += _nums[(unsigned char) *str++]; 81 g = h & ((unsigned long) 0xf << 16u); 82 if (g) { 83 h ^= g >> 16u; 84 h ^= g >> 5u; 85 } 86 } 87 88 return h; 89 } 90 91 struct dm_hash_table *dm_hash_create(unsigned size_hint) 92 { 93 size_t len; 94 unsigned new_size = 16u; 95 struct dm_hash_table *hc = dm_malloc(sizeof(*hc)); 96 97 if (!hc) { 98 stack; 99 return 0; 100 } 101 102 memset(hc, 0, sizeof(*hc)); 103 104 /* round size hint up to a power of two */ 105 while (new_size < size_hint) 106 new_size = new_size << 1; 107 108 hc->num_slots = new_size; 109 len = sizeof(*(hc->slots)) * new_size; 110 if (!(hc->slots = dm_malloc(len))) { 111 stack; 112 goto bad; 113 } 114 memset(hc->slots, 0, len); 115 return hc; 116 117 bad: 118 dm_free(hc->slots); 119 dm_free(hc); 120 return 0; 121 } 122 123 static void _free_nodes(struct dm_hash_table *t) 124 { 125 struct dm_hash_node *c, *n; 126 unsigned i; 127 128 for (i = 0; i < t->num_slots; i++) 129 for (c = t->slots[i]; c; c = n) { 130 n = c->next; 131 dm_free(c); 132 } 133 } 134 135 void dm_hash_destroy(struct dm_hash_table *t) 136 { 137 _free_nodes(t); 138 dm_free(t->slots); 139 dm_free(t); 140 } 141 142 static struct dm_hash_node **_find(struct dm_hash_table *t, const char *key, 143 uint32_t len) 144 { 145 unsigned h = _hash(key, len) & (t->num_slots - 1); 146 struct dm_hash_node **c; 147 148 for (c = &t->slots[h]; *c; c = &((*c)->next)) { 149 if ((*c)->keylen != len) 150 continue; 151 152 if (!memcmp(key, (*c)->key, len)) 153 break; 154 } 155 156 return c; 157 } 158 159 void *dm_hash_lookup_binary(struct dm_hash_table *t, const char *key, 160 uint32_t len) 161 { 162 struct dm_hash_node **c = _find(t, key, len); 163 164 return *c ? (*c)->data : 0; 165 } 166 167 int dm_hash_insert_binary(struct dm_hash_table *t, const char *key, 168 uint32_t len, void *data) 169 { 170 struct dm_hash_node **c = _find(t, key, len); 171 172 if (*c) 173 (*c)->data = data; 174 else { 175 struct dm_hash_node *n = _create_node(key, len); 176 177 if (!n) 178 return 0; 179 180 n->data = data; 181 n->next = 0; 182 *c = n; 183 t->num_nodes++; 184 } 185 186 return 1; 187 } 188 189 void dm_hash_remove_binary(struct dm_hash_table *t, const char *key, 190 uint32_t len) 191 { 192 struct dm_hash_node **c = _find(t, key, len); 193 194 if (*c) { 195 struct dm_hash_node *old = *c; 196 *c = (*c)->next; 197 dm_free(old); 198 t->num_nodes--; 199 } 200 } 201 202 void *dm_hash_lookup(struct dm_hash_table *t, const char *key) 203 { 204 return dm_hash_lookup_binary(t, key, strlen(key) + 1); 205 } 206 207 int dm_hash_insert(struct dm_hash_table *t, const char *key, void *data) 208 { 209 return dm_hash_insert_binary(t, key, strlen(key) + 1, data); 210 } 211 212 void dm_hash_remove(struct dm_hash_table *t, const char *key) 213 { 214 dm_hash_remove_binary(t, key, strlen(key) + 1); 215 } 216 217 unsigned dm_hash_get_num_entries(struct dm_hash_table *t) 218 { 219 return t->num_nodes; 220 } 221 222 void dm_hash_iter(struct dm_hash_table *t, dm_hash_iterate_fn f) 223 { 224 struct dm_hash_node *c, *n; 225 unsigned i; 226 227 for (i = 0; i < t->num_slots; i++) 228 for (c = t->slots[i]; c; c = n) { 229 n = c->next; 230 f(c->data); 231 } 232 } 233 234 void dm_hash_wipe(struct dm_hash_table *t) 235 { 236 _free_nodes(t); 237 memset(t->slots, 0, sizeof(struct dm_hash_node *) * t->num_slots); 238 t->num_nodes = 0u; 239 } 240 241 char *dm_hash_get_key(struct dm_hash_table *t __attribute((unused)), 242 struct dm_hash_node *n) 243 { 244 return n->key; 245 } 246 247 void *dm_hash_get_data(struct dm_hash_table *t __attribute((unused)), 248 struct dm_hash_node *n) 249 { 250 return n->data; 251 } 252 253 static struct dm_hash_node *_next_slot(struct dm_hash_table *t, unsigned s) 254 { 255 struct dm_hash_node *c = NULL; 256 unsigned i; 257 258 for (i = s; i < t->num_slots && !c; i++) 259 c = t->slots[i]; 260 261 return c; 262 } 263 264 struct dm_hash_node *dm_hash_get_first(struct dm_hash_table *t) 265 { 266 return _next_slot(t, 0); 267 } 268 269 struct dm_hash_node *dm_hash_get_next(struct dm_hash_table *t, struct dm_hash_node *n) 270 { 271 unsigned h = _hash(n->key, n->keylen) & (t->num_slots - 1); 272 273 return n->next ? n->next : _next_slot(t, h + 1); 274 } 275