src/hashmap.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2010 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU General Public License as published by
  10   the Free Software Foundation; either version 2 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   General Public License for more details.
  17
  18   You should have received a copy of the GNU General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include <assert.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <errno.h>
  26
  27 #include "util.h"
  28 #include "hashmap.h"
  29 #include "macro.h"
  30
  31 #define NBUCKETS 127
  32
  33 struct hashmap_entry {
  34         const void *key;
  35         void *value;
  36         struct hashmap_entry *bucket_next, *bucket_previous;
  37         struct hashmap_entry *iterate_next, *iterate_previous;
  38 };
  39
  40 struct Hashmap {
  41         hash_func_t hash_func;
  42         compare_func_t compare_func;
  43
  44         struct hashmap_entry *iterate_list_head, *iterate_list_tail;
  45         unsigned n_entries;
  46
  47         bool from_pool;
  48 };
  49
  50 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
  51
  52 struct pool {
  53         struct pool *next;
  54         unsigned n_tiles;
  55         unsigned n_used;
  56 };
  57
  58 struct pool *first_hashmap_pool = NULL;
  59 static void *first_hashmap_tile = NULL;
  60
  61 struct pool *first_entry_pool = NULL;
  62 static void *first_entry_tile = NULL;
  63
  64 static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size) {
  65         unsigned i;
  66
  67         if (*first_tile) {
  68                 void *r;
  69
  70                 r = *first_tile;
  71                 *first_tile = * (void**) (*first_tile);
  72                 return r;
  73         }
  74
  75         if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
  76                 unsigned n;
  77                 size_t size;
  78                 struct pool *p;
  79
  80                 n = *first_pool ? (*first_pool)->n_tiles : 0;
  81                 n = MAX(512U, n * 2);
  82                 size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
  83                 n = (size - ALIGN(sizeof(struct pool))) / tile_size;
  84
  85                 p = malloc(size);
  86                 if (!p)
  87                         return NULL;
  88
  89                 p->next = *first_pool;
  90                 p->n_tiles = n;
  91                 p->n_used = 0;
  92
  93                 *first_pool = p;
  94         }
  95
  96         i = (*first_pool)->n_used++;
  97
  98         return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
  99 }
 100
 101 static void deallocate_tile(void **first_tile, void *p) {
 102         * (void**) p = *first_tile;
 103         *first_tile = p;
 104 }
 105
 106 #ifndef __OPTIMIZE__
 107
 108 static void drop_pool(struct pool *p) {
 109         while (p) {
 110                 struct pool *n;
 111                 n = p->next;
 112                 free(p);
 113                 p = n;
 114         }
 115 }
 116
 117 __attribute__((destructor)) static void cleanup_pool(void) {
 118         /* Be nice to valgrind */
 119
 120         drop_pool(first_hashmap_pool);
 121         drop_pool(first_entry_pool);
 122 }
 123
 124 #endif
 125
 126 unsigned string_hash_func(const void *p) {
 127         unsigned hash = 0;
 128         const char *c;
 129
 130         for (c = p; *c; c++)
 131                 hash = 31 * hash + (unsigned) *c;
 132
 133         return hash;
 134 }
 135
 136 int string_compare_func(const void *a, const void *b) {
 137         return strcmp(a, b);
 138 }
 139
 140 unsigned trivial_hash_func(const void *p) {
 141         return PTR_TO_UINT(p);
 142 }
 143
 144 int trivial_compare_func(const void *a, const void *b) {
 145         return a < b ? -1 : (a > b ? 1 : 0);
 146 }
 147
 148 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
 149         bool b;
 150         Hashmap *h;
 151         size_t size;
 152
 153         b = is_main_thread();
 154
 155         size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
 156
 157         if (b) {
 158                 h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
 159                 if (!h)
 160                         return NULL;
 161
 162                 memset(h, 0, size);
 163         } else {
 164                 h = malloc0(size);
 165
 166                 if (!h)
 167                         return NULL;
 168         }
 169
 170         h->hash_func = hash_func ? hash_func : trivial_hash_func;
 171         h->compare_func = compare_func ? compare_func : trivial_compare_func;
 172
 173         h->n_entries = 0;
 174         h->iterate_list_head = h->iterate_list_tail = NULL;
 175
 176         h->from_pool = b;
 177
 178         return h;
 179 }
 180
 181 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
 182         assert(h);
 183
 184         if (*h)
 185                 return 0;
 186
 187         if (!(*h = hashmap_new(hash_func, compare_func)))
 188                 return -ENOMEM;
 189
 190         return 0;
 191 }
 192
 193 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 194         assert(h);
 195         assert(e);
 196
 197         /* Insert into hash table */
 198         e->bucket_next = BY_HASH(h)[hash];
 199         e->bucket_previous = NULL;
 200         if (BY_HASH(h)[hash])
 201                 BY_HASH(h)[hash]->bucket_previous = e;
 202         BY_HASH(h)[hash] = e;
 203
 204         /* Insert into iteration list */
 205         e->iterate_previous = h->iterate_list_tail;
 206         e->iterate_next = NULL;
 207         if (h->iterate_list_tail) {
 208                 assert(h->iterate_list_head);
 209                 h->iterate_list_tail->iterate_next = e;
 210         } else {
 211                 assert(!h->iterate_list_head);
 212                 h->iterate_list_head = e;
 213         }
 214         h->iterate_list_tail = e;
 215
 216         h->n_entries++;
 217         assert(h->n_entries >= 1);
 218 }
 219
 220 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 221         assert(h);
 222         assert(e);
 223
 224         /* Remove from iteration list */
 225         if (e->iterate_next)
 226                 e->iterate_next->iterate_previous = e->iterate_previous;
 227         else
 228                 h->iterate_list_tail = e->iterate_previous;
 229
 230         if (e->iterate_previous)
 231                 e->iterate_previous->iterate_next = e->iterate_next;
 232         else
 233                 h->iterate_list_head = e->iterate_next;
 234
 235         /* Remove from hash table bucket list */
 236         if (e->bucket_next)
 237                 e->bucket_next->bucket_previous = e->bucket_previous;
 238
 239         if (e->bucket_previous)
 240                 e->bucket_previous->bucket_next = e->bucket_next;
 241         else
 242                 BY_HASH(h)[hash] = e->bucket_next;
 243
 244         assert(h->n_entries >= 1);
 245         h->n_entries--;
 246 }
 247
 248 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 249         unsigned hash;
 250
 251         assert(h);
 252         assert(e);
 253
 254         hash = h->hash_func(e->key) % NBUCKETS;
 255
 256         unlink_entry(h, e, hash);
 257
 258         if (h->from_pool)
 259                 deallocate_tile(&first_entry_tile, e);
 260         else
 261                 free(e);
 262 }
 263
 264 void hashmap_free(Hashmap*h) {
 265
 266         if (!h)
 267                 return;
 268
 269         hashmap_clear(h);
 270
 271         if (h->from_pool)
 272                 deallocate_tile(&first_hashmap_tile, h);
 273         else
 274                 free(h);
 275 }
 276
 277 void hashmap_free_free(Hashmap *h) {
 278         void *p;
 279
 280         while ((p = hashmap_steal_first(h)))
 281                 free(p);
 282
 283         hashmap_free(h);
 284 }
 285
 286 void hashmap_clear(Hashmap *h) {
 287         if (!h)
 288                 return;
 289
 290         while (h->iterate_list_head)
 291                 remove_entry(h, h->iterate_list_head);
 292 }
 293
 294 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 295         struct hashmap_entry *e;
 296         assert(h);
 297         assert(hash < NBUCKETS);
 298
 299         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 300                 if (h->compare_func(e->key, key) == 0)
 301                         return e;
 302
 303         return NULL;
 304 }
 305
 306 int hashmap_put(Hashmap *h, const void *key, void *value) {
 307         struct hashmap_entry *e;
 308         unsigned hash;
 309
 310         assert(h);
 311
 312         hash = h->hash_func(key) % NBUCKETS;
 313
 314         if ((e = hash_scan(h, hash, key))) {
 315
 316                 if (e->value == value)
 317                         return 0;
 318
 319                 return -EEXIST;
 320         }
 321
 322         if (h->from_pool)
 323                 e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
 324         else
 325                 e = new(struct hashmap_entry, 1);
 326
 327         if (!e)
 328                 return -ENOMEM;
 329
 330         e->key = key;
 331         e->value = value;
 332
 333         link_entry(h, e, hash);
 334
 335         return 1;
 336 }
 337
 338 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 339         struct hashmap_entry *e;
 340         unsigned hash;
 341
 342         assert(h);
 343
 344         hash = h->hash_func(key) % NBUCKETS;
 345
 346         if ((e = hash_scan(h, hash, key))) {
 347                 e->key = key;
 348                 e->value = value;
 349                 return 0;
 350         }
 351
 352         return hashmap_put(h, key, value);
 353 }
 354
 355 void* hashmap_get(Hashmap *h, const void *key) {
 356         unsigned hash;
 357         struct hashmap_entry *e;
 358
 359         if (!h)
 360                 return NULL;
 361
 362         hash = h->hash_func(key) % NBUCKETS;
 363
 364         if (!(e = hash_scan(h, hash, key)))
 365                 return NULL;
 366
 367         return e->value;
 368 }
 369
 370 void* hashmap_remove(Hashmap *h, const void *key) {
 371         struct hashmap_entry *e;
 372         unsigned hash;
 373         void *data;
 374
 375         if (!h)
 376                 return NULL;
 377
 378         hash = h->hash_func(key) % NBUCKETS;
 379
 380         if (!(e = hash_scan(h, hash, key)))
 381                 return NULL;
 382
 383         data = e->value;
 384         remove_entry(h, e);
 385
 386         return data;
 387 }
 388
 389 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 390         struct hashmap_entry *e;
 391         unsigned old_hash, new_hash;
 392
 393         if (!h)
 394                 return -ENOENT;
 395
 396         old_hash = h->hash_func(old_key) % NBUCKETS;
 397         if (!(e = hash_scan(h, old_hash, old_key)))
 398                 return -ENOENT;
 399
 400         new_hash = h->hash_func(new_key) % NBUCKETS;
 401         if (hash_scan(h, new_hash, new_key))
 402                 return -EEXIST;
 403
 404         unlink_entry(h, e, old_hash);
 405
 406         e->key = new_key;
 407         e->value = value;
 408
 409         link_entry(h, e, new_hash);
 410
 411         return 0;
 412 }
 413
 414 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 415         struct hashmap_entry *e, *k;
 416         unsigned old_hash, new_hash;
 417
 418         if (!h)
 419                 return -ENOENT;
 420
 421         old_hash = h->hash_func(old_key) % NBUCKETS;
 422         if (!(e = hash_scan(h, old_hash, old_key)))
 423                 return -ENOENT;
 424
 425         new_hash = h->hash_func(new_key) % NBUCKETS;
 426
 427         if ((k = hash_scan(h, new_hash, new_key)))
 428                 if (e != k)
 429                         remove_entry(h, k);
 430
 431         unlink_entry(h, e, old_hash);
 432
 433         e->key = new_key;
 434         e->value = value;
 435
 436         link_entry(h, e, new_hash);
 437
 438         return 0;
 439 }
 440
 441 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 442         struct hashmap_entry *e;
 443         unsigned hash;
 444
 445         if (!h)
 446                 return NULL;
 447
 448         hash = h->hash_func(key) % NBUCKETS;
 449
 450         if (!(e = hash_scan(h, hash, key)))
 451                 return NULL;
 452
 453         if (e->value != value)
 454                 return NULL;
 455
 456         remove_entry(h, e);
 457
 458         return value;
 459 }
 460
 461 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 462         struct hashmap_entry *e;
 463
 464         assert(i);
 465
 466         if (!h)
 467                 goto at_end;
 468
 469         if (*i == ITERATOR_LAST)
 470                 goto at_end;
 471
 472         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 473                 goto at_end;
 474
 475         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 476
 477         if (e->iterate_next)
 478                 *i = (Iterator) e->iterate_next;
 479         else
 480                 *i = ITERATOR_LAST;
 481
 482         if (key)
 483                 *key = e->key;
 484
 485         return e->value;
 486
 487 at_end:
 488         *i = ITERATOR_LAST;
 489
 490         if (key)
 491                 *key = NULL;
 492
 493         return NULL;
 494 }
 495
 496 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 497         struct hashmap_entry *e;
 498
 499         assert(i);
 500
 501         if (!h)
 502                 goto at_beginning;
 503
 504         if (*i == ITERATOR_FIRST)
 505                 goto at_beginning;
 506
 507         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 508                 goto at_beginning;
 509
 510         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 511
 512         if (e->iterate_previous)
 513                 *i = (Iterator) e->iterate_previous;
 514         else
 515                 *i = ITERATOR_FIRST;
 516
 517         if (key)
 518                 *key = e->key;
 519
 520         return e->value;
 521
 522 at_beginning:
 523         *i = ITERATOR_FIRST;
 524
 525         if (key)
 526                 *key = NULL;
 527
 528         return NULL;
 529 }
 530
 531 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 532         unsigned hash;
 533         struct hashmap_entry *e;
 534
 535         if (!h)
 536                 return NULL;
 537
 538         hash = h->hash_func(key) % NBUCKETS;
 539
 540         if (!(e = hash_scan(h, hash, key)))
 541                 return NULL;
 542
 543         *i = (Iterator) e;
 544
 545         return e->value;
 546 }
 547
 548 void* hashmap_first(Hashmap *h) {
 549
 550         if (!h)
 551                 return NULL;
 552
 553         if (!h->iterate_list_head)
 554                 return NULL;
 555
 556         return h->iterate_list_head->value;
 557 }
 558
 559 void* hashmap_last(Hashmap *h) {
 560
 561         if (!h)
 562                 return NULL;
 563
 564         if (!h->iterate_list_tail)
 565                 return NULL;
 566
 567         return h->iterate_list_tail->value;
 568 }
 569
 570 void* hashmap_steal_first(Hashmap *h) {
 571         void *data;
 572
 573         if (!h)
 574                 return NULL;
 575
 576         if (!h->iterate_list_head)
 577                 return NULL;
 578
 579         data = h->iterate_list_head->value;
 580         remove_entry(h, h->iterate_list_head);
 581
 582         return data;
 583 }
 584
 585 void* hashmap_steal_first_key(Hashmap *h) {
 586         void *key;
 587
 588         if (!h)
 589                 return NULL;
 590
 591         if (!h->iterate_list_head)
 592                 return NULL;
 593
 594         key = (void*) h->iterate_list_head->key;
 595         remove_entry(h, h->iterate_list_head);
 596
 597         return key;
 598 }
 599
 600 unsigned hashmap_size(Hashmap *h) {
 601
 602         if (!h)
 603                 return 0;
 604
 605         return h->n_entries;
 606 }
 607
 608 bool hashmap_isempty(Hashmap *h) {
 609
 610         if (!h)
 611                 return true;
 612
 613         return h->n_entries == 0;
 614 }
 615
 616 int hashmap_merge(Hashmap *h, Hashmap *other) {
 617         struct hashmap_entry *e;
 618
 619         assert(h);
 620
 621         if (!other)
 622                 return 0;
 623
 624         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 625                 int r;
 626
 627                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 628                         if (r != -EEXIST)
 629                                 return r;
 630         }
 631
 632         return 0;
 633 }
 634
 635 void hashmap_move(Hashmap *h, Hashmap *other) {
 636         struct hashmap_entry *e, *n;
 637
 638         assert(h);
 639
 640         /* The same as hashmap_merge(), but every new item from other
 641          * is moved to h. This function is guaranteed to succeed. */
 642
 643         if (!other)
 644                 return;
 645
 646         for (e = other->iterate_list_head; e; e = n) {
 647                 unsigned h_hash, other_hash;
 648
 649                 n = e->iterate_next;
 650
 651                 h_hash = h->hash_func(e->key) % NBUCKETS;
 652
 653                 if (hash_scan(h, h_hash, e->key))
 654                         continue;
 655
 656                 other_hash = other->hash_func(e->key) % NBUCKETS;
 657
 658                 unlink_entry(other, e, other_hash);
 659                 link_entry(h, e, h_hash);
 660         }
 661 }
 662
 663 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 664         unsigned h_hash, other_hash;
 665         struct hashmap_entry *e;
 666
 667         if (!other)
 668                 return 0;
 669
 670         assert(h);
 671
 672         h_hash = h->hash_func(key) % NBUCKETS;
 673         if (hash_scan(h, h_hash, key))
 674                 return -EEXIST;
 675
 676         other_hash = other->hash_func(key) % NBUCKETS;
 677         if (!(e = hash_scan(other, other_hash, key)))
 678                 return -ENOENT;
 679
 680         unlink_entry(other, e, other_hash);
 681         link_entry(h, e, h_hash);
 682
 683         return 0;
 684 }
 685
 686 Hashmap *hashmap_copy(Hashmap *h) {
 687         Hashmap *copy;
 688
 689         assert(h);
 690
 691         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 692                 return NULL;
 693
 694         if (hashmap_merge(copy, h) < 0) {
 695                 hashmap_free(copy);
 696                 return NULL;
 697         }
 698
 699         return copy;
 700 }
 701
 702 char **hashmap_get_strv(Hashmap *h) {
 703         char **sv;
 704         Iterator it;
 705         char *item;
 706         int n;
 707
 708         sv = new(char*, h->n_entries+1);
 709         if (!sv)
 710                 return NULL;
 711
 712         n = 0;
 713         HASHMAP_FOREACH(item, h, it)
 714                 sv[n++] = item;
 715         sv[n] = NULL;
 716
 717         return sv;
 718 }