hashmap.h revision fc86aa0ed204922dcafa85353cb10e1aa7d91a76
/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
#pragma once
/***
This file is part of systemd.
Copyright 2010 Lennart Poettering
Copyright 2014 Michal Schmidt
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 <stdbool.h>
#include "macro.h"
#include "util.h"
/*
* A hash table implementation. As a minor optimization a NULL hashmap object
* will be treated as empty hashmap for all read operations. That way it is not
* necessary to instantiate an object for each Hashmap use.
*
* If ENABLE_DEBUG_HASHMAP is defined (by configuring with --enable-debug=hashmap),
* the implemention will:
* - store extra data for debugging and statistics (see tools/gdb-sd_dump_hashmaps.py)
* - perform extra checks for invalid use of iterators
*/
#define HASH_KEY_SIZE 16
/* The base type for all hashmap and set types. Many functions in the
* implementation take (HashmapBase*) parameters and are run-time polymorphic,
* though the API is not meant to be polymorphic (do not call functions
* internal_*() directly). */
typedef struct HashmapBase HashmapBase;
typedef struct OrderedHashmap OrderedHashmap; /* Like Hashmap, but also remembers entry insertion order */
/* Ideally the Iterator would be an opaque struct, but it is instantiated
* by hashmap users, so the definition has to be here. Do not use its fields
* directly. */
typedef struct {
unsigned idx; /* index of an entry to be iterated next */
const void *next_key; /* expected value of that entry's key pointer */
#ifdef ENABLE_DEBUG_HASHMAP
unsigned put_count; /* hashmap's put_count recorded at start of iteration */
unsigned rem_count; /* hashmap's rem_count in previous iteration */
unsigned prev_idx; /* idx in previous iteration */
#endif
} Iterator;
typedef int (*compare_func_t)(const void *a, const void *b);
struct hash_ops {
};
int string_compare_func(const void *a, const void *b) _pure_;
extern const struct hash_ops string_hash_ops;
/* This will compare the passed pointers directly, and will not
* dereference them. This is hence not useful for strings or
* suchlike. */
int trivial_compare_func(const void *a, const void *b) _const_;
extern const struct hash_ops trivial_hash_ops;
/* 32bit values we can always just embedd in the pointer itself, but
* in order to support 32bit archs we need store 64bit values
* indirectly, since they don't fit in a pointer. */
int uint64_compare_func(const void *a, const void *b) _pure_;
extern const struct hash_ops uint64_hash_ops;
/* On some archs dev_t is 32bit, and on others 64bit. And sometimes
* it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
#if SIZEOF_DEV_T != 8
int devt_compare_func(const void *a, const void *b) _pure_;
extern const struct hash_ops devt_hash_ops = {
.hash = devt_hash_func,
};
#else
#define devt_hash_func uint64_hash_func
#define devt_compare_func uint64_compare_func
#define devt_hash_ops uint64_hash_ops
#endif
/* Macros for type checking */
#define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
#define PTR_COMPATIBLE_WITH_PLAIN_HASHMAP(h) \
#define HASHMAP_BASE(h) \
(HashmapBase*)(h), \
(void)0)
#define PLAIN_HASHMAP(h) \
(Hashmap*)(h), \
(void)0)
#ifdef ENABLE_DEBUG_HASHMAP
#else
# define HASHMAP_DEBUG_PARAMS
# define HASHMAP_DEBUG_SRC_ARGS
# define HASHMAP_DEBUG_PASS_ARGS
#endif
void internal_hashmap_free(HashmapBase *h);
static inline void hashmap_free(Hashmap *h) {
}
static inline void ordered_hashmap_free(OrderedHashmap *h) {
}
void internal_hashmap_free_free(HashmapBase *h);
static inline void hashmap_free_free(Hashmap *h) {
}
static inline void ordered_hashmap_free_free(OrderedHashmap *h) {
}
void hashmap_free_free_free(Hashmap *h);
static inline void ordered_hashmap_free_free_free(OrderedHashmap *h) {
}
}
}
int internal_hashmap_ensure_allocated(Hashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS);
int internal_ordered_hashmap_ensure_allocated(OrderedHashmap **h, const struct hash_ops *hash_ops HASHMAP_DEBUG_PARAMS);
#define hashmap_ensure_allocated(h, ops) internal_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
#define ordered_hashmap_ensure_allocated(h, ops) internal_ordered_hashmap_ensure_allocated(h, ops HASHMAP_DEBUG_SRC_ARGS)
}
}
}
}
}
}
}
}
}
}
}
}
static inline int ordered_hashmap_remove_and_put(OrderedHashmap *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) {
}
/* Since merging data from a OrderedHashmap into a Hashmap or vice-versa
* should just work, allow this by having looser type-checking here. */
}
}
/* Unlike hashmap_merge, hashmap_move does not allow mixing the types. */
}
}
}
static inline int ordered_hashmap_move_one(OrderedHashmap *h, OrderedHashmap *other, const void *key) {
}
static inline unsigned hashmap_size(Hashmap *h) {
return internal_hashmap_size(HASHMAP_BASE(h));
}
static inline unsigned ordered_hashmap_size(OrderedHashmap *h) {
return internal_hashmap_size(HASHMAP_BASE(h));
}
static inline bool hashmap_isempty(Hashmap *h) {
return hashmap_size(h) == 0;
}
static inline bool ordered_hashmap_isempty(OrderedHashmap *h) {
return ordered_hashmap_size(h) == 0;
}
static inline unsigned hashmap_buckets(Hashmap *h) {
return internal_hashmap_buckets(HASHMAP_BASE(h));
}
static inline unsigned ordered_hashmap_buckets(OrderedHashmap *h) {
return internal_hashmap_buckets(HASHMAP_BASE(h));
}
}
}
void internal_hashmap_clear(HashmapBase *h);
static inline void hashmap_clear(Hashmap *h) {
}
static inline void ordered_hashmap_clear(OrderedHashmap *h) {
}
void internal_hashmap_clear_free(HashmapBase *h);
static inline void hashmap_clear_free(Hashmap *h) {
}
static inline void ordered_hashmap_clear_free(OrderedHashmap *h) {
}
void hashmap_clear_free_free(Hashmap *h);
static inline void ordered_hashmap_clear_free_free(OrderedHashmap *h) {
}
/*
* Note about all *_first*() functions
*
* For plain Hashmaps and Sets the order of entries is undefined.
* The functions find whatever entry is first in the implementation
* internal order.
*
* Only for OrderedHashmaps the order is well defined and finding
* the first entry is O(1).
*/
void *internal_hashmap_steal_first(HashmapBase *h);
static inline void *hashmap_steal_first(Hashmap *h) {
return internal_hashmap_steal_first(HASHMAP_BASE(h));
}
static inline void *ordered_hashmap_steal_first(OrderedHashmap *h) {
return internal_hashmap_steal_first(HASHMAP_BASE(h));
}
void *internal_hashmap_steal_first_key(HashmapBase *h);
static inline void *hashmap_steal_first_key(Hashmap *h) {
return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
}
static inline void *ordered_hashmap_steal_first_key(OrderedHashmap *h) {
return internal_hashmap_steal_first_key(HASHMAP_BASE(h));
}
static inline void *hashmap_first_key(Hashmap *h) {
return internal_hashmap_first_key(HASHMAP_BASE(h));
}
static inline void *ordered_hashmap_first_key(OrderedHashmap *h) {
return internal_hashmap_first_key(HASHMAP_BASE(h));
}
static inline void *hashmap_first(Hashmap *h) {
return internal_hashmap_first(HASHMAP_BASE(h));
}
static inline void *ordered_hashmap_first(OrderedHashmap *h) {
return internal_hashmap_first(HASHMAP_BASE(h));
}
/* no hashmap_next */
char **internal_hashmap_get_strv(HashmapBase *h);
static inline char **hashmap_get_strv(Hashmap *h) {
return internal_hashmap_get_strv(HASHMAP_BASE(h));
}
static inline char **ordered_hashmap_get_strv(OrderedHashmap *h) {
return internal_hashmap_get_strv(HASHMAP_BASE(h));
}
/*
* Hashmaps are iterated in unpredictable order.
* OrderedHashmaps are an exception to this. They are iterated in the order
* the entries were inserted.
* It is safe to remove the current entry.
*/
#define HASHMAP_FOREACH(e, h, i) \
(e); \
(e) = hashmap_iterate((h), &(i), NULL))
#define ORDERED_HASHMAP_FOREACH(e, h, i) \
(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)))