Mercurial > hg > toolkit / file comparison

comparison: ucx/hash_map.c

ucx/hash_map.c

branch
newapi
changeset 324
ce13a778654a
parent 174
0358f1d9c506
equal deleted inserted replaced
323:38cb8e3992e8 324:ce13a778654a
51 do { 51 do {
52 struct cx_hash_map_element_s *next = elem->next; 52 struct cx_hash_map_element_s *next = elem->next;
53 // invoke the destructor 53 // invoke the destructor
54 cx_invoke_destructor(map, elem->data); 54 cx_invoke_destructor(map, elem->data);
55 // free the key data 55 // free the key data
56 cxFree(map->allocator, (void *) elem->key.data); 56 cxFree(map->collection.allocator, (void *) elem->key.data);
57 // free the node 57 // free the node
58 cxFree(map->allocator, elem); 58 cxFree(map->collection.allocator, elem);
59 // proceed 59 // proceed
60 elem = next; 60 elem = next;
61 } while (elem != NULL); 61 } while (elem != NULL);
62 62
63 // do not leave a dangling pointer 63 // do not leave a dangling pointer
64 hash_map->buckets[i] = NULL; 64 hash_map->buckets[i] = NULL;
65 } 65 }
66 } 66 }
67 map->size = 0; 67 map->collection.size = 0;
68 } 68 }
69 69
70 static void cx_hash_map_destructor(struct cx_map_s *map) { 70 static void cx_hash_map_destructor(struct cx_map_s *map) {
71 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 71 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
72 72
73 // free the buckets 73 // free the buckets
74 cx_hash_map_clear(map); 74 cx_hash_map_clear(map);
75 cxFree(map->allocator, hash_map->buckets); 75 cxFree(map->collection.allocator, hash_map->buckets);
76 76
77 // free the map structure 77 // free the map structure
78 cxFree(map->allocator, map); 78 cxFree(map->collection.allocator, map);
79 } 79 }
80 80
81 static int cx_hash_map_put( 81 static int cx_hash_map_put(
82 CxMap *map, 82 CxMap *map,
83 CxHashKey key, 83 CxHashKey key,
84 void *value 84 void *value
85 ) { 85 ) {
86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
87 CxAllocator const *allocator = map->allocator; 87 const CxAllocator *allocator = map->collection.allocator;
88 88
89 unsigned hash = key.hash; 89 unsigned hash = key.hash;
90 if (hash == 0) { 90 if (hash == 0) {
91 cx_hash_murmur(&key); 91 cx_hash_murmur(&key);
92 hash = key.hash; 92 hash = key.hash;
102 } 102 }
103 103
104 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && 104 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
105 memcmp(elm->key.data, key.data, key.len) == 0) { 105 memcmp(elm->key.data, key.data, key.len) == 0) {
106 // overwrite existing element 106 // overwrite existing element
107 if (map->store_pointer) { 107 if (map->collection.store_pointer) {
108 memcpy(elm->data, &value, sizeof(void *)); 108 memcpy(elm->data, &value, sizeof(void *));
109 } else { 109 } else {
110 memcpy(elm->data, value, map->item_size); 110 memcpy(elm->data, value, map->collection.elem_size);
111 } 111 }
112 } else { 112 } else {
113 // allocate new element 113 // allocate new element
114 struct cx_hash_map_element_s *e = cxMalloc( 114 struct cx_hash_map_element_s *e = cxMalloc(
115 allocator, 115 allocator,
116 sizeof(struct cx_hash_map_element_s) + map->item_size 116 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size
117 ); 117 );
118 if (e == NULL) { 118 if (e == NULL) {
119 return -1; 119 return -1;
120 } 120 }
121 121
122 // write the value 122 // write the value
123 if (map->store_pointer) { 123 if (map->collection.store_pointer) {
124 memcpy(e->data, &value, sizeof(void *)); 124 memcpy(e->data, &value, sizeof(void *));
125 } else { 125 } else {
126 memcpy(e->data, value, map->item_size); 126 memcpy(e->data, value, map->collection.elem_size);
127 } 127 }
128 128
129 // copy the key 129 // copy the key
130 void *kd = cxMalloc(allocator, key.len); 130 void *kd = cxMalloc(allocator, key.len);
131 if (kd == NULL) { 131 if (kd == NULL) {
143 prev->next = e; 143 prev->next = e;
144 } 144 }
145 e->next = elm; 145 e->next = elm;
146 146
147 // increase the size 147 // increase the size
148 map->size++; 148 map->collection.size++;
149 } 149 }
150 150
151 return 0; 151 return 0;
152 } 152 }
153 153
162 hash_map->buckets[slot] = elm->next; 162 hash_map->buckets[slot] = elm->next;
163 } else { 163 } else {
164 prev->next = elm->next; 164 prev->next = elm->next;
165 } 165 }
166 // free element 166 // free element
167 cxFree(hash_map->base.allocator, (void *) elm->key.data); 167 cxFree(hash_map->base.collection.allocator, (void *) elm->key.data);
168 cxFree(hash_map->base.allocator, elm); 168 cxFree(hash_map->base.collection.allocator, elm);
169 // decrease size 169 // decrease size
170 hash_map->base.size--; 170 hash_map->base.collection.size--;
171 } 171 }
172 172
173 /** 173 /**
174 * Helper function to avoid code duplication. 174 * Helper function to avoid code duplication.
175 * 175 *
201 if (memcmp(elm->key.data, key.data, key.len) == 0) { 201 if (memcmp(elm->key.data, key.data, key.len) == 0) {
202 void *data = NULL; 202 void *data = NULL;
203 if (destroy) { 203 if (destroy) {
204 cx_invoke_destructor(map, elm->data); 204 cx_invoke_destructor(map, elm->data);
205 } else { 205 } else {
206 if (map->store_pointer) { 206 if (map->collection.store_pointer) {
207 data = *(void **) elm->data; 207 data = *(void **) elm->data;
208 } else { 208 } else {
209 data = elm->data; 209 data = elm->data;
210 } 210 }
211 } 211 }
221 221
222 return NULL; 222 return NULL;
223 } 223 }
224 224
225 static void *cx_hash_map_get( 225 static void *cx_hash_map_get(
226 CxMap const *map, 226 const CxMap *map,
227 CxHashKey key 227 CxHashKey key
228 ) { 228 ) {
229 // we can safely cast, because we know the map stays untouched 229 // we can safely cast, because we know the map stays untouched
230 return cx_hash_map_get_remove((CxMap *) map, key, false, false); 230 return cx_hash_map_get_remove((CxMap *) map, key, false, false);
231 } 231 }
236 bool destroy 236 bool destroy
237 ) { 237 ) {
238 return cx_hash_map_get_remove(map, key, true, destroy); 238 return cx_hash_map_get_remove(map, key, true, destroy);
239 } 239 }
240 240
241 static void *cx_hash_map_iter_current_entry(void const *it) { 241 static void *cx_hash_map_iter_current_entry(const void *it) {
242 struct cx_iterator_s const *iter = it; 242 const struct cx_iterator_s *iter = it;
243 // struct has to have a compatible signature 243 // struct has to have a compatible signature
244 return (struct cx_map_entry_s *) &(iter->kv_data); 244 return (struct cx_map_entry_s *) &(iter->kv_data);
245 } 245 }
246 246
247 static void *cx_hash_map_iter_current_key(void const *it) { 247 static void *cx_hash_map_iter_current_key(const void *it) {
248 struct cx_iterator_s const *iter = it; 248 const struct cx_iterator_s *iter = it;
249 struct cx_hash_map_element_s *elm = iter->elem_handle; 249 struct cx_hash_map_element_s *elm = iter->elem_handle;
250 return &elm->key; 250 return &elm->key;
251 } 251 }
252 252
253 static void *cx_hash_map_iter_current_value(void const *it) { 253 static void *cx_hash_map_iter_current_value(const void *it) {
254 struct cx_iterator_s const *iter = it; 254 const struct cx_iterator_s *iter = it;
255 struct cx_hash_map_s const *map = iter->src_handle; 255 const struct cx_hash_map_s *map = iter->src_handle.c;
256 struct cx_hash_map_element_s *elm = iter->elem_handle; 256 struct cx_hash_map_element_s *elm = iter->elem_handle;
257 if (map->base.store_pointer) { 257 if (map->base.collection.store_pointer) {
258 return *(void **) elm->data; 258 return *(void **) elm->data;
259 } else { 259 } else {
260 return elm->data; 260 return elm->data;
261 } 261 }
262 } 262 }
263 263
264 static bool cx_hash_map_iter_valid(void const *it) { 264 static bool cx_hash_map_iter_valid(const void *it) {
265 struct cx_iterator_s const *iter = it; 265 const struct cx_iterator_s *iter = it;
266 return iter->elem_handle != NULL; 266 return iter->elem_handle != NULL;
267 } 267 }
268 268
269 static void cx_hash_map_iter_next(void *it) { 269 static void cx_hash_map_iter_next(void *it) {
270 struct cx_iterator_s *iter = it; 270 struct cx_iterator_s *iter = it;
271 struct cx_hash_map_element_s *elm = iter->elem_handle; 271 struct cx_hash_map_element_s *elm = iter->elem_handle;
272 struct cx_hash_map_s *map = iter->src_handle.m;
272 273
273 // remove current element, if asked 274 // remove current element, if asked
274 if (iter->base.remove) { 275 if (iter->base.remove) {
275 // obtain mutable pointer to the map
276 struct cx_mut_iterator_s *miter = it;
277 struct cx_hash_map_s *map = miter->src_handle;
278 276
279 // clear the flag 277 // clear the flag
280 iter->base.remove = false; 278 iter->base.remove = false;
281 279
282 // determine the next element 280 // determine the next element
304 elm = elm->next; 302 elm = elm->next;
305 iter->index++; 303 iter->index++;
306 } 304 }
307 305
308 // search the next bucket, if required 306 // search the next bucket, if required
309 struct cx_hash_map_s const *map = iter->src_handle;
310 while (elm == NULL && ++iter->slot < map->bucket_count) { 307 while (elm == NULL && ++iter->slot < map->bucket_count) {
311 elm = map->buckets[iter->slot]; 308 elm = map->buckets[iter->slot];
312 } 309 }
313 310
314 // fill the struct with the next element 311 // fill the struct with the next element
316 if (elm == NULL) { 313 if (elm == NULL) {
317 iter->kv_data.key = NULL; 314 iter->kv_data.key = NULL;
318 iter->kv_data.value = NULL; 315 iter->kv_data.value = NULL;
319 } else { 316 } else {
320 iter->kv_data.key = &elm->key; 317 iter->kv_data.key = &elm->key;
321 if (map->base.store_pointer) { 318 if (map->base.collection.store_pointer) {
322 iter->kv_data.value = *(void **) elm->data; 319 iter->kv_data.value = *(void **) elm->data;
323 } else { 320 } else {
324 iter->kv_data.value = elm->data; 321 iter->kv_data.value = elm->data;
325 } 322 }
326 } 323 }
327 } 324 }
328 325
329 static bool cx_hash_map_iter_flag_rm(void *it) {
330 struct cx_iterator_base_s *iter = it;
331 if (iter->mutating) {
332 iter->remove = true;
333 return true;
334 } else {
335 return false;
336 }
337 }
338
339 static CxIterator cx_hash_map_iterator( 326 static CxIterator cx_hash_map_iterator(
340 CxMap const *map, 327 const CxMap *map,
341 enum cx_map_iterator_type type 328 enum cx_map_iterator_type type
342 ) { 329 ) {
343 CxIterator iter; 330 CxIterator iter;
344 331
345 iter.src_handle = map; 332 iter.src_handle.c = map;
346 iter.base.valid = cx_hash_map_iter_valid; 333 iter.elem_count = map->collection.size;
347 iter.base.next = cx_hash_map_iter_next;
348 334
349 switch (type) { 335 switch (type) {
350 case CX_MAP_ITERATOR_PAIRS: 336 case CX_MAP_ITERATOR_PAIRS:
337 iter.elem_size = sizeof(CxMapEntry);
351 iter.base.current = cx_hash_map_iter_current_entry; 338 iter.base.current = cx_hash_map_iter_current_entry;
352 break; 339 break;
353 case CX_MAP_ITERATOR_KEYS: 340 case CX_MAP_ITERATOR_KEYS:
341 iter.elem_size = sizeof(CxHashKey);
354 iter.base.current = cx_hash_map_iter_current_key; 342 iter.base.current = cx_hash_map_iter_current_key;
355 break; 343 break;
356 case CX_MAP_ITERATOR_VALUES: 344 case CX_MAP_ITERATOR_VALUES:
345 iter.elem_size = map->collection.elem_size;
357 iter.base.current = cx_hash_map_iter_current_value; 346 iter.base.current = cx_hash_map_iter_current_value;
358 break; 347 break;
359 default: 348 default:
360 assert(false); 349 assert(false);
361 } 350 }
362 351
363 iter.base.flag_removal = cx_hash_map_iter_flag_rm; 352 iter.base.valid = cx_hash_map_iter_valid;
353 iter.base.next = cx_hash_map_iter_next;
364 iter.base.remove = false; 354 iter.base.remove = false;
365 iter.base.mutating = false; 355 iter.base.mutating = false;
366 356
367 iter.slot = 0; 357 iter.slot = 0;
368 iter.index = 0; 358 iter.index = 0;
369 359
370 if (map->size > 0) { 360 if (map->collection.size > 0) {
371 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 361 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
372 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; 362 struct cx_hash_map_element_s *elm = hash_map->buckets[0];
373 while (elm == NULL) { 363 while (elm == NULL) {
374 elm = hash_map->buckets[++iter.slot]; 364 elm = hash_map->buckets[++iter.slot];
375 } 365 }
376 iter.elem_handle = elm; 366 iter.elem_handle = elm;
377 iter.kv_data.key = &elm->key; 367 iter.kv_data.key = &elm->key;
378 if (map->store_pointer) { 368 if (map->collection.store_pointer) {
379 iter.kv_data.value = *(void **) elm->data; 369 iter.kv_data.value = *(void **) elm->data;
380 } else { 370 } else {
381 iter.kv_data.value = elm->data; 371 iter.kv_data.value = elm->data;
382 } 372 }
383 } else { 373 } else {
397 cx_hash_map_remove, 387 cx_hash_map_remove,
398 cx_hash_map_iterator, 388 cx_hash_map_iterator,
399 }; 389 };
400 390
401 CxMap *cxHashMapCreate( 391 CxMap *cxHashMapCreate(
402 CxAllocator const *allocator, 392 const CxAllocator *allocator,
403 size_t itemsize, 393 size_t itemsize,
404 size_t buckets 394 size_t buckets
405 ) { 395 ) {
406 if (buckets == 0) { 396 if (buckets == 0) {
407 // implementation defined default 397 // implementation defined default
421 return NULL; 411 return NULL;
422 } 412 }
423 413
424 // initialize base members 414 // initialize base members
425 map->base.cl = &cx_hash_map_class; 415 map->base.cl = &cx_hash_map_class;
426 map->base.allocator = allocator; 416 map->base.collection.allocator = allocator;
427 417
428 if (itemsize > 0) { 418 if (itemsize > 0) {
429 map->base.store_pointer = false; 419 map->base.collection.store_pointer = false;
430 map->base.item_size = itemsize; 420 map->base.collection.elem_size = itemsize;
431 } else { 421 } else {
432 map->base.store_pointer = true; 422 map->base.collection.store_pointer = true;
433 map->base.item_size = sizeof(void *); 423 map->base.collection.elem_size = sizeof(void *);
434 } 424 }
435 425
436 return (CxMap *) map; 426 return (CxMap *) map;
437 } 427 }
438 428
439 int cxMapRehash(CxMap *map) { 429 int cxMapRehash(CxMap *map) {
440 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 430 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
441 if (map->size > ((hash_map->bucket_count * 3) >> 2)) { 431 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) {
442 432
443 size_t new_bucket_count = (map->size * 5) >> 1; 433 size_t new_bucket_count = (map->collection.size * 5) >> 1;
444 struct cx_hash_map_element_s **new_buckets = cxCalloc( 434 struct cx_hash_map_element_s **new_buckets = cxCalloc(
445 map->allocator, 435 map->collection.allocator,
446 new_bucket_count, sizeof(struct cx_hash_map_element_s *) 436 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
447 ); 437 );
448 438
449 if (new_buckets == NULL) { 439 if (new_buckets == NULL) {
450 return 1; 440 return 1;
480 } 470 }
481 } 471 }
482 472
483 // assign result to the map 473 // assign result to the map
484 hash_map->bucket_count = new_bucket_count; 474 hash_map->bucket_count = new_bucket_count;
485 cxFree(map->allocator, hash_map->buckets); 475 cxFree(map->collection.allocator, hash_map->buckets);
486 hash_map->buckets = new_buckets; 476 hash_map->buckets = new_buckets;
487 } 477 }
488 return 0; 478 return 0;
489 } 479 }

Mercurial Repository: toolkit

mercurial