summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--hashmap.c146
-rw-r--r--hashmap.h3
-rw-r--r--set.c12
-rw-r--r--set.h3
4 files changed, 137 insertions, 27 deletions
diff --git a/hashmap.c b/hashmap.c
index 28256bd353..2102db8b26 100644
--- a/hashmap.c
+++ b/hashmap.c
@@ -96,7 +96,34 @@ int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t
return 0;
}
-static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
+static void link_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
+ assert(h);
+ assert(e);
+
+ /* Insert into hash table */
+ e->bucket_next = BY_HASH(h)[hash];
+ e->bucket_previous = NULL;
+ if (BY_HASH(h)[hash])
+ BY_HASH(h)[hash]->bucket_previous = e;
+ BY_HASH(h)[hash] = e;
+
+ /* Insert into iteration list */
+ e->iterate_previous = h->iterate_list_tail;
+ e->iterate_next = NULL;
+ if (h->iterate_list_tail) {
+ assert(h->iterate_list_head);
+ h->iterate_list_tail->iterate_next = e;
+ } else {
+ assert(!h->iterate_list_head);
+ h->iterate_list_head = e;
+ }
+ h->iterate_list_tail = e;
+
+ h->n_entries++;
+ assert(h->n_entries >= 1);
+}
+
+static void unlink_entry(Hashmap *h, struct hashmap_entry *e, unsigned hash) {
assert(h);
assert(e);
@@ -117,17 +144,25 @@ static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
if (e->bucket_previous)
e->bucket_previous->bucket_next = e->bucket_next;
- else {
- unsigned hash = h->hash_func(e->key) % NBUCKETS;
+ else
BY_HASH(h)[hash] = e->bucket_next;
- }
-
- free(e);
assert(h->n_entries >= 1);
h->n_entries--;
}
+static void remove_entry(Hashmap *h, struct hashmap_entry *e) {
+ unsigned hash;
+
+ assert(h);
+ assert(e);
+
+ hash = h->hash_func(e->key) % NBUCKETS;
+
+ unlink_entry(h, e, hash);
+ free(e);
+}
+
void hashmap_free(Hashmap*h) {
if (!h)
@@ -180,27 +215,7 @@ int hashmap_put(Hashmap *h, const void *key, void *value) {
e->key = key;
e->value = value;
- /* Insert into hash table */
- e->bucket_next = BY_HASH(h)[hash];
- e->bucket_previous = NULL;
- if (BY_HASH(h)[hash])
- BY_HASH(h)[hash]->bucket_previous = e;
- BY_HASH(h)[hash] = e;
-
- /* Insert into iteration list */
- e->iterate_previous = h->iterate_list_tail;
- e->iterate_next = NULL;
- if (h->iterate_list_tail) {
- assert(h->iterate_list_head);
- h->iterate_list_tail->iterate_next = e;
- } else {
- assert(!h->iterate_list_head);
- h->iterate_list_head = e;
- }
- h->iterate_list_tail = e;
-
- h->n_entries++;
- assert(h->n_entries >= 1);
+ link_entry(h, e, hash);
return 0;
}
@@ -214,6 +229,7 @@ int hashmap_replace(Hashmap *h, const void *key, void *value) {
hash = h->hash_func(key) % NBUCKETS;
if ((e = hash_scan(h, hash, key))) {
+ e->key = key;
e->value = value;
return 0;
}
@@ -255,6 +271,31 @@ void* hashmap_remove(Hashmap *h, const void *key) {
return data;
}
+int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
+ struct hashmap_entry *e;
+ unsigned old_hash, new_hash;
+
+ if (!h)
+ return -ENOENT;
+
+ old_hash = h->hash_func(old_key) % NBUCKETS;
+ if (!(e = hash_scan(h, old_hash, old_key)))
+ return -ENOENT;
+
+ new_hash = h->hash_func(new_key) % NBUCKETS;
+ if (hash_scan(h, new_hash, new_key))
+ return -EEXIST;
+
+ unlink_entry(h, e, old_hash);
+
+ e->key = new_key;
+ e->value = value;
+
+ link_entry(h, e, new_hash);
+
+ return 0;
+}
+
void* hashmap_remove_value(Hashmap *h, const void *key, void *value) {
struct hashmap_entry *e;
unsigned hash;
@@ -434,6 +475,57 @@ int hashmap_merge(Hashmap *h, Hashmap *other) {
return 0;
}
+void 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. */
+
+ if (!other)
+ return;
+
+ for (e = other->iterate_list_head; e; e = n) {
+ unsigned h_hash, other_hash;
+
+ n = e->iterate_next;
+
+ h_hash = h->hash_func(e->key) % NBUCKETS;
+
+ if (hash_scan(h, h_hash, e->key))
+ continue;
+
+ other_hash = other->hash_func(e->key) % NBUCKETS;
+
+ unlink_entry(other, e, other_hash);
+ link_entry(h, e, h_hash);
+ }
+}
+
+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 = h->hash_func(key) % NBUCKETS;
+ if (hash_scan(h, h_hash, key))
+ return -EEXIST;
+
+ other_hash = other->hash_func(key) % NBUCKETS;
+ if (!(e = hash_scan(other, other_hash, key)))
+ return -ENOENT;
+
+ unlink_entry(other, e, other_hash);
+ link_entry(h, e, h_hash);
+
+ return 0;
+}
+
Hashmap *hashmap_copy(Hashmap *h) {
Hashmap *copy;
diff --git a/hashmap.h b/hashmap.h
index bd57bca24a..9cdd7016bc 100644
--- a/hashmap.h
+++ b/hashmap.h
@@ -55,8 +55,11 @@ int hashmap_replace(Hashmap *h, const void *key, void *value);
void* hashmap_get(Hashmap *h, const void *key);
void* hashmap_remove(Hashmap *h, const void *key);
void* hashmap_remove_value(Hashmap *h, const void *key, void *value);
+int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
int hashmap_merge(Hashmap *h, Hashmap *other);
+void hashmap_move(Hashmap *h, Hashmap *other);
+int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);
unsigned hashmap_size(Hashmap *h);
bool hashmap_isempty(Hashmap *h);
diff --git a/set.c b/set.c
index 708f12a947..efd20db536 100644
--- a/set.c
+++ b/set.c
@@ -57,6 +57,10 @@ void *set_remove(Set *s, void *value) {
return hashmap_remove(MAKE_HASHMAP(s), value);
}
+int set_remove_and_put(Set *s, void *old_value, void *new_value) {
+ return hashmap_remove_and_put(MAKE_HASHMAP(s), old_value, new_value, new_value);
+}
+
unsigned set_size(Set *s) {
return hashmap_size(MAKE_HASHMAP(s));
}
@@ -93,6 +97,14 @@ int set_merge(Set *s, Set *other) {
return hashmap_merge(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
}
+void set_move(Set *s, Set *other) {
+ return hashmap_move(MAKE_HASHMAP(s), MAKE_HASHMAP(other));
+}
+
+int set_move_one(Set *s, Set *other, void *value) {
+ return hashmap_move_one(MAKE_HASHMAP(s), MAKE_HASHMAP(other), value);
+}
+
Set* set_copy(Set *s) {
return MAKE_SET(hashmap_copy(MAKE_HASHMAP(s)));
}
diff --git a/set.h b/set.h
index b0f2242c88..dd2e91dd11 100644
--- a/set.h
+++ b/set.h
@@ -41,8 +41,11 @@ int set_put(Set *s, void *value);
int set_replace(Set *s, void *value);
void *set_get(Set *s, void *value);
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);
+void set_move(Set *s, Set *other);
+int set_move_one(Set *s, Set *other, void *value);
unsigned set_size(Set *s);
bool set_isempty(Set *s);
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-11-07 17:32:52 +0000