Mercurial > hg > ucx / file comparison

comparison: src/hash_map.c

src/hash_map.c

changeset 658
56c62780582e
parent 630
ac5e7f789048
child 665
c4041b07165e
equal deleted inserted replaced
657:3eeadf666d6b 658:56c62780582e
27 */ 27 */
28 28
29 #include <string.h> 29 #include <string.h>
30 #include "cx/hash_map.h" 30 #include "cx/hash_map.h"
31 #include "cx/utils.h" 31 #include "cx/utils.h"
32
33 struct cx_hash_map_element_s {
34 /** A pointer to the next element in the current bucket. */
35 struct cx_hash_map_element_s *next;
36
37 /** The corresponding key. */
38 CxHashKey key;
39
40 /** The value data. */
41 char data[];
42 };
32 43
33 static void cx_hash_map_clear(struct cx_map_s *map) { 44 static void cx_hash_map_clear(struct cx_map_s *map) {
34 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 45 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
35 cx_for_n(i, hash_map->bucket_count) { 46 cx_for_n(i, hash_map->bucket_count) {
36 struct cx_hash_map_element_s *elem = hash_map->buckets[i]; 47 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
87 } 98 }
88 99
89 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && 100 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
90 memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { 101 memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
91 // overwrite existing element 102 // overwrite existing element
92 elm->data = value; 103 if (map->store_pointers) {
104 memcpy(elm->data, &value, sizeof(void *));
105 } else {
106 memcpy(elm->data, value, map->itemsize);
107 }
93 } else { 108 } else {
94 // allocate new element 109 // allocate new element
95 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s)); 110 struct cx_hash_map_element_s *e = cxMalloc(
111 allocator,
112 sizeof(struct cx_hash_map_element_s) + map->itemsize
113 );
96 if (e == NULL) { 114 if (e == NULL) {
97 return -1; 115 return -1;
98 } 116 }
99 117
100 // write the value 118 // write the value
101 // TODO: depending on future map features, we may want to copy here 119 if (map->store_pointers) {
102 e->data = value; 120 memcpy(e->data, &value, sizeof(void *));
121 } else {
122 memcpy(e->data, value, map->itemsize);
123 }
103 124
104 // copy the key 125 // copy the key
105 void *kd = cxMalloc(allocator, key.len); 126 void *kd = cxMalloc(allocator, key.len);
106 if (kd == NULL) { 127 if (kd == NULL) {
107 return -1; 128 return -1;
149 * Helper function to avoid code duplication. 170 * Helper function to avoid code duplication.
150 * 171 *
151 * @param map the map 172 * @param map the map
152 * @param key the key to look up 173 * @param key the key to look up
153 * @param remove flag indicating whether the looked up entry shall be removed 174 * @param remove flag indicating whether the looked up entry shall be removed
154 * @return the value corresponding to the key or \c NULL 175 * @return a pointer to the value corresponding to the key or \c NULL
155 */ 176 */
156 static void *cx_hash_map_get_remove( 177 static void *cx_hash_map_get_remove(
157 CxMap *map, 178 CxMap *map,
158 CxHashKey key, 179 CxHashKey key,
159 bool remove 180 bool remove
170 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; 191 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
171 struct cx_hash_map_element_s *prev = NULL; 192 struct cx_hash_map_element_s *prev = NULL;
172 while (elm && elm->key.hash <= hash) { 193 while (elm && elm->key.hash <= hash) {
173 if (elm->key.hash == hash && elm->key.len == key.len) { 194 if (elm->key.hash == hash && elm->key.len == key.len) {
174 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) { 195 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
175 void *data = elm->data; 196 void *data = NULL;
197 if (map->store_pointers) {
198 data = *(void **) elm->data;
199 } else if (!remove) {
200 data = elm->data;
201 }
176 if (remove) { 202 if (remove) {
177 cx_hash_map_unlink(hash_map, slot, prev, elm); 203 cx_hash_map_unlink(hash_map, slot, prev, elm);
178 } 204 }
179 return data; 205 return data;
180 } 206 }
213 return &elm->key; 239 return &elm->key;
214 } 240 }
215 241
216 static void *cx_hash_map_iter_current_value(void const *it) { 242 static void *cx_hash_map_iter_current_value(void const *it) {
217 struct cx_iterator_s const *iter = it; 243 struct cx_iterator_s const *iter = it;
244 struct cx_hash_map_s const *map = iter->src_handle;
218 struct cx_hash_map_element_s *elm = iter->elem_handle; 245 struct cx_hash_map_element_s *elm = iter->elem_handle;
219 // TODO: return a pointer to data if this map is storing copies 246 if (map->base.store_pointers) {
220 return elm->data; 247 return *(void **) elm->data;
248 } else {
249 return elm->data;
250 }
221 } 251 }
222 252
223 static bool cx_hash_map_iter_valid(void const *it) { 253 static bool cx_hash_map_iter_valid(void const *it) {
224 struct cx_iterator_s const *iter = it; 254 struct cx_iterator_s const *iter = it;
225 return iter->elem_handle != NULL; 255 return iter->elem_handle != NULL;
272 if (elm == NULL) { 302 if (elm == NULL) {
273 iter->kv_data.key = NULL; 303 iter->kv_data.key = NULL;
274 iter->kv_data.value = NULL; 304 iter->kv_data.value = NULL;
275 } else { 305 } else {
276 iter->kv_data.key = &elm->key; 306 iter->kv_data.key = &elm->key;
277 // TODO: pointer to data if this map is storing copies 307 if (map->base.store_pointers) {
278 iter->kv_data.value = elm->data; 308 iter->kv_data.value = *(void **) elm->data;
309 } else {
310 iter->kv_data.value = elm->data;
311 }
279 } 312 }
280 } 313 }
281 314
282 static bool cx_hash_map_iter_flag_rm(void *it) { 315 static bool cx_hash_map_iter_flag_rm(void *it) {
283 struct cx_iterator_base_s *iter = it; 316 struct cx_iterator_base_s *iter = it;
309 for (; elm == NULL; iter.slot++) { 342 for (; elm == NULL; iter.slot++) {
310 elm = hash_map->buckets[iter.slot]; 343 elm = hash_map->buckets[iter.slot];
311 } 344 }
312 iter.elem_handle = elm; 345 iter.elem_handle = elm;
313 iter.kv_data.key = &elm->key; 346 iter.kv_data.key = &elm->key;
314 // TODO: pointer to data if this map is storing copies 347 if (map->store_pointers) {
315 iter.kv_data.value = elm->data; 348 iter.kv_data.value = *(void **) elm->data;
349 } else {
350 iter.kv_data.value = elm->data;
351 }
316 } else { 352 } else {
317 iter.elem_handle = NULL; 353 iter.elem_handle = NULL;
318 iter.kv_data.key = NULL; 354 iter.kv_data.key = NULL;
319 iter.kv_data.value = NULL; 355 iter.kv_data.value = NULL;
320 } 356 }
370 cx_hash_map_mut_iterator_values, 406 cx_hash_map_mut_iterator_values,
371 }; 407 };
372 408
373 CxMap *cxHashMapCreate( 409 CxMap *cxHashMapCreate(
374 CxAllocator *allocator, 410 CxAllocator *allocator,
411 size_t itemsize,
375 size_t buckets 412 size_t buckets
376 ) { 413 ) {
377 if (buckets == 0) { 414 if (buckets == 0) {
378 // implementation defined default 415 // implementation defined default
379 buckets = 16; 416 buckets = 16;
389 cxFree(allocator, map); 426 cxFree(allocator, map);
390 return NULL; 427 return NULL;
391 } 428 }
392 429
393 // initialize base members 430 // initialize base members
431 map->base.store_pointers = false;
394 map->base.cl = &cx_hash_map_class; 432 map->base.cl = &cx_hash_map_class;
395 map->base.allocator = allocator; 433 map->base.allocator = allocator;
396 map->base.size = 0; 434 map->base.size = 0;
435 map->base.itemsize = itemsize;
397 436
398 return (CxMap *) map; 437 return (CxMap *) map;
399 } 438 }
400 439
401 int cxMapRehash(CxMap *map) { 440 int cxMapRehash(CxMap *map) {

Mercurial Repository: ucx

mercurial