hashmap.c

   1 /*-*- Mode: C; c-basic-offset: 8 -*-*/
   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
  48 #define BY_HASH(h) ((struct hashmap_entry**) ((uint8_t*) (h) + ALIGN(sizeof(Hashmap))))
  49
  50 unsigned string_hash_func(const void *p) {
  51         unsigned hash = 0;
  52         const char *c;
  53
  54         for (c = p; *c; c++)
  55                 hash = 31 * hash + (unsigned) *c;
  56
  57         return hash;
  58 }
  59
  60 int string_compare_func(const void *a, const void *b) {
  61         return strcmp(a, b);
  62 }
  63
  64 unsigned trivial_hash_func(const void *p) {
  65         return PTR_TO_UINT(p);
  66 }
  67
  68 int trivial_compare_func(const void *a, const void *b) {
  69         return a < b ? -1 : (a > b ? 1 : 0);
  70 }
  71
  72 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
  73         Hashmap *h;
  74
  75         if (!(h = malloc0(ALIGN(sizeof(Hashmap)) + NBUCKETS * ALIGN(sizeof(struct hashmap_entry*)))))
  76                 return NULL;
  77
  78         h->hash_func = hash_func ? hash_func : trivial_hash_func;
  79         h->compare_func = compare_func ? compare_func : trivial_compare_func;
  80
  81         h->n_entries = 0;
  82         h->iterate_list_head = h->iterate_list_tail = NULL;
  83
  84         return h;
  85 }
  86
  87 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
  88         assert(h);
  89
  90         if (*h)
  91                 return 0;
  92
  93         if (!(*h = hashmap_new(hash_func, compare_func)))
  94                 return -ENOMEM;
  95
  96         return 0;
  97 }
  98
  99 static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 100         assert(h);
 101         assert(e);
 102
 103         /* Insert into hash table */
 104         e->bucket_next = BY_HASH(h)[hash];
 105         e->bucket_previous = NULL;
 106         if (BY_HASH(h)[hash])
 107                 BY_HASH(h)[hash]->bucket_previous = e;
 108         BY_HASH(h)[hash] = e;
 109
 110         /* Insert into iteration list */
 111         e->iterate_previous = h->iterate_list_tail;
 112         e->iterate_next = NULL;
 113         if (h->iterate_list_tail) {
 114                 assert(h->iterate_list_head);
 115                 h->iterate_list_tail->iterate_next = e;
 116         } else {
 117                 assert(!h->iterate_list_head);
 118                 h->iterate_list_head = e;
 119         }
 120         h->iterate_list_tail = e;
 121
 122         h->n_entries++;
 123         assert(h->n_entries >= 1);
 124 }
 125
 126 static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 127         assert(h);
 128         assert(e);
 129
 130         /* Remove from iteration list */
 131         if (e->iterate_next)
 132                 e->iterate_next->iterate_previous = e->iterate_previous;
 133         else
 134                 h->iterate_list_tail = e->iterate_previous;
 135
 136         if (e->iterate_previous)
 137                 e->iterate_previous->iterate_next = e->iterate_next;
 138         else
 139                 h->iterate_list_head = e->iterate_next;
 140
 141         /* Remove from hash table bucket list */
 142         if (e->bucket_next)
 143                 e->bucket_next->bucket_previous = e->bucket_previous;
 144
 145         if (e->bucket_previous)
 146                 e->bucket_previous->bucket_next = e->bucket_next;
 147         else
 148                 BY_HASH(h)[hash] = e->bucket_next;
 149
 150         assert(h->n_entries >= 1);
 151         h->n_entries--;
 152 }
 153
 154 static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 155         unsigned hash;
 156
 157         assert(h);
 158         assert(e);
 159
 160         hash = h->hash_func(e->key) % NBUCKETS;
 161
 162         unlink_entry(h, e, hash);
 163         free(e);
 164 }
 165
 166 void hashmap_free(Hashmap*h) {
 167
 168         if (!h)
 169                 return;
 170
 171         hashmap_clear(h);
 172
 173         free(h);
 174 }
 175
 176 void hashmap_clear(Hashmap *h) {
 177         if (!h)
 178                 return;
 179
 180         while (h->iterate_list_head)
 181                 remove_entry(h, h->iterate_list_head);
 182 }
 183
 184 static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 185         struct hashmap_entry *e;
 186         assert(h);
 187         assert(hash < NBUCKETS);
 188
 189         for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 190                 if (h->compare_func(e->key, key) == 0)
 191                         return e;
 192
 193         return NULL;
 194 }
 195
 196 int hashmap_put(Hashmap *h, const void *key, void *value) {
 197         struct hashmap_entry *e;
 198         unsigned hash;
 199
 200         assert(h);
 201
 202         hash = h->hash_func(key) % NBUCKETS;
 203
 204         if ((e = hash_scan(h, hash, key))) {
 205
 206                 if (e->value == value)
 207                         return 0;
 208
 209                 return -EEXIST;
 210         }
 211
 212         if (!(e = new(struct hashmap_entry, 1)))
 213                 return -ENOMEM;
 214
 215         e->key = key;
 216         e->value = value;
 217
 218         link_entry(h, e, hash);
 219
 220         return 1;
 221 }
 222
 223 int hashmap_replace(Hashmap *h, const void *key, void *value) {
 224         struct hashmap_entry *e;
 225         unsigned hash;
 226
 227         assert(h);
 228
 229         hash = h->hash_func(key) % NBUCKETS;
 230
 231         if ((e = hash_scan(h, hash, key))) {
 232                 e->key = key;
 233                 e->value = value;
 234                 return 0;
 235         }
 236
 237         return hashmap_put(h, key, value);
 238 }
 239
 240 void* hashmap_get(Hashmap *h, const void *key) {
 241         unsigned hash;
 242         struct hashmap_entry *e;
 243
 244         if (!h)
 245                 return NULL;
 246
 247         hash = h->hash_func(key) % NBUCKETS;
 248
 249         if (!(e = hash_scan(h, hash, key)))
 250                 return NULL;
 251
 252         return e->value;
 253 }
 254
 255 void* hashmap_remove(Hashmap *h, const void *key) {
 256         struct hashmap_entry *e;
 257         unsigned hash;
 258         void *data;
 259
 260         if (!h)
 261                 return NULL;
 262
 263         hash = h->hash_func(key) % NBUCKETS;
 264
 265         if (!(e = hash_scan(h, hash, key)))
 266                 return NULL;
 267
 268         data = e->value;
 269         remove_entry(h, e);
 270
 271         return data;
 272 }
 273
 274 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 275         struct hashmap_entry *e;
 276         unsigned old_hash, new_hash;
 277
 278         if (!h)
 279                 return -ENOENT;
 280
 281         old_hash = h->hash_func(old_key) % NBUCKETS;
 282         if (!(e = hash_scan(h, old_hash, old_key)))
 283                 return -ENOENT;
 284
 285         new_hash = h->hash_func(new_key) % NBUCKETS;
 286         if (hash_scan(h, new_hash, new_key))
 287                 return -EEXIST;
 288
 289         unlink_entry(h, e, old_hash);
 290
 291         e->key = new_key;
 292         e->value = value;
 293
 294         link_entry(h, e, new_hash);
 295
 296         return 0;
 297 }
 298
 299 void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 300         struct hashmap_entry *e;
 301         unsigned hash;
 302
 303         if (!h)
 304                 return NULL;
 305
 306         hash = h->hash_func(key) % NBUCKETS;
 307
 308         if (!(e = hash_scan(h, hash, key)))
 309                 return NULL;
 310
 311         if (e->value != value)
 312                 return NULL;
 313
 314         remove_entry(h, e);
 315
 316         return value;
 317 }
 318
 319 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 320         struct hashmap_entry *e;
 321
 322         assert(i);
 323
 324         if (!h)
 325                 goto at_end;
 326
 327         if (*i == ITERATOR_LAST)
 328                 goto at_end;
 329
 330         if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 331                 goto at_end;
 332
 333         e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 334
 335         if (e->iterate_next)
 336                 *i = (Iterator) e->iterate_next;
 337         else
 338                 *i = ITERATOR_LAST;
 339
 340         if (key)
 341                 *key = e->key;
 342
 343         return e->value;
 344
 345 at_end:
 346         *i = ITERATOR_LAST;
 347
 348         if (key)
 349                 *key = NULL;
 350
 351         return NULL;
 352 }
 353
 354 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 355         struct hashmap_entry *e;
 356
 357         assert(i);
 358
 359         if (!h)
 360                 goto at_beginning;
 361
 362         if (*i == ITERATOR_FIRST)
 363                 goto at_beginning;
 364
 365         if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 366                 goto at_beginning;
 367
 368         e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 369
 370         if (e->iterate_previous)
 371                 *i = (Iterator) e->iterate_previous;
 372         else
 373                 *i = ITERATOR_FIRST;
 374
 375         if (key)
 376                 *key = e->key;
 377
 378         return e->value;
 379
 380 at_beginning:
 381         *i = ITERATOR_FIRST;
 382
 383         if (key)
 384                 *key = NULL;
 385
 386         return NULL;
 387 }
 388
 389 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 390         unsigned hash;
 391         struct hashmap_entry *e;
 392
 393         if (!h)
 394                 return NULL;
 395
 396         hash = h->hash_func(key) % NBUCKETS;
 397
 398         if (!(e = hash_scan(h, hash, key)))
 399                 return NULL;
 400
 401         *i = (Iterator) e;
 402
 403         return e->value;
 404 }
 405
 406 void* hashmap_first(Hashmap *h) {
 407
 408         if (!h)
 409                 return NULL;
 410
 411         if (!h->iterate_list_head)
 412                 return NULL;
 413
 414         return h->iterate_list_head->value;
 415 }
 416
 417 void* hashmap_last(Hashmap *h) {
 418
 419         if (!h)
 420                 return NULL;
 421
 422         if (!h->iterate_list_tail)
 423                 return NULL;
 424
 425         return h->iterate_list_tail->value;
 426 }
 427
 428 void* hashmap_steal_first(Hashmap *h) {
 429         void *data;
 430
 431         if (!h)
 432                 return NULL;
 433
 434         if (!h->iterate_list_head)
 435                 return NULL;
 436
 437         data = h->iterate_list_head->value;
 438         remove_entry(h, h->iterate_list_head);
 439
 440         return data;
 441 }
 442
 443 unsigned hashmap_size(Hashmap *h) {
 444
 445         if (!h)
 446                 return 0;
 447
 448         return h->n_entries;
 449 }
 450
 451 bool hashmap_isempty(Hashmap *h) {
 452
 453         if (!h)
 454                 return true;
 455
 456         return h->n_entries == 0;
 457 }
 458
 459 int hashmap_merge(Hashmap *h, Hashmap *other) {
 460         struct hashmap_entry *e;
 461
 462         assert(h);
 463
 464         if (!other)
 465                 return 0;
 466
 467         for (e = other->iterate_list_head; e; e = e->iterate_next) {
 468                 int r;
 469
 470                 if ((r = hashmap_put(h, e->key, e->value)) < 0)
 471                         if (r != -EEXIST)
 472                                 return r;
 473         }
 474
 475         return 0;
 476 }
 477
 478 void hashmap_move(Hashmap *h, Hashmap *other) {
 479         struct hashmap_entry *e, *n;
 480
 481         assert(h);
 482
 483         /* The same as hashmap_merge(), but every new item from other
 484          * is moved to h. This function is guaranteed to succeed. */
 485
 486         if (!other)
 487                 return;
 488
 489         for (e = other->iterate_list_head; e; e = n) {
 490                 unsigned h_hash, other_hash;
 491
 492                 n = e->iterate_next;
 493
 494                 h_hash = h->hash_func(e->key) % NBUCKETS;
 495
 496                 if (hash_scan(h, h_hash, e->key))
 497                         continue;
 498
 499                 other_hash = other->hash_func(e->key) % NBUCKETS;
 500
 501                 unlink_entry(other, e, other_hash);
 502                 link_entry(h, e, h_hash);
 503         }
 504 }
 505
 506 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 507         unsigned h_hash, other_hash;
 508         struct hashmap_entry *e;
 509
 510         if (!other)
 511                 return 0;
 512
 513         assert(h);
 514
 515         h_hash = h->hash_func(key) % NBUCKETS;
 516         if (hash_scan(h, h_hash, key))
 517                 return -EEXIST;
 518
 519         other_hash = other->hash_func(key) % NBUCKETS;
 520         if (!(e = hash_scan(other, other_hash, key)))
 521                 return -ENOENT;
 522
 523         unlink_entry(other, e, other_hash);
 524         link_entry(h, e, h_hash);
 525
 526         return 0;
 527 }
 528
 529 Hashmap *hashmap_copy(Hashmap *h) {
 530         Hashmap *copy;
 531
 532         assert(h);
 533
 534         if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 535                 return NULL;
 536
 537         if (hashmap_merge(copy, h) < 0) {
 538                 hashmap_free(copy);
 539                 return NULL;
 540         }
 541
 542         return copy;
 543 }