dict.c revision 82fa4c470a908ab4fc6713d120ae87b278edeacf
1/* 2 * This file is part of ltrace. 3 * Copyright (C) 2012 Petr Machata, Red Hat Inc. 4 * 5 * This program is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU General Public License as 7 * published by the Free Software Foundation; either version 2 of the 8 * License, or (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, but 11 * WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, write to the Free Software 17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 18 * 02110-1301 USA 19 */ 20 21#include <string.h> 22#include <stdlib.h> 23#include <stdio.h> 24#include "dict.h" 25 26struct status_bits { 27 unsigned char taken : 1; 28 unsigned char erased : 1; 29}; 30 31static struct status_bits * 32bitp(struct dict *dict, size_t n) 33{ 34 return VECT_ELEMENT(&dict->status, struct status_bits, n); 35} 36 37void 38dict_init(struct dict *dict, 39 size_t key_size, size_t value_size, 40 size_t (*hash1)(const void *), 41 int (*eq)(const void *, const void *), 42 size_t (*hash2)(size_t)) 43{ 44 assert(hash1 != NULL); 45 assert(eq != NULL); 46 47 vect_init(&dict->keys, key_size); 48 vect_init(&dict->values, value_size); 49 VECT_INIT(&dict->status, struct status_bits); 50 dict->size = 0; 51 52 dict->hash1 = hash1; 53 dict->hash2 = hash2; 54 dict->eq = eq; 55} 56 57struct clone_data { 58 struct dict *target; 59 int (*clone_key)(void *tgt, const void *src, void *data); 60 int (*clone_value)(void *tgt, const void *src, void *data); 61 void (*dtor_key)(void *tgt, void *data); 62 void (*dtor_value)(void *tgt, void *data); 63 void *data; 64}; 65 66static enum callback_status 67clone_cb(void *key, void *value, void *data) 68{ 69 struct clone_data *clone_data = data; 70 71 char nkey[clone_data->target->keys.elt_size]; 72 if (clone_data->clone_key == NULL) 73 memmove(nkey, key, sizeof(nkey)); 74 else if (clone_data->clone_key(&nkey, key, clone_data->data) < 0) 75 return CBS_STOP; 76 77 char nvalue[clone_data->target->values.elt_size]; 78 if (clone_data->clone_value == NULL) { 79 memmove(nvalue, value, sizeof(nvalue)); 80 } else if (clone_data->clone_value(&nvalue, value, 81 clone_data->data) < 0) { 82 fail: 83 if (clone_data->clone_key != NULL) 84 clone_data->dtor_key(&nkey, clone_data->data); 85 return CBS_STOP; 86 } 87 88 if (dict_insert(clone_data->target, nkey, nvalue) < 0) { 89 if (clone_data->clone_value != NULL) 90 clone_data->dtor_value(&nvalue, clone_data->data); 91 goto fail; 92 } 93 94 return CBS_CONT; 95} 96 97int 98dict_clone(struct dict *target, const struct dict *source, 99 int (*clone_key)(void *tgt, const void *src, void *data), 100 void (*dtor_key)(void *tgt, void *data), 101 int (*clone_value)(void *tgt, const void *src, void *data), 102 void (*dtor_value)(void *tgt, void *data), 103 void *data) 104{ 105 assert((clone_key != NULL) == (dtor_key != NULL)); 106 assert((clone_value != NULL) == (dtor_value != NULL)); 107 108 dict_init(target, source->keys.elt_size, source->values.elt_size, 109 source->hash1, source->eq, source->hash2); 110 struct clone_data clone_data = { 111 target, clone_key, clone_value, dtor_key, dtor_value, data 112 }; 113 if (dict_each((struct dict *)source, NULL, 114 clone_cb, &clone_data) != NULL) { 115 dict_destroy(target, dtor_key, dtor_value, data); 116 return -1; 117 } 118 return 0; 119} 120 121size_t 122dict_size(const struct dict *dict) 123{ 124 return dict->size; 125} 126 127int 128dict_empty(const struct dict *dict) 129{ 130 return dict->size == 0; 131} 132 133struct destroy_data { 134 void (*dtor_key)(void *tgt, void *data); 135 void (*dtor_value)(void *tgt, void *data); 136 void *data; 137}; 138 139static enum callback_status 140destroy_cb(void *key, void *value, void *data) 141{ 142 struct destroy_data *destroy_data = data; 143 if (destroy_data->dtor_key) 144 destroy_data->dtor_key(key, destroy_data->data); 145 if (destroy_data->dtor_value) 146 destroy_data->dtor_value(value, destroy_data->data); 147 return CBS_CONT; 148} 149 150void 151dict_destroy(struct dict *dict, 152 void (*dtor_key)(void *tgt, void *data), 153 void (*dtor_value)(void *tgt, void *data), 154 void *data) 155{ 156 /* Some keys and values are not initialized, so we can't call 157 * dtors for them. Iterate DICT instead. */ 158 if (dtor_key != NULL || dtor_value != NULL) { 159 struct destroy_data destroy_data = { 160 dtor_key, dtor_value, data 161 }; 162 dict_each(dict, NULL, destroy_cb, &destroy_data); 163 } 164 165 vect_destroy(&dict->keys, NULL, NULL); 166 vect_destroy(&dict->values, NULL, NULL); 167 vect_destroy(&dict->status, NULL, NULL); 168} 169 170static size_t 171default_secondary_hash(size_t pos) 172{ 173 return pos % 97 + 1; 174} 175 176static size_t 177small_secondary_hash(size_t pos) 178{ 179 return 1; 180} 181 182static inline size_t 183n(struct dict *dict) 184{ 185 return vect_size(&dict->keys); 186} 187 188static inline size_t (* 189hash2(struct dict *dict))(size_t) 190{ 191 if (dict->hash2 != NULL) 192 return dict->hash2; 193 else if (n(dict) < 100) 194 return small_secondary_hash; 195 else 196 return default_secondary_hash; 197} 198 199static void * 200getkey(struct dict *dict, size_t pos) 201{ 202 return ((unsigned char *)dict->keys.data) 203 + dict->keys.elt_size * pos; 204} 205 206static void * 207getvalue(struct dict *dict, size_t pos) 208{ 209 return ((unsigned char *)dict->values.data) 210 + dict->values.elt_size * pos; 211} 212 213static size_t 214find_slot(struct dict *dict, const void *key, 215 int *foundp, int *should_rehash, size_t *pi) 216{ 217 assert(n(dict) > 0); 218 size_t pos = dict->hash1(key) % n(dict); 219 size_t pos0 = -1; 220 size_t d = hash2(dict)(pos); 221 size_t i = 0; 222 *foundp = 0; 223 224 /* We skip over any taken or erased slots. But we remember 225 * the first erased that we find, and if we don't find the key 226 * later, we return that position. */ 227 for (; bitp(dict, pos)->taken || bitp(dict, pos)->erased; 228 pos = (pos + d) % n(dict)) { 229 if (pos0 == (size_t)-1 && bitp(dict, pos)->erased) 230 pos0 = pos; 231 232 /* If there is a loop, but we've seen an erased 233 * element, take that one. Otherwise give up. */ 234 if (++i > dict->size) { 235 if (pos0 != (size_t)-1) 236 break; 237 return (size_t)-1; 238 } 239 240 if (bitp(dict, pos)->taken 241 && dict->eq(getkey(dict, pos), key)) { 242 *foundp = 1; 243 break; 244 } 245 } 246 247 if (!*foundp && pos0 != (size_t)-1) 248 pos = pos0; 249 250 /* If the hash table degraded into a linked list, request a 251 * rehash. */ 252 if (should_rehash != NULL) 253 *should_rehash = i > 10 && i > n(dict) / 10; 254 255 if (pi != NULL) 256 *pi = i; 257 return pos; 258} 259 260static enum callback_status 261rehash_move(void *key, void *value, void *data) 262{ 263 if (dict_insert(data, key, value) < 0) 264 return CBS_STOP; 265 else 266 return CBS_CONT; 267} 268 269static int 270rehash(struct dict *dict, size_t nn) 271{ 272 assert(nn != n(dict)); 273 int ret = -1; 274 275 struct dict tmp; 276 dict_init(&tmp, dict->keys.elt_size, dict->values.elt_size, 277 dict->hash1, dict->eq, dict->hash2); 278 279 /* To honor all invariants (so that we can safely call 280 * dict_destroy), we first make a request to _reserve_ enough 281 * room in all vectors. This has no observable effect on 282 * contents of vectors. */ 283 if (vect_reserve(&tmp.keys, nn) < 0 284 || vect_reserve(&tmp.values, nn) < 0 285 || vect_reserve(&tmp.status, nn) < 0) 286 goto done; 287 288 /* Now that we know that there is enough size in vectors, we 289 * simply bump the size. */ 290 tmp.keys.size = nn; 291 tmp.values.size = nn; 292 size_t old_size = tmp.status.size; 293 tmp.status.size = nn; 294 memset(VECT_ELEMENT(&tmp.status, struct status_bits, old_size), 295 0, (tmp.status.size - old_size) * tmp.status.elt_size); 296 297 /* At this point, TMP is once more an empty dictionary with NN 298 * slots. Now move stuff from DICT to TMP. */ 299 if (dict_each(dict, NULL, rehash_move, &tmp) != NULL) 300 goto done; 301 302 /* And now swap contents of DICT and TMP, and we are done. */ 303 { 304 struct dict tmp2 = *dict; 305 *dict = tmp; 306 tmp = tmp2; 307 } 308 309 ret = 0; 310 311done: 312 /* We only want to release the containers, not the actual data 313 * that they hold, so it's fine if we don't pass any dtor. */ 314 dict_destroy(&tmp, NULL, NULL, NULL); 315 return ret; 316 317} 318 319static const size_t primes[] = { 320 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 321 8191, 16381, 32749, 65521, 130981, 0 322}; 323 324static size_t 325larger_size(size_t current) 326{ 327 if (current == 0) 328 return primes[0]; 329 330 if (current < primes[sizeof(primes)/sizeof(*primes) - 2]) { 331 size_t i; 332 for (i = 0; primes[i] != 0; ++i) 333 if (primes[i] > current) 334 return primes[i]; 335 abort(); 336 } 337 338 /* We ran out of primes, so invent a new one. The following 339 * gives primes until about 17M elements (and then some more 340 * later). */ 341 return 2 * current + 6585; 342} 343 344static size_t 345smaller_size(size_t current) 346{ 347 if (current <= primes[0]) 348 return primes[0]; 349 350 if (current <= primes[sizeof(primes)/sizeof(*primes) - 2]) { 351 size_t i; 352 size_t prev = 0; 353 for (i = 0; primes[i] != 0; ++i) { 354 if (primes[i] >= current) 355 return prev; 356 prev = primes[i]; 357 } 358 abort(); 359 } 360 361 return (current - 6585) / 2; 362} 363 364int 365dict_insert(struct dict *dict, void *key, void *value) 366{ 367 if (n(dict) == 0 || dict->size > 0.7 * n(dict)) 368 rehash: 369 if (rehash(dict, larger_size(n(dict))) < 0) 370 return -1; 371 372 int found; 373 int should_rehash; 374 size_t slot_n = find_slot(dict, key, &found, &should_rehash, NULL); 375 if (slot_n == (size_t)-1) 376 return -1; 377 if (found) 378 return 1; 379 assert(!bitp(dict, slot_n)->taken); 380 381 /* If rehash was requested, do that, and retry. But just live 382 * with it for apparently sparse tables. No resizing can fix 383 * a rubbish hash. */ 384 if (should_rehash && dict->size > 0.3 * n(dict)) 385 goto rehash; 386 387 memmove(getkey(dict, slot_n), key, dict->keys.elt_size); 388 memmove(getvalue(dict, slot_n), value, dict->values.elt_size); 389 390 bitp(dict, slot_n)->taken = 1; 391 bitp(dict, slot_n)->erased = 0; 392 ++dict->size; 393 394 return 0; 395} 396 397void * 398dict_find(struct dict *dict, const void *key) 399{ 400 if (dict->size == 0) 401 return NULL; 402 assert(n(dict) > 0); 403 404 int found; 405 size_t slot_n = find_slot(dict, key, &found, NULL, NULL); 406 if (found) 407 return getvalue(dict, slot_n); 408 else 409 return NULL; 410} 411 412int 413dict_erase(struct dict *dict, const void *key, 414 void (*dtor_key)(void *tgt, void *data), 415 void (*dtor_value)(void *tgt, void *data), 416 void *data) 417{ 418 int found; 419 size_t i; 420 size_t slot_n = find_slot(dict, key, &found, NULL, &i); 421 if (!found) 422 return -1; 423 424 if (dtor_key != NULL) 425 dtor_key(getkey(dict, slot_n), data); 426 if (dtor_value != NULL) 427 dtor_value(getvalue(dict, slot_n), data); 428 429 bitp(dict, slot_n)->taken = 0; 430 bitp(dict, slot_n)->erased = 1; 431 --dict->size; 432 433 if (dict->size < 0.3 * n(dict)) { 434 size_t smaller = smaller_size(n(dict)); 435 if (smaller != n(dict)) 436 /* Don't mind if it fails when shrinking. */ 437 rehash(dict, smaller); 438 } 439 440 return 0; 441} 442 443void * 444dict_each(struct dict *dict, void *start_after, 445 enum callback_status (*cb)(void *, void *, void *), void *data) 446{ 447 size_t i; 448 if (start_after != NULL) 449 i = ((start_after - dict->keys.data) / dict->keys.elt_size) + 1; 450 else 451 i = 0; 452 453 for (; i < dict->keys.size; ++i) 454 if (bitp(dict, i)->taken && !bitp(dict, i)->erased) { 455 void *key = getkey(dict, i); 456 if (cb(key, getvalue(dict, i), data) != CBS_CONT) 457 return key; 458 } 459 460 return NULL; 461} 462 463size_t 464dict_hash_int(const int *key) 465{ 466 return (size_t)(*key * 2654435761); 467} 468 469int 470dict_eq_int(const int *key1, const int *key2) 471{ 472 return *key1 == *key2; 473} 474 475size_t 476dict_hash_string(const char **key) 477{ 478 size_t h = 5381; 479 const char *str = *key; 480 while (*str != 0) 481 h = h * 33 ^ *str++; 482 return h; 483} 484 485int 486dict_eq_string(const char **key1, const char **key2) 487{ 488 return strcmp(*key1, *key2) == 0; 489} 490 491void 492dict_dtor_string(const char **key, void *data) 493{ 494 free((char *)*key); 495} 496 497int 498dict_clone_string(const char **tgt, const char **src, void *data) 499{ 500 *tgt = strdup(*src); 501 return *tgt != NULL ? 0 : -1; 502} 503 504#ifdef TEST 505static enum callback_status 506dump(int *key, int *value, void *data) 507{ 508 char *seen = data; 509 assert(seen[*key] == 0); 510 seen[*key] = 1; 511 assert(*value == *key * 2 + 1); 512 return CBS_STOP; 513} 514 515static size_t 516dict_hash_int_silly(const int *key) 517{ 518 return *key % 10; 519} 520 521static void 522verify(struct dict *di, size_t len, char *seen) 523{ 524 size_t ct = 0; 525 int *it; 526 for (it = NULL; (it = DICT_EACH(di, int, int, it, dump, seen)) != NULL;) 527 ct++; 528 assert(ct == len); 529 memset(seen, 0, len); 530} 531 532static enum callback_status 533fill_keys(int *key, int *value, void *data) 534{ 535 int *array = data; 536 array[++array[0]] = *key; 537 return CBS_CONT; 538} 539 540static void 541test1(void) 542{ 543 struct dict di; 544 DICT_INIT(&di, int, int, dict_hash_int, dict_eq_int, NULL); 545 546 char seen[100000] = {}; 547 size_t i; 548 for (i = 0; i < sizeof(seen); ++i) { 549 int key = i; 550 int value = 2 * i + 1; 551 DICT_INSERT(&di, &key, &value); 552 int *valp = DICT_FIND(&di, &key, int); 553 assert(valp != NULL); 554 assert(*valp == value); 555 assert(dict_size(&di) == i + 1); 556 } 557 558 verify(&di, sizeof(seen), seen); 559 560 struct dict d2; 561 DICT_CLONE(&d2, &di, int, int, NULL, NULL, NULL, NULL, NULL); 562 DICT_DESTROY(&di, int, int, NULL, NULL, NULL); 563 verify(&d2, sizeof(seen), seen); 564 565 /* Now we try to gradually erase all elements. We can't erase 566 * inside a DICT_EACH call, so copy first keys to a separate 567 * memory area first. */ 568 int keys[d2.size + 1]; 569 size_t ct = 0; 570 keys[0] = 0; 571 DICT_EACH(&d2, int, int, NULL, fill_keys, keys); 572 for (i = 0; i < (size_t)keys[0]; ++i) { 573 assert(DICT_ERASE(&d2, &keys[i + 1], int, 574 NULL, NULL, NULL) == 0); 575 ++ct; 576 } 577 assert(ct == sizeof(seen)); 578 DICT_DESTROY(&d2, int, int, NULL, NULL, NULL); 579} 580 581static void 582test_erase(void) 583{ 584 int i; 585 586 /* To test erase, we need a relatively bad hash function, so 587 * that there are some overlapping chains in the table. */ 588 struct dict d2; 589 DICT_INIT(&d2, int, int, dict_hash_int_silly, dict_eq_int, NULL); 590 const int limit = 500; 591 for (i = 0; i < limit; ++i) { 592 int key = 2 * i + 1; 593 int value = 2 * key + 1; 594 DICT_INSERT(&d2, &key, &value); 595 } 596 597 /* Now we try to delete each of the keys, and verify that none 598 * of the chains was broken. */ 599 for (i = 0; i < limit; ++i) { 600 struct dict copy; 601 DICT_CLONE(©, &d2, int, int, NULL, NULL, NULL, NULL, NULL); 602 int key = 2 * i + 1; 603 DICT_ERASE(©, &key, int, NULL, NULL, NULL); 604 assert(dict_size(©) == dict_size(&d2) - 1); 605 606 int j; 607 for (j = 0; j < limit; ++j) { 608 key = 2 * j + 1; 609 int *valp = DICT_FIND(©, &key, int); 610 if (i != j) { 611 assert(valp != NULL); 612 assert(*valp == 2 * key + 1); 613 } else { 614 assert(valp == NULL); 615 } 616 } 617 618 DICT_DESTROY(©, int, int, NULL, NULL, NULL); 619 } 620 DICT_DESTROY(&d2, int, int, NULL, NULL, NULL); 621} 622 623int main(int argc, char *argv[]) 624{ 625 test1(); 626 test_erase(); 627 return 0; 628} 629 630#endif 631