along with systemd; If not, see <http://www.gnu.org/licenses/>.
***/
-#include <assert.h>
#include <stdlib.h>
-#include <string.h>
#include <errno.h>
#include "util.h"
#include "macro.h"
#include "siphash24.h"
#include "strv.h"
-#include "list.h"
#include "mempool.h"
+#include "random-util.h"
+
+#ifdef ENABLE_DEBUG_HASHMAP
+#include "list.h"
+#endif
/*
* Implementation of hashmaps.
/* Distance from Initial Bucket */
typedef uint8_t dib_raw_t;
-#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
-#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
-#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
-#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
+#define DIB_RAW_OVERFLOW ((dib_raw_t)0xfdU) /* indicates DIB value is greater than representable */
+#define DIB_RAW_REHASH ((dib_raw_t)0xfeU) /* entry yet to be rehashed during in-place resize */
+#define DIB_RAW_FREE ((dib_raw_t)0xffU) /* a free bucket */
+#define DIB_RAW_INIT ((char)DIB_RAW_FREE) /* a byte to memset a DIB store with when initializing */
#define DIB_FREE UINT_MAX
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
struct hashmap_debug_info {
LIST_FIELDS(struct hashmap_debug_info, debug_list);
unsigned max_entries; /* high watermark of n_entries */
#define HASHMAP_DEBUG_FIELDS struct hashmap_debug_info debug;
-#else /* !ENABLE_HASHMAP_DEBUG */
+#else /* !ENABLE_DEBUG_HASHMAP */
#define HASHMAP_DEBUG_FIELDS
-#endif /* ENABLE_HASHMAP_DEBUG */
+#endif /* ENABLE_DEBUG_HASHMAP */
enum HashmapType {
HASHMAP_TYPE_PLAIN,
}
static void bucket_mark_free(HashmapBase *h, unsigned idx) {
- memset(bucket_at(h, idx), 0, hashmap_type_info[h->type].entry_size);
+ memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
bucket_set_dib(h, idx, DIB_FREE);
}
dibs = dib_raw_ptr(h);
assert(dibs[idx] != DIB_RAW_FREE);
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
h->debug.rem_count++;
h->debug.last_rem_idx = idx;
#endif
assert(e->p.b.key == i->next_key);
}
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
i->prev_idx = idx;
#endif
}
idx = i->idx;
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
i->prev_idx = idx;
#endif
return IDX_NIL;
}
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
if (i->idx == IDX_FIRST) {
i->put_count = h->debug.put_count;
i->rem_count = h->debug.rem_count;
: hashmap_iterate_in_internal_order(h, i);
}
-void *internal_hashmap_iterate(HashmapBase *h, Iterator *i, const void **key) {
+bool internal_hashmap_iterate(HashmapBase *h, Iterator *i, void **value, const void **key) {
struct hashmap_base_entry *e;
void *data;
unsigned idx;
idx = hashmap_iterate_entry(h, i);
if (idx == IDX_NIL) {
+ if (value)
+ *value = NULL;
if (key)
*key = NULL;
- return NULL;
+ return false;
}
e = bucket_at(h, idx);
data = entry_value(h, e);
+ if (value)
+ *value = data;
if (key)
*key = e->key;
- return data;
+ return true;
}
-void *set_iterate(Set *s, Iterator *i) {
- return internal_hashmap_iterate(HASHMAP_BASE(s), i, NULL);
+bool set_iterate(Set *s, Iterator *i, void **value) {
+ return internal_hashmap_iterate(HASHMAP_BASE(s), i, value, NULL);
}
#define HASHMAP_FOREACH_IDX(idx, h, i) \
memset(p, DIB_RAW_INIT, sizeof(dib_raw_t) * hi->n_direct_buckets);
}
-static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {
+static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enum HashmapType type HASHMAP_DEBUG_PARAMS) {
HashmapBase *h;
const struct hashmap_type_info *hi = &hashmap_type_info[type];
bool use_pool;
shared_hash_key_initialized= true;
}
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
LIST_PREPEND(debug_list, hashmap_debug_list, &h->debug);
h->debug.func = func;
h->debug.file = file;
}
Hashmap *internal_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
- return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
+ return (Hashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
}
OrderedHashmap *internal_ordered_hashmap_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
- return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
+ return (OrderedHashmap*) hashmap_base_new(hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
}
Set *internal_set_new(const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
- return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
+ return (Set*) hashmap_base_new(hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
}
static int hashmap_base_ensure_allocated(HashmapBase **h, const struct hash_ops *hash_ops,
- enum HashmapType type HASHMAP_DEBUG_PARAMS) {
+ enum HashmapType type HASHMAP_DEBUG_PARAMS) {
HashmapBase *q;
assert(h);
if (*h)
return 0;
- q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);
+ q = hashmap_base_new(hash_ops, type HASHMAP_DEBUG_PASS_ARGS);
if (!q)
return -ENOMEM;
}
int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
- return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
+ return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_PLAIN HASHMAP_DEBUG_PASS_ARGS);
}
int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
- return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
+ return hashmap_base_ensure_allocated((HashmapBase**)h, hash_ops, HASHMAP_TYPE_ORDERED HASHMAP_DEBUG_PASS_ARGS);
}
int internal_set_ensure_allocated(Set **s, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS) {
- return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
+ return hashmap_base_ensure_allocated((HashmapBase**)s, hash_ops, HASHMAP_TYPE_SET HASHMAP_DEBUG_PASS_ARGS);
}
static void hashmap_free_no_clear(HashmapBase *h) {
assert(!h->has_indirect);
assert(!h->n_direct_entries);
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
LIST_REMOVE(debug_list, hashmap_debug_list, &h->debug);
#endif
free(h);
}
-void internal_hashmap_free(HashmapBase *h) {
+HashmapBase *internal_hashmap_free(HashmapBase *h) {
/* Free the hashmap, but nothing in it */
- if (!h)
- return;
+ if (h) {
+ internal_hashmap_clear(h);
+ hashmap_free_no_clear(h);
+ }
- internal_hashmap_clear(h);
- hashmap_free_no_clear(h);
+ return NULL;
}
-void internal_hashmap_free_free(HashmapBase *h) {
+HashmapBase *internal_hashmap_free_free(HashmapBase *h) {
/* Free the hashmap and all data objects in it, but not the
* keys */
- if (!h)
- return;
+ if (h) {
+ internal_hashmap_clear_free(h);
+ hashmap_free_no_clear(h);
+ }
- internal_hashmap_clear_free(h);
- hashmap_free_no_clear(h);
+ return NULL;
}
-void hashmap_free_free_free(Hashmap *h) {
+Hashmap *hashmap_free_free_free(Hashmap *h) {
/* Free the hashmap and all data and key objects in it */
- if (!h)
- return;
+ if (h) {
+ hashmap_clear_free_free(h);
+ hashmap_free_no_clear(HASHMAP_BASE(h));
+ }
- hashmap_clear_free_free(h);
- hashmap_free_no_clear(HASHMAP_BASE(h));
+ return NULL;
}
void internal_hashmap_clear(HashmapBase *h) {
dib_raw_t raw_dib, *dibs;
unsigned dib, distance;
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
h->debug.put_count++;
#endif
if (dib < distance) {
/* Found a wealthier entry. Go Robin Hood! */
-
bucket_set_dib(h, idx, distance);
/* swap the entries */
assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
n_entries_inc(h);
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
#endif
/*
* Returns 0 if resize is not needed.
- * 1 if succesfully resized.
+ * 1 if successfully resized.
* -ENOMEM on allocation failure.
*/
static int resize_buckets(HashmapBase *h, unsigned entries_add) {
}
/* Zero the area of newly added entries (including the old DIB area) */
- memset(bucket_at(h, old_n_buckets), 0,
+ memzero(bucket_at(h, old_n_buckets),
(n_buckets(h) - old_n_buckets) * hi->entry_size);
/* The upper half of the new DIB array needs initialization */
new_dibs[idx] = DIB_RAW_FREE;
bucket_move_entry(h, &swap, idx, IDX_PUT);
/* bucket_move_entry does not clear the source */
- memset(bucket_at(h, idx), 0, hi->entry_size);
+ memzero(bucket_at(h, idx), hi->entry_size);
do {
/*
idx = bucket_scan(h, hash, key);
if (idx != IDX_NIL) {
e = plain_bucket_at(h, idx);
-#ifdef ENABLE_HASHMAP_DEBUG
+#ifdef ENABLE_DEBUG_HASHMAP
/* Although the key is equal, the key pointer may have changed,
* and this would break our assumption for iterating. So count
* this operation as incompatible with iteration. */
int r;
r = set_put(s, value);
- if (r < 0)
+ if (r <= 0)
free(value);
return r;
~ianmdlvl / elogind.git / blobdiff