← Back to branch summary

~ubuntu-branches/ubuntu/trusty/systemd/trusty

« back to all changes in this revision

Viewing changes to src/shared/hashmap.c

  • Committer: Package Import Robot
  • Author(s): Michael Biebl, Michael Biebl, Michael Stapelberg, Daniel Schaal, Ondrej Balaz
  • Date: 2013-09-12 00:13:11 UTC
  • mfrom: (1.1.11) (9.1.2 experimental)
  • mto: This revision was merged to the branch mainline in revision 53.
  • Revision ID: package-import@ubuntu.com-20130912001311-dz35it34wr2lbday
Tags: 204-3
http://bugs.debian.org/719444
http://bugs.debian.org/721347
http://bugs.debian.org/722180
http://bugs.debian.org/709780
http://bugs.debian.org/711245
[ Michael Biebl ]
* Upload to unstable.
* Use /bin/bash in debug-shell.service as Debian doesn't have /sbin/sushell.
* Only import net.ifaces cmdline property for network devices.
* Generate strict dependencies between the binary packages using a
  shlibs.local file and add an explicit versioned dependency on
  libsystemd-login0 to systemd to ensure packages are upgraded in sync.
  Closes: #719444
* Drop obsolete Replaces: libudev0 from udev package.
* Use correct paths for various binaries, like /sbin/quotaon, which are
  installed in / and not /usr in Debian.  Closes: #721347
* Don't install kernel-install(8) man page since we don't install the
  corresponding binary either.  Closes: #722180
* Cherry-pick upstream fixes to make switching runlevels and starting
  reboot via ctrl-alt-del more robust.
* Cherry-pick upstream fix to properly apply ACLs to Journal files.

[ Michael Stapelberg ]
* Make systemctl enable|disable call update-rc.d for SysV init scripts.
  Closes: #709780
* Don't mount /tmp as tmpfs by default and make it possible to enable this
  feature via "systemctl enable tmp.mount".

[ Daniel Schaal ]
* Add bug-script to systemd and udev.  Closes: #711245

[ Ondrej Balaz ]
* Recognize discard option in /etc/crypttab.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/shared/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 Lesser General Public License as published by
 
10
  the Free Software Foundation; either version 2.1 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
  Lesser General Public License for more details.
 
17
 
 
18
  You should have received a copy of the GNU Lesser 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
static struct pool *first_hashmap_pool = NULL;
 
59
static void *first_hashmap_tile = NULL;
 
60
 
 
61
static 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
#ifdef VALGRIND
 
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 = 5381;
 
128
        const signed char *c;
 
129
 
 
130
        /* DJB's hash function */
 
131
 
 
132
        for (c = p; *c; c++)
 
133
                hash = (hash << 5) + hash + (unsigned) *c;
 
134
 
 
135
        return hash;
 
136
}
 
137
 
 
138
int string_compare_func(const void *a, const void *b) {
 
139
        return strcmp(a, b);
 
140
}
 
141
 
 
142
unsigned trivial_hash_func(const void *p) {
 
143
        return PTR_TO_UINT(p);
 
144
}
 
145
 
 
146
int trivial_compare_func(const void *a, const void *b) {
 
147
        return a < b ? -1 : (a > b ? 1 : 0);
 
148
}
 
149
 
 
150
unsigned uint64_hash_func(const void *p) {
 
151
        uint64_t u;
 
152
 
 
153
        assert_cc(sizeof(uint64_t) == 2*sizeof(unsigned));
 
154
 
 
155
        u = *(const uint64_t*) p;
 
156
 
 
157
        return (unsigned) ((u >> 32) ^ u);
 
158
}
 
159
 
 
160
int uint64_compare_func(const void *_a, const void *_b) {
 
161
        uint64_t a, b;
 
162
 
 
163
        a = *(const uint64_t*) _a;
 
164
        b = *(const uint64_t*) _b;
 
165
 
 
166
        return a < b ? -1 : (a > b ? 1 : 0);
 
167
}
 
168
 
 
169
Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func) {
 
170
        bool b;
 
171
        Hashmap *h;
 
172
        size_t size;
 
173
 
 
174
        b = is_main_thread();
 
175
 
 
176
        size = ALIGN(sizeof(Hashmap)) + NBUCKETS * sizeof(struct hashmap_entry*);
 
177
 
 
178
        if (b) {
 
179
                h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size);
 
180
                if (!h)
 
181
                        return NULL;
 
182
 
 
183
                memset(h, 0, size);
 
184
        } else {
 
185
                h = malloc0(size);
 
186
 
 
187
                if (!h)
 
188
                        return NULL;
 
189
        }
 
190
 
 
191
        h->hash_func = hash_func ? hash_func : trivial_hash_func;
 
192
        h->compare_func = compare_func ? compare_func : trivial_compare_func;
 
193
 
 
194
        h->n_entries = 0;
 
195
        h->iterate_list_head = h->iterate_list_tail = NULL;
 
196
 
 
197
        h->from_pool = b;
 
198
 
 
199
        return h;
 
200
}
 
201
 
 
202
int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func) {
 
203
        assert(h);
 
204
 
 
205
        if (*h)
 
206
                return 0;
 
207
 
 
208
        if (!(*h = hashmap_new(hash_func, compare_func)))
 
209
                return -ENOMEM;
 
210
 
 
211
        return 0;
 
212
}
 
213
 
 
214
static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 
215
        assert(h);
 
216
        assert(e);
 
217
 
 
218
        /* Insert into hash table */
 
219
        e->bucket_next = BY_HASH(h)[hash];
 
220
        e->bucket_previous = NULL;
 
221
        if (BY_HASH(h)[hash])
 
222
                BY_HASH(h)[hash]->bucket_previous = e;
 
223
        BY_HASH(h)[hash] = e;
 
224
 
 
225
        /* Insert into iteration list */
 
226
        e->iterate_previous = h->iterate_list_tail;
 
227
        e->iterate_next = NULL;
 
228
        if (h->iterate_list_tail) {
 
229
                assert(h->iterate_list_head);
 
230
                h->iterate_list_tail->iterate_next = e;
 
231
        } else {
 
232
                assert(!h->iterate_list_head);
 
233
                h->iterate_list_head = e;
 
234
        }
 
235
        h->iterate_list_tail = e;
 
236
 
 
237
        h->n_entries++;
 
238
        assert(h->n_entries >= 1);
 
239
}
 
240
 
 
241
static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
 
242
        assert(h);
 
243
        assert(e);
 
244
 
 
245
        /* Remove from iteration list */
 
246
        if (e->iterate_next)
 
247
                e->iterate_next->iterate_previous = e->iterate_previous;
 
248
        else
 
249
                h->iterate_list_tail = e->iterate_previous;
 
250
 
 
251
        if (e->iterate_previous)
 
252
                e->iterate_previous->iterate_next = e->iterate_next;
 
253
        else
 
254
                h->iterate_list_head = e->iterate_next;
 
255
 
 
256
        /* Remove from hash table bucket list */
 
257
        if (e->bucket_next)
 
258
                e->bucket_next->bucket_previous = e->bucket_previous;
 
259
 
 
260
        if (e->bucket_previous)
 
261
                e->bucket_previous->bucket_next = e->bucket_next;
 
262
        else
 
263
                BY_HASH(h)[hash] = e->bucket_next;
 
264
 
 
265
        assert(h->n_entries >= 1);
 
266
        h->n_entries--;
 
267
}
 
268
 
 
269
static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
 
270
        unsigned hash;
 
271
 
 
272
        assert(h);
 
273
        assert(e);
 
274
 
 
275
        hash = h->hash_func(e->key) % NBUCKETS;
 
276
 
 
277
        unlink_entry(h, e, hash);
 
278
 
 
279
        if (h->from_pool)
 
280
                deallocate_tile(&first_entry_tile, e);
 
281
        else
 
282
                free(e);
 
283
}
 
284
 
 
285
void hashmap_free(Hashmap*h) {
 
286
 
 
287
        /* Free the hashmap, but nothing in it */
 
288
 
 
289
        if (!h)
 
290
                return;
 
291
 
 
292
        hashmap_clear(h);
 
293
 
 
294
        if (h->from_pool)
 
295
                deallocate_tile(&first_hashmap_tile, h);
 
296
        else
 
297
                free(h);
 
298
}
 
299
 
 
300
void hashmap_free_free(Hashmap *h) {
 
301
 
 
302
        /* Free the hashmap and all data objects in it, but not the
 
303
         * keys */
 
304
 
 
305
        if (!h)
 
306
                return;
 
307
 
 
308
        hashmap_clear_free(h);
 
309
        hashmap_free(h);
 
310
}
 
311
 
 
312
void hashmap_free_free_free(Hashmap *h) {
 
313
 
 
314
        /* Free the hashmap and all data and key objects in it */
 
315
 
 
316
        if (!h)
 
317
                return;
 
318
 
 
319
        hashmap_clear_free_free(h);
 
320
        hashmap_free(h);
 
321
}
 
322
 
 
323
void hashmap_clear(Hashmap *h) {
 
324
        if (!h)
 
325
                return;
 
326
 
 
327
        while (h->iterate_list_head)
 
328
                remove_entry(h, h->iterate_list_head);
 
329
}
 
330
 
 
331
void hashmap_clear_free(Hashmap *h) {
 
332
        void *p;
 
333
 
 
334
        if (!h)
 
335
                return;
 
336
 
 
337
        while ((p = hashmap_steal_first(h)))
 
338
                free(p);
 
339
}
 
340
 
 
341
void hashmap_clear_free_free(Hashmap *h) {
 
342
        if (!h)
 
343
                return;
 
344
 
 
345
        while (h->iterate_list_head) {
 
346
                void *a, *b;
 
347
 
 
348
                a = h->iterate_list_head->value;
 
349
                b = (void*) h->iterate_list_head->key;
 
350
                remove_entry(h, h->iterate_list_head);
 
351
                free(a);
 
352
                free(b);
 
353
        }
 
354
}
 
355
 
 
356
 
 
357
static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *key) {
 
358
        struct hashmap_entry *e;
 
359
        assert(h);
 
360
        assert(hash < NBUCKETS);
 
361
 
 
362
        for (e = BY_HASH(h)[hash]; e; e = e->bucket_next)
 
363
                if (h->compare_func(e->key, key) == 0)
 
364
                        return e;
 
365
 
 
366
        return NULL;
 
367
}
 
368
 
 
369
int hashmap_put(Hashmap *h, const void *key, void *value) {
 
370
        struct hashmap_entry *e;
 
371
        unsigned hash;
 
372
 
 
373
        assert(h);
 
374
 
 
375
        hash = h->hash_func(key) % NBUCKETS;
 
376
 
 
377
        e = hash_scan(h, hash, key);
 
378
        if (e) {
 
379
 
 
380
                if (e->value == value)
 
381
                        return 0;
 
382
 
 
383
                return -EEXIST;
 
384
        }
 
385
 
 
386
        if (h->from_pool)
 
387
                e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry));
 
388
        else
 
389
                e = new(struct hashmap_entry, 1);
 
390
 
 
391
        if (!e)
 
392
                return -ENOMEM;
 
393
 
 
394
        e->key = key;
 
395
        e->value = value;
 
396
 
 
397
        link_entry(h, e, hash);
 
398
 
 
399
        return 1;
 
400
}
 
401
 
 
402
int hashmap_replace(Hashmap *h, const void *key, void *value) {
 
403
        struct hashmap_entry *e;
 
404
        unsigned hash;
 
405
 
 
406
        assert(h);
 
407
 
 
408
        hash = h->hash_func(key) % NBUCKETS;
 
409
        e = hash_scan(h, hash, key);
 
410
        if (e) {
 
411
                e->key = key;
 
412
                e->value = value;
 
413
                return 0;
 
414
        }
 
415
 
 
416
        return hashmap_put(h, key, value);
 
417
}
 
418
 
 
419
int hashmap_update(Hashmap *h, const void *key, void *value) {
 
420
        struct hashmap_entry *e;
 
421
        unsigned hash;
 
422
 
 
423
        assert(h);
 
424
 
 
425
        hash = h->hash_func(key) % NBUCKETS;
 
426
        e = hash_scan(h, hash, key);
 
427
        if (!e)
 
428
                return -ENOENT;
 
429
 
 
430
        e->value = value;
 
431
        return 0;
 
432
}
 
433
 
 
434
void* hashmap_get(Hashmap *h, const void *key) {
 
435
        unsigned hash;
 
436
        struct hashmap_entry *e;
 
437
 
 
438
        if (!h)
 
439
                return NULL;
 
440
 
 
441
        hash = h->hash_func(key) % NBUCKETS;
 
442
        e = hash_scan(h, hash, key);
 
443
        if (!e)
 
444
                return NULL;
 
445
 
 
446
        return e->value;
 
447
}
 
448
 
 
449
void* hashmap_get2(Hashmap *h, const void *key, void **key2) {
 
450
        unsigned hash;
 
451
        struct hashmap_entry *e;
 
452
 
 
453
        if (!h)
 
454
                return NULL;
 
455
 
 
456
        hash = h->hash_func(key) % NBUCKETS;
 
457
        e = hash_scan(h, hash, key);
 
458
        if (!e)
 
459
                return NULL;
 
460
 
 
461
        if (key2)
 
462
                *key2 = (void*) e->key;
 
463
 
 
464
        return e->value;
 
465
}
 
466
 
 
467
bool hashmap_contains(Hashmap *h, const void *key) {
 
468
        unsigned hash;
 
469
 
 
470
        if (!h)
 
471
                return false;
 
472
 
 
473
        hash = h->hash_func(key) % NBUCKETS;
 
474
 
 
475
        if (!hash_scan(h, hash, key))
 
476
                return false;
 
477
 
 
478
        return true;
 
479
}
 
480
 
 
481
void* hashmap_remove(Hashmap *h, const void *key) {
 
482
        struct hashmap_entry *e;
 
483
        unsigned hash;
 
484
        void *data;
 
485
 
 
486
        if (!h)
 
487
                return NULL;
 
488
 
 
489
        hash = h->hash_func(key) % NBUCKETS;
 
490
 
 
491
        if (!(e = hash_scan(h, hash, key)))
 
492
                return NULL;
 
493
 
 
494
        data = e->value;
 
495
        remove_entry(h, e);
 
496
 
 
497
        return data;
 
498
}
 
499
 
 
500
int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 
501
        struct hashmap_entry *e;
 
502
        unsigned old_hash, new_hash;
 
503
 
 
504
        if (!h)
 
505
                return -ENOENT;
 
506
 
 
507
        old_hash = h->hash_func(old_key) % NBUCKETS;
 
508
        if (!(e = hash_scan(h, old_hash, old_key)))
 
509
                return -ENOENT;
 
510
 
 
511
        new_hash = h->hash_func(new_key) % NBUCKETS;
 
512
        if (hash_scan(h, new_hash, new_key))
 
513
                return -EEXIST;
 
514
 
 
515
        unlink_entry(h, e, old_hash);
 
516
 
 
517
        e->key = new_key;
 
518
        e->value = value;
 
519
 
 
520
        link_entry(h, e, new_hash);
 
521
 
 
522
        return 0;
 
523
}
 
524
 
 
525
int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
 
526
        struct hashmap_entry *e, *k;
 
527
        unsigned old_hash, new_hash;
 
528
 
 
529
        if (!h)
 
530
                return -ENOENT;
 
531
 
 
532
        old_hash = h->hash_func(old_key) % NBUCKETS;
 
533
        if (!(e = hash_scan(h, old_hash, old_key)))
 
534
                return -ENOENT;
 
535
 
 
536
        new_hash = h->hash_func(new_key) % NBUCKETS;
 
537
 
 
538
        if ((k = hash_scan(h, new_hash, new_key)))
 
539
                if (e != k)
 
540
                        remove_entry(h, k);
 
541
 
 
542
        unlink_entry(h, e, old_hash);
 
543
 
 
544
        e->key = new_key;
 
545
        e->value = value;
 
546
 
 
547
        link_entry(h, e, new_hash);
 
548
 
 
549
        return 0;
 
550
}
 
551
 
 
552
void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
 
553
        struct hashmap_entry *e;
 
554
        unsigned hash;
 
555
 
 
556
        if (!h)
 
557
                return NULL;
 
558
 
 
559
        hash = h->hash_func(key) % NBUCKETS;
 
560
 
 
561
        if (!(e = hash_scan(h, hash, key)))
 
562
                return NULL;
 
563
 
 
564
        if (e->value != value)
 
565
                return NULL;
 
566
 
 
567
        remove_entry(h, e);
 
568
 
 
569
        return value;
 
570
}
 
571
 
 
572
void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key) {
 
573
        struct hashmap_entry *e;
 
574
 
 
575
        assert(i);
 
576
 
 
577
        if (!h)
 
578
                goto at_end;
 
579
 
 
580
        if (*i == ITERATOR_LAST)
 
581
                goto at_end;
 
582
 
 
583
        if (*i == ITERATOR_FIRST && !h->iterate_list_head)
 
584
                goto at_end;
 
585
 
 
586
        e = *i == ITERATOR_FIRST ? h->iterate_list_head : (struct hashmap_entry*) *i;
 
587
 
 
588
        if (e->iterate_next)
 
589
                *i = (Iterator) e->iterate_next;
 
590
        else
 
591
                *i = ITERATOR_LAST;
 
592
 
 
593
        if (key)
 
594
                *key = e->key;
 
595
 
 
596
        return e->value;
 
597
 
 
598
at_end:
 
599
        *i = ITERATOR_LAST;
 
600
 
 
601
        if (key)
 
602
                *key = NULL;
 
603
 
 
604
        return NULL;
 
605
}
 
606
 
 
607
void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key) {
 
608
        struct hashmap_entry *e;
 
609
 
 
610
        assert(i);
 
611
 
 
612
        if (!h)
 
613
                goto at_beginning;
 
614
 
 
615
        if (*i == ITERATOR_FIRST)
 
616
                goto at_beginning;
 
617
 
 
618
        if (*i == ITERATOR_LAST && !h->iterate_list_tail)
 
619
                goto at_beginning;
 
620
 
 
621
        e = *i == ITERATOR_LAST ? h->iterate_list_tail : (struct hashmap_entry*) *i;
 
622
 
 
623
        if (e->iterate_previous)
 
624
                *i = (Iterator) e->iterate_previous;
 
625
        else
 
626
                *i = ITERATOR_FIRST;
 
627
 
 
628
        if (key)
 
629
                *key = e->key;
 
630
 
 
631
        return e->value;
 
632
 
 
633
at_beginning:
 
634
        *i = ITERATOR_FIRST;
 
635
 
 
636
        if (key)
 
637
                *key = NULL;
 
638
 
 
639
        return NULL;
 
640
}
 
641
 
 
642
void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i) {
 
643
        unsigned hash;
 
644
        struct hashmap_entry *e;
 
645
 
 
646
        if (!h)
 
647
                return NULL;
 
648
 
 
649
        hash = h->hash_func(key) % NBUCKETS;
 
650
 
 
651
        if (!(e = hash_scan(h, hash, key)))
 
652
                return NULL;
 
653
 
 
654
        *i = (Iterator) e;
 
655
 
 
656
        return e->value;
 
657
}
 
658
 
 
659
void* hashmap_first(Hashmap *h) {
 
660
 
 
661
        if (!h)
 
662
                return NULL;
 
663
 
 
664
        if (!h->iterate_list_head)
 
665
                return NULL;
 
666
 
 
667
        return h->iterate_list_head->value;
 
668
}
 
669
 
 
670
void* hashmap_first_key(Hashmap *h) {
 
671
 
 
672
        if (!h)
 
673
                return NULL;
 
674
 
 
675
        if (!h->iterate_list_head)
 
676
                return NULL;
 
677
 
 
678
        return (void*) h->iterate_list_head->key;
 
679
}
 
680
 
 
681
void* hashmap_last(Hashmap *h) {
 
682
 
 
683
        if (!h)
 
684
                return NULL;
 
685
 
 
686
        if (!h->iterate_list_tail)
 
687
                return NULL;
 
688
 
 
689
        return h->iterate_list_tail->value;
 
690
}
 
691
 
 
692
void* hashmap_steal_first(Hashmap *h) {
 
693
        void *data;
 
694
 
 
695
        if (!h)
 
696
                return NULL;
 
697
 
 
698
        if (!h->iterate_list_head)
 
699
                return NULL;
 
700
 
 
701
        data = h->iterate_list_head->value;
 
702
        remove_entry(h, h->iterate_list_head);
 
703
 
 
704
        return data;
 
705
}
 
706
 
 
707
void* hashmap_steal_first_key(Hashmap *h) {
 
708
        void *key;
 
709
 
 
710
        if (!h)
 
711
                return NULL;
 
712
 
 
713
        if (!h->iterate_list_head)
 
714
                return NULL;
 
715
 
 
716
        key = (void*) h->iterate_list_head->key;
 
717
        remove_entry(h, h->iterate_list_head);
 
718
 
 
719
        return key;
 
720
}
 
721
 
 
722
unsigned hashmap_size(Hashmap *h) {
 
723
 
 
724
        if (!h)
 
725
                return 0;
 
726
 
 
727
        return h->n_entries;
 
728
}
 
729
 
 
730
bool hashmap_isempty(Hashmap *h) {
 
731
 
 
732
        if (!h)
 
733
                return true;
 
734
 
 
735
        return h->n_entries == 0;
 
736
}
 
737
 
 
738
int hashmap_merge(Hashmap *h, Hashmap *other) {
 
739
        struct hashmap_entry *e;
 
740
 
 
741
        assert(h);
 
742
 
 
743
        if (!other)
 
744
                return 0;
 
745
 
 
746
        for (e = other->iterate_list_head; e; e = e->iterate_next) {
 
747
                int r;
 
748
 
 
749
                if ((r = hashmap_put(h, e->key, e->value)) < 0)
 
750
                        if (r != -EEXIST)
 
751
                                return r;
 
752
        }
 
753
 
 
754
        return 0;
 
755
}
 
756
 
 
757
void hashmap_move(Hashmap *h, Hashmap *other) {
 
758
        struct hashmap_entry *e, *n;
 
759
 
 
760
        assert(h);
 
761
 
 
762
        /* The same as hashmap_merge(), but every new item from other
 
763
         * is moved to h. This function is guaranteed to succeed. */
 
764
 
 
765
        if (!other)
 
766
                return;
 
767
 
 
768
        for (e = other->iterate_list_head; e; e = n) {
 
769
                unsigned h_hash, other_hash;
 
770
 
 
771
                n = e->iterate_next;
 
772
 
 
773
                h_hash = h->hash_func(e->key) % NBUCKETS;
 
774
 
 
775
                if (hash_scan(h, h_hash, e->key))
 
776
                        continue;
 
777
 
 
778
                other_hash = other->hash_func(e->key) % NBUCKETS;
 
779
 
 
780
                unlink_entry(other, e, other_hash);
 
781
                link_entry(h, e, h_hash);
 
782
        }
 
783
}
 
784
 
 
785
int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
 
786
        unsigned h_hash, other_hash;
 
787
        struct hashmap_entry *e;
 
788
 
 
789
        if (!other)
 
790
                return 0;
 
791
 
 
792
        assert(h);
 
793
 
 
794
        h_hash = h->hash_func(key) % NBUCKETS;
 
795
        if (hash_scan(h, h_hash, key))
 
796
                return -EEXIST;
 
797
 
 
798
        other_hash = other->hash_func(key) % NBUCKETS;
 
799
        if (!(e = hash_scan(other, other_hash, key)))
 
800
                return -ENOENT;
 
801
 
 
802
        unlink_entry(other, e, other_hash);
 
803
        link_entry(h, e, h_hash);
 
804
 
 
805
        return 0;
 
806
}
 
807
 
 
808
Hashmap *hashmap_copy(Hashmap *h) {
 
809
        Hashmap *copy;
 
810
 
 
811
        assert(h);
 
812
 
 
813
        if (!(copy = hashmap_new(h->hash_func, h->compare_func)))
 
814
                return NULL;
 
815
 
 
816
        if (hashmap_merge(copy, h) < 0) {
 
817
                hashmap_free(copy);
 
818
                return NULL;
 
819
        }
 
820
 
 
821
        return copy;
 
822
}
 
823
 
 
824
char **hashmap_get_strv(Hashmap *h) {
 
825
        char **sv;
 
826
        Iterator it;
 
827
        char *item;
 
828
        int n;
 
829
 
 
830
        sv = new(char*, h->n_entries+1);
 
831
        if (!sv)
 
832
                return NULL;
 
833
 
 
834
        n = 0;
 
835
        HASHMAP_FOREACH(item, h, it)
 
836
                sv[n++] = item;
 
837
        sv[n] = NULL;
 
838
 
 
839
        return sv;
 
840
}
 
841
 
 
842
void *hashmap_next(Hashmap *h, const void *key) {
 
843
        unsigned hash;
 
844
        struct hashmap_entry *e;
 
845
 
 
846
        assert(h);
 
847
        assert(key);
 
848
 
 
849
        if (!h)
 
850
                return NULL;
 
851
 
 
852
        hash = h->hash_func(key) % NBUCKETS;
 
853
        e = hash_scan(h, hash, key);
 
854
        if (!e)
 
855
                return NULL;
 
856
 
 
857
        e = e->iterate_next;
 
858
        if (!e)
 
859
                return NULL;
 
860
 
 
861
        return e->value;
 
862
}