comparison: ucx/hash_map.c
ucx/hash_map.c
- changeset 102
- 64ded9f6a6c6
- parent 101
- 7b3a3130be44
equal
deleted
inserted
replaced
| 101:7b3a3130be44 | 102:64ded9f6a6c6 |
|---|---|
| 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 && 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, but call destructors first |
| 107 cx_invoke_destructor(map, elm->data); | |
| 107 if (map->collection.store_pointer) { | 108 if (map->collection.store_pointer) { |
| 108 memcpy(elm->data, &value, sizeof(void *)); | 109 memcpy(elm->data, &value, sizeof(void *)); |
| 109 } else { | 110 } else { |
| 110 memcpy(elm->data, value, map->collection.elem_size); | 111 memcpy(elm->data, value, map->collection.elem_size); |
| 111 } | 112 } |
| 250 ) { | 251 ) { |
| 251 return cx_hash_map_get_remove(map, key, targetbuf, true); | 252 return cx_hash_map_get_remove(map, key, targetbuf, true); |
| 252 } | 253 } |
| 253 | 254 |
| 254 static void *cx_hash_map_iter_current_entry(const void *it) { | 255 static void *cx_hash_map_iter_current_entry(const void *it) { |
| 255 const struct cx_iterator_s *iter = it; | 256 const CxMapIterator *iter = it; |
| 256 // struct has to have a compatible signature | 257 // we have to cast away const, because of the signature |
| 257 return (struct cx_map_entry_s *) &(iter->kv_data); | 258 return (void*) &iter->entry; |
| 258 } | 259 } |
| 259 | 260 |
| 260 static void *cx_hash_map_iter_current_key(const void *it) { | 261 static void *cx_hash_map_iter_current_key(const void *it) { |
| 261 const struct cx_iterator_s *iter = it; | 262 const CxMapIterator *iter = it; |
| 262 struct cx_hash_map_element_s *elm = iter->elem_handle; | 263 struct cx_hash_map_element_s *elm = iter->elem; |
| 263 return &elm->key; | 264 return &elm->key; |
| 264 } | 265 } |
| 265 | 266 |
| 266 static void *cx_hash_map_iter_current_value(const void *it) { | 267 static void *cx_hash_map_iter_current_value(const void *it) { |
| 267 const struct cx_iterator_s *iter = it; | 268 const CxMapIterator *iter = it; |
| 268 const struct cx_hash_map_s *map = iter->src_handle.c; | 269 const CxMap *map = iter->map.c; |
| 269 struct cx_hash_map_element_s *elm = iter->elem_handle; | 270 struct cx_hash_map_element_s *elm = iter->elem; |
| 270 if (map->base.collection.store_pointer) { | 271 if (map->collection.store_pointer) { |
| 271 return *(void **) elm->data; | 272 return *(void **) elm->data; |
| 272 } else { | 273 } else { |
| 273 return elm->data; | 274 return elm->data; |
| 274 } | 275 } |
| 275 } | 276 } |
| 276 | 277 |
| 277 static bool cx_hash_map_iter_valid(const void *it) { | 278 static bool cx_hash_map_iter_valid(const void *it) { |
| 278 const struct cx_iterator_s *iter = it; | 279 const CxMapIterator *iter = it; |
| 279 return iter->elem_handle != NULL; | 280 return iter->elem != NULL; |
| 280 } | 281 } |
| 281 | 282 |
| 282 static void cx_hash_map_iter_next(void *it) { | 283 static void cx_hash_map_iter_next(void *it) { |
| 283 struct cx_iterator_s *iter = it; | 284 CxMapIterator *iter = it; |
| 284 struct cx_hash_map_element_s *elm = iter->elem_handle; | 285 CxMap *map = iter->map.m; |
| 285 struct cx_hash_map_s *map = iter->src_handle.m; | 286 struct cx_hash_map_s *hmap = (struct cx_hash_map_s *) map; |
| 287 struct cx_hash_map_element_s *elm = iter->elem; | |
| 286 | 288 |
| 287 // remove current element, if asked | 289 // remove current element, if asked |
| 288 if (iter->base.remove) { | 290 if (iter->base.remove) { |
| 289 | 291 |
| 290 // clear the flag | 292 // clear the flag |
| 293 // determine the next element | 295 // determine the next element |
| 294 struct cx_hash_map_element_s *next = elm->next; | 296 struct cx_hash_map_element_s *next = elm->next; |
| 295 | 297 |
| 296 // search the previous element | 298 // search the previous element |
| 297 struct cx_hash_map_element_s *prev = NULL; | 299 struct cx_hash_map_element_s *prev = NULL; |
| 298 if (map->buckets[iter->slot] != elm) { | 300 if (hmap->buckets[iter->slot] != elm) { |
| 299 prev = map->buckets[iter->slot]; | 301 prev = hmap->buckets[iter->slot]; |
| 300 while (prev->next != elm) { | 302 while (prev->next != elm) { |
| 301 prev = prev->next; | 303 prev = prev->next; |
| 302 } | 304 } |
| 303 } | 305 } |
| 304 | 306 |
| 305 // destroy | 307 // destroy |
| 306 cx_invoke_destructor((struct cx_map_s *) map, elm->data); | 308 cx_invoke_destructor(map, elm->data); |
| 307 | 309 |
| 308 // unlink | 310 // unlink |
| 309 cx_hash_map_unlink(map, iter->slot, prev, elm); | 311 cx_hash_map_unlink(hmap, iter->slot, prev, elm); |
| 310 | 312 |
| 311 // advance | 313 // advance |
| 312 elm = next; | 314 elm = next; |
| 313 } else { | 315 } else { |
| 314 // just advance | 316 // just advance |
| 315 elm = elm->next; | 317 elm = elm->next; |
| 316 iter->index++; | 318 iter->index++; |
| 317 } | 319 } |
| 318 | 320 |
| 319 // search the next bucket, if required | 321 // search the next bucket, if required |
| 320 while (elm == NULL && ++iter->slot < map->bucket_count) { | 322 while (elm == NULL && ++iter->slot < hmap->bucket_count) { |
| 321 elm = map->buckets[iter->slot]; | 323 elm = hmap->buckets[iter->slot]; |
| 322 } | 324 } |
| 323 | 325 iter->elem = elm; |
| 324 // fill the struct with the next element | 326 |
| 325 iter->elem_handle = elm; | 327 // copy data to a location where the iterator can point to |
| 326 if (elm == NULL) { | 328 // we need to do it here, because the iterator function call |
| 327 iter->kv_data.key = NULL; | 329 // must not modify the iterator (the parameter is const) |
| 328 iter->kv_data.value = NULL; | 330 if (elm != NULL) { |
| 329 } else { | 331 iter->entry.key = &elm->key; |
| 330 iter->kv_data.key = &elm->key; | 332 if (iter->map.c->collection.store_pointer) { |
| 331 if (map->base.collection.store_pointer) { | 333 iter->entry.value = *(void **) elm->data; |
| 332 iter->kv_data.value = *(void **) elm->data; | |
| 333 } else { | 334 } else { |
| 334 iter->kv_data.value = elm->data; | 335 iter->entry.value = elm->data; |
| 335 } | 336 } |
| 336 } | 337 } |
| 337 } | 338 } |
| 338 | 339 |
| 339 static CxIterator cx_hash_map_iterator( | 340 static CxMapIterator cx_hash_map_iterator( |
| 340 const CxMap *map, | 341 const CxMap *map, |
| 341 enum cx_map_iterator_type type | 342 enum cx_map_iterator_type type |
| 342 ) { | 343 ) { |
| 343 CxIterator iter; | 344 CxMapIterator iter; |
| 344 | 345 |
| 345 iter.src_handle.c = map; | 346 iter.map.c = map; |
| 346 iter.elem_count = map->collection.size; | 347 iter.elem_count = map->collection.size; |
| 347 | 348 |
| 348 switch (type) { | 349 switch (type) { |
| 349 case CX_MAP_ITERATOR_PAIRS: | 350 case CX_MAP_ITERATOR_PAIRS: |
| 350 iter.elem_size = sizeof(CxMapEntry); | 351 iter.elem_size = sizeof(CxMapEntry); |
| 374 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; | 375 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
| 375 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; | 376 struct cx_hash_map_element_s *elm = hash_map->buckets[0]; |
| 376 while (elm == NULL) { | 377 while (elm == NULL) { |
| 377 elm = hash_map->buckets[++iter.slot]; | 378 elm = hash_map->buckets[++iter.slot]; |
| 378 } | 379 } |
| 379 iter.elem_handle = elm; | 380 iter.elem = elm; |
| 380 iter.kv_data.key = &elm->key; | 381 iter.entry.key = &elm->key; |
| 381 if (map->collection.store_pointer) { | 382 if (map->collection.store_pointer) { |
| 382 iter.kv_data.value = *(void **) elm->data; | 383 iter.entry.value = *(void **) elm->data; |
| 383 } else { | 384 } else { |
| 384 iter.kv_data.value = elm->data; | 385 iter.entry.value = elm->data; |
| 385 } | 386 } |
| 386 } else { | 387 } else { |
| 387 iter.elem_handle = NULL; | 388 iter.elem = NULL; |
| 388 iter.kv_data.key = NULL; | |
| 389 iter.kv_data.value = NULL; | |
| 390 } | 389 } |
| 391 | 390 |
| 392 return iter; | 391 return iter; |
| 393 } | 392 } |
| 394 | 393 |
| 431 // initialize base members | 430 // initialize base members |
| 432 map->base.cl = &cx_hash_map_class; | 431 map->base.cl = &cx_hash_map_class; |
| 433 map->base.collection.allocator = allocator; | 432 map->base.collection.allocator = allocator; |
| 434 | 433 |
| 435 if (itemsize > 0) { | 434 if (itemsize > 0) { |
| 436 map->base.collection.store_pointer = false; | |
| 437 map->base.collection.elem_size = itemsize; | 435 map->base.collection.elem_size = itemsize; |
| 438 } else { | 436 } else { |
| 437 map->base.collection.elem_size = sizeof(void *); | |
| 439 map->base.collection.store_pointer = true; | 438 map->base.collection.store_pointer = true; |
| 440 map->base.collection.elem_size = sizeof(void *); | |
| 441 } | 439 } |
| 442 | 440 |
| 443 return (CxMap *) map; | 441 return (CxMap *) map; |
| 444 } | 442 } |
| 445 | 443 |
