Mercurial > hg > dav / file comparison

comparison: ucx/hash_map.c

ucx/hash_map.c

branch
dav-2
changeset 889
42cdbf9bbd49
parent 886
da79af4baec8
equal deleted inserted replaced
887:26541c37b619 889:42cdbf9bbd49
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 const CxAllocator *allocator = map->collection.allocator; 87 const CxAllocator *allocator = map->collection.allocator;
88 88
89 unsigned hash = key.hash; 89 uint64_t 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;
93 } 93 }
94 94
99 while (elm != NULL && elm->key.hash < hash) { 99 while (elm != NULL && elm->key.hash < hash) {
100 prev = elm; 100 prev = elm;
101 elm = elm->next; 101 elm = elm->next;
102 } 102 }
103 103
104 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && 104 if (elm != NULL && cx_hash_key_cmp(&elm->key, &key) == 0) {
105 memcmp(elm->key.data, key.data, key.len) == 0) {
106 // overwrite existing element, but call destructors first 105 // overwrite existing element, but call destructors first
107 cx_invoke_destructor(map, elm->data); 106 cx_invoke_destructor(map, elm->data);
108 if (value == NULL) { 107 if (value == NULL) {
109 memset(elm->data, 0, map->collection.elem_size); 108 memset(elm->data, 0, map->collection.elem_size);
110 } else if (map->collection.store_pointer) { 109 } else if (map->collection.store_pointer) {
202 void *targetbuf, 201 void *targetbuf,
203 bool remove 202 bool remove
204 ) { 203 ) {
205 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; 204 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
206 205
207 unsigned hash = key.hash; 206 uint64_t hash = key.hash;
208 if (hash == 0) { 207 if (hash == 0) {
209 cx_hash_murmur(&key); 208 cx_hash_murmur(&key);
210 hash = key.hash; 209 hash = key.hash;
211 } 210 }
212 211
213 size_t slot = hash % hash_map->bucket_count; 212 size_t slot = hash % hash_map->bucket_count;
214 struct cx_hash_map_element_s *elm = hash_map->buckets[slot]; 213 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
215 struct cx_hash_map_element_s *prev = NULL; 214 struct cx_hash_map_element_s *prev = NULL;
216 while (elm && elm->key.hash <= hash) { 215 while (elm && elm->key.hash <= hash) {
217 if (elm->key.hash == hash && elm->key.len == key.len) { 216 if (cx_hash_key_cmp(&elm->key, &key) == 0) {
218 if (memcmp(elm->key.data, key.data, key.len) == 0) { 217 if (remove) {
219 if (remove) { 218 if (targetbuf == NULL) {
220 if (targetbuf == NULL) { 219 cx_invoke_destructor(map, elm->data);
221 cx_invoke_destructor(map, elm->data);
222 } else {
223 memcpy(targetbuf, elm->data, map->collection.elem_size);
224 }
225 cx_hash_map_unlink(hash_map, slot, prev, elm);
226 } else { 220 } else {
227 assert(targetbuf != NULL); 221 memcpy(targetbuf, elm->data, map->collection.elem_size);
228 void *data = NULL;
229 if (map->collection.store_pointer) {
230 data = *(void **) elm->data;
231 } else {
232 data = elm->data;
233 }
234 memcpy(targetbuf, &data, sizeof(void *));
235 } 222 }
236 return 0; 223 cx_hash_map_unlink(hash_map, slot, prev, elm);
224 } else {
225 assert(targetbuf != NULL);
226 void *data = NULL;
227 if (map->collection.store_pointer) {
228 data = *(void **) elm->data;
229 } else {
230 data = elm->data;
231 }
232 memcpy(targetbuf, &data, sizeof(void *));
237 } 233 }
234 return 0;
238 } 235 }
239 prev = elm; 236 prev = elm;
240 elm = prev->next; 237 elm = prev->next;
241 } 238 }
242 239
267 return (void*) &iter->entry; 264 return (void*) &iter->entry;
268 } 265 }
269 266
270 static void *cx_hash_map_iter_current_key(const void *it) { 267 static void *cx_hash_map_iter_current_key(const void *it) {
271 const CxMapIterator *iter = it; 268 const CxMapIterator *iter = it;
272 struct cx_hash_map_element_s *elm = iter->elem; 269 return (void*) iter->entry.key;
273 return &elm->key;
274 } 270 }
275 271
276 static void *cx_hash_map_iter_current_value(const void *it) { 272 static void *cx_hash_map_iter_current_value(const void *it) {
277 const CxMapIterator *iter = it; 273 const CxMapIterator *iter = it;
278 const CxMap *map = iter->map.c; 274 return iter->entry.value;
279 struct cx_hash_map_element_s *elm = iter->elem;
280 if (map->collection.store_pointer) {
281 return *(void **) elm->data;
282 } else {
283 return elm->data;
284 }
285 } 275 }
286 276
287 static bool cx_hash_map_iter_valid(const void *it) { 277 static bool cx_hash_map_iter_valid(const void *it) {
288 const CxMapIterator *iter = it; 278 const CxMapIterator *iter = it;
289 return iter->elem != NULL; 279 return iter->elem != NULL;
290 } 280 }
291 281
292 static void cx_hash_map_iter_next(void *it) { 282 static void cx_hash_map_iter_next(void *it) {
293 CxMapIterator *iter = it; 283 CxMapIterator *iter = it;
294 CxMap *map = iter->map.m; 284 CxMap *map = iter->map;
295 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; 285 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map;
296 struct cx_hash_map_element_s *elm = iter->elem; 286 struct cx_hash_map_element_s *elm = iter->elem;
297 287
298 // remove current element, if asked 288 // remove current element, if asked
299 if (iter->base.remove) { 289 if (iter->base.remove) {
316 // destroy 306 // destroy
317 cx_invoke_destructor(map, elm->data); 307 cx_invoke_destructor(map, elm->data);
318 308
319 // unlink 309 // unlink
320 cx_hash_map_unlink(hmap, iter->slot, prev, elm); 310 cx_hash_map_unlink(hmap, iter->slot, prev, elm);
311 iter->elem_count--;
321 312
322 // advance 313 // advance
323 elm = next; 314 elm = next;
324 } else { 315 } else {
325 // just advance 316 // just advance
336 // copy data to a location where the iterator can point to 327 // copy data to a location where the iterator can point to
337 // we need to do it here, because the iterator function call 328 // we need to do it here, because the iterator function call
338 // must not modify the iterator (the parameter is const) 329 // must not modify the iterator (the parameter is const)
339 if (elm != NULL) { 330 if (elm != NULL) {
340 iter->entry.key = &elm->key; 331 iter->entry.key = &elm->key;
341 if (iter->map.c->collection.store_pointer) { 332 if (map->collection.store_pointer) {
342 iter->entry.value = *(void **) elm->data; 333 iter->entry.value = *(void **) elm->data;
343 } else { 334 } else {
344 iter->entry.value = elm->data; 335 iter->entry.value = elm->data;
345 } 336 }
346 } 337 }
350 const CxMap *map, 341 const CxMap *map,
351 enum cx_map_iterator_type type 342 enum cx_map_iterator_type type
352 ) { 343 ) {
353 CxMapIterator iter; 344 CxMapIterator iter;
354 345
355 iter.map.c = map; 346 iter.map = (CxMap*) map;
356 iter.elem_count = map->collection.size; 347 iter.elem_count = map->collection.size;
357 348
358 switch (type) { 349 switch (type) {
359 case CX_MAP_ITERATOR_PAIRS: 350 case CX_MAP_ITERATOR_PAIRS:
360 iter.elem_size = sizeof(CxMapEntry); 351 iter.elem_size = sizeof(CxMapEntry);
373 } 364 }
374 365
375 iter.base.valid = cx_hash_map_iter_valid; 366 iter.base.valid = cx_hash_map_iter_valid;
376 iter.base.next = cx_hash_map_iter_next; 367 iter.base.next = cx_hash_map_iter_next;
377 iter.base.remove = false; 368 iter.base.remove = false;
378 iter.base.mutating = false; 369 iter.base.allow_remove = true;
379 370
380 iter.slot = 0; 371 iter.slot = 0;
381 iter.index = 0; 372 iter.index = 0;
382 373
383 if (map->collection.size > 0) { 374 if (map->collection.size > 0) {

Mercurial Repository: dav

mercurial