[systemd-commits] 19 commits - Makefile.am src/cgtop src/core src/journal src/libsystemd src/resolve src/shared src/test
Michal Schmidt
michich at kemper.freedesktop.org
Thu Oct 23 08:46:46 PDT 2014
Makefile.am | 23
src/cgtop/cgtop.c | 4
src/core/unit.c | 65 ++
src/journal/journal-file.c | 16
src/journal/journal-file.h | 2
src/journal/journal-internal.h | 2
src/journal/journalctl.c | 6
src/journal/journald-server.c | 24
src/journal/journald-server.h | 2
src/journal/sd-journal.c | 38 -
src/libsystemd/sd-bus/bus-internal.h | 2
src/libsystemd/sd-bus/bus-slot.c | 2
src/libsystemd/sd-bus/sd-bus.c | 14
src/resolve/resolved-dns-scope.c | 10
src/resolve/resolved-dns-scope.h | 2
src/shared/hashmap.c | 154 ++----
src/shared/hashmap.h | 122 +++++
src/shared/install.c | 70 +-
src/shared/mempool.c | 94 +++
src/shared/mempool.h | 48 +
src/shared/set.c | 6
src/shared/set.h | 3
src/test/.gitignore | 1
src/test/test-hashmap-plain.c | 844 +++++++++++++++++++++++++++++++++++
src/test/test-hashmap.c | 542 ----------------------
25 files changed, 1379 insertions(+), 717 deletions(-)
New commits:
commit 7c0b05e58ba6a74317a332c475196c656b321829
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 00:23:21 2014 +0200
unit: adjust for the possibility of set_move() failing
diff --git a/src/core/unit.c b/src/core/unit.c
index 41b9ba4..e40e6f2 100644
--- a/src/core/unit.c
+++ b/src/core/unit.c
@@ -553,29 +553,38 @@ const char* unit_sub_state_to_string(Unit *u) {
return UNIT_VTABLE(u)->sub_state_to_string(u);
}
-static void complete_move(Set **s, Set **other) {
+static int complete_move(Set **s, Set **other) {
+ int r;
+
assert(s);
assert(other);
if (!*other)
- return;
+ return 0;
- if (*s)
- set_move(*s, *other);
- else {
+ if (*s) {
+ r = set_move(*s, *other);
+ if (r < 0)
+ return r;
+ } else {
*s = *other;
*other = NULL;
}
+
+ return 0;
}
-static void merge_names(Unit *u, Unit *other) {
+static int merge_names(Unit *u, Unit *other) {
char *t;
Iterator i;
+ int r;
assert(u);
assert(other);
- complete_move(&u->names, &other->names);
+ r = complete_move(&u->names, &other->names);
+ if (r < 0)
+ return r;
set_free_free(other->names);
other->names = NULL;
@@ -583,6 +592,8 @@ static void merge_names(Unit *u, Unit *other) {
SET_FOREACH(t, u->names, i)
assert_se(hashmap_replace(u->manager->units, t, u) == 0);
+
+ return 0;
}
static int reserve_dependencies(Unit *u, Unit *other, UnitDependency d) {
@@ -639,7 +650,8 @@ static void merge_dependencies(Unit *u, Unit *other, const char *other_id, UnitD
if (back)
maybe_warn_about_dependency(u->id, other_id, d);
- complete_move(&u->dependencies[d], &other->dependencies[d]);
+ /* The move cannot fail. The caller must have performed a reservation. */
+ assert_se(complete_move(&u->dependencies[d], &other->dependencies[d]) == 0);
set_free(other->dependencies[d]);
other->dependencies[d] = NULL;
@@ -694,7 +706,9 @@ int unit_merge(Unit *u, Unit *other) {
}
/* Merge names */
- merge_names(u, other);
+ r = merge_names(u, other);
+ if (r < 0)
+ return r;
/* Redirect all references */
while (other->refs)
commit 7ad63f57b6ce7ae9e3cc19dcb441f0a4494fa3f2
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 00:17:51 2014 +0200
hashmap: allow hashmap_move() to fail
It cannot fail in the current hashmap implementation, but it may fail in
alternative implementations (unless a sufficiently large reservation has
been placed beforehand).
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index ebc2ef1..6f5f820 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -815,16 +815,16 @@ int hashmap_reserve(Hashmap *h, unsigned entries_add) {
return 0;
}
-void hashmap_move(Hashmap *h, Hashmap *other) {
+int hashmap_move(Hashmap *h, Hashmap *other) {
struct hashmap_entry *e, *n;
assert(h);
/* The same as hashmap_merge(), but every new item from other
- * is moved to h. This function is guaranteed to succeed. */
+ * is moved to h. */
if (!other)
- return;
+ return 0;
for (e = other->iterate_list_head; e; e = n) {
unsigned h_hash, other_hash;
@@ -839,6 +839,8 @@ void hashmap_move(Hashmap *h, Hashmap *other) {
unlink_entry(other, e, other_hash);
link_entry(h, e, h_hash);
}
+
+ return 0;
}
int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h
index e0ff26c..65fb3c0 100644
--- a/src/shared/hashmap.h
+++ b/src/shared/hashmap.h
@@ -160,9 +160,9 @@ int hashmap_reserve(Hashmap *h, unsigned entries_add);
static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
return hashmap_reserve((Hashmap*) h, entries_add);
}
-void hashmap_move(Hashmap *h, Hashmap *other);
-static inline void ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
- hashmap_move((Hashmap*) h, (Hashmap*) other);
+int hashmap_move(Hashmap *h, Hashmap *other);
+static inline int ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
+ return hashmap_move((Hashmap*) h, (Hashmap*) other);
}
int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);
static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
diff --git a/src/shared/set.c b/src/shared/set.c
index 1a3465c..84ab82a 100644
--- a/src/shared/set.c
+++ b/src/shared/set.c
@@ -141,7 +141,7 @@ int set_reserve(Set *s, unsigned entries_add) {
return hashmap_reserve(MAKE_HASHMAP(s), entries_add);
}
-void set_move(Set *s, Set *other) {
+int set_move(Set *s, Set *other) {
return hashmap_move(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
}
diff --git a/src/shared/set.h b/src/shared/set.h
index 8fe071a..d2622d1 100644
--- a/src/shared/set.h
+++ b/src/shared/set.h
@@ -51,7 +51,7 @@ int set_remove_and_put(Set *s, void *old_value, void *new_value);
int set_merge(Set *s, Set *other);
int set_reserve(Set *s, unsigned entries_add);
-void set_move(Set *s, Set *other);
+int set_move(Set *s, Set *other);
int set_move_one(Set *s, Set *other, void *value);
unsigned set_size(Set *s);
diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c
index 8f7c039..ce686b6 100644
--- a/src/test/test-hashmap-plain.c
+++ b/src/test/test-hashmap-plain.c
@@ -194,8 +194,8 @@ static void test_hashmap_move(void) {
hashmap_put(m, "key 3", val3);
hashmap_put(m, "key 4", val4);
- hashmap_move(n, NULL);
- hashmap_move(n, m);
+ assert(hashmap_move(n, NULL) == 0);
+ assert(hashmap_move(n, m) == 0);
assert_se(hashmap_size(m) == 1);
r = hashmap_get(m, "key 1");
commit 09a65f92994445d8fecca34e71b423a8be1769bf
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 00:00:30 2014 +0200
unit: place reservations before merging other's dependencies
With the hashmap implementation that uses chaining the reservations
merely ensure that the merging won't result in long bucket chains.
With a future alternative implementation it will additionally reserve
memory to make sure the merging won't fail.
diff --git a/src/core/unit.c b/src/core/unit.c
index 0389e6e..41b9ba4 100644
--- a/src/core/unit.c
+++ b/src/core/unit.c
@@ -585,6 +585,27 @@ static void merge_names(Unit *u, Unit *other) {
assert_se(hashmap_replace(u->manager->units, t, u) == 0);
}
+static int reserve_dependencies(Unit *u, Unit *other, UnitDependency d) {
+ unsigned n_reserve;
+
+ assert(u);
+ assert(other);
+ assert(d < _UNIT_DEPENDENCY_MAX);
+
+ /*
+ * If u does not have this dependency set allocated, there is no need
+ * to reserve anything. In that case other's set will be transfered
+ * as a whole to u by complete_move().
+ */
+ if (!u->dependencies[d])
+ return 0;
+
+ /* merge_dependencies() will skip a u-on-u dependency */
+ n_reserve = set_size(other->dependencies[d]) - !!set_get(other->dependencies[d], u);
+
+ return set_reserve(u->dependencies[d], n_reserve);
+}
+
static void merge_dependencies(Unit *u, Unit *other, const char *other_id, UnitDependency d) {
Iterator i;
Unit *back;
@@ -627,6 +648,7 @@ static void merge_dependencies(Unit *u, Unit *other, const char *other_id, UnitD
int unit_merge(Unit *u, Unit *other) {
UnitDependency d;
const char *other_id = NULL;
+ int r;
assert(u);
assert(other);
@@ -660,6 +682,17 @@ int unit_merge(Unit *u, Unit *other) {
if (other->id)
other_id = strdupa(other->id);
+ /* Make reservations to ensure merge_dependencies() won't fail */
+ for (d = 0; d < _UNIT_DEPENDENCY_MAX; d++) {
+ r = reserve_dependencies(u, other, d);
+ /*
+ * We don't rollback reservations if we fail. We don't have
+ * a way to undo reservations. A reservation is not a leak.
+ */
+ if (r < 0)
+ return r;
+ }
+
/* Merge names */
merge_names(u, other);
commit 2d5c93c7af05bfa25cad85909acdb7b0bfc3f4e1
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Sat Oct 4 21:29:10 2014 +0200
install, cgtop: adjust hashmap_move_one() callers for -ENOMEM possibility
That hashmap_move_one() currently cannot fail with -ENOMEM is an
implementation detail, which is not possible to guarantee in general.
Hashmap implementations based on anything else than chaining of
individual entries may have to allocate.
hashmap_move_one will not fail with -ENOMEM if a proper reservation has
been made beforehand. Use reservations in install.c.
In cgtop.c simply propagate the error instead of asserting.
diff --git a/src/cgtop/cgtop.c b/src/cgtop/cgtop.c
index ab8c4cf..932a7ba 100644
--- a/src/cgtop/cgtop.c
+++ b/src/cgtop/cgtop.c
@@ -126,7 +126,9 @@ static int process(const char *controller, const char *path, Hashmap *a, Hashmap
return r;
}
} else {
- assert_se(hashmap_move_one(a, b, path) == 0);
+ r = hashmap_move_one(a, b, path);
+ if (r < 0)
+ return r;
g->cpu_valid = g->memory_valid = g->io_valid = g->n_tasks_valid = false;
}
}
diff --git a/src/shared/install.c b/src/shared/install.c
index 4ef7dc8..0d7c30e 100644
--- a/src/shared/install.c
+++ b/src/shared/install.c
@@ -1395,18 +1395,24 @@ static int install_context_apply(
unsigned *n_changes) {
InstallInfo *i;
- int r = 0, q;
+ int r, q;
assert(c);
assert(paths);
assert(config_path);
- while ((i = ordered_hashmap_first(c->will_install))) {
+ if (!ordered_hashmap_isempty(c->will_install)) {
+ r = ordered_hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
+ if (r < 0)
+ return r;
- q = ordered_hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
- if (q < 0)
- return q;
+ r = ordered_hashmap_reserve(c->have_installed, ordered_hashmap_size(c->will_install));
+ if (r < 0)
+ return r;
+ }
+ r = 0;
+ while ((i = ordered_hashmap_first(c->will_install))) {
assert_se(ordered_hashmap_move_one(c->have_installed, c->will_install, i->name) == 0);
q = unit_file_search(c, i, paths, root_dir, false, true);
@@ -1434,7 +1440,7 @@ static int install_context_mark_for_removal(
const char *root_dir) {
InstallInfo *i;
- int r = 0, q;
+ int r, q;
assert(c);
assert(paths);
@@ -1442,12 +1448,18 @@ static int install_context_mark_for_removal(
/* Marks all items for removal */
- while ((i = ordered_hashmap_first(c->will_install))) {
+ if (!ordered_hashmap_isempty(c->will_install)) {
+ r = ordered_hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
+ if (r < 0)
+ return r;
- q = ordered_hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
- if (q < 0)
- return q;
+ r = ordered_hashmap_reserve(c->have_installed, ordered_hashmap_size(c->will_install));
+ if (r < 0)
+ return r;
+ }
+ r = 0;
+ while ((i = ordered_hashmap_first(c->will_install))) {
assert_se(ordered_hashmap_move_one(c->have_installed, c->will_install, i->name) == 0);
q = unit_file_search(c, i, paths, root_dir, false, true);
@@ -1544,11 +1556,17 @@ int unit_file_add_dependency(
return r;
}
- while ((info = ordered_hashmap_first(c.will_install))) {
+ if (!ordered_hashmap_isempty(c.will_install)) {
r = ordered_hashmap_ensure_allocated(&c.have_installed, &string_hash_ops);
if (r < 0)
return r;
+ r = ordered_hashmap_reserve(c.have_installed, ordered_hashmap_size(c.will_install));
+ if (r < 0)
+ return r;
+ }
+
+ while ((info = ordered_hashmap_first(c.will_install))) {
assert_se(ordered_hashmap_move_one(c.have_installed, c.will_install, info->name) == 0);
r = unit_file_search(&c, info, &paths, root_dir, false, false);
commit 8f88aed740ded77af443bb1b7c79bb229b50f8f8
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 00:30:54 2014 +0200
test: add test for hashmap_reserve()
diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c
index ef78ed6..8f7c039 100644
--- a/src/test/test-hashmap-plain.c
+++ b/src/test/test-hashmap-plain.c
@@ -795,6 +795,23 @@ static void test_hashmap_clear_free_free(void) {
assert_se(hashmap_isempty(m));
}
+static void test_hashmap_reserve(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+
+ m = hashmap_new(&string_hash_ops);
+
+ assert_se(hashmap_reserve(m, 1) == 0);
+ assert_se(hashmap_buckets(m) < 1000);
+ assert_se(hashmap_reserve(m, 1000) == 0);
+ assert_se(hashmap_buckets(m) >= 1000);
+ assert_se(hashmap_isempty(m));
+
+ assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
+
+ assert_se(hashmap_reserve(m, UINT_MAX) == -ENOMEM);
+ assert_se(hashmap_reserve(m, UINT_MAX - 1) == -ENOMEM);
+}
+
void test_hashmap_funcs(void) {
test_hashmap_copy();
test_hashmap_get_strv();
@@ -823,4 +840,5 @@ void test_hashmap_funcs(void) {
test_hashmap_steal_first_key();
test_hashmap_steal_first();
test_hashmap_clear_free_free();
+ test_hashmap_reserve();
}
commit e4c691b59db60ef2e6d8e64766d6ae02cd0dd457
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Tue Oct 14 23:35:24 2014 +0200
hashmap: introduce hashmap_reserve()
With the current hashmap implementation that uses chaining, placing a
reservation can serve two purposes:
- To optimize putting of entries if the number of entries to put is
known. The reservation allocates buckets, so later resizing can be
avoided.
- To avoid having very long bucket chains after using
hashmap_move(_one).
In an alternative hashmap implementation it will serve an additional
purpose:
- To guarantee a subsequent hashmap_move(_one) will not fail with
-ENOMEM (this never happens in the current implementation).
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 0b45641..ebc2ef1 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -369,18 +369,26 @@ static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *ke
return NULL;
}
-static int resize_buckets(Hashmap *h) {
+static int resize_buckets(Hashmap *h, unsigned entries_add) {
struct hashmap_entry **n, *i;
- unsigned m;
+ unsigned m, new_n_entries, new_n_buckets;
uint8_t nkey[HASH_KEY_SIZE];
assert(h);
- if (_likely_(h->n_entries*4 < h->n_buckets*3))
+ new_n_entries = h->n_entries + entries_add;
+
+ /* overflow? */
+ if (_unlikely_(new_n_entries < entries_add || new_n_entries > UINT_MAX / 4))
+ return -ENOMEM;
+
+ new_n_buckets = new_n_entries * 4 / 3;
+
+ if (_likely_(new_n_buckets <= h->n_buckets))
return 0;
- /* Increase by four */
- m = (h->n_entries+1)*4-1;
+ /* Increase by four at least */
+ m = MAX((h->n_entries+1)*4-1, new_n_buckets);
/* If we hit OOM we simply risk packed hashmaps... */
n = new0(struct hashmap_entry*, m);
@@ -432,7 +440,7 @@ static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash
struct hashmap_entry *e;
- if (resize_buckets(h) > 0)
+ if (resize_buckets(h, 1) > 0)
hash = bucket_hash(h, key);
if (h->from_pool)
@@ -795,6 +803,18 @@ int hashmap_merge(Hashmap *h, Hashmap *other) {
return 0;
}
+int hashmap_reserve(Hashmap *h, unsigned entries_add) {
+ int r;
+
+ assert(h);
+
+ r = resize_buckets(h, entries_add);
+ if (r < 0)
+ return r;
+
+ return 0;
+}
+
void hashmap_move(Hashmap *h, Hashmap *other) {
struct hashmap_entry *e, *n;
diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h
index 9789ad7..e0ff26c 100644
--- a/src/shared/hashmap.h
+++ b/src/shared/hashmap.h
@@ -156,6 +156,10 @@ int hashmap_merge(Hashmap *h, Hashmap *other);
static inline int ordered_hashmap_merge(OrderedHashmap *h, OrderedHashmap *other) {
return hashmap_merge((Hashmap*) h, (Hashmap*) other);
}
+int hashmap_reserve(Hashmap *h, unsigned entries_add);
+static inline int ordered_hashmap_reserve(OrderedHashmap *h, unsigned entries_add) {
+ return hashmap_reserve((Hashmap*) h, entries_add);
+}
void hashmap_move(Hashmap *h, Hashmap *other);
static inline void ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
hashmap_move((Hashmap*) h, (Hashmap*) other);
diff --git a/src/shared/set.c b/src/shared/set.c
index ed16067..1a3465c 100644
--- a/src/shared/set.c
+++ b/src/shared/set.c
@@ -137,6 +137,10 @@ int set_merge(Set *s, Set *other) {
return hashmap_merge(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
}
+int set_reserve(Set *s, unsigned entries_add) {
+ return hashmap_reserve(MAKE_HASHMAP(s), entries_add);
+}
+
void set_move(Set *s, Set *other) {
return hashmap_move(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
}
diff --git a/src/shared/set.h b/src/shared/set.h
index 840ee0a..8fe071a 100644
--- a/src/shared/set.h
+++ b/src/shared/set.h
@@ -50,6 +50,7 @@ void *set_remove(Set *s, void *value);
int set_remove_and_put(Set *s, void *old_value, void *new_value);
int set_merge(Set *s, Set *other);
+int set_reserve(Set *s, unsigned entries_add);
void set_move(Set *s, Set *other);
int set_move_one(Set *s, Set *other, void *value);
commit 9700d6980f7c212b10a69399e6430b82a6f45587
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 00:36:45 2014 +0200
hashmap: return more information from resize_buckets()
Return 0 if no resize was needed, 1 if successfully resized and
negative on error.
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 1c3a452..0b45641 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -369,7 +369,7 @@ static struct hashmap_entry *hash_scan(Hashmap *h, unsigned hash, const void *ke
return NULL;
}
-static bool resize_buckets(Hashmap *h) {
+static int resize_buckets(Hashmap *h) {
struct hashmap_entry **n, *i;
unsigned m;
uint8_t nkey[HASH_KEY_SIZE];
@@ -377,7 +377,7 @@ static bool resize_buckets(Hashmap *h) {
assert(h);
if (_likely_(h->n_entries*4 < h->n_buckets*3))
- return false;
+ return 0;
/* Increase by four */
m = (h->n_entries+1)*4-1;
@@ -385,7 +385,7 @@ static bool resize_buckets(Hashmap *h) {
/* If we hit OOM we simply risk packed hashmaps... */
n = new0(struct hashmap_entry*, m);
if (!n)
- return false;
+ return -ENOMEM;
/* Let's use a different randomized hash key for the
* extension, so that people cannot guess what we are using
@@ -424,7 +424,7 @@ static bool resize_buckets(Hashmap *h) {
memcpy(h->hash_key, nkey, HASH_KEY_SIZE);
- return true;
+ return 1;
}
static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash) {
@@ -432,7 +432,7 @@ static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash
struct hashmap_entry *e;
- if (resize_buckets(h))
+ if (resize_buckets(h) > 0)
hash = bucket_hash(h, key);
if (h->from_pool)
commit b3dcf58e283ff1bcb2c1ffacccb158d6e0c271e6
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Tue Aug 12 23:35:23 2014 +0200
shared: split mempool implementation from hashmaps
diff --git a/Makefile.am b/Makefile.am
index 4d93304..fae946a 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -768,6 +768,8 @@ libsystemd_shared_la_SOURCES = \
src/shared/time-util.h \
src/shared/locale-util.c \
src/shared/locale-util.h \
+ src/shared/mempool.c \
+ src/shared/mempool.h \
src/shared/hashmap.c \
src/shared/hashmap.h \
src/shared/siphash24.c \
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 8225b8e..1c3a452 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -28,6 +28,7 @@
#include "hashmap.h"
#include "macro.h"
#include "siphash24.h"
+#include "mempool.h"
#define INITIAL_N_BUCKETS 31
@@ -50,82 +51,21 @@ struct Hashmap {
bool from_pool:1;
};
-struct pool {
- struct pool *next;
- unsigned n_tiles;
- unsigned n_used;
+struct hashmap_tile {
+ Hashmap h;
+ struct hashmap_entry *initial_buckets[INITIAL_N_BUCKETS];
};
-static struct pool *first_hashmap_pool = NULL;
-static void *first_hashmap_tile = NULL;
-
-static struct pool *first_entry_pool = NULL;
-static void *first_entry_tile = NULL;
-
-static void* allocate_tile(struct pool **first_pool, void **first_tile, size_t tile_size, unsigned at_least) {
- unsigned i;
-
- /* When a tile is released we add it to the list and simply
- * place the next pointer at its offset 0. */
-
- assert(tile_size >= sizeof(void*));
- assert(at_least > 0);
-
- if (*first_tile) {
- void *r;
-
- r = *first_tile;
- *first_tile = * (void**) (*first_tile);
- return r;
- }
-
- if (_unlikely_(!*first_pool) || _unlikely_((*first_pool)->n_used >= (*first_pool)->n_tiles)) {
- unsigned n;
- size_t size;
- struct pool *p;
-
- n = *first_pool ? (*first_pool)->n_tiles : 0;
- n = MAX(at_least, n * 2);
- size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*tile_size);
- n = (size - ALIGN(sizeof(struct pool))) / tile_size;
-
- p = malloc(size);
- if (!p)
- return NULL;
-
- p->next = *first_pool;
- p->n_tiles = n;
- p->n_used = 0;
-
- *first_pool = p;
- }
-
- i = (*first_pool)->n_used++;
-
- return ((uint8_t*) (*first_pool)) + ALIGN(sizeof(struct pool)) + i*tile_size;
-}
-
-static void deallocate_tile(void **first_tile, void *p) {
- * (void**) p = *first_tile;
- *first_tile = p;
-}
+static DEFINE_MEMPOOL(hashmap_pool, struct hashmap_tile, 8);
+static DEFINE_MEMPOOL(hashmap_entry_pool, struct hashmap_entry, 64);
#ifdef VALGRIND
-static void drop_pool(struct pool *p) {
- while (p) {
- struct pool *n;
- n = p->next;
- free(p);
- p = n;
- }
-}
-
-__attribute__((destructor)) static void cleanup_pool(void) {
+__attribute__((destructor)) static void cleanup_pools(void) {
/* Be nice to valgrind */
- drop_pool(first_hashmap_pool);
- drop_pool(first_entry_pool);
+ mempool_drop(&hashmap_entry_pool);
+ mempool_drop(&hashmap_pool);
}
#endif
@@ -223,33 +163,32 @@ static void get_hash_key(uint8_t hash_key[HASH_KEY_SIZE], bool reuse_is_ok) {
Hashmap *hashmap_new(const struct hash_ops *hash_ops) {
bool b;
+ struct hashmap_tile *ht;
Hashmap *h;
- size_t size;
b = is_main_thread();
- size = ALIGN(sizeof(Hashmap)) + INITIAL_N_BUCKETS * sizeof(struct hashmap_entry*);
-
if (b) {
- h = allocate_tile(&first_hashmap_pool, &first_hashmap_tile, size, 8);
- if (!h)
+ ht = mempool_alloc_tile(&hashmap_pool);
+ if (!ht)
return NULL;
- memzero(h, size);
+ memzero(ht, sizeof(struct hashmap_tile));
} else {
- h = malloc0(size);
+ ht = malloc0(sizeof(struct hashmap_tile));
- if (!h)
+ if (!ht)
return NULL;
}
+ h = &ht->h;
h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops;
h->n_buckets = INITIAL_N_BUCKETS;
h->n_entries = 0;
h->iterate_list_head = h->iterate_list_tail = NULL;
- h->buckets = (struct hashmap_entry**) ((uint8_t*) h + ALIGN(sizeof(Hashmap)));
+ h->buckets = ht->initial_buckets;
h->from_pool = b;
@@ -339,7 +278,7 @@ static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
unlink_entry(h, e, hash);
if (h->from_pool)
- deallocate_tile(&first_entry_tile, e);
+ mempool_free_tile(&hashmap_entry_pool, e);
else
free(e);
}
@@ -357,7 +296,7 @@ void hashmap_free(Hashmap*h) {
free(h->buckets);
if (h->from_pool)
- deallocate_tile(&first_hashmap_tile, h);
+ mempool_free_tile(&hashmap_pool, container_of(h, struct hashmap_tile, h));
else
free(h);
}
@@ -497,7 +436,7 @@ static int __hashmap_put(Hashmap *h, const void *key, void *value, unsigned hash
hash = bucket_hash(h, key);
if (h->from_pool)
- e = allocate_tile(&first_entry_pool, &first_entry_tile, sizeof(struct hashmap_entry), 64U);
+ e = mempool_alloc_tile(&hashmap_entry_pool);
else
e = new(struct hashmap_entry, 1);
diff --git a/src/shared/mempool.c b/src/shared/mempool.c
new file mode 100644
index 0000000..b39a37f
--- /dev/null
+++ b/src/shared/mempool.c
@@ -0,0 +1,94 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+ This file is part of systemd.
+
+ Copyright 2010-2014 Lennart Poettering
+ Copyright 2014 Michal Schmidt
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "mempool.h"
+#include "macro.h"
+#include "util.h"
+
+struct pool {
+ struct pool *next;
+ unsigned n_tiles;
+ unsigned n_used;
+};
+
+void* mempool_alloc_tile(struct mempool *mp) {
+ unsigned i;
+
+ /* When a tile is released we add it to the list and simply
+ * place the next pointer at its offset 0. */
+
+ assert(mp->tile_size >= sizeof(void*));
+ assert(mp->at_least > 0);
+
+ if (mp->freelist) {
+ void *r;
+
+ r = mp->freelist;
+ mp->freelist = * (void**) mp->freelist;
+ return r;
+ }
+
+ if (_unlikely_(!mp->first_pool) ||
+ _unlikely_(mp->first_pool->n_used >= mp->first_pool->n_tiles)) {
+ unsigned n;
+ size_t size;
+ struct pool *p;
+
+ n = mp->first_pool ? mp->first_pool->n_tiles : 0;
+ n = MAX(mp->at_least, n * 2);
+ size = PAGE_ALIGN(ALIGN(sizeof(struct pool)) + n*mp->tile_size);
+ n = (size - ALIGN(sizeof(struct pool))) / mp->tile_size;
+
+ p = malloc(size);
+ if (!p)
+ return NULL;
+
+ p->next = mp->first_pool;
+ p->n_tiles = n;
+ p->n_used = 0;
+
+ mp->first_pool = p;
+ }
+
+ i = mp->first_pool->n_used++;
+
+ return ((uint8_t*) mp->first_pool) + ALIGN(sizeof(struct pool)) + i*mp->tile_size;
+}
+
+void mempool_free_tile(struct mempool *mp, void *p) {
+ * (void**) p = mp->freelist;
+ mp->freelist = p;
+}
+
+#ifdef VALGRIND
+
+void mempool_drop(struct mempool *mp) {
+ struct pool *p = mp->first_pool;
+ while (p) {
+ struct pool *n;
+ n = p->next;
+ free(p);
+ p = n;
+ }
+}
+
+#endif
diff --git a/src/shared/mempool.h b/src/shared/mempool.h
new file mode 100644
index 0000000..8b0bf38
--- /dev/null
+++ b/src/shared/mempool.h
@@ -0,0 +1,48 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+ This file is part of systemd.
+
+ Copyright 2011-2014 Lennart Poettering
+ Copyright 2014 Michal Schmidt
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <stddef.h>
+
+struct pool;
+
+struct mempool {
+ struct pool *first_pool;
+ void *freelist;
+ size_t tile_size;
+ unsigned at_least;
+};
+
+void* mempool_alloc_tile(struct mempool *mp);
+void mempool_free_tile(struct mempool *mp, void *p);
+
+#define DEFINE_MEMPOOL(pool_name, tile_type, alloc_at_least) \
+struct mempool pool_name = { \
+ .tile_size = sizeof(tile_type), \
+ .at_least = alloc_at_least, \
+}
+
+
+#ifdef VALGRIND
+void mempool_drop(struct mempool *mp);
+#endif
commit 1e43061b67336052b5b231840a38508a5397a363
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Fri Aug 22 13:56:51 2014 +0200
resolve: make DnsScope::conflict_queue an OrderedHashmap
on_conflict_dispatch() uses hashmap_steal_first() and then does
something non-trivial with it. It may care about the order.
diff --git a/src/resolve/resolved-dns-scope.c b/src/resolve/resolved-dns-scope.c
index 40d5992..1664b13 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -82,10 +82,10 @@ DnsScope* dns_scope_free(DnsScope *s) {
dns_transaction_free(t);
}
- while ((rr = hashmap_steal_first(s->conflict_queue)))
+ while ((rr = ordered_hashmap_steal_first(s->conflict_queue)))
dns_resource_record_unref(rr);
- hashmap_free(s->conflict_queue);
+ ordered_hashmap_free(s->conflict_queue);
sd_event_source_unref(s->conflict_event_source);
dns_cache_flush(&s->cache);
@@ -682,7 +682,7 @@ static int on_conflict_dispatch(sd_event_source *es, usec_t usec, void *userdata
_cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
_cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
- rr = hashmap_steal_first(scope->conflict_queue);
+ rr = ordered_hashmap_steal_first(scope->conflict_queue);
if (!rr)
break;
@@ -709,7 +709,7 @@ int dns_scope_notify_conflict(DnsScope *scope, DnsResourceRecord *rr) {
/* We don't send these queries immediately. Instead, we queue
* them, and send them after some jitter delay. */
- r = hashmap_ensure_allocated(&scope->conflict_queue, &dns_resource_key_hash_ops);
+ r = ordered_hashmap_ensure_allocated(&scope->conflict_queue, &dns_resource_key_hash_ops);
if (r < 0) {
log_oom();
return r;
@@ -718,7 +718,7 @@ int dns_scope_notify_conflict(DnsScope *scope, DnsResourceRecord *rr) {
/* We only place one RR per key in the conflict
* messages, not all of them. That should be enough to
* indicate where there might be a conflict */
- r = hashmap_put(scope->conflict_queue, rr->key, rr);
+ r = ordered_hashmap_put(scope->conflict_queue, rr->key, rr);
if (r == -EEXIST || r == 0)
return 0;
if (r < 0) {
diff --git a/src/resolve/resolved-dns-scope.h b/src/resolve/resolved-dns-scope.h
index a022309..f05648e 100644
--- a/src/resolve/resolved-dns-scope.h
+++ b/src/resolve/resolved-dns-scope.h
@@ -55,7 +55,7 @@ struct DnsScope {
DnsCache cache;
DnsZone zone;
- Hashmap *conflict_queue;
+ OrderedHashmap *conflict_queue;
sd_event_source *conflict_event_source;
RateLimit ratelimit;
commit c9fe4af70d2c884c1f95714a81ad6d1de31d5186
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Tue Oct 14 18:27:55 2014 +0200
sd-bus: make sd_bus::reply_callbacks a OrderedHashmap
The way process_closing() picks the first entry from reply_callbacks
and works with it makes it likely that it cares about the order.
diff --git a/src/libsystemd/sd-bus/bus-internal.h b/src/libsystemd/sd-bus/bus-internal.h
index 601ea5a..57247d7 100644
--- a/src/libsystemd/sd-bus/bus-internal.h
+++ b/src/libsystemd/sd-bus/bus-internal.h
@@ -230,7 +230,7 @@ struct sd_bus {
struct bus_match_node match_callbacks;
Prioq *reply_callbacks_prioq;
- Hashmap *reply_callbacks;
+ OrderedHashmap *reply_callbacks;
LIST_HEAD(struct filter_callback, filter_callbacks);
Hashmap *nodes;
diff --git a/src/libsystemd/sd-bus/bus-slot.c b/src/libsystemd/sd-bus/bus-slot.c
index d6793c2..568a6ed 100644
--- a/src/libsystemd/sd-bus/bus-slot.c
+++ b/src/libsystemd/sd-bus/bus-slot.c
@@ -75,7 +75,7 @@ void bus_slot_disconnect(sd_bus_slot *slot) {
case BUS_REPLY_CALLBACK:
if (slot->reply_callback.cookie != 0)
- hashmap_remove(slot->bus->reply_callbacks, &slot->reply_callback.cookie);
+ ordered_hashmap_remove(slot->bus->reply_callbacks, &slot->reply_callback.cookie);
if (slot->reply_callback.timeout != 0)
prioq_remove(slot->bus->reply_callbacks_prioq, &slot->reply_callback, &slot->reply_callback.prioq_idx);
diff --git a/src/libsystemd/sd-bus/sd-bus.c b/src/libsystemd/sd-bus/sd-bus.c
index e677a88..c17b1a0 100644
--- a/src/libsystemd/sd-bus/sd-bus.c
+++ b/src/libsystemd/sd-bus/sd-bus.c
@@ -139,7 +139,7 @@ static void bus_free(sd_bus *b) {
bus_reset_queues(b);
- hashmap_free_free(b->reply_callbacks);
+ ordered_hashmap_free_free(b->reply_callbacks);
prioq_free(b->reply_callbacks_prioq);
assert(b->match_callbacks.type == BUS_MATCH_ROOT);
@@ -1759,7 +1759,7 @@ _public_ int sd_bus_call_async(
if (!BUS_IS_OPEN(bus->state))
return -ENOTCONN;
- r = hashmap_ensure_allocated(&bus->reply_callbacks, &uint64_hash_ops);
+ r = ordered_hashmap_ensure_allocated(&bus->reply_callbacks, &uint64_hash_ops);
if (r < 0)
return r;
@@ -1782,7 +1782,7 @@ _public_ int sd_bus_call_async(
s->reply_callback.callback = callback;
s->reply_callback.cookie = BUS_MESSAGE_COOKIE(m);
- r = hashmap_put(bus->reply_callbacks, &s->reply_callback.cookie, &s->reply_callback);
+ r = ordered_hashmap_put(bus->reply_callbacks, &s->reply_callback.cookie, &s->reply_callback);
if (r < 0) {
s->reply_callback.cookie = 0;
return r;
@@ -2096,7 +2096,7 @@ static int process_timeout(sd_bus *bus) {
assert_se(prioq_pop(bus->reply_callbacks_prioq) == c);
c->timeout = 0;
- hashmap_remove(bus->reply_callbacks, &c->cookie);
+ ordered_hashmap_remove(bus->reply_callbacks, &c->cookie);
c->cookie = 0;
slot = container_of(c, sd_bus_slot, reply_callback);
@@ -2165,7 +2165,7 @@ static int process_reply(sd_bus *bus, sd_bus_message *m) {
if (m->destination && bus->unique_name && !streq_ptr(m->destination, bus->unique_name))
return 0;
- c = hashmap_remove(bus->reply_callbacks, &m->reply_cookie);
+ c = ordered_hashmap_remove(bus->reply_callbacks, &m->reply_cookie);
if (!c)
return 0;
@@ -2499,7 +2499,7 @@ static int process_closing(sd_bus *bus, sd_bus_message **ret) {
assert(bus);
assert(bus->state == BUS_CLOSING);
- c = hashmap_first(bus->reply_callbacks);
+ c = ordered_hashmap_first(bus->reply_callbacks);
if (c) {
_cleanup_bus_error_free_ sd_bus_error error_buffer = SD_BUS_ERROR_NULL;
sd_bus_slot *slot;
@@ -2522,7 +2522,7 @@ static int process_closing(sd_bus *bus, sd_bus_message **ret) {
c->timeout = 0;
}
- hashmap_remove(bus->reply_callbacks, &c->cookie);
+ ordered_hashmap_remove(bus->reply_callbacks, &c->cookie);
c->cookie = 0;
slot = container_of(c, sd_bus_slot, reply_callback);
commit c1f906bd91c388fd84a006a56e1e6692e23f8ae3
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Tue Aug 19 13:38:53 2014 +0200
journal: make sd_journal::files a OrderedHashmap
Anything that uses hashmap_next() almost certainly cares about the order
and needs to be an OrderedHashmap.
diff --git a/src/journal/journal-internal.h b/src/journal/journal-internal.h
index e591fb6..70847db 100644
--- a/src/journal/journal-internal.h
+++ b/src/journal/journal-internal.h
@@ -100,7 +100,7 @@ struct sd_journal {
char *path;
char *prefix;
- Hashmap *files;
+ OrderedHashmap *files;
MMapCache *mmap;
Location current_location;
diff --git a/src/journal/journalctl.c b/src/journal/journalctl.c
index c320282..dfde0a9 100644
--- a/src/journal/journalctl.c
+++ b/src/journal/journalctl.c
@@ -1508,7 +1508,7 @@ static int verify(sd_journal *j) {
log_show_color(true);
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
int k;
usec_t first, validated, last;
@@ -1603,7 +1603,7 @@ static int access_check(sd_journal *j) {
assert(j);
if (set_isempty(j->errors)) {
- if (hashmap_isempty(j->files))
+ if (ordered_hashmap_isempty(j->files))
log_notice("No journal files were found.");
return 0;
}
@@ -1635,7 +1635,7 @@ static int access_check(sd_journal *j) {
}
#endif
- if (hashmap_isempty(j->files)) {
+ if (ordered_hashmap_isempty(j->files)) {
log_error("No journal files were opened due to insufficient permissions.");
r = -EACCES;
}
diff --git a/src/journal/sd-journal.c b/src/journal/sd-journal.c
index ac57f4f..cf21c4d 100644
--- a/src/journal/sd-journal.c
+++ b/src/journal/sd-journal.c
@@ -86,7 +86,7 @@ static void detach_location(sd_journal *j) {
j->current_file = NULL;
j->current_field = 0;
- HASHMAP_FOREACH(f, j->files, i)
+ ORDERED_HASHMAP_FOREACH(f, j->files, i)
f->current_offset = 0;
}
@@ -879,7 +879,7 @@ static int real_journal_next(sd_journal *j, direction_t direction) {
assert_return(j, -EINVAL);
assert_return(!journal_pid_changed(j), -ECHILD);
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
bool found;
r = next_beyond_location(j, f, direction, &o, &p);
@@ -1288,10 +1288,10 @@ static int add_any_file(sd_journal *j, const char *path) {
assert(j);
assert(path);
- if (hashmap_get(j->files, path))
+ if (ordered_hashmap_get(j->files, path))
return 0;
- if (hashmap_size(j->files) >= JOURNAL_FILES_MAX) {
+ if (ordered_hashmap_size(j->files) >= JOURNAL_FILES_MAX) {
log_warning("Too many open journal files, not adding %s.", path);
return set_put_error(j, -ETOOMANYREFS);
}
@@ -1302,7 +1302,7 @@ static int add_any_file(sd_journal *j, const char *path) {
/* journal_file_dump(f); */
- r = hashmap_put(j->files, f->path, f);
+ r = ordered_hashmap_put(j->files, f->path, f);
if (r < 0) {
journal_file_close(f);
return r;
@@ -1351,7 +1351,7 @@ static int remove_file(sd_journal *j, const char *prefix, const char *filename)
if (!path)
return -ENOMEM;
- f = hashmap_get(j->files, path);
+ f = ordered_hashmap_get(j->files, path);
if (!f)
return 0;
@@ -1363,7 +1363,7 @@ static void remove_file_real(sd_journal *j, JournalFile *f) {
assert(j);
assert(f);
- hashmap_remove(j->files, f->path);
+ ordered_hashmap_remove(j->files, f->path);
log_debug("File %s removed.", f->path);
@@ -1374,7 +1374,7 @@ static void remove_file_real(sd_journal *j, JournalFile *f) {
if (j->unique_file == f) {
/* Jump to the next unique_file or NULL if that one was last */
- j->unique_file = hashmap_next(j->files, j->unique_file->path);
+ j->unique_file = ordered_hashmap_next(j->files, j->unique_file->path);
j->unique_offset = 0;
if (!j->unique_file)
j->unique_file_lost = true;
@@ -1634,7 +1634,7 @@ static int add_current_paths(sd_journal *j) {
* "root" directories. We don't expect errors here, so we
* treat them as fatal. */
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
_cleanup_free_ char *dir;
int r;
@@ -1689,7 +1689,7 @@ static sd_journal *journal_new(int flags, const char *path) {
goto fail;
}
- j->files = hashmap_new(&string_hash_ops);
+ j->files = ordered_hashmap_new(&string_hash_ops);
j->directories_by_path = hashmap_new(&string_hash_ops);
j->mmap = mmap_cache_new();
if (!j->files || !j->directories_by_path || !j->mmap)
@@ -1835,10 +1835,10 @@ _public_ void sd_journal_close(sd_journal *j) {
sd_journal_flush_matches(j);
- while ((f = hashmap_steal_first(j->files)))
+ while ((f = ordered_hashmap_steal_first(j->files)))
journal_file_close(f);
- hashmap_free(j->files);
+ ordered_hashmap_free(j->files);
while ((d = hashmap_first(j->directories_by_path)))
remove_directory(j, d);
@@ -2368,7 +2368,7 @@ _public_ int sd_journal_get_cutoff_realtime_usec(sd_journal *j, uint64_t *from,
assert_return(from || to, -EINVAL);
assert_return(from != to, -EINVAL);
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
usec_t fr, t;
r = journal_file_get_cutoff_realtime_usec(f, &fr, &t);
@@ -2408,7 +2408,7 @@ _public_ int sd_journal_get_cutoff_monotonic_usec(sd_journal *j, sd_id128_t boot
assert_return(from || to, -EINVAL);
assert_return(from != to, -EINVAL);
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
usec_t fr, t;
r = journal_file_get_cutoff_monotonic_usec(f, boot_id, &fr, &t);
@@ -2443,7 +2443,7 @@ void journal_print_header(sd_journal *j) {
assert(j);
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
if (newline)
putchar('\n');
else
@@ -2462,7 +2462,7 @@ _public_ int sd_journal_get_usage(sd_journal *j, uint64_t *bytes) {
assert_return(!journal_pid_changed(j), -ECHILD);
assert_return(bytes, -EINVAL);
- HASHMAP_FOREACH(f, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(f, j->files, i) {
struct stat st;
if (fstat(f->fd, &st) < 0)
@@ -2511,7 +2511,7 @@ _public_ int sd_journal_enumerate_unique(sd_journal *j, const void **data, size_
if (j->unique_file_lost)
return 0;
- j->unique_file = hashmap_first(j->files);
+ j->unique_file = ordered_hashmap_first(j->files);
if (!j->unique_file)
return 0;
@@ -2545,7 +2545,7 @@ _public_ int sd_journal_enumerate_unique(sd_journal *j, const void **data, size_
/* We reached the end of the list? Then start again, with the next file */
if (j->unique_offset == 0) {
- j->unique_file = hashmap_next(j->files, j->unique_file->path);
+ j->unique_file = ordered_hashmap_next(j->files, j->unique_file->path);
if (!j->unique_file)
return 0;
@@ -2594,7 +2594,7 @@ _public_ int sd_journal_enumerate_unique(sd_journal *j, const void **data, size_
* object by checking if it exists in the earlier
* traversed files. */
found = false;
- HASHMAP_FOREACH(of, j->files, i) {
+ ORDERED_HASHMAP_FOREACH(of, j->files, i) {
Object *oo;
uint64_t op;
commit 43cf8388ea4ffed1801468d4b650d6e48eefce9e
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Fri Aug 22 13:44:14 2014 +0200
journal: make Server::user_journals an OrderedHashmap
Order matters here. It replaces oldest entries first when
USER_JOURNALS_MAX is reached.
diff --git a/src/journal/journald-server.c b/src/journal/journald-server.c
index 9709889..b49359e 100644
--- a/src/journal/journald-server.c
+++ b/src/journal/journald-server.c
@@ -266,7 +266,7 @@ static JournalFile* find_journal(Server *s, uid_t uid) {
if (r < 0)
return s->system_journal;
- f = hashmap_get(s->user_journals, UINT32_TO_PTR(uid));
+ f = ordered_hashmap_get(s->user_journals, UINT32_TO_PTR(uid));
if (f)
return f;
@@ -274,9 +274,9 @@ static JournalFile* find_journal(Server *s, uid_t uid) {
SD_ID128_FORMAT_VAL(machine), uid) < 0)
return s->system_journal;
- while (hashmap_size(s->user_journals) >= USER_JOURNALS_MAX) {
+ while (ordered_hashmap_size(s->user_journals) >= USER_JOURNALS_MAX) {
/* Too many open? Then let's close one */
- f = hashmap_steal_first(s->user_journals);
+ f = ordered_hashmap_steal_first(s->user_journals);
assert(f);
journal_file_close(f);
}
@@ -287,7 +287,7 @@ static JournalFile* find_journal(Server *s, uid_t uid) {
server_fix_perms(s, f, uid);
- r = hashmap_put(s->user_journals, UINT32_TO_PTR(uid), f);
+ r = ordered_hashmap_put(s->user_journals, UINT32_TO_PTR(uid), f);
if (r < 0) {
journal_file_close(f);
return s->system_journal;
@@ -328,13 +328,13 @@ void server_rotate(Server *s) {
do_rotate(s, &s->runtime_journal, "runtime", false, 0);
do_rotate(s, &s->system_journal, "system", s->seal, 0);
- HASHMAP_FOREACH_KEY(f, k, s->user_journals, i) {
+ ORDERED_HASHMAP_FOREACH_KEY(f, k, s->user_journals, i) {
r = do_rotate(s, &f, "user", s->seal, PTR_TO_UINT32(k));
if (r >= 0)
- hashmap_replace(s->user_journals, k, f);
+ ordered_hashmap_replace(s->user_journals, k, f);
else if (!f)
/* Old file has been closed and deallocated */
- hashmap_remove(s->user_journals, k);
+ ordered_hashmap_remove(s->user_journals, k);
}
}
@@ -350,7 +350,7 @@ void server_sync(Server *s) {
log_error("Failed to sync system journal: %s", strerror(-r));
}
- HASHMAP_FOREACH_KEY(f, k, s->user_journals, i) {
+ ORDERED_HASHMAP_FOREACH_KEY(f, k, s->user_journals, i) {
r = journal_file_set_offline(f);
if (r < 0)
log_error("Failed to sync user journal: %s", strerror(-r));
@@ -1484,7 +1484,7 @@ int server_init(Server *s) {
mkdir_p("/run/systemd/journal", 0755);
- s->user_journals = hashmap_new(NULL);
+ s->user_journals = ordered_hashmap_new(NULL);
if (!s->user_journals)
return log_oom();
@@ -1604,7 +1604,7 @@ void server_maybe_append_tags(Server *s) {
if (s->system_journal)
journal_file_maybe_append_tag(s->system_journal, n);
- HASHMAP_FOREACH(f, s->user_journals, i)
+ ORDERED_HASHMAP_FOREACH(f, s->user_journals, i)
journal_file_maybe_append_tag(f, n);
#endif
}
@@ -1622,10 +1622,10 @@ void server_done(Server *s) {
if (s->runtime_journal)
journal_file_close(s->runtime_journal);
- while ((f = hashmap_steal_first(s->user_journals)))
+ while ((f = ordered_hashmap_steal_first(s->user_journals)))
journal_file_close(f);
- hashmap_free(s->user_journals);
+ ordered_hashmap_free(s->user_journals);
sd_event_source_unref(s->syslog_event_source);
sd_event_source_unref(s->native_event_source);
diff --git a/src/journal/journald-server.h b/src/journal/journald-server.h
index 42a2235..6888187 100644
--- a/src/journal/journald-server.h
+++ b/src/journal/journald-server.h
@@ -76,7 +76,7 @@ typedef struct Server {
JournalFile *runtime_journal;
JournalFile *system_journal;
- Hashmap *user_journals;
+ OrderedHashmap *user_journals;
uint64_t seqnum;
commit 4743015db6ad394bd43efadb0651e3906b4efc25
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Tue Oct 14 17:58:13 2014 +0200
journal: make JournalFile::chain_cache an OrderedHashmap
The order of entries may matter here. Oldest entries are evicted first
when the cache is full.
(Though I don't see anything to rejuvenate entries on cache hits.)
diff --git a/src/journal/journal-file.c b/src/journal/journal-file.c
index 038b437..d06dbc2 100644
--- a/src/journal/journal-file.c
+++ b/src/journal/journal-file.c
@@ -136,7 +136,7 @@ void journal_file_close(JournalFile *f) {
if (f->mmap)
mmap_cache_unref(f->mmap);
- hashmap_free_free(f->chain_cache);
+ ordered_hashmap_free_free(f->chain_cache);
#if defined(HAVE_XZ) || defined(HAVE_LZ4)
free(f->compress_buffer);
@@ -1366,7 +1366,7 @@ typedef struct ChainCacheItem {
} ChainCacheItem;
static void chain_cache_put(
- Hashmap *h,
+ OrderedHashmap *h,
ChainCacheItem *ci,
uint64_t first,
uint64_t array,
@@ -1380,8 +1380,8 @@ static void chain_cache_put(
if (array == first)
return;
- if (hashmap_size(h) >= CHAIN_CACHE_MAX)
- ci = hashmap_steal_first(h);
+ if (ordered_hashmap_size(h) >= CHAIN_CACHE_MAX)
+ ci = ordered_hashmap_steal_first(h);
else {
ci = new(ChainCacheItem, 1);
if (!ci)
@@ -1390,7 +1390,7 @@ static void chain_cache_put(
ci->first = first;
- if (hashmap_put(h, &ci->first, ci) < 0) {
+ if (ordered_hashmap_put(h, &ci->first, ci) < 0) {
free(ci);
return;
}
@@ -1419,7 +1419,7 @@ static int generic_array_get(
a = first;
/* Try the chain cache first */
- ci = hashmap_get(f->chain_cache, &first);
+ ci = ordered_hashmap_get(f->chain_cache, &first);
if (ci && i > ci->total) {
a = ci->array;
i -= ci->total;
@@ -1522,7 +1522,7 @@ static int generic_array_bisect(
/* Start with the first array in the chain */
a = first;
- ci = hashmap_get(f->chain_cache, &first);
+ ci = ordered_hashmap_get(f->chain_cache, &first);
if (ci && n > ci->total) {
/* Ah, we have iterated this bisection array chain
* previously! Let's see if we can skip ahead in the
@@ -2498,7 +2498,7 @@ int journal_file_open(
goto fail;
}
- f->chain_cache = hashmap_new(&uint64_hash_ops);
+ f->chain_cache = ordered_hashmap_new(&uint64_hash_ops);
if (!f->chain_cache) {
r = -ENOMEM;
goto fail;
diff --git a/src/journal/journal-file.h b/src/journal/journal-file.h
index fa5b943..211e121 100644
--- a/src/journal/journal-file.h
+++ b/src/journal/journal-file.h
@@ -76,7 +76,7 @@ typedef struct JournalFile {
JournalMetrics metrics;
MMapCache *mmap;
- Hashmap *chain_cache;
+ OrderedHashmap *chain_cache;
#if defined(HAVE_XZ) || defined(HAVE_LZ4)
void *compress_buffer;
commit 9f03ee51a2207954ef18be79ca3e11cd14ca56fd
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Fri Aug 22 10:35:59 2014 +0200
install: make InstallContext::{will_install,have_installed} OrderedHashmaps
It appears order may matter here. Use OrderedHashmaps to be safe.
diff --git a/src/shared/install.c b/src/shared/install.c
index ff5dcba..4ef7dc8 100644
--- a/src/shared/install.c
+++ b/src/shared/install.c
@@ -41,8 +41,8 @@
#include "special.h"
typedef struct {
- Hashmap *will_install;
- Hashmap *have_installed;
+ OrderedHashmap *will_install;
+ OrderedHashmap *have_installed;
} InstallContext;
static int in_search_path(const char *path, char **search) {
@@ -844,16 +844,16 @@ static void install_info_free(InstallInfo *i) {
free(i);
}
-static void install_info_hashmap_free(Hashmap *m) {
+static void install_info_hashmap_free(OrderedHashmap *m) {
InstallInfo *i;
if (!m)
return;
- while ((i = hashmap_steal_first(m)))
+ while ((i = ordered_hashmap_steal_first(m)))
install_info_free(i);
- hashmap_free(m);
+ ordered_hashmap_free(m);
}
static void install_context_done(InstallContext *c) {
@@ -881,11 +881,11 @@ static int install_info_add(
if (!unit_name_is_valid(name, TEMPLATE_VALID))
return -EINVAL;
- if (hashmap_get(c->have_installed, name) ||
- hashmap_get(c->will_install, name))
+ if (ordered_hashmap_get(c->have_installed, name) ||
+ ordered_hashmap_get(c->will_install, name))
return 0;
- r = hashmap_ensure_allocated(&c->will_install, &string_hash_ops);
+ r = ordered_hashmap_ensure_allocated(&c->will_install, &string_hash_ops);
if (r < 0)
return r;
@@ -907,7 +907,7 @@ static int install_info_add(
}
}
- r = hashmap_put(c->will_install, i->name, i);
+ r = ordered_hashmap_put(c->will_install, i->name, i);
if (r < 0)
goto fail;
@@ -1180,7 +1180,7 @@ static int unit_file_can_install(
if (r < 0)
return r;
- assert_se(i = hashmap_first(c.will_install));
+ assert_se(i = ordered_hashmap_first(c.will_install));
r = unit_file_search(&c, i, paths, root_dir, allow_symlink, true);
@@ -1401,13 +1401,13 @@ static int install_context_apply(
assert(paths);
assert(config_path);
- while ((i = hashmap_first(c->will_install))) {
+ while ((i = ordered_hashmap_first(c->will_install))) {
- q = hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
+ q = ordered_hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
if (q < 0)
return q;
- assert_se(hashmap_move_one(c->have_installed, c->will_install, i->name) == 0);
+ assert_se(ordered_hashmap_move_one(c->have_installed, c->will_install, i->name) == 0);
q = unit_file_search(c, i, paths, root_dir, false, true);
if (q < 0) {
@@ -1442,13 +1442,13 @@ static int install_context_mark_for_removal(
/* Marks all items for removal */
- while ((i = hashmap_first(c->will_install))) {
+ while ((i = ordered_hashmap_first(c->will_install))) {
- q = hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
+ q = ordered_hashmap_ensure_allocated(&c->have_installed, &string_hash_ops);
if (q < 0)
return q;
- assert_se(hashmap_move_one(c->have_installed, c->will_install, i->name) == 0);
+ assert_se(ordered_hashmap_move_one(c->have_installed, c->will_install, i->name) == 0);
q = unit_file_search(c, i, paths, root_dir, false, true);
if (q == -ENOENT) {
@@ -1544,12 +1544,12 @@ int unit_file_add_dependency(
return r;
}
- while ((info = hashmap_first(c.will_install))) {
- r = hashmap_ensure_allocated(&c.have_installed, &string_hash_ops);
+ while ((info = ordered_hashmap_first(c.will_install))) {
+ r = ordered_hashmap_ensure_allocated(&c.have_installed, &string_hash_ops);
if (r < 0)
return r;
- assert_se(hashmap_move_one(c.have_installed, c.will_install, info->name) == 0);
+ assert_se(ordered_hashmap_move_one(c.have_installed, c.will_install, info->name) == 0);
r = unit_file_search(&c, info, &paths, root_dir, false, false);
if (r < 0)
@@ -1720,7 +1720,7 @@ int unit_file_set_default(
if (r < 0)
return r;
- assert_se(i = hashmap_first(c.will_install));
+ assert_se(i = ordered_hashmap_first(c.will_install));
r = unit_file_search(&c, i, &paths, root_dir, false, true);
if (r < 0)
commit dd0124f6cb6ff7da1ce8be23ec7e1137fe15958d
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Fri Oct 10 23:30:21 2014 +0200
hashmap: drop assert(h) from hashmap_next()
It's handled just fine by returning NULL.
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index c4fde89..8225b8e 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -945,7 +945,6 @@ void *hashmap_next(Hashmap *h, const void *key) {
unsigned hash;
struct hashmap_entry *e;
- assert(h);
assert(key);
if (!h)
commit bf3d3e2bb7ae2d3854be57f28dd1403c8f7e4c3c
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Mon Oct 13 18:14:07 2014 +0200
hashmap: hashmap_move_one() should return -ENOENT when 'other' is NULL
-ENOENT is the same return value as if 'other' were an allocated hashmap
that does not contain the key. A NULL hashmap is a possible way of
expressing a hashmap that contains no key.
diff --git a/src/shared/hashmap.c b/src/shared/hashmap.c
index 4c51705..c4fde89 100644
--- a/src/shared/hashmap.c
+++ b/src/shared/hashmap.c
@@ -886,15 +886,15 @@ int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key) {
unsigned h_hash, other_hash;
struct hashmap_entry *e;
- if (!other)
- return 0;
-
assert(h);
h_hash = bucket_hash(h, key);
if (hash_scan(h, h_hash, key))
return -EEXIST;
+ if (!other)
+ return -ENOENT;
+
other_hash = bucket_hash(other, key);
e = hash_scan(other, other_hash, key);
if (!e)
commit 9ba81d5a61b7c992a1d2e5e02f334b8e2a0b0c22
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 11:06:08 2014 +0200
test: add and improve hashmap tests
Test more corner cases and error states in several tests.
Add new tests for:
hashmap_move
hashmap_remove
hashmap_remove2
hashmap_remove_value
hashmap_remove_and_replace
hashmap_get2
hashmap_first
In test_hashmap_many additionally test with an intentionally bad hash
function.
diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c
index 9080df5..ef78ed6 100644
--- a/src/test/test-hashmap-plain.c
+++ b/src/test/test-hashmap-plain.c
@@ -154,8 +154,10 @@ static void test_hashmap_move_one(void) {
hashmap_put(m, "key 3", val3);
hashmap_put(m, "key 4", val4);
- hashmap_move_one(n, m, "key 3");
- hashmap_move_one(n, m, "key 4");
+ assert_se(hashmap_move_one(n, NULL, "key 3") == -ENOENT);
+ assert_se(hashmap_move_one(n, m, "key 5") == -ENOENT);
+ assert_se(hashmap_move_one(n, m, "key 3") == 0);
+ assert_se(hashmap_move_one(n, m, "key 4") == 0);
r = hashmap_get(n, "key 3");
assert_se(r && streq(r, "val3"));
@@ -164,6 +166,49 @@ static void test_hashmap_move_one(void) {
r = hashmap_get(m, "key 3");
assert_se(!r);
+ assert_se(hashmap_move_one(n, m, "key 3") == -EEXIST);
+
+ hashmap_free_free(m);
+ hashmap_free_free(n);
+}
+
+static void test_hashmap_move(void) {
+ Hashmap *m, *n;
+ char *val1, *val2, *val3, *val4, *r;
+
+ val1 = strdup("val1");
+ assert_se(val1);
+ val2 = strdup("val2");
+ assert_se(val2);
+ val3 = strdup("val3");
+ assert_se(val3);
+ val4 = strdup("val4");
+ assert_se(val4);
+
+ m = hashmap_new(&string_hash_ops);
+ n = hashmap_new(&string_hash_ops);
+
+ hashmap_put(n, "key 1", strdup(val1));
+ hashmap_put(m, "key 1", val1);
+ hashmap_put(m, "key 2", val2);
+ hashmap_put(m, "key 3", val3);
+ hashmap_put(m, "key 4", val4);
+
+ hashmap_move(n, NULL);
+ hashmap_move(n, m);
+
+ assert_se(hashmap_size(m) == 1);
+ r = hashmap_get(m, "key 1");
+ assert_se(r && streq(r, "val1"));
+
+ r = hashmap_get(n, "key 1");
+ assert_se(r && streq(r, "val1"));
+ r = hashmap_get(n, "key 2");
+ assert_se(r && streq(r, "val2"));
+ r = hashmap_get(n, "key 3");
+ assert_se(r && streq(r, "val3"));
+ r = hashmap_get(n, "key 4");
+ assert_se(r && streq(r, "val4"));
hashmap_free_free(m);
hashmap_free_free(n);
@@ -183,7 +228,11 @@ static void test_hashmap_update(void) {
r = hashmap_get(m, "key 1");
assert_se(streq(r, "old_value"));
- hashmap_update(m, "key 1", val2);
+ assert_se(hashmap_update(m, "key 2", val2) == -ENOENT);
+ r = hashmap_get(m, "key 1");
+ assert_se(streq(r, "old_value"));
+
+ assert_se(hashmap_update(m, "key 1", val2) == 0);
r = hashmap_get(m, "key 1");
assert_se(streq(r, "new_value"));
@@ -193,18 +242,107 @@ static void test_hashmap_update(void) {
}
static void test_hashmap_put(void) {
- Hashmap *m;
+ Hashmap *m = NULL;
int valid_hashmap_put;
+ void *val1 = (void*) "val 1";
- m = hashmap_new(&string_hash_ops);
+ hashmap_ensure_allocated(&m, &string_hash_ops);
+ assert_se(m);
- valid_hashmap_put = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
+ valid_hashmap_put = hashmap_put(m, "key 1", val1);
assert_se(valid_hashmap_put == 1);
+ assert_se(hashmap_put(m, "key 1", val1) == 0);
+ assert_se(hashmap_put(m, "key 1", (void *)"val 2") == -EEXIST);
- assert_se(m);
hashmap_free(m);
}
+static void test_hashmap_remove(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+ char *r;
+
+ r = hashmap_remove(NULL, "key 1");
+ assert_se(r == NULL);
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ r = hashmap_remove(m, "no such key");
+ assert_se(r == NULL);
+
+ hashmap_put(m, "key 1", (void*) "val 1");
+ hashmap_put(m, "key 2", (void*) "val 2");
+
+ r = hashmap_remove(m, "key 1");
+ assert_se(streq(r, "val 1"));
+
+ r = hashmap_get(m, "key 2");
+ assert_se(streq(r, "val 2"));
+ assert_se(!hashmap_get(m, "key 1"));
+}
+
+static void test_hashmap_remove2(void) {
+ _cleanup_hashmap_free_free_free_ Hashmap *m = NULL;
+ char key1[] = "key 1";
+ char key2[] = "key 2";
+ char val1[] = "val 1";
+ char val2[] = "val 2";
+ void *r, *r2;
+
+ r = hashmap_remove2(NULL, "key 1", &r2);
+ assert_se(r == NULL);
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ r = hashmap_remove2(m, "no such key", &r2);
+ assert_se(r == NULL);
+
+ hashmap_put(m, strdup(key1), strdup(val1));
+ hashmap_put(m, strdup(key2), strdup(val2));
+
+ r = hashmap_remove2(m, key1, &r2);
+ assert_se(streq(r, val1));
+ assert_se(streq(r2, key1));
+ free(r);
+ free(r2);
+
+ r = hashmap_get(m, key2);
+ assert_se(streq(r, val2));
+ assert_se(!hashmap_get(m, key1));
+}
+
+static void test_hashmap_remove_value(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+ char *r;
+
+ r = hashmap_remove_value(NULL, "key 1", (void*) "val 1");
+ assert_se(r == NULL);
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ r = hashmap_remove_value(m, "key 1", (void*) "val 1");
+ assert_se(r == NULL);
+
+ hashmap_put(m, "key 1", (void*) "val 1");
+ hashmap_put(m, "key 2", (void*) "val 2");
+
+ r = hashmap_remove_value(m, "key 1", (void*) "val 1");
+ assert_se(streq(r, "val 1"));
+
+ r = hashmap_get(m, "key 2");
+ assert_se(streq(r, "val 2"));
+ assert_se(!hashmap_get(m, "key 1"));
+
+ r = hashmap_remove_value(m, "key 2", (void*) "val 1");
+ assert_se(r == NULL);
+
+ r = hashmap_get(m, "key 2");
+ assert_se(streq(r, "val 2"));
+ assert_se(!hashmap_get(m, "key 1"));
+}
+
static void test_hashmap_remove_and_put(void) {
_cleanup_hashmap_free_ Hashmap *m = NULL;
int valid;
@@ -213,11 +351,15 @@ static void test_hashmap_remove_and_put(void) {
m = hashmap_new(&string_hash_ops);
assert_se(m);
- valid = hashmap_remove_and_put(m, "unvalid key", "new key", NULL);
- assert_se(valid < 0);
+ valid = hashmap_remove_and_put(m, "invalid key", "new key", NULL);
+ assert_se(valid == -ENOENT);
valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
assert_se(valid == 1);
+
+ valid = hashmap_remove_and_put(NULL, "key 1", "key 2", (void*) (const char *) "val 2");
+ assert_se(valid == -ENOENT);
+
valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
assert_se(valid == 0);
@@ -228,7 +370,43 @@ static void test_hashmap_remove_and_put(void) {
valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
assert_se(valid == 1);
valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
- assert_se(valid < 0);
+ assert_se(valid == -EEXIST);
+}
+
+static void test_hashmap_remove_and_replace(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+ int valid;
+ void *key1 = UINT_TO_PTR(1);
+ void *key2 = UINT_TO_PTR(2);
+ void *key3 = UINT_TO_PTR(3);
+ void *r;
+
+ m = hashmap_new(&trivial_hash_ops);
+ assert_se(m);
+
+ valid = hashmap_remove_and_replace(m, key1, key2, NULL);
+ assert_se(valid == -ENOENT);
+
+ valid = hashmap_put(m, key1, key1);
+ assert_se(valid == 1);
+
+ valid = hashmap_remove_and_replace(NULL, key1, key2, key2);
+ assert_se(valid == -ENOENT);
+
+ valid = hashmap_remove_and_replace(m, key1, key2, key2);
+ assert_se(valid == 0);
+
+ r = hashmap_get(m, key2);
+ assert_se(r == key2);
+ assert_se(!hashmap_get(m, key1));
+
+ valid = hashmap_put(m, key3, key3);
+ assert_se(valid == 1);
+ valid = hashmap_remove_and_replace(m, key3, key2, key2);
+ assert_se(valid == 0);
+ r = hashmap_get(m, key2);
+ assert_se(r == key2);
+ assert_se(!hashmap_get(m, key3));
}
static void test_hashmap_ensure_allocated(void) {
@@ -283,6 +461,7 @@ static void test_hashmap_foreach(void) {
Iterator i;
bool value_found[] = { false, false, false, false };
char *val1, *val2, *val3, *val4, *s;
+ unsigned count;
val1 = strdup("my val1");
assert_se(val1);
@@ -293,8 +472,20 @@ static void test_hashmap_foreach(void) {
val4 = strdup("my val4");
assert_se(val4);
+ m = NULL;
+
+ count = 0;
+ HASHMAP_FOREACH(s, m, i)
+ count++;
+ assert_se(count == 0);
+
m = hashmap_new(&string_hash_ops);
+ count = 0;
+ HASHMAP_FOREACH(s, m, i)
+ count++;
+ assert_se(count == 0);
+
hashmap_put(m, "Key 1", val1);
hashmap_put(m, "Key 2", val2);
hashmap_put(m, "Key 3", val3);
@@ -363,6 +554,9 @@ static void test_hashmap_contains(void) {
assert_se(!hashmap_contains(m, "Key 1"));
hashmap_put(m, "Key 1", val1);
assert_se(hashmap_contains(m, "Key 1"));
+ assert_se(!hashmap_contains(m, "Key 2"));
+
+ assert_se(!hashmap_contains(NULL, "Key 1"));
assert_se(m);
hashmap_free_free(m);
@@ -398,6 +592,9 @@ static void test_hashmap_size(void) {
val4 = strdup("my val");
assert_se(val4);
+ assert_se(hashmap_size(NULL) == 0);
+ assert_se(hashmap_buckets(NULL) == 0);
+
m = hashmap_new(&string_hash_ops);
hashmap_put(m, "Key 1", val1);
@@ -407,6 +604,7 @@ static void test_hashmap_size(void) {
assert_se(m);
assert_se(hashmap_size(m) == 4);
+ assert_se(hashmap_buckets(m) >= 4);
hashmap_free_free(m);
}
@@ -418,6 +616,9 @@ static void test_hashmap_get(void) {
val = strdup("my val");
assert_se(val);
+ r = hashmap_get(NULL, "Key 1");
+ assert_se(r == NULL);
+
m = hashmap_new(&string_hash_ops);
hashmap_put(m, "Key 1", val);
@@ -425,32 +626,109 @@ static void test_hashmap_get(void) {
r = hashmap_get(m, "Key 1");
assert_se(streq(r, val));
+ r = hashmap_get(m, "no such key");
+ assert_se(r == NULL);
+
assert_se(m);
hashmap_free_free(m);
}
+static void test_hashmap_get2(void) {
+ Hashmap *m;
+ char *r;
+ char *val;
+ char key_orig[] = "Key 1";
+ void *key_copy;
+
+ val = strdup("my val");
+ assert_se(val);
+
+ key_copy = strdup(key_orig);
+ assert_se(key_copy);
+
+ r = hashmap_get2(NULL, key_orig, &key_copy);
+ assert_se(r == NULL);
+
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, key_copy, val);
+ key_copy = NULL;
+
+ r = hashmap_get2(m, key_orig, &key_copy);
+ assert_se(streq(r, val));
+ assert_se(key_orig != key_copy);
+ assert_se(streq(key_orig, key_orig));
+
+ r = hashmap_get2(m, "no such key", NULL);
+ assert_se(r == NULL);
+
+ assert_se(m);
+ hashmap_free_free_free(m);
+}
+
+static unsigned long crippled_hashmap_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) {
+ return trivial_hash_func(p, hash_key) & 0xff;
+}
+
+static const struct hash_ops crippled_hashmap_ops = {
+ .hash = crippled_hashmap_func,
+ .compare = trivial_compare_func,
+};
+
static void test_hashmap_many(void) {
Hashmap *h;
- unsigned i;
+ unsigned i, j;
+ void *v, *k;
+ static const struct {
+ const struct hash_ops *ops;
+ unsigned n_entries;
+ } tests[] = {
+ { .ops = NULL, .n_entries = 1 << 20 },
+ { .ops = &crippled_hashmap_ops, .n_entries = 1 << 11 },
+ };
-#define N_ENTRIES 100000
- assert_se(h = hashmap_new(NULL));
+ for (j = 0; j < ELEMENTSOF(tests); j++) {
+ assert_se(h = hashmap_new(tests[j].ops));
- for (i = 1; i < N_ENTRIES*3; i+=3) {
- assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
- assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
- }
+ for (i = 1; i < tests[j].n_entries*3; i+=3) {
+ assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
+ assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
+ }
+
+ for (i = 1; i < tests[j].n_entries*3; i++)
+ assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
- for (i = 1; i < N_ENTRIES*3; i++)
- assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
+ log_info("%u <= %u * 0.75 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.75);
- log_info("%u <= %u * 0.75 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.75);
+ assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75);
+ assert_se(hashmap_size(h) == tests[j].n_entries);
- assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75);
- assert_se(hashmap_size(h) == N_ENTRIES);
+ while (!hashmap_isempty(h)) {
+ k = hashmap_first_key(h);
+ v = hashmap_remove(h, k);
+ assert_se(v == k);
+ }
- hashmap_free(h);
+ hashmap_free(h);
+ }
+}
+
+static void test_hashmap_first(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ assert_se(!hashmap_first(m));
+ assert_se(hashmap_put(m, "key 1", (void*) "val 1") == 1);
+ assert_se(streq(hashmap_first(m), "val 1"));
+ assert_se(hashmap_put(m, "key 2", (void*) "val 2") == 1);
+#ifdef ORDERED
+ assert_se(streq(hashmap_first(m), "val 1"));
+ assert_se(hashmap_remove(m, "key 1"));
+ assert_se(streq(hashmap_first(m), "val 2"));
+#endif
}
static void test_hashmap_first_key(void) {
@@ -521,10 +799,15 @@ void test_hashmap_funcs(void) {
test_hashmap_copy();
test_hashmap_get_strv();
test_hashmap_move_one();
+ test_hashmap_move();
test_hashmap_replace();
test_hashmap_update();
test_hashmap_put();
+ test_hashmap_remove();
+ test_hashmap_remove2();
+ test_hashmap_remove_value();
test_hashmap_remove_and_put();
+ test_hashmap_remove_and_replace();
test_hashmap_ensure_allocated();
test_hashmap_foreach();
test_hashmap_foreach_key();
@@ -532,8 +815,10 @@ void test_hashmap_funcs(void) {
test_hashmap_merge();
test_hashmap_isempty();
test_hashmap_get();
+ test_hashmap_get2();
test_hashmap_size();
test_hashmap_many();
+ test_hashmap_first();
test_hashmap_first_key();
test_hashmap_steal_first_key();
test_hashmap_steal_first();
commit 32a4456cc252689f51f383d150d34ed636bfec4d
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Wed Oct 15 11:00:46 2014 +0200
test: generate tests for OrderedHashmap from Hashmap tests
test-hashmap-ordered.c is generated from test-hashmap-plain.c simply by
substituting "ordered_hashmap" for "hashmap" etc.
In the cases where tests rely on the order of entries, a distinction
between plain and ordered hashmaps is made using the ORDERED macro,
which is defined only for test-hashmap-ordered.c.
diff --git a/Makefile.am b/Makefile.am
index 3b0ba0a..4d93304 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -1569,8 +1569,27 @@ test_namespace_SOURCES = \
test_namespace_LDADD = \
libsystemd-core.la
+CLEANFILES += \
+ src/test/test-hashmap-ordered.c
+
+BUILT_SOURCES += \
+ src/test/test-hashmap-ordered.c
+
+src/test/test-hashmap-ordered.c: src/test/test-hashmap-plain.c
+ $(AM_V_at)$(MKDIR_P) $(dir $@)
+ $(AM_V_GEN)$(AWK) 'BEGIN { print "/* GENERATED FILE */\n#define ORDERED" } \
+ { if (!match($$0, "^#include")) \
+ gsub(/hashmap/, "ordered_hashmap"); \
+ gsub(/HASHMAP/, "ORDERED_HASHMAP"); \
+ gsub(/Hashmap/, "OrderedHashmap"); \
+ print }' <$< >$@
+
+nodist_test_hashmap_SOURCES = \
+ src/test/test-hashmap-ordered.c
+
test_hashmap_SOURCES = \
- src/test/test-hashmap.c
+ src/test/test-hashmap.c \
+ src/test/test-hashmap-plain.c
test_hashmap_LDADD = \
libsystemd-core.la
diff --git a/src/test/.gitignore b/src/test/.gitignore
new file mode 100644
index 0000000..e4c198a
--- /dev/null
+++ b/src/test/.gitignore
@@ -0,0 +1 @@
+test-hashmap-ordered.c
diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c
new file mode 100644
index 0000000..9080df5
--- /dev/null
+++ b/src/test/test-hashmap-plain.c
@@ -0,0 +1,541 @@
+/***
+ This file is part of systemd
+
+ Copyright 2013 Daniel Buch
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "strv.h"
+#include "util.h"
+#include "hashmap.h"
+
+void test_hashmap_funcs(void);
+
+static void test_hashmap_replace(void) {
+ Hashmap *m;
+ char *val1, *val2, *val3, *val4, *val5, *r;
+
+ m = hashmap_new(&string_hash_ops);
+
+ val1 = strdup("val1");
+ assert_se(val1);
+ val2 = strdup("val2");
+ assert_se(val2);
+ val3 = strdup("val3");
+ assert_se(val3);
+ val4 = strdup("val4");
+ assert_se(val4);
+ val5 = strdup("val5");
+ assert_se(val5);
+
+ hashmap_put(m, "key 1", val1);
+ hashmap_put(m, "key 2", val2);
+ hashmap_put(m, "key 3", val3);
+ hashmap_put(m, "key 4", val4);
+
+ hashmap_replace(m, "key 3", val1);
+ r = hashmap_get(m, "key 3");
+ assert_se(streq(r, "val1"));
+
+ hashmap_replace(m, "key 5", val5);
+ r = hashmap_get(m, "key 5");
+ assert_se(streq(r, "val5"));
+
+ free(val1);
+ free(val2);
+ free(val3);
+ free(val4);
+ free(val5);
+ hashmap_free(m);
+}
+
+static void test_hashmap_copy(void) {
+ Hashmap *m, *copy;
+ char *val1, *val2, *val3, *val4, *r;
+
+ val1 = strdup("val1");
+ assert_se(val1);
+ val2 = strdup("val2");
+ assert_se(val2);
+ val3 = strdup("val3");
+ assert_se(val3);
+ val4 = strdup("val4");
+ assert_se(val4);
+
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "key 1", val1);
+ hashmap_put(m, "key 2", val2);
+ hashmap_put(m, "key 3", val3);
+ hashmap_put(m, "key 4", val4);
+
+ copy = hashmap_copy(m);
+
+ r = hashmap_get(copy, "key 1");
+ assert_se(streq(r, "val1"));
+ r = hashmap_get(copy, "key 2");
+ assert_se(streq(r, "val2"));
+ r = hashmap_get(copy, "key 3");
+ assert_se(streq(r, "val3"));
+ r = hashmap_get(copy, "key 4");
+ assert_se(streq(r, "val4"));
+
+ hashmap_free_free(copy);
+ hashmap_free(m);
+}
+
+static void test_hashmap_get_strv(void) {
+ Hashmap *m;
+ char **strv;
+ char *val1, *val2, *val3, *val4;
+
+ val1 = strdup("val1");
+ assert_se(val1);
+ val2 = strdup("val2");
+ assert_se(val2);
+ val3 = strdup("val3");
+ assert_se(val3);
+ val4 = strdup("val4");
+ assert_se(val4);
+
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "key 1", val1);
+ hashmap_put(m, "key 2", val2);
+ hashmap_put(m, "key 3", val3);
+ hashmap_put(m, "key 4", val4);
+
+ strv = hashmap_get_strv(m);
+
+#ifndef ORDERED
+ strv = strv_sort(strv);
+#endif
+
+ assert_se(streq(strv[0], "val1"));
+ assert_se(streq(strv[1], "val2"));
+ assert_se(streq(strv[2], "val3"));
+ assert_se(streq(strv[3], "val4"));
+
+ strv_free(strv);
+
+ hashmap_free(m);
+}
+
+static void test_hashmap_move_one(void) {
+ Hashmap *m, *n;
+ char *val1, *val2, *val3, *val4, *r;
+
+ val1 = strdup("val1");
+ assert_se(val1);
+ val2 = strdup("val2");
+ assert_se(val2);
+ val3 = strdup("val3");
+ assert_se(val3);
+ val4 = strdup("val4");
+ assert_se(val4);
+
+ m = hashmap_new(&string_hash_ops);
+ n = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "key 1", val1);
+ hashmap_put(m, "key 2", val2);
+ hashmap_put(m, "key 3", val3);
+ hashmap_put(m, "key 4", val4);
+
+ hashmap_move_one(n, m, "key 3");
+ hashmap_move_one(n, m, "key 4");
+
+ r = hashmap_get(n, "key 3");
+ assert_se(r && streq(r, "val3"));
+ r = hashmap_get(n, "key 4");
+ assert_se(r && streq(r, "val4"));
+ r = hashmap_get(m, "key 3");
+ assert_se(!r);
+
+
+ hashmap_free_free(m);
+ hashmap_free_free(n);
+}
+
+static void test_hashmap_update(void) {
+ Hashmap *m;
+ char *val1, *val2, *r;
+
+ m = hashmap_new(&string_hash_ops);
+ val1 = strdup("old_value");
+ assert_se(val1);
+ val2 = strdup("new_value");
+ assert_se(val2);
+
+ hashmap_put(m, "key 1", val1);
+ r = hashmap_get(m, "key 1");
+ assert_se(streq(r, "old_value"));
+
+ hashmap_update(m, "key 1", val2);
+ r = hashmap_get(m, "key 1");
+ assert_se(streq(r, "new_value"));
+
+ free(val1);
+ free(val2);
+ hashmap_free(m);
+}
+
+static void test_hashmap_put(void) {
+ Hashmap *m;
+ int valid_hashmap_put;
+
+ m = hashmap_new(&string_hash_ops);
+
+ valid_hashmap_put = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
+ assert_se(valid_hashmap_put == 1);
+
+ assert_se(m);
+ hashmap_free(m);
+}
+
+static void test_hashmap_remove_and_put(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+ int valid;
+ char *r;
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ valid = hashmap_remove_and_put(m, "unvalid key", "new key", NULL);
+ assert_se(valid < 0);
+
+ valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
+ assert_se(valid == 1);
+ valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
+ assert_se(valid == 0);
+
+ r = hashmap_get(m, "key 2");
+ assert_se(streq(r, "val 2"));
+ assert_se(!hashmap_get(m, "key 1"));
+
+ valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
+ assert_se(valid == 1);
+ valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
+ assert_se(valid < 0);
+}
+
+static void test_hashmap_ensure_allocated(void) {
+ Hashmap *m;
+ int valid_hashmap;
+
+ m = hashmap_new(&string_hash_ops);
+
+ valid_hashmap = hashmap_ensure_allocated(&m, &string_hash_ops);
+ assert_se(valid_hashmap == 0);
+
+ assert_se(m);
+ hashmap_free(m);
+}
+
+static void test_hashmap_foreach_key(void) {
+ Hashmap *m;
+ Iterator i;
+ bool key_found[] = { false, false, false, false };
+ const char *s;
+ const char *key;
+ static const char key_table[] =
+ "key 1\0"
+ "key 2\0"
+ "key 3\0"
+ "key 4\0";
+
+ m = hashmap_new(&string_hash_ops);
+
+ NULSTR_FOREACH(key, key_table)
+ hashmap_put(m, key, (void*) (const char*) "my dummy val");
+
+ HASHMAP_FOREACH_KEY(s, key, m, i) {
+ if (!key_found[0] && streq(key, "key 1"))
+ key_found[0] = true;
+ else if (!key_found[1] && streq(key, "key 2"))
+ key_found[1] = true;
+ else if (!key_found[2] && streq(key, "key 3"))
+ key_found[2] = true;
+ else if (!key_found[3] && streq(key, "fail"))
+ key_found[3] = true;
+ }
+
+ assert_se(m);
+ assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
+
+ hashmap_free(m);
+}
+
+static void test_hashmap_foreach(void) {
+ Hashmap *m;
+ Iterator i;
+ bool value_found[] = { false, false, false, false };
+ char *val1, *val2, *val3, *val4, *s;
+
+ val1 = strdup("my val1");
+ assert_se(val1);
+ val2 = strdup("my val2");
+ assert_se(val2);
+ val3 = strdup("my val3");
+ assert_se(val3);
+ val4 = strdup("my val4");
+ assert_se(val4);
+
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "Key 1", val1);
+ hashmap_put(m, "Key 2", val2);
+ hashmap_put(m, "Key 3", val3);
+ hashmap_put(m, "Key 4", val4);
+
+ HASHMAP_FOREACH(s, m, i) {
+ if (!value_found[0] && streq(s, val1))
+ value_found[0] = true;
+ else if (!value_found[1] && streq(s, val2))
+ value_found[1] = true;
+ else if (!value_found[2] && streq(s, val3))
+ value_found[2] = true;
+ else if (!value_found[3] && streq(s, val4))
+ value_found[3] = true;
+ }
+
+ assert_se(m);
+ assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
+
+ hashmap_free_free(m);
+}
+
+static void test_hashmap_merge(void) {
+ Hashmap *m;
+ Hashmap *n;
+ char *val1, *val2, *val3, *val4, *r;
+
+ val1 = strdup("my val1");
+ assert_se(val1);
+ val2 = strdup("my val2");
+ assert_se(val2);
+ val3 = strdup("my val3");
+ assert_se(val3);
+ val4 = strdup("my val4");
+ assert_se(val4);
+
+ n = hashmap_new(&string_hash_ops);
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "Key 1", val1);
+ hashmap_put(m, "Key 2", val2);
+ hashmap_put(n, "Key 3", val3);
+ hashmap_put(n, "Key 4", val4);
+
+ assert_se(hashmap_merge(m, n) == 0);
+ r = hashmap_get(m, "Key 3");
+ assert_se(r && streq(r, "my val3"));
+ r = hashmap_get(m, "Key 4");
+ assert_se(r && streq(r, "my val4"));
+
+ assert_se(n);
+ assert_se(m);
+ hashmap_free(n);
+ hashmap_free_free(m);
+}
+
+static void test_hashmap_contains(void) {
+ Hashmap *m;
+ char *val1;
+
+ val1 = strdup("my val");
+ assert_se(val1);
+
+ m = hashmap_new(&string_hash_ops);
+
+ assert_se(!hashmap_contains(m, "Key 1"));
+ hashmap_put(m, "Key 1", val1);
+ assert_se(hashmap_contains(m, "Key 1"));
+
+ assert_se(m);
+ hashmap_free_free(m);
+}
+
+static void test_hashmap_isempty(void) {
+ Hashmap *m;
+ char *val1;
+
+ val1 = strdup("my val");
+ assert_se(val1);
+
+ m = hashmap_new(&string_hash_ops);
+
+ assert_se(hashmap_isempty(m));
+ hashmap_put(m, "Key 1", val1);
+ assert_se(!hashmap_isempty(m));
+
+ assert_se(m);
+ hashmap_free_free(m);
+}
+
+static void test_hashmap_size(void) {
+ Hashmap *m;
+ char *val1, *val2, *val3, *val4;
+
+ val1 = strdup("my val");
+ assert_se(val1);
+ val2 = strdup("my val");
+ assert_se(val2);
+ val3 = strdup("my val");
+ assert_se(val3);
+ val4 = strdup("my val");
+ assert_se(val4);
+
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "Key 1", val1);
+ hashmap_put(m, "Key 2", val2);
+ hashmap_put(m, "Key 3", val3);
+ hashmap_put(m, "Key 4", val4);
+
+ assert_se(m);
+ assert_se(hashmap_size(m) == 4);
+ hashmap_free_free(m);
+}
+
+static void test_hashmap_get(void) {
+ Hashmap *m;
+ char *r;
+ char *val;
+
+ val = strdup("my val");
+ assert_se(val);
+
+ m = hashmap_new(&string_hash_ops);
+
+ hashmap_put(m, "Key 1", val);
+
+ r = hashmap_get(m, "Key 1");
+ assert_se(streq(r, val));
+
+ assert_se(m);
+ hashmap_free_free(m);
+}
+
+static void test_hashmap_many(void) {
+ Hashmap *h;
+ unsigned i;
+
+#define N_ENTRIES 100000
+
+ assert_se(h = hashmap_new(NULL));
+
+ for (i = 1; i < N_ENTRIES*3; i+=3) {
+ assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
+ assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
+ }
+
+ for (i = 1; i < N_ENTRIES*3; i++)
+ assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
+
+ log_info("%u <= %u * 0.75 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.75);
+
+ assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75);
+ assert_se(hashmap_size(h) == N_ENTRIES);
+
+ hashmap_free(h);
+}
+
+static void test_hashmap_first_key(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ assert_se(!hashmap_first_key(m));
+ assert_se(hashmap_put(m, "key 1", NULL) == 1);
+ assert_se(streq(hashmap_first_key(m), "key 1"));
+ assert_se(hashmap_put(m, "key 2", NULL) == 1);
+#ifdef ORDERED
+ assert_se(streq(hashmap_first_key(m), "key 1"));
+ assert_se(hashmap_remove(m, "key 1") == NULL);
+ assert_se(streq(hashmap_first_key(m), "key 2"));
+#endif
+}
+
+static void test_hashmap_steal_first_key(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ assert_se(!hashmap_steal_first_key(m));
+ assert_se(hashmap_put(m, "key 1", NULL) == 1);
+ assert_se(streq(hashmap_steal_first_key(m), "key 1"));
+
+ assert_se(hashmap_isempty(m));
+}
+
+static void test_hashmap_steal_first(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+ int seen[3] = {};
+ char *val;
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ assert_se(hashmap_put(m, "key 1", (void*) "1") == 1);
+ assert_se(hashmap_put(m, "key 2", (void*) "22") == 1);
+ assert_se(hashmap_put(m, "key 3", (void*) "333") == 1);
+
+ while ((val = hashmap_steal_first(m)))
+ seen[strlen(val) - 1]++;
+
+ assert_se(seen[0] == 1 && seen[1] == 1 && seen[2] == 1);
+
+ assert_se(hashmap_isempty(m));
+}
+
+static void test_hashmap_clear_free_free(void) {
+ _cleanup_hashmap_free_ Hashmap *m = NULL;
+
+ m = hashmap_new(&string_hash_ops);
+ assert_se(m);
+
+ assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
+ assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
+ assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
+
+ hashmap_clear_free_free(m);
+ assert_se(hashmap_isempty(m));
+}
+
+void test_hashmap_funcs(void) {
+ test_hashmap_copy();
+ test_hashmap_get_strv();
+ test_hashmap_move_one();
+ test_hashmap_replace();
+ test_hashmap_update();
+ test_hashmap_put();
+ test_hashmap_remove_and_put();
+ test_hashmap_ensure_allocated();
+ test_hashmap_foreach();
+ test_hashmap_foreach_key();
+ test_hashmap_contains();
+ test_hashmap_merge();
+ test_hashmap_isempty();
+ test_hashmap_get();
+ test_hashmap_size();
+ test_hashmap_many();
+ test_hashmap_first_key();
+ test_hashmap_steal_first_key();
+ test_hashmap_steal_first();
+ test_hashmap_clear_free_free();
+}
diff --git a/src/test/test-hashmap.c b/src/test/test-hashmap.c
index f907206..6900da9 100644
--- a/src/test/test-hashmap.c
+++ b/src/test/test-hashmap.c
@@ -22,153 +22,14 @@
#include "util.h"
#include "hashmap.h"
-static void test_hashmap_replace(void) {
- Hashmap *m;
- char *val1, *val2, *val3, *val4, *val5, *r;
+void test_hashmap_funcs(void);
+void test_ordered_hashmap_funcs(void);
- m = hashmap_new(&string_hash_ops);
-
- val1 = strdup("val1");
- assert_se(val1);
- val2 = strdup("val2");
- assert_se(val2);
- val3 = strdup("val3");
- assert_se(val3);
- val4 = strdup("val4");
- assert_se(val4);
- val5 = strdup("val5");
- assert_se(val5);
-
- hashmap_put(m, "key 1", val1);
- hashmap_put(m, "key 2", val2);
- hashmap_put(m, "key 3", val3);
- hashmap_put(m, "key 4", val4);
-
- hashmap_replace(m, "key 3", val1);
- r = hashmap_get(m, "key 3");
- assert_se(streq(r, "val1"));
-
- hashmap_replace(m, "key 5", val5);
- r = hashmap_get(m, "key 5");
- assert_se(streq(r, "val5"));
-
- free(val1);
- free(val2);
- free(val3);
- free(val4);
- free(val5);
- hashmap_free(m);
-}
-
-static void test_hashmap_copy(void) {
- Hashmap *m, *copy;
- char *val1, *val2, *val3, *val4, *r;
-
- val1 = strdup("val1");
- assert_se(val1);
- val2 = strdup("val2");
- assert_se(val2);
- val3 = strdup("val3");
- assert_se(val3);
- val4 = strdup("val4");
- assert_se(val4);
-
- m = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "key 1", val1);
- hashmap_put(m, "key 2", val2);
- hashmap_put(m, "key 3", val3);
- hashmap_put(m, "key 4", val4);
-
- copy = hashmap_copy(m);
-
- r = hashmap_get(copy, "key 1");
- assert_se(streq(r, "val1"));
- r = hashmap_get(copy, "key 2");
- assert_se(streq(r, "val2"));
- r = hashmap_get(copy, "key 3");
- assert_se(streq(r, "val3"));
- r = hashmap_get(copy, "key 4");
- assert_se(streq(r, "val4"));
-
- hashmap_free_free(copy);
- hashmap_free(m);
-}
-
-static void test_hashmap_get_strv(void) {
- Hashmap *m;
- char **strv;
- char *val1, *val2, *val3, *val4;
-
- val1 = strdup("val1");
- assert_se(val1);
- val2 = strdup("val2");
- assert_se(val2);
- val3 = strdup("val3");
- assert_se(val3);
- val4 = strdup("val4");
- assert_se(val4);
-
- m = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "key 1", val1);
- hashmap_put(m, "key 2", val2);
- hashmap_put(m, "key 3", val3);
- hashmap_put(m, "key 4", val4);
-
- strv = hashmap_get_strv(m);
-
- assert_se(streq(strv[0], "val1"));
- assert_se(streq(strv[1], "val2"));
- assert_se(streq(strv[2], "val3"));
- assert_se(streq(strv[3], "val4"));
-
- strv_free(strv);
-
- hashmap_free(m);
-}
-
-static void test_hashmap_move_one(void) {
- Hashmap *m, *n;
- char *val1, *val2, *val3, *val4, *r;
-
- val1 = strdup("val1");
- assert_se(val1);
- val2 = strdup("val2");
- assert_se(val2);
- val3 = strdup("val3");
- assert_se(val3);
- val4 = strdup("val4");
- assert_se(val4);
-
- m = hashmap_new(&string_hash_ops);
- n = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "key 1", val1);
- hashmap_put(m, "key 2", val2);
- hashmap_put(m, "key 3", val3);
- hashmap_put(m, "key 4", val4);
-
- hashmap_move_one(n, m, "key 3");
- hashmap_move_one(n, m, "key 4");
-
- r = hashmap_get(n, "key 3");
- assert_se(r && streq(r, "val3"));
- r = hashmap_get(n, "key 4");
- assert_se(r && streq(r, "val4"));
- r = hashmap_get(m, "key 3");
- assert_se(!r);
-
-
- hashmap_free_free(m);
- hashmap_free_free(n);
-}
-
-static void test_hashmap_next(void) {
- Hashmap *m;
+static void test_ordered_hashmap_next(void) {
+ OrderedHashmap *m;
char *val1, *val2, *val3, *val4, *r;
- m = hashmap_new(&string_hash_ops);
+ m = ordered_hashmap_new(&string_hash_ops);
val1 = strdup("val1");
assert_se(val1);
val2 = strdup("val2");
@@ -178,367 +39,25 @@ static void test_hashmap_next(void) {
val4 = strdup("val4");
assert_se(val4);
- hashmap_put(m, "key 1", val1);
- hashmap_put(m, "key 2", val2);
- hashmap_put(m, "key 3", val3);
- hashmap_put(m, "key 4", val4);
+ ordered_hashmap_put(m, "key 1", val1);
+ ordered_hashmap_put(m, "key 2", val2);
+ ordered_hashmap_put(m, "key 3", val3);
+ ordered_hashmap_put(m, "key 4", val4);
- r = hashmap_next(m, "key 1");
+ r = ordered_hashmap_next(m, "key 1");
assert_se(streq(r, val2));
- r = hashmap_next(m, "key 2");
+ r = ordered_hashmap_next(m, "key 2");
assert_se(streq(r, val3));
- r = hashmap_next(m, "key 3");
+ r = ordered_hashmap_next(m, "key 3");
assert_se(streq(r, val4));
- r = hashmap_next(m, "key 4");
+ r = ordered_hashmap_next(m, "key 4");
+ assert_se(!r);
+ r = ordered_hashmap_next(NULL, "key 1");
+ assert_se(!r);
+ r = ordered_hashmap_next(m, "key 5");
assert_se(!r);
- hashmap_free_free(m);
-}
-
-static void test_hashmap_update(void) {
- Hashmap *m;
- char *val1, *val2, *r;
-
- m = hashmap_new(&string_hash_ops);
- val1 = strdup("old_value");
- assert_se(val1);
- val2 = strdup("new_value");
- assert_se(val2);
-
- hashmap_put(m, "key 1", val1);
- r = hashmap_get(m, "key 1");
- assert_se(streq(r, "old_value"));
-
- hashmap_update(m, "key 1", val2);
- r = hashmap_get(m, "key 1");
- assert_se(streq(r, "new_value"));
-
- free(val1);
- free(val2);
- hashmap_free(m);
-}
-
-static void test_hashmap_put(void) {
- Hashmap *m;
- int valid_hashmap_put;
-
- m = hashmap_new(&string_hash_ops);
-
- valid_hashmap_put = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
- assert_se(valid_hashmap_put == 1);
-
- assert_se(m);
- hashmap_free(m);
-}
-
-static void test_hashmap_remove_and_put(void) {
- _cleanup_hashmap_free_ Hashmap *m = NULL;
- int valid;
- char *r;
-
- m = hashmap_new(&string_hash_ops);
- assert_se(m);
-
- valid = hashmap_remove_and_put(m, "unvalid key", "new key", NULL);
- assert_se(valid < 0);
-
- valid = hashmap_put(m, "key 1", (void*) (const char *) "val 1");
- assert_se(valid == 1);
- valid = hashmap_remove_and_put(m, "key 1", "key 2", (void*) (const char *) "val 2");
- assert_se(valid == 0);
-
- r = hashmap_get(m, "key 2");
- assert_se(streq(r, "val 2"));
- assert_se(!hashmap_get(m, "key 1"));
-
- valid = hashmap_put(m, "key 3", (void*) (const char *) "val 3");
- assert_se(valid == 1);
- valid = hashmap_remove_and_put(m, "key 3", "key 2", (void*) (const char *) "val 2");
- assert_se(valid < 0);
-}
-
-static void test_hashmap_ensure_allocated(void) {
- Hashmap *m;
- int valid_hashmap;
-
- m = hashmap_new(&string_hash_ops);
-
- valid_hashmap = hashmap_ensure_allocated(&m, &string_hash_ops);
- assert_se(valid_hashmap == 0);
-
- assert_se(m);
- hashmap_free(m);
-}
-
-static void test_hashmap_foreach_key(void) {
- Hashmap *m;
- Iterator i;
- bool key_found[] = { false, false, false, false };
- const char *s;
- const char *key;
- static const char key_table[] =
- "key 1\0"
- "key 2\0"
- "key 3\0"
- "key 4\0";
-
- m = hashmap_new(&string_hash_ops);
-
- NULSTR_FOREACH(key, key_table)
- hashmap_put(m, key, (void*) (const char*) "my dummy val");
-
- HASHMAP_FOREACH_KEY(s, key, m, i) {
- if (!key_found[0] && streq(key, "key 1"))
- key_found[0] = true;
- else if (!key_found[1] && streq(key, "key 2"))
- key_found[1] = true;
- else if (!key_found[2] && streq(key, "key 3"))
- key_found[2] = true;
- else if (!key_found[3] && streq(key, "fail"))
- key_found[3] = true;
- }
-
- assert_se(m);
- assert_se(key_found[0] && key_found[1] && key_found[2] && !key_found[3]);
-
- hashmap_free(m);
-}
-
-static void test_hashmap_foreach(void) {
- Hashmap *m;
- Iterator i;
- bool value_found[] = { false, false, false, false };
- char *val1, *val2, *val3, *val4, *s;
-
- val1 = strdup("my val1");
- assert_se(val1);
- val2 = strdup("my val2");
- assert_se(val2);
- val3 = strdup("my val3");
- assert_se(val3);
- val4 = strdup("my val4");
- assert_se(val4);
-
- m = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "Key 1", val1);
- hashmap_put(m, "Key 2", val2);
- hashmap_put(m, "Key 3", val3);
- hashmap_put(m, "Key 4", val4);
-
- HASHMAP_FOREACH(s, m, i) {
- if (!value_found[0] && streq(s, val1))
- value_found[0] = true;
- else if (!value_found[1] && streq(s, val2))
- value_found[1] = true;
- else if (!value_found[2] && streq(s, val3))
- value_found[2] = true;
- else if (!value_found[3] && streq(s, val4))
- value_found[3] = true;
- }
-
- assert_se(m);
- assert_se(value_found[0] && value_found[1] && value_found[2] && value_found[3]);
-
- hashmap_free_free(m);
-}
-
-static void test_hashmap_merge(void) {
- Hashmap *m;
- Hashmap *n;
- char *val1, *val2, *val3, *val4, *r;
-
- val1 = strdup("my val1");
- assert_se(val1);
- val2 = strdup("my val2");
- assert_se(val2);
- val3 = strdup("my val3");
- assert_se(val3);
- val4 = strdup("my val4");
- assert_se(val4);
-
- n = hashmap_new(&string_hash_ops);
- m = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "Key 1", val1);
- hashmap_put(m, "Key 2", val2);
- hashmap_put(n, "Key 3", val3);
- hashmap_put(n, "Key 4", val4);
-
- assert_se(hashmap_merge(m, n) == 0);
- r = hashmap_get(m, "Key 3");
- assert_se(r && streq(r, "my val3"));
- r = hashmap_get(m, "Key 4");
- assert_se(r && streq(r, "my val4"));
-
- assert_se(n);
- assert_se(m);
- hashmap_free(n);
- hashmap_free_free(m);
-}
-
-static void test_hashmap_contains(void) {
- Hashmap *m;
- char *val1;
-
- val1 = strdup("my val");
- assert_se(val1);
-
- m = hashmap_new(&string_hash_ops);
-
- assert_se(!hashmap_contains(m, "Key 1"));
- hashmap_put(m, "Key 1", val1);
- assert_se(hashmap_contains(m, "Key 1"));
-
- assert_se(m);
- hashmap_free_free(m);
-}
-
-static void test_hashmap_isempty(void) {
- Hashmap *m;
- char *val1;
-
- val1 = strdup("my val");
- assert_se(val1);
-
- m = hashmap_new(&string_hash_ops);
-
- assert_se(hashmap_isempty(m));
- hashmap_put(m, "Key 1", val1);
- assert_se(!hashmap_isempty(m));
-
- assert_se(m);
- hashmap_free_free(m);
-}
-
-static void test_hashmap_size(void) {
- Hashmap *m;
- char *val1, *val2, *val3, *val4;
-
- val1 = strdup("my val");
- assert_se(val1);
- val2 = strdup("my val");
- assert_se(val2);
- val3 = strdup("my val");
- assert_se(val3);
- val4 = strdup("my val");
- assert_se(val4);
-
- m = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "Key 1", val1);
- hashmap_put(m, "Key 2", val2);
- hashmap_put(m, "Key 3", val3);
- hashmap_put(m, "Key 4", val4);
-
- assert_se(m);
- assert_se(hashmap_size(m) == 4);
- hashmap_free_free(m);
-}
-
-static void test_hashmap_get(void) {
- Hashmap *m;
- char *r;
- char *val;
-
- val = strdup("my val");
- assert_se(val);
-
- m = hashmap_new(&string_hash_ops);
-
- hashmap_put(m, "Key 1", val);
-
- r = hashmap_get(m, "Key 1");
- assert_se(streq(r, val));
-
- assert_se(m);
- hashmap_free_free(m);
-}
-
-static void test_hashmap_many(void) {
- Hashmap *h;
- unsigned i;
-
-#define N_ENTRIES 100000
-
- assert_se(h = hashmap_new(NULL));
-
- for (i = 1; i < N_ENTRIES*3; i+=3) {
- assert_se(hashmap_put(h, UINT_TO_PTR(i), UINT_TO_PTR(i)) >= 0);
- assert_se(PTR_TO_UINT(hashmap_get(h, UINT_TO_PTR(i))) == i);
- }
-
- for (i = 1; i < N_ENTRIES*3; i++)
- assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1));
-
- log_info("%u <= %u * 0.75 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.75);
-
- assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.75);
- assert_se(hashmap_size(h) == N_ENTRIES);
-
- hashmap_free(h);
-}
-
-static void test_hashmap_first_key(void) {
- _cleanup_hashmap_free_ Hashmap *m = NULL;
-
- m = hashmap_new(&string_hash_ops);
- assert_se(m);
-
- assert_se(!hashmap_first_key(m));
- assert_se(hashmap_put(m, "key 1", NULL) == 1);
- assert_se(streq(hashmap_first_key(m), "key 1"));
- assert_se(hashmap_put(m, "key 2", NULL) == 1);
- assert_se(streq(hashmap_first_key(m), "key 1"));
- assert_se(hashmap_remove(m, "key 1") == NULL);
- assert_se(streq(hashmap_first_key(m), "key 2"));
-}
-
-static void test_hashmap_steal_first_key(void) {
- _cleanup_hashmap_free_ Hashmap *m = NULL;
-
- m = hashmap_new(&string_hash_ops);
- assert_se(m);
-
- assert_se(!hashmap_steal_first_key(m));
- assert_se(hashmap_put(m, "key 1", NULL) == 1);
- assert_se(streq(hashmap_steal_first_key(m), "key 1"));
-
- assert_se(hashmap_isempty(m));
-}
-
-static void test_hashmap_steal_first(void) {
- _cleanup_hashmap_free_ Hashmap *m = NULL;
- int seen[3] = {};
- char *val;
-
- m = hashmap_new(&string_hash_ops);
- assert_se(m);
-
- assert_se(hashmap_put(m, "key 1", (void*) "1") == 1);
- assert_se(hashmap_put(m, "key 2", (void*) "22") == 1);
- assert_se(hashmap_put(m, "key 3", (void*) "333") == 1);
-
- while ((val = hashmap_steal_first(m)))
- seen[strlen(val) - 1]++;
-
- assert_se(seen[0] == 1 && seen[1] == 1 && seen[2] == 1);
-
- assert_se(hashmap_isempty(m));
-}
-
-static void test_hashmap_clear_free_free(void) {
- _cleanup_hashmap_free_ Hashmap *m = NULL;
-
- m = hashmap_new(&string_hash_ops);
- assert_se(m);
-
- assert_se(hashmap_put(m, strdup("key 1"), NULL) == 1);
- assert_se(hashmap_put(m, strdup("key 2"), NULL) == 1);
- assert_se(hashmap_put(m, strdup("key 3"), NULL) == 1);
-
- hashmap_clear_free_free(m);
- assert_se(hashmap_isempty(m));
+ ordered_hashmap_free_free(m);
}
static void test_uint64_compare_func(void) {
@@ -561,27 +80,10 @@ static void test_string_compare_func(void) {
}
int main(int argc, const char *argv[]) {
- test_hashmap_copy();
- test_hashmap_get_strv();
- test_hashmap_move_one();
- test_hashmap_next();
- test_hashmap_replace();
- test_hashmap_update();
- test_hashmap_put();
- test_hashmap_remove_and_put();
- test_hashmap_ensure_allocated();
- test_hashmap_foreach();
- test_hashmap_foreach_key();
- test_hashmap_contains();
- test_hashmap_merge();
- test_hashmap_isempty();
- test_hashmap_get();
- test_hashmap_size();
- test_hashmap_many();
- test_hashmap_first_key();
- test_hashmap_steal_first_key();
- test_hashmap_steal_first();
- test_hashmap_clear_free_free();
+ test_hashmap_funcs();
+ test_ordered_hashmap_funcs();
+
+ test_ordered_hashmap_next();
test_uint64_compare_func();
test_trivial_compare_func();
test_string_compare_func();
commit 5ba43716f345e205eba33156c0171fb657f4451f
Author: Michal Schmidt <mschmidt at redhat.com>
Date: Mon Oct 13 18:11:16 2014 +0200
hashmap: add OrderedHashmap as a distinct type
Few Hashmaps/Sets need to remember the insertion order. Most don't care
about the order when iterating. It would be possible to use more compact
hashmap storage in the latter cases.
Add OrderedHashmap as a distinct type from Hashmap, with functions
prefixed with "ordered_". For now, the functions are nothing more than
inline wrappers for plain Hashmap functions.
diff --git a/src/shared/hashmap.h b/src/shared/hashmap.h
index e25840f..9789ad7 100644
--- a/src/shared/hashmap.h
+++ b/src/shared/hashmap.h
@@ -34,6 +34,7 @@
#define HASH_KEY_SIZE 16
typedef struct Hashmap Hashmap;
+typedef struct OrderedHashmap OrderedHashmap;
typedef struct _IteratorStruct _IteratorStruct;
typedef _IteratorStruct* Iterator;
@@ -82,56 +83,171 @@ extern const struct hash_ops devt_hash_ops = {
#endif
Hashmap *hashmap_new(const struct hash_ops *hash_ops);
+static inline OrderedHashmap *ordered_hashmap_new(const struct hash_ops *hash_ops) {
+ return (OrderedHashmap*) hashmap_new(hash_ops);
+}
void hashmap_free(Hashmap *h);
+static inline void ordered_hashmap_free(OrderedHashmap *h) {
+ hashmap_free((Hashmap*) h);
+}
void hashmap_free_free(Hashmap *h);
+static inline void ordered_hashmap_free_free(OrderedHashmap *h) {
+ hashmap_free_free((Hashmap*) h);
+}
void hashmap_free_free_free(Hashmap *h);
+static inline void ordered_hashmap_free_free_free(OrderedHashmap *h) {
+ hashmap_free_free_free((Hashmap*) h);
+}
Hashmap *hashmap_copy(Hashmap *h);
+static inline OrderedHashmap *ordered_hashmap_copy(OrderedHashmap *h) {
+ return (OrderedHashmap*) hashmap_copy((Hashmap*) h);
+}
int hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops);
+static inline int ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops) {
+ return hashmap_ensure_allocated((Hashmap**) h, hash_ops);
+}
int hashmap_put(Hashmap *h, const void *key, void *value);
+static inline int ordered_hashmap_put(OrderedHashmap *h, const void *key, void *value) {
+ return hashmap_put((Hashmap*) h, key, value);
+}
int hashmap_update(Hashmap *h, const void *key, void *value);
+static inline int ordered_hashmap_update(OrderedHashmap *h, const void *key, void *value) {
+ return hashmap_update((Hashmap*) h, key, value);
+}
int hashmap_replace(Hashmap *h, const void *key, void *value);
+static inline int ordered_hashmap_replace(OrderedHashmap *h, const void *key, void *value) {
+ return hashmap_replace((Hashmap*) h, key, value);
+}
void *hashmap_get(Hashmap *h, const void *key);
+static inline void *ordered_hashmap_get(OrderedHashmap *h, const void *key) {
+ return hashmap_get((Hashmap*) h, key);
+}
void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
+static inline void *ordered_hashmap_get2(OrderedHashmap *h, const void *key, void **rkey) {
+ return hashmap_get2((Hashmap*) h, key, rkey);
+}
bool hashmap_contains(Hashmap *h, const void *key);
+static inline bool ordered_hashmap_contains(OrderedHashmap *h, const void *key) {
+ return hashmap_contains((Hashmap*) h, key);
+}
void *hashmap_remove(Hashmap *h, const void *key);
+static inline void *ordered_hashmap_remove(OrderedHashmap *h, const void *key) {
+ return hashmap_remove((Hashmap*) h, key);
+}
void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
+static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, void **rkey) {
+ return hashmap_remove2((Hashmap*) h, key, rkey);
+}
void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
+static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) {
+ return hashmap_remove_value((Hashmap*) h, key, value);
+}
int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
+static inline int ordered_hashmap_remove_and_put(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
+ return hashmap_remove_and_put((Hashmap*) h, old_key, new_key, value);
+}
int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
+static inline int ordered_hashmap_remove_and_replace(OrderedHashmap *h, const void *old_key, const void *new_key, void *value) {
+ return hashmap_remove_and_replace((Hashmap*) h, old_key, new_key, value);
+}
int hashmap_merge(Hashmap *h, Hashmap *other);
+static inline int ordered_hashmap_merge(OrderedHashmap *h, OrderedHashmap *other) {
+ return hashmap_merge((Hashmap*) h, (Hashmap*) other);
+}
void hashmap_move(Hashmap *h, Hashmap *other);
+static inline void ordered_hashmap_move(OrderedHashmap *h, OrderedHashmap *other) {
+ hashmap_move((Hashmap*) h, (Hashmap*) other);
+}
int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);
+static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
+ return hashmap_move_one((Hashmap*) h, (Hashmap*) other, key);
+}
unsigned hashmap_size(Hashmap *h) _pure_;
+static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
+ return hashmap_size((Hashmap*) h);
+}
bool hashmap_isempty(Hashmap *h) _pure_;
+static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
+ return hashmap_isempty((Hashmap*) h);
+}
unsigned hashmap_buckets(Hashmap *h) _pure_;
+static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
+ return hashmap_buckets((Hashmap*) h);
+}
void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key);
+static inline void *ordered_hashmap_iterate(OrderedHashmap *h, Iterator *i, const void **key) {
+ return hashmap_iterate((Hashmap*) h, i, key);
+}
void hashmap_clear(Hashmap *h);
+static inline void ordered_hashmap_clear(OrderedHashmap *h) {
+ hashmap_clear((Hashmap*) h);
+}
void hashmap_clear_free(Hashmap *h);
+static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
+ hashmap_clear_free((Hashmap*) h);
+}
void hashmap_clear_free_free(Hashmap *h);
+static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
+ hashmap_clear_free_free((Hashmap*) h);
+}
void *hashmap_steal_first(Hashmap *h);
+static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
+ return hashmap_steal_first((Hashmap*) h);
+}
void *hashmap_steal_first_key(Hashmap *h);
+static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
+ return hashmap_steal_first_key((Hashmap*) h);
+}
void *hashmap_first(Hashmap *h) _pure_;
+static inline void *ordered_hashmap_first(OrderedHashmap *h) {
+ return hashmap_first((Hashmap*) h);
+}
void *hashmap_first_key(Hashmap *h) _pure_;
+static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
+ return hashmap_first_key((Hashmap*) h);
+}
void *hashmap_next(Hashmap *h, const void *key);
+static inline void *ordered_hashmap_next(OrderedHashmap *h, const void *key) {
+ return hashmap_next((Hashmap*) h, key);
+}
char **hashmap_get_strv(Hashmap *h);
+static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
+ return hashmap_get_strv((Hashmap*) h);
+}
#define HASHMAP_FOREACH(e, h, i) \
for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); (e); (e) = hashmap_iterate((h), &(i), NULL))
+#define ORDERED_HASHMAP_FOREACH(e, h, i) \
+ for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), NULL); \
+ (e); \
+ (e) = ordered_hashmap_iterate((h), &(i), NULL))
+
#define HASHMAP_FOREACH_KEY(e, k, h, i) \
for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); (e); (e) = hashmap_iterate((h), &(i), (const void**) &(k)))
+#define ORDERED_HASHMAP_FOREACH_KEY(e, k, h, i) \
+ for ((i) = ITERATOR_FIRST, (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)); \
+ (e); \
+ (e) = ordered_hashmap_iterate((h), &(i), (const void**) &(k)))
+
DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
+DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free);
+DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free);
+DEFINE_TRIVIAL_CLEANUP_FUNC(OrderedHashmap*, ordered_hashmap_free_free_free);
#define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
#define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
#define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)
+#define _cleanup_ordered_hashmap_free_ _cleanup_(ordered_hashmap_freep)
+#define _cleanup_ordered_hashmap_free_free_ _cleanup_(ordered_hashmap_free_freep)
+#define _cleanup_ordered_hashmap_free_free_free_ _cleanup_(ordered_hashmap_free_free_freep)
More information about the systemd-commits
mailing list