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->base.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->base.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->base.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->base.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->base.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->base.allocator; |
87 CxAllocator const *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->base.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->base.elem_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->base.elem_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->base.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->base.elem_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) { |
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.base.allocator, (void *) elm->key.data); |
167 cxFree(hash_map->base.collection.allocator, (void *) elm->key.data); |
168 cxFree(hash_map->base.base.allocator, elm); |
168 cxFree(hash_map->base.collection.allocator, elm); |
169 // decrease size |
169 // decrease size |
170 hash_map->base.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->base.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 } |
252 |
252 |
253 static void *cx_hash_map_iter_current_value(void const *it) { |
253 static void *cx_hash_map_iter_current_value(void const *it) { |
254 struct cx_iterator_s const *iter = it; |
254 struct cx_iterator_s const *iter = it; |
255 struct cx_hash_map_s const *map = iter->src_handle.c; |
255 struct cx_hash_map_s const *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.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 } |
313 if (elm == NULL) { |
313 if (elm == NULL) { |
314 iter->kv_data.key = NULL; |
314 iter->kv_data.key = NULL; |
315 iter->kv_data.value = NULL; |
315 iter->kv_data.value = NULL; |
316 } else { |
316 } else { |
317 iter->kv_data.key = &elm->key; |
317 iter->kv_data.key = &elm->key; |
318 if (map->base.base.store_pointer) { |
318 if (map->base.collection.store_pointer) { |
319 iter->kv_data.value = *(void **) elm->data; |
319 iter->kv_data.value = *(void **) elm->data; |
320 } else { |
320 } else { |
321 iter->kv_data.value = elm->data; |
321 iter->kv_data.value = elm->data; |
322 } |
322 } |
323 } |
323 } |
328 enum cx_map_iterator_type type |
328 enum cx_map_iterator_type type |
329 ) { |
329 ) { |
330 CxIterator iter; |
330 CxIterator iter; |
331 |
331 |
332 iter.src_handle.c = map; |
332 iter.src_handle.c = map; |
333 iter.elem_count = map->base.size; |
333 iter.elem_count = map->collection.size; |
334 |
334 |
335 switch (type) { |
335 switch (type) { |
336 case CX_MAP_ITERATOR_PAIRS: |
336 case CX_MAP_ITERATOR_PAIRS: |
337 iter.elem_size = sizeof(CxMapEntry); |
337 iter.elem_size = sizeof(CxMapEntry); |
338 iter.base.current = cx_hash_map_iter_current_entry; |
338 iter.base.current = cx_hash_map_iter_current_entry; |
340 case CX_MAP_ITERATOR_KEYS: |
340 case CX_MAP_ITERATOR_KEYS: |
341 iter.elem_size = sizeof(CxHashKey); |
341 iter.elem_size = sizeof(CxHashKey); |
342 iter.base.current = cx_hash_map_iter_current_key; |
342 iter.base.current = cx_hash_map_iter_current_key; |
343 break; |
343 break; |
344 case CX_MAP_ITERATOR_VALUES: |
344 case CX_MAP_ITERATOR_VALUES: |
345 iter.elem_size = map->base.elem_size; |
345 iter.elem_size = map->collection.elem_size; |
346 iter.base.current = cx_hash_map_iter_current_value; |
346 iter.base.current = cx_hash_map_iter_current_value; |
347 break; |
347 break; |
348 default: |
348 default: |
349 assert(false); |
349 assert(false); |
350 } |
350 } |
355 iter.base.mutating = false; |
355 iter.base.mutating = false; |
356 |
356 |
357 iter.slot = 0; |
357 iter.slot = 0; |
358 iter.index = 0; |
358 iter.index = 0; |
359 |
359 |
360 if (map->base.size > 0) { |
360 if (map->collection.size > 0) { |
361 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; |
362 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; |
362 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; |
363 while (elm == NULL) { |
363 while (elm == NULL) { |
364 elm = hash_map->buckets[++iter.slot]; |
364 elm = hash_map->buckets[++iter.slot]; |
365 } |
365 } |
366 iter.elem_handle = elm; |
366 iter.elem_handle = elm; |
367 iter.kv_data.key = &elm->key; |
367 iter.kv_data.key = &elm->key; |
368 if (map->base.store_pointer) { |
368 if (map->collection.store_pointer) { |
369 iter.kv_data.value = *(void **) elm->data; |
369 iter.kv_data.value = *(void **) elm->data; |
370 } else { |
370 } else { |
371 iter.kv_data.value = elm->data; |
371 iter.kv_data.value = elm->data; |
372 } |
372 } |
373 } else { |
373 } else { |
411 return NULL; |
411 return NULL; |
412 } |
412 } |
413 |
413 |
414 // initialize base members |
414 // initialize base members |
415 map->base.cl = &cx_hash_map_class; |
415 map->base.cl = &cx_hash_map_class; |
416 map->base.base.allocator = allocator; |
416 map->base.collection.allocator = allocator; |
417 |
417 |
418 if (itemsize > 0) { |
418 if (itemsize > 0) { |
419 map->base.base.store_pointer = false; |
419 map->base.collection.store_pointer = false; |
420 map->base.base.elem_size = itemsize; |
420 map->base.collection.elem_size = itemsize; |
421 } else { |
421 } else { |
422 map->base.base.store_pointer = true; |
422 map->base.collection.store_pointer = true; |
423 map->base.base.elem_size = sizeof(void *); |
423 map->base.collection.elem_size = sizeof(void *); |
424 } |
424 } |
425 |
425 |
426 return (CxMap *) map; |
426 return (CxMap *) map; |
427 } |
427 } |
428 |
428 |
429 int cxMapRehash(CxMap *map) { |
429 int cxMapRehash(CxMap *map) { |
430 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; |
431 if (map->base.size > ((hash_map->bucket_count * 3) >> 2)) { |
431 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) { |
432 |
432 |
433 size_t new_bucket_count = (map->base.size * 5) >> 1; |
433 size_t new_bucket_count = (map->collection.size * 5) >> 1; |
434 struct cx_hash_map_element_s **new_buckets = cxCalloc( |
434 struct cx_hash_map_element_s **new_buckets = cxCalloc( |
435 map->base.allocator, |
435 map->collection.allocator, |
436 new_bucket_count, sizeof(struct cx_hash_map_element_s *) |
436 new_bucket_count, sizeof(struct cx_hash_map_element_s *) |
437 ); |
437 ); |
438 |
438 |
439 if (new_buckets == NULL) { |
439 if (new_buckets == NULL) { |
440 return 1; |
440 return 1; |