Mercurial > hg > ucx / file comparison

comparison: src/hash_map.c

src/hash_map.c

changeset 856
6bbbf219251d
parent 855
35bcb3216c0d
equal deleted inserted replaced
855:35bcb3216c0d 856:6bbbf219251d
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) {
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->base.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.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;
470 } 470 }
471 } 471 }
472 472
473 // assign result to the map 473 // assign result to the map
474 hash_map->bucket_count = new_bucket_count; 474 hash_map->bucket_count = new_bucket_count;
475 cxFree(map->base.allocator, hash_map->buckets); 475 cxFree(map->collection.allocator, hash_map->buckets);
476 hash_map->buckets = new_buckets; 476 hash_map->buckets = new_buckets;
477 } 477 }
478 return 0; 478 return 0;
479 } 479 }

Mercurial Repository: ucx

mercurial