diff options
Diffstat (limited to 'fluent-bit/lib/librdkafka-2.1.0/src/rdmap.h')
| -rw-r--r-- | fluent-bit/lib/librdkafka-2.1.0/src/rdmap.h | 487 |
1 files changed, 487 insertions, 0 deletions
diff --git a/fluent-bit/lib/librdkafka-2.1.0/src/rdmap.h b/fluent-bit/lib/librdkafka-2.1.0/src/rdmap.h new file mode 100644 index 000000000..a79dcda06 --- /dev/null +++ b/fluent-bit/lib/librdkafka-2.1.0/src/rdmap.h @@ -0,0 +1,487 @@ +/* + * librdkafka - The Apache Kafka C/C++ library + * + * Copyright (c) 2020 Magnus Edenhill + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _RDMAP_H_ +#define _RDMAP_H_ + +/** + * @name Hash maps. + * + * Memory of key and value are allocated by the user but owned by the hash map + * until elements are deleted or overwritten. + * + * The lower-case API provides a generic typeless (void *) hash map while + * the upper-case API provides a strictly typed hash map implemented as macros + * on top of the generic API. + * + * See rd_map_init(), et.al, for the generic API and RD_MAP_INITIALIZER() + * for the typed API. + * + * @remark Not thread safe. + */ + + +/** + * @struct Map element. This is the internal representation + * of the element and exposed to the user for iterating over the hash. + */ +typedef struct rd_map_elem_s { + LIST_ENTRY(rd_map_elem_s) hlink; /**< Hash bucket link */ + LIST_ENTRY(rd_map_elem_s) link; /**< Iterator link */ + unsigned int hash; /**< Key hash value */ + const void *key; /**< Key (memory owned by map) */ + const void *value; /**< Value (memory owned by map) */ +} rd_map_elem_t; + + +/** + * @struct Hash buckets (internal use). + */ +struct rd_map_buckets { + LIST_HEAD(, rd_map_elem_s) * p; /**< Hash buckets array */ + int cnt; /**< Bucket count */ +}; + + +/** + * @struct Hash map. + */ +typedef struct rd_map_s { + struct rd_map_buckets rmap_buckets; /**< Hash buckets */ + int rmap_cnt; /**< Element count */ + + LIST_HEAD(, rd_map_elem_s) + rmap_iter; /**< Element list for iterating + * over all elements. */ + + int (*rmap_cmp)(const void *a, const void *b); /**< Key comparator */ + unsigned int (*rmap_hash)(const void *key); /**< Key hash function */ + void (*rmap_destroy_key)(void *key); /**< Optional key free */ + void (*rmap_destroy_value)(void *value); /**< Optional value free */ + + void *rmap_opaque; +} rd_map_t; + + + +/** + * @brief Set/overwrite value in map. + * + * If an existing entry with the same key already exists its key and value + * will be freed with the destroy_key and destroy_value functions + * passed to rd_map_init(). + * + * The map assumes memory ownership of both the \p key and \p value and will + * use the destroy_key and destroy_value functions (if set) to free + * the key and value memory when the map is destroyed or element removed. + * + * @returns the map element. + */ +rd_map_elem_t *rd_map_set(rd_map_t *rmap, void *key, void *value); + + +/** + * @brief Look up \p key in the map and return its value, or NULL + * if \p key was not found. + * + * The returned memory is still owned by the map. + */ +void *rd_map_get(const rd_map_t *rmap, const void *key); + + +/** + * @brief Delete \p key from the map, if it exists. + * + * The destroy_key and destroy_value functions (if set) will be used + * to free the key and value memory. + */ +void rd_map_delete(rd_map_t *rmap, const void *key); + + +/** Key or Value Copy function signature. */ +typedef void *(rd_map_copy_t)(const void *key_or_value); + + +/** + * @brief Copy all elements from \p src to \p dst. + * \p dst must be initialized and compatible with \p src. + * + * @param dst Destination map to copy to. + * @param src Source map to copy from. + * @param key_copy Key copy callback. If NULL the \p dst key will just + * reference the \p src key. + * @param value_copy Value copy callback. If NULL the \p dst value will just + * reference the \p src value. + */ +void rd_map_copy(rd_map_t *dst, + const rd_map_t *src, + rd_map_copy_t *key_copy, + rd_map_copy_t *value_copy); + + +/** + * @returns the current number of elements in the map. + */ +size_t rd_map_cnt(const rd_map_t *rmap); + +/** + * @returns true if map is empty, else false. + */ +rd_bool_t rd_map_is_empty(const rd_map_t *rmap); + + +/** + * @brief Iterate over all elements in the map. + * + * @warning The map MUST NOT be modified during the loop. + * + * @remark This is part of the untyped generic API. + */ +#define RD_MAP_FOREACH_ELEM(ELEM, RMAP) \ + for (rd_map_iter_begin((RMAP), &(ELEM)); rd_map_iter(&(ELEM)); \ + rd_map_iter_next(&(ELEM))) + + +/** + * @brief Begin iterating \p rmap, first element is set in \p *elem. + */ +void rd_map_iter_begin(const rd_map_t *rmap, const rd_map_elem_t **elem); + +/** + * @returns 1 if \p *elem is a valid iteration element, else 0. + */ +static RD_INLINE RD_UNUSED int rd_map_iter(const rd_map_elem_t **elem) { + return *elem != NULL; +} + +/** + * @brief Advances the iteration to the next element. + */ +static RD_INLINE RD_UNUSED void rd_map_iter_next(const rd_map_elem_t **elem) { + *elem = LIST_NEXT(*elem, link); +} + + +/** + * @brief Initialize a map that is expected to hold \p expected_cnt elements. + * + * @param expected_cnt Expected number of elements in the map, + * this is used to select a suitable bucket count. + * Passing a value of 0 will set the bucket count + * to a reasonable default. + * @param cmp Key comparator that must return 0 if the two keys match. + * @param hash Key hashing function that is used to map a key to a bucket. + * It must return an integer hash >= 0 of the key. + * @param destroy_key (Optional) When an element is deleted or overwritten + * this function will be used to free the key memory. + * @param destroy_value (Optional) When an element is deleted or overwritten + * this function will be used to free the value memory. + * + * Destroy the map with rd_map_destroy() + * + * @remarks The map is not thread-safe. + */ +void rd_map_init(rd_map_t *rmap, + size_t expected_cnt, + int (*cmp)(const void *a, const void *b), + unsigned int (*hash)(const void *key), + void (*destroy_key)(void *key), + void (*destroy_value)(void *value)); + + +/** + * @brief Internal use + */ +struct rd_map_buckets rd_map_alloc_buckets(size_t expected_cnt); + + +/** + * @brief Empty the map and free all elements. + */ +void rd_map_clear(rd_map_t *rmap); + + +/** + * @brief Free all elements in the map and free all memory associated + * with the map, but not the rd_map_t itself. + * + * The map is unusable after this call but can be re-initialized using + * rd_map_init(). + * + * @sa rd_map_clear() + */ +void rd_map_destroy(rd_map_t *rmap); + + +/** + * @brief String comparator for (const char *) keys. + */ +int rd_map_str_cmp(const void *a, const void *b); + + +/** + * @brief String hash function (djb2) for (const char *) keys. + */ +unsigned int rd_map_str_hash(const void *a); + + + +/** + * @name Typed hash maps. + * + * Typed hash maps provides a type-safe layer on top of the standard hash maps. + */ + +/** + * @brief Define a typed map type which can later be used with + * RD_MAP_INITIALIZER() and typed RD_MAP_*() API. + */ +#define RD_MAP_TYPE(KEY_TYPE, VALUE_TYPE) \ + struct { \ + rd_map_t rmap; \ + KEY_TYPE key; \ + VALUE_TYPE value; \ + const rd_map_elem_t *elem; \ + } + +/** + * @brief Initialize a typed hash map. The left hand side variable must be + * a typed hash map defined by RD_MAP_TYPE(). + * + * The typed hash map is a macro layer on top of the rd_map_t implementation + * that provides type safety. + * The methods are the same as the underlying implementation but in all caps + * (to indicate their macro use), e.g., RD_MAP_SET() is the typed version + * of rd_map_set(). + * + * @param EXPECTED_CNT Expected number of elements in hash. + * @param KEY_TYPE The type of the hash key. + * @param VALUE_TYPE The type of the hash value. + * @param CMP Comparator function for the key. + * @param HASH Hash function for the key. + * @param DESTROY_KEY Destructor for the key type. + * @param DESTROY_VALUE Destructor for the value type. + * + * @sa rd_map_init() + */ +#define RD_MAP_INITIALIZER(EXPECTED_CNT, CMP, HASH, DESTROY_KEY, \ + DESTROY_VALUE) \ + { \ + .rmap = { \ + .rmap_buckets = rd_map_alloc_buckets(EXPECTED_CNT), \ + .rmap_cmp = CMP, \ + .rmap_hash = HASH, \ + .rmap_destroy_key = DESTROY_KEY, \ + .rmap_destroy_value = DESTROY_VALUE \ + } \ + } + + +/** + * @brief Initialize a locally-defined typed hash map. + * This hash map can only be used in the current scope/function + * as its type is private to this initializement. + * + * @param RMAP Hash map variable name. + * + * For the other parameters, see RD_MAP_INITIALIZER(). + * + * @sa RD_MAP_INITIALIZER() + */ +#define RD_MAP_LOCAL_INITIALIZER(RMAP, EXPECTED_CNT, KEY_TYPE, VALUE_TYPE, \ + CMP, HASH, DESTROY_KEY, DESTROY_VALUE) \ + struct { \ + rd_map_t rmap; \ + KEY_TYPE key; \ + VALUE_TYPE value; \ + const rd_map_elem_t *elem; \ + } RMAP = RD_MAP_INITIALIZER(EXPECTED_CNT, CMP, HASH, DESTROY_KEY, \ + DESTROY_VALUE) + + +/** + * @brief Initialize typed map \p RMAP. + * + * @sa rd_map_init() + */ +#define RD_MAP_INIT(RMAP, EXPECTED_CNT, CMP, HASH, DESTROY_KEY, DESTROY_VALUE) \ + rd_map_init(&(RMAP)->rmap, EXPECTED_CNT, CMP, HASH, DESTROY_KEY, \ + DESTROY_VALUE) + + +/** + * @brief Allocate and initialize a typed map. + */ + + +/** + * @brief Typed hash map: Set key/value in map. + * + * @sa rd_map_set() + */ +#define RD_MAP_SET(RMAP, KEY, VALUE) \ + ((RMAP)->key = KEY, (RMAP)->value = VALUE, \ + rd_map_set(&(RMAP)->rmap, (void *)(RMAP)->key, \ + (void *)(RMAP)->value)) + +/** + * @brief Typed hash map: Get value for key. + * + * @sa rd_map_get() + */ +#define RD_MAP_GET(RMAP, KEY) \ + ((RMAP)->key = (KEY), \ + (RMAP)->value = rd_map_get(&(RMAP)->rmap, (RMAP)->key), \ + (RMAP)->value) + + + +/** + * @brief Get value for key. If key does not exist in map a new + * entry is added using the DEFAULT_CODE. + */ +#define RD_MAP_GET_OR_SET(RMAP, KEY, DEFAULT_CODE) \ + (RD_MAP_GET(RMAP, KEY) \ + ? (RMAP)->value \ + : (RD_MAP_SET(RMAP, (RMAP)->key, DEFAULT_CODE), (RMAP)->value)) + + +/** + * @brief Typed hash map: Delete element by key. + * + * The destroy_key and destroy_value functions (if set) will be used + * to free the key and value memory. + * + * @sa rd_map_delete() + */ +#define RD_MAP_DELETE(RMAP, KEY) \ + ((RMAP)->key = (KEY), rd_map_delete(&(RMAP)->rmap, (RMAP)->key)) + + +/** + * @brief Copy all elements from \p SRC to \p DST. + * \p DST must be initialized and compatible with \p SRC. + * + * @param DST Destination map to copy to. + * @param SRC Source map to copy from. + * @param KEY_COPY Key copy callback. If NULL the \p DST key will just + * reference the \p SRC key. + * @param VALUE_COPY Value copy callback. If NULL the \p DST value will just + * reference the \p SRC value. + */ +#define RD_MAP_COPY(DST, SRC, KEY_COPY, VALUE_COPY) \ + do { \ + if ((DST) != (SRC)) /*implicit type-check*/ \ + rd_map_copy(&(DST)->rmap, &(SRC)->rmap, KEY_COPY, \ + VALUE_COPY); \ + } while (0) + + +/** + * @brief Empty the map and free all elements. + * + * @sa rd_map_clear() + */ +#define RD_MAP_CLEAR(RMAP) rd_map_clear(&(RMAP)->rmap) + + +/** + * @brief Typed hash map: Destroy hash map. + * + * @sa rd_map_destroy() + */ +#define RD_MAP_DESTROY(RMAP) rd_map_destroy(&(RMAP)->rmap) + + +/** + * @brief Typed hash map: Destroy and free the hash map. + * + * @sa rd_map_destroy() + */ +#define RD_MAP_DESTROY_AND_FREE(RMAP) \ + do { \ + rd_map_destroy(&(RMAP)->rmap); \ + rd_free(RMAP); \ + } while (0) + + +/** + * @brief Typed hash map: Iterate over all elements in the map. + * + * @warning The current or previous elements may be removed, but the next + * element after the current one MUST NOT be modified during the loop. + * + * @warning RD_MAP_FOREACH() only supports one simultaneous invocation, + * that is, special care must be taken not to call FOREACH() from + * within a FOREACH() or FOREACH_KEY() loop on the same map. + * This is due to how RMAP->elem is used as the iterator. + * This restriction is unfortunately not enforced at build or run time. + * + * @remark The \p RMAP may not be const. + */ +#define RD_MAP_FOREACH(K, V, RMAP) \ + for (rd_map_iter_begin(&(RMAP)->rmap, &(RMAP)->elem), (K) = NULL, \ + (V) = NULL; \ + rd_map_iter(&(RMAP)->elem) && \ + ((RMAP)->key = (void *)(RMAP)->elem->key, (K) = (RMAP)->key, \ + (RMAP)->value = (void *)(RMAP)->elem->value, (V) = (RMAP)->value, \ + rd_map_iter_next(&(RMAP)->elem), rd_true);) + + +/** + * @brief Typed hash map: Iterate over all keys in the map. + * + * @warning The current or previous elements may be removed, but the next + * element after the current one MUST NOT be modified during the loop. + * + * @warning RD_MAP_FOREACH_KEY() only supports one simultaneous invocation, + * that is, special care must be taken not to call FOREACH_KEY() from + * within a FOREACH() or FOREACH_KEY() loop on the same map. + * This is due to how RMAP->elem is used as the iterator. + * This restriction is unfortunately not enforced at build or run time. + * + * @remark The \p RMAP may not be const. + */ +#define RD_MAP_FOREACH_KEY(K, RMAP) \ + for (rd_map_iter_begin(&(RMAP)->rmap, &(RMAP)->elem), (K) = NULL; \ + rd_map_iter(&(RMAP)->elem) && \ + ((RMAP)->key = (void *)(RMAP)->elem->key, (K) = (RMAP)->key, \ + rd_map_iter_next(&(RMAP)->elem), rd_true);) + + +/** + * @returns the number of elements in the map. + */ +#define RD_MAP_CNT(RMAP) rd_map_cnt(&(RMAP)->rmap) + +/** + * @returns true if map is empty, else false. + */ +#define RD_MAP_IS_EMPTY(RMAP) rd_map_is_empty(&(RMAP)->rmap) + +#endif /* _RDMAP_H_ */ |