hashmap.h revision de99c9dcbaf6e474551266d8f0b519bf2d8d0522
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#pragma once
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/***
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering This file is part of systemd.
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering Copyright 2010 Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering systemd is free software; you can redistribute it and/or modify it
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering under the terms of the GNU Lesser General Public License as published by
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering the Free Software Foundation; either version 2.1 of the License, or
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering (at your option) any later version.
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering systemd is distributed in the hope that it will be useful, but
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering WITHOUT ANY WARRANTY; without even the implied warranty of
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering Lesser General Public License for more details.
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering You should have received a copy of the GNU Lesser General Public License
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering along with systemd; If not, see <http://www.gnu.org/licenses/>.
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering***/
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
8b43440b7ef4b81c69c31de7ff820dc07a780254Lennart Poettering#include <stdbool.h>
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#include "macro.h"
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#include "util.h"
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/* Pretty straightforward hash table implementation. As a minor
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * optimization a NULL hashmap object will be treated as empty hashmap
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * for all read operations. That way it is not necessary to
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * instantiate an object for each Hashmap use. */
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#define HASH_KEY_SIZE 16
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringtypedef struct Hashmap Hashmap;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringtypedef struct _IteratorStruct _IteratorStruct;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringtypedef _IteratorStruct* Iterator;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#define ITERATOR_FIRST ((Iterator) 0)
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#define ITERATOR_LAST ((Iterator) -1)
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringtypedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringtypedef int (*compare_func_t)(const void *a, const void *b);
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringunsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringint string_compare_func(const void *a, const void *b) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/* This will compare the passed pointers directly, and will not
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * dereference them. This is hence not useful for strings or
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * suchlike. */
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringunsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringint trivial_compare_func(const void *a, const void *b) _const_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/* 32bit values we can always just embedd in the pointer itself, but
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * in order to support 32bit archs we need store 64bit values
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * indirectly, since they don't fit in a pointer. */
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringunsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringint uint64_compare_func(const void *a, const void *b) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/* On some archs dev_t is 32bit, and on others 64bit. And sometimes
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#if SIZEOF_DEV_T != 8
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringunsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poetteringint devt_compare_func(const void *a, const void *b) _pure_;
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#else
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering/* No need to define a second version of this... */
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#define devt_hash_func uint64_hash_func
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#define devt_compare_func uint64_compare_func
78f22b973fa2c9b09bd974680836df17163d9ee0Lennart Poettering#endif
Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func);
void hashmap_free(Hashmap *h);
void hashmap_free_free(Hashmap *h);
void hashmap_free_free_free(Hashmap *h);
Hashmap *hashmap_copy(Hashmap *h);
int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func);
int hashmap_put(Hashmap *h, const void *key, void *value);
int hashmap_update(Hashmap *h, const void *key, void *value);
int hashmap_replace(Hashmap *h, const void *key, void *value);
void *hashmap_get(Hashmap *h, const void *key);
void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
bool hashmap_contains(Hashmap *h, const void *key);
void *hashmap_remove(Hashmap *h, const void *key);
void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
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_remove_and_replace(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) _pure_;
bool hashmap_isempty(Hashmap *h) _pure_;
unsigned hashmap_buckets(Hashmap *h) _pure_;
void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key);
void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key);
void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i);
void hashmap_clear(Hashmap *h);
void hashmap_clear_free(Hashmap *h);
void hashmap_clear_free_free(Hashmap *h);
void *hashmap_steal_first(Hashmap *h);
void *hashmap_steal_first_key(Hashmap *h);
void *hashmap_first(Hashmap *h) _pure_;
void *hashmap_first_key(Hashmap *h) _pure_;
void *hashmap_last(Hashmap *h) _pure_;
void *hashmap_next(Hashmap *h, const void *key);
char **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 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 HASHMAP_FOREACH_BACKWARDS(e, h, i) \
for ((i) = ITERATOR_LAST, (e) = hashmap_iterate_backwards((h), &(i), NULL); (e); (e) = hashmap_iterate_backwards((h), &(i), NULL))
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 _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)