HALF ECHO LEARN / REFERENCE COLLECTION

v262.2

src/basic/hashmap.c

69,795 bytesGit mode 100644Download original fileLGPL-2.1-or-later

Git blob: 89517b99f724167eeb42f77e7647a8d9c851797f

Lines 1001–2000 of 2,264

#if ENABLE_DEBUG_HASHMAP
        assert(h);
        h->debug.put_count++;
#endif
 
        dibs = dib_raw_ptr(h);
 
        for (distance = 0; ; distance++) {
                raw_dib = dibs[idx];
                if (IN_SET(raw_dib, DIB_RAW_FREE, DIB_RAW_REHASH)) {
                        if (raw_dib == DIB_RAW_REHASH)
                                bucket_move_entry(h, swap, idx, IDX_TMP);
 
                        if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
                                h->indirect.idx_lowest_entry = idx;
 
                        bucket_set_dib(h, idx, distance);
                        bucket_move_entry(h, swap, IDX_PUT, idx);
                        if (raw_dib == DIB_RAW_REHASH) {
                                bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
                                return true;
                        }
 
                        return false;
                }
 
                dib = bucket_calculate_dib(h, idx, raw_dib);
 
                if (dib < distance) {
                        /* Found a wealthier entry. Go Robin Hood! */
                        bucket_set_dib(h, idx, distance);
 
                        /* swap the entries */
                        bucket_move_entry(h, swap, idx, IDX_TMP);
                        bucket_move_entry(h, swap, IDX_PUT, idx);
                        bucket_move_entry(h, swap, IDX_TMP, IDX_PUT);
 
                        distance = dib;
                }
 
                idx = next_idx(h, idx);
        }
}
 
/*
 * Puts an entry into a hashmap, boldly - no check whether key already exists.
 * The caller must place the entry (only its key and value, not link indexes)
 * in swap slot IDX_PUT.
 * Caller must ensure: the key does not exist yet in the hashmap.
 *                     that resize is not needed if !may_resize.
 * Returns: 1 if entry was put successfully.
 *          -ENOMEM if may_resize==true and resize failed with -ENOMEM.
 *          Cannot return -ENOMEM if !may_resize.
 */
static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
                                   struct swap_entries *swap, bool may_resize) {
        struct ordered_hashmap_entry *new_entry;
        int r;
 
        assert(idx < n_buckets(h));
 
        new_entry = bucket_at_swap(swap, IDX_PUT);
 
        if (may_resize) {
                r = resize_buckets(h, 1);
                if (r < 0)
                        return r;
                if (r > 0)
                        idx = bucket_hash(h, new_entry->p.b.key);
        }
        assert(n_entries(h) < n_buckets(h));
 
        if (h->type == HASHMAP_TYPE_ORDERED) {
                OrderedHashmap *lh = (OrderedHashmap*) h;
 
                new_entry->iterate_next = IDX_NIL;
                new_entry->iterate_previous = lh->iterate_list_tail;
 
                if (lh->iterate_list_tail != IDX_NIL) {
                        struct ordered_hashmap_entry *old_tail;
 
                        old_tail = ordered_bucket_at(lh, lh->iterate_list_tail);
                        assert(old_tail->iterate_next == IDX_NIL);
                        old_tail->iterate_next = IDX_PUT;
                }
 
                lh->iterate_list_tail = IDX_PUT;
                if (lh->iterate_list_head == IDX_NIL)
                        lh->iterate_list_head = IDX_PUT;
        }
 
        assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
 
        n_entries_inc(h);
#if ENABLE_DEBUG_HASHMAP
        h->debug.max_entries = MAX(h->debug.max_entries, n_entries(h));
#endif
 
        base_set_dirty(h);
 
        return 1;
}
#define hashmap_put_boldly(h, idx, swap, may_resize) \
        hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
 
/*
 * Returns 0 if resize is not needed.
 *         1 if successfully resized.
 *         -ENOMEM on allocation failure.
 */
static int resize_buckets(HashmapBase *h, unsigned entries_add) {
        struct swap_entries swap;
        void *new_storage;
        dib_raw_t *old_dibs, *new_dibs;
        const struct hashmap_type_info *hi;
        unsigned idx, optimal_idx;
        unsigned old_n_buckets, new_n_buckets, n_rehashed, new_n_entries;
        uint8_t new_shift;
        bool rehash_next;
 
        assert(h);
 
        hi = &hashmap_type_info[h->type];
        new_n_entries = n_entries(h) + entries_add;
 
        /* overflow? */
        if (_unlikely_(new_n_entries < entries_add))
                return -ENOMEM;
 
        /* For direct storage we allow 100% load, because it's tiny. */
        if (!h->has_indirect && new_n_entries <= hi->n_direct_buckets)
                return 0;
 
        /*
         * Load factor = n/m = 1 - (1/INV_KEEP_FREE).
         * From it follows: m = n + n/(INV_KEEP_FREE - 1)
         */
        new_n_buckets = new_n_entries + new_n_entries / (INV_KEEP_FREE - 1);
        /* overflow? */
        if (_unlikely_(new_n_buckets < new_n_entries))
                return -ENOMEM;
 
        if (_unlikely_(new_n_buckets > UINT_MAX / (hi->entry_size + sizeof(dib_raw_t))))
                return -ENOMEM;
 
        old_n_buckets = n_buckets(h);
 
        if (_likely_(new_n_buckets <= old_n_buckets))
                return 0;
 
        new_shift = log2u_round_up(MAX(
                        new_n_buckets * (hi->entry_size + sizeof(dib_raw_t)),
                        2 * sizeof(struct direct_storage)));
 
        /* Realloc storage (buckets and DIB array). */
        new_storage = realloc(h->has_indirect ? h->indirect.storage : NULL,
                              1U << new_shift);
        if (!new_storage)
                return -ENOMEM;
 
        /* Must upgrade direct to indirect storage. */
        if (!h->has_indirect) {
                memcpy(new_storage, h->direct.storage,
                       old_n_buckets * (hi->entry_size + sizeof(dib_raw_t)));
                h->indirect.n_entries = h->n_direct_entries;
                h->indirect.idx_lowest_entry = 0;
                h->n_direct_entries = 0;
        }
 
        /* Get a new hash key. If we've just upgraded to indirect storage,
         * allow reusing a previously generated key. It's still a different key
         * from the shared one that we used for direct storage. */
        get_hash_key(h->indirect.hash_key, !h->has_indirect);
 
        h->has_indirect = true;
        h->indirect.storage = new_storage;
        h->indirect.n_buckets = (1U << new_shift) /
                                (hi->entry_size + sizeof(dib_raw_t));
 
        old_dibs = (dib_raw_t*)((uint8_t*) new_storage + hi->entry_size * old_n_buckets);
        new_dibs = dib_raw_ptr(h);
 
        /*
         * Move the DIB array to the new place, replacing valid DIB values with
         * DIB_RAW_REHASH to indicate all of the used buckets need rehashing.
         * Note: Overlap is not possible, because we have at least doubled the
         * number of buckets and dib_raw_t is smaller than any entry type.
         */
        for (idx = 0; idx < old_n_buckets; idx++) {
                assert(old_dibs[idx] != DIB_RAW_REHASH);
                new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
                                                              : DIB_RAW_REHASH;
        }
 
        /* Zero the area of newly added entries (including the old DIB area) */
        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 */
        memset(&new_dibs[old_n_buckets], DIB_RAW_INIT,
               (n_buckets(h) - old_n_buckets) * sizeof(dib_raw_t));
 
        /* Rehash entries that need it */
        n_rehashed = 0;
        for (idx = 0; idx < old_n_buckets; idx++) {
                if (new_dibs[idx] != DIB_RAW_REHASH)
                        continue;
 
                optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
 
                /*
                 * Not much to do if by luck the entry hashes to its current
                 * location. Just set its DIB.
                 */
                if (optimal_idx == idx) {
                        new_dibs[idx] = 0;
                        n_rehashed++;
                        continue;
                }
 
                new_dibs[idx] = DIB_RAW_FREE;
                bucket_move_entry(h, &swap, idx, IDX_PUT);
                /* bucket_move_entry does not clear the source */
                memzero(bucket_at(h, idx), hi->entry_size);
 
                do {
                        /*
                         * Find the new bucket for the current entry. This may make
                         * another entry homeless and load it into IDX_PUT.
                         */
                        rehash_next = hashmap_put_robin_hood(h, optimal_idx, &swap);
                        n_rehashed++;
 
                        /* Did the current entry displace another one? */
                        if (rehash_next)
                                optimal_idx = bucket_hash(h, bucket_at_swap(&swap, IDX_PUT)->p.b.key);
                } while (rehash_next);
        }
 
        assert_se(n_rehashed == n_entries(h));
 
        return 1;
}
 
/*
 * Finds an entry with a matching key
 * Returns: index of the found entry, or IDX_NIL if not found.
 */
static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
        struct hashmap_base_entry *e;
        unsigned dib, distance;
        dib_raw_t *dibs = dib_raw_ptr(h);
 
        assert(idx < n_buckets(h));
 
        for (distance = 0; ; distance++) {
                if (dibs[idx] == DIB_RAW_FREE)
                        return IDX_NIL;
 
                dib = bucket_calculate_dib(h, idx, dibs[idx]);
 
                if (dib < distance)
                        return IDX_NIL;
                if (dib == distance) {
                        e = bucket_at(h, idx);
                        if (h->hash_ops->compare(e->key, key) == 0)
                                return idx;
                }
 
                idx = next_idx(h, idx);
        }
}
#define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
 
int hashmap_put(Hashmap *h, const void *key, void *value) {
        struct swap_entries swap;
        struct plain_hashmap_entry *e;
        unsigned hash, idx;
 
        assert(h);
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx != IDX_NIL) {
                e = plain_bucket_at(h, idx);
                if (e->value == value)
                        return 0;
                return -EEXIST;
        }
 
        e = &bucket_at_swap(&swap, IDX_PUT)->p;
        e->b.key = key;
        e->value = value;
        return hashmap_put_boldly(h, hash, &swap, true);
}
 
int set_put(Set *s, const void *key) {
        struct swap_entries swap;
        struct hashmap_base_entry *e;
        unsigned hash, idx;
 
        assert(s);
 
        hash = bucket_hash(s, key);
        idx = bucket_scan(s, hash, key);
        if (idx != IDX_NIL)
                return 0;
 
        e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
        e->key = key;
        return hashmap_put_boldly(s, hash, &swap, true);
}
 
int set_ensure_put(Set **s, const struct hash_ops *hash_ops, const void *key) {
        int r;
 
        assert(s);
 
        r = set_ensure_allocated(s, hash_ops);
        if (r < 0)
                return r;
 
        return set_put(*s, key);
}
 
int set_ensure_consume(Set **s, const struct hash_ops *hash_ops, void *key) {
        int r;
 
        r = set_ensure_put(s, hash_ops, key);
        if (r <= 0) {
                if (hash_ops && hash_ops->free_key)
                        hash_ops->free_key(key);
                else if (hash_ops && hash_ops->free_value)
                        /* Sets store their element in the key slot but may carry a value destructor. */
                        hash_ops->free_value(key);
                else
                        free(key);
        }
 
        return r;
}
 
int hashmap_replace(Hashmap *h, const void *key, void *value) {
        struct swap_entries swap;
        struct plain_hashmap_entry *e;
        unsigned hash, idx;
 
        assert(h);
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx != IDX_NIL) {
                e = plain_bucket_at(h, idx);
#if 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. */
                if (e->b.key != key) {
                        h->b.debug.put_count++;
                        h->b.debug.rem_count++;
                        h->b.debug.last_rem_idx = idx;
                }
#endif
                e->b.key = key;
                e->value = value;
                hashmap_set_dirty(h);
 
                return 0;
        }
 
        e = &bucket_at_swap(&swap, IDX_PUT)->p;
        e->b.key = key;
        e->value = value;
        return hashmap_put_boldly(h, hash, &swap, true);
}
 
int hashmap_update(Hashmap *h, const void *key, void *value) {
        struct plain_hashmap_entry *e;
        unsigned hash, idx;
 
        assert(h);
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL)
                return -ENOENT;
 
        e = plain_bucket_at(h, idx);
        e->value = value;
        hashmap_set_dirty(h);
 
        return 0;
}
 
void* _hashmap_get(HashmapBase *h, const void *key) {
        struct hashmap_base_entry *e;
        unsigned hash, idx;
 
        if (!h)
                return NULL;
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL)
                return NULL;
 
        e = bucket_at(h, idx);
        return entry_value(h, e);
}
 
void* hashmap_get2(Hashmap *h, const void *key, void **ret) {
        struct plain_hashmap_entry *e;
        unsigned hash, idx;
 
        if (!h)
                return NULL;
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL)
                return NULL;
 
        e = plain_bucket_at(h, idx);
        if (ret)
                *ret = (void*) e->b.key;
 
        return e->value;
}
 
bool _hashmap_contains(HashmapBase *h, const void *key) {
        unsigned hash;
 
        if (!h)
                return false;
 
        hash = bucket_hash(h, key);
        return bucket_scan(h, hash, key) != IDX_NIL;
}
 
void* _hashmap_remove(HashmapBase *h, const void *key) {
        struct hashmap_base_entry *e;
        unsigned hash, idx;
        void *data;
 
        if (!h)
                return NULL;
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL)
                return NULL;
 
        e = bucket_at(h, idx);
        data = entry_value(h, e);
        remove_entry(h, idx);
 
        return data;
}
 
void* hashmap_remove2(Hashmap *h, const void *key, void **ret) {
        struct plain_hashmap_entry *e;
        unsigned hash, idx;
        void *data;
 
        if (!h) {
                if (ret)
                        *ret = NULL;
                return NULL;
        }
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL) {
                if (ret)
                        *ret = NULL;
                return NULL;
        }
 
        e = plain_bucket_at(h, idx);
        data = e->value;
        if (ret)
                *ret = (void*) e->b.key;
 
        remove_entry(h, idx);
 
        return data;
}
 
int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value) {
        struct swap_entries swap;
        struct plain_hashmap_entry *e;
        unsigned old_hash, new_hash, idx;
 
        if (!h)
                return -ENOENT;
 
        old_hash = bucket_hash(h, old_key);
        idx = bucket_scan(h, old_hash, old_key);
        if (idx == IDX_NIL)
                return -ENOENT;
 
        new_hash = bucket_hash(h, new_key);
        if (bucket_scan(h, new_hash, new_key) != IDX_NIL)
                return -EEXIST;
 
        remove_entry(h, idx);
 
        e = &bucket_at_swap(&swap, IDX_PUT)->p;
        e->b.key = new_key;
        e->value = value;
        assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
 
        return 0;
}
 
int set_remove_and_put(Set *s, const void *old_key, const void *new_key) {
        struct swap_entries swap;
        struct hashmap_base_entry *e;
        unsigned old_hash, new_hash, idx;
 
        if (!s)
                return -ENOENT;
 
        old_hash = bucket_hash(s, old_key);
        idx = bucket_scan(s, old_hash, old_key);
        if (idx == IDX_NIL)
                return -ENOENT;
 
        new_hash = bucket_hash(s, new_key);
        if (bucket_scan(s, new_hash, new_key) != IDX_NIL)
                return -EEXIST;
 
        remove_entry(s, idx);
 
        e = &bucket_at_swap(&swap, IDX_PUT)->p.b;
        e->key = new_key;
        assert_se(hashmap_put_boldly(s, new_hash, &swap, false) == 1);
 
        return 0;
}
 
int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value) {
        struct swap_entries swap;
        struct plain_hashmap_entry *e;
        unsigned old_hash, new_hash, idx_old, idx_new;
 
        if (!h)
                return -ENOENT;
 
        old_hash = bucket_hash(h, old_key);
        idx_old = bucket_scan(h, old_hash, old_key);
        if (idx_old == IDX_NIL)
                return -ENOENT;
 
        old_key = bucket_at(HASHMAP_BASE(h), idx_old)->key;
 
        new_hash = bucket_hash(h, new_key);
        idx_new = bucket_scan(h, new_hash, new_key);
        if (idx_new != IDX_NIL)
                if (idx_old != idx_new) {
                        remove_entry(h, idx_new);
                        /* Compensate for a possible backward shift. */
                        if (old_key != bucket_at(HASHMAP_BASE(h), idx_old)->key)
                                idx_old = prev_idx(HASHMAP_BASE(h), idx_old);
                        assert(old_key == bucket_at(HASHMAP_BASE(h), idx_old)->key);
                }
 
        remove_entry(h, idx_old);
 
        e = &bucket_at_swap(&swap, IDX_PUT)->p;
        e->b.key = new_key;
        e->value = value;
        assert_se(hashmap_put_boldly(h, new_hash, &swap, false) == 1);
 
        return 0;
}
 
void* _hashmap_remove_value(HashmapBase *h, const void *key, void *value) {
        struct hashmap_base_entry *e;
        unsigned hash, idx;
 
        if (!h)
                return NULL;
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL)
                return NULL;
 
        e = bucket_at(h, idx);
        if (entry_value(h, e) != value)
                return NULL;
 
        remove_entry(h, idx);
 
        return value;
}
 
static unsigned find_first_entry(HashmapBase *h) {
        Iterator i = ITERATOR_FIRST;
 
        if (!h || !n_entries(h))
                return IDX_NIL;
 
        return hashmap_iterate_entry(h, &i);
}
 
void* _hashmap_first_key_and_value(HashmapBase *h, bool remove, void **ret_key) {
        struct hashmap_base_entry *e;
        void *key, *data;
        unsigned idx;
 
        idx = find_first_entry(h);
        if (idx == IDX_NIL) {
                if (ret_key)
                        *ret_key = NULL;
                return NULL;
        }
 
        e = bucket_at(h, idx);
        key = (void*) e->key;
        data = entry_value(h, e);
 
        if (remove)
                remove_entry(h, idx);
 
        if (ret_key)
                *ret_key = key;
 
        return data;
}
 
unsigned _hashmap_size(HashmapBase *h) {
        if (!h)
                return 0;
 
        return n_entries(h);
}
 
unsigned _hashmap_buckets(HashmapBase *h) {
        if (!h)
                return 0;
 
        return n_buckets(h);
}
 
int _hashmap_merge(Hashmap *h, Hashmap *other) {
        Iterator i;
        unsigned idx;
 
        assert(h);
 
        HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
                struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
                int r;
 
                r = hashmap_put(h, pe->b.key, pe->value);
                if (r < 0 && r != -EEXIST)
                        return r;
        }
 
        return 0;
}
 
int set_merge(Set *s, Set *other) {
        Iterator i;
        unsigned idx;
 
        assert(s);
 
        HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
                struct set_entry *se = set_bucket_at(other, idx);
                int r;
 
                r = set_put(s, se->b.key);
                if (r < 0)
                        return r;
        }
 
        return 0;
}
 
int _hashmap_reserve(HashmapBase *h, unsigned entries_add) {
        int r;
 
        assert(h);
 
        r = resize_buckets(h, entries_add);
        if (r < 0)
                return r;
 
        return 0;
}
 
/*
 * The same as hashmap_merge(), but every new item from other is moved to h.
 * Keys already in h are skipped and stay in other.
 * Returns: 0 on success.
 *          -ENOMEM on alloc failure, in which case no move has been done.
 */
int _hashmap_move(HashmapBase *h, HashmapBase *other) {
        struct swap_entries swap;
        struct hashmap_base_entry *e, *n;
        Iterator i;
        unsigned idx;
        int r;
 
        assert(h);
 
        if (!other)
                return 0;
 
        assert(other->type == h->type);
 
        /*
         * This reserves buckets for the worst case, where none of other's
         * entries are yet present in h. This is preferable to risking
         * an allocation failure in the middle of the moving and having to
         * rollback or return a partial result.
         */
        r = resize_buckets(h, n_entries(other));
        if (r < 0)
                return r;
 
        HASHMAP_FOREACH_IDX(idx, other, i) {
                unsigned h_hash;
 
                e = bucket_at(other, idx);
                h_hash = bucket_hash(h, e->key);
                if (bucket_scan(h, h_hash, e->key) != IDX_NIL)
                        continue;
 
                n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
                n->key = e->key;
                if (h->type != HASHMAP_TYPE_SET)
                        ((struct plain_hashmap_entry*) n)->value =
                                ((struct plain_hashmap_entry*) e)->value;
                assert_se(hashmap_put_boldly(h, h_hash, &swap, false) == 1);
 
                remove_entry(other, idx);
        }
 
        return 0;
}
 
int _hashmap_move_one(HashmapBase *h, HashmapBase *other, const void *key) {
        struct swap_entries swap;
        unsigned h_hash, other_hash, idx;
        struct hashmap_base_entry *e, *n;
        int r;
 
        assert(h);
 
        h_hash = bucket_hash(h, key);
        if (bucket_scan(h, h_hash, key) != IDX_NIL)
                return -EEXIST;
 
        if (!other)
                return -ENOENT;
 
        assert(other->type == h->type);
 
        other_hash = bucket_hash(other, key);
        idx = bucket_scan(other, other_hash, key);
        if (idx == IDX_NIL)
                return -ENOENT;
 
        e = bucket_at(other, idx);
 
        n = &bucket_at_swap(&swap, IDX_PUT)->p.b;
        n->key = e->key;
        if (h->type != HASHMAP_TYPE_SET)
                ((struct plain_hashmap_entry*) n)->value =
                        ((struct plain_hashmap_entry*) e)->value;
        r = hashmap_put_boldly(h, h_hash, &swap, true);
        if (r < 0)
                return r;
 
        remove_entry(other, idx);
        return 0;
}
 
HashmapBase* _hashmap_copy(HashmapBase *h) {
        HashmapBase *copy;
        int r;
 
        assert(h);
 
        copy = hashmap_base_new(h->hash_ops, h->type);
        if (!copy)
                return NULL;
 
        switch (h->type) {
        case HASHMAP_TYPE_PLAIN:
        case HASHMAP_TYPE_ORDERED:
                r = hashmap_merge((Hashmap*)copy, (Hashmap*)h);
                break;
        case HASHMAP_TYPE_SET:
                r = set_merge((Set*)copy, (Set*)h);
                break;
        default:
                assert_not_reached();
        }
 
        if (r < 0)
                return _hashmap_free(copy);
 
        return copy;
}
 
char** _hashmap_get_strv(HashmapBase *h) {
        char **sv;
        Iterator i;
        unsigned idx, n;
 
        if (!h)
                return new0(char*, 1);
 
        sv = new(char*, n_entries(h)+1);
        if (!sv)
                return NULL;
 
        n = 0;
        HASHMAP_FOREACH_IDX(idx, h, i)
                sv[n++] = entry_value(h, bucket_at(h, idx));
        sv[n] = NULL;
 
        return sv;
}
 
char** set_to_strv(Set **s) {
        assert(s);
 
        /* This is similar to set_get_strv(), but invalidates the set on success. */
 
        char **v = new(char*, set_size(*s) + 1);
        if (!v)
                return NULL;
 
        for (char **p = v; (*p = set_steal_first(*s)); p++)
                ;
 
        assert(set_isempty(*s));
        *s = set_free(*s);
        return v;
}
 
void* ordered_hashmap_next(OrderedHashmap *h, const void *key) {
        struct ordered_hashmap_entry *e;
        unsigned hash, idx;
 
        if (!h)
                return NULL;
 
        hash = bucket_hash(h, key);
        idx = bucket_scan(h, hash, key);
        if (idx == IDX_NIL)
                return NULL;
 
        e = ordered_bucket_at(h, idx);
        if (e->iterate_next == IDX_NIL)
                return NULL;
        return ordered_bucket_at(h, e->iterate_next)->p.value;
}
 
int set_consume(Set *s, void *value) {
        int r;
 
        assert(s);
        assert(value);
 
        r = set_put(s, value);
        if (r <= 0)
                free(value);
 
        return r;
}
 
int hashmap_put_strdup_full(Hashmap **h, const struct hash_ops *hash_ops, const char *k, const char *v) {
        int r;
 
        assert(h);
 
        r = hashmap_ensure_allocated(h, hash_ops);
        if (r < 0)
                return r;
 
        _cleanup_free_ char *kdup = NULL, *vdup = NULL;
 
        kdup = strdup(k);
        if (!kdup)
                return -ENOMEM;
 
        if (v) {
                vdup = strdup(v);
                if (!vdup)
                        return -ENOMEM;
        }
 
        r = hashmap_put(*h, kdup, vdup);
        if (r < 0) {
                if (r == -EEXIST && streq_ptr(v, hashmap_get(*h, kdup)))
                        return 0;
                return r;
        }
 
        /* 0 with non-null vdup would mean vdup is already in the hashmap, which cannot be */
        assert(vdup == NULL || r > 0);
        if (r > 0)
                kdup = vdup = NULL;
 
        return r;
}
 
int set_put_strndup_full(Set **s, const struct hash_ops *hash_ops, const char *p, size_t n) {
        char *c;
        int r;
 
        assert(s);
        assert(p);
 
        r = set_ensure_allocated(s, hash_ops);
        if (r < 0)
                return r;
 
        if (n == SIZE_MAX) {
                if (set_contains(*s, (char*) p))
                        return 0;
 
                c = strdup(p);
        } else
                c = strndup(p, n);
        if (!c)
                return -ENOMEM;
 
        return set_consume(*s, c);
}
 
int set_put_strdupv_full(Set **s, const struct hash_ops *hash_ops, char **l) {
        int n = 0, r;
 
        assert(s);
 
        STRV_FOREACH(i, l) {
                r = set_put_strndup_full(s, hash_ops, *i, SIZE_MAX);
                if (r < 0)
                        return r;
 
                n += r;
        }
 
        return n;
}
 
int set_put_strsplit(Set *s, const char *v, const char *separators, ExtractFlags flags) {
        const char *p = ASSERT_PTR(v);
        int r;
 
        assert(s);
 
        for (;;) {
                char *word;
 
                r = extract_first_word(&p, &word, separators, flags);
                if (r <= 0)
                        return r;
 
                r = set_consume(s, word);
                if (r < 0)
                        return r;
        }
}
 
/* expand the cachemem if needed, return true if newly (re)activated. */
static int cachemem_maintain(CacheMem *mem, size_t size) {
        assert(mem);
 
        if (!GREEDY_REALLOC(mem->ptr, size)) {
                if (size > 0)
                        return -ENOMEM;
        }
 
        if (!mem->active) {
                mem->active = true;
                return true;
        }
 
        return false;
}
 
int iterated_cache_get(IteratedCache *cache, const void ***res_keys, const void ***res_values, unsigned *res_n_entries) {
        bool sync_keys = false, sync_values = false;
        size_t size;
        int r;
 
        assert(cache);
        assert(cache->hashmap);
 
        size = n_entries(cache->hashmap);