diff options
Diffstat (limited to 'lib/generic/pack.h')
| -rw-r--r-- | lib/generic/pack.h | 221 |
1 files changed, 221 insertions, 0 deletions
diff --git a/lib/generic/pack.h b/lib/generic/pack.h new file mode 100644 index 0000000..18d57db --- /dev/null +++ b/lib/generic/pack.h @@ -0,0 +1,221 @@ +/* Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz> + * SPDX-License-Identifier: GPL-3.0-or-later + */ + +/** + * @file pack.h + * @brief A length-prefixed list of objects, also an array list. + * + * Each object is prefixed by item length, unlike array this structure + * permits variable-length data. It is also equivalent to forward-only list + * backed by an array. + * + * @note Maximum object size is 2^16 bytes, see ::pack_objlen_t + * @todo If some mistake happens somewhere, the access may end up in an infinite loop. + * (equality comparison on pointers) + * + * # Example usage: + * + * @code{.c} + * pack_t pack; + * pack_init(pack); + * + * // Reserve 2 objects, 6 bytes total + * pack_reserve(pack, 2, 4 + 2); + * + * // Push 2 objects + * pack_obj_push(pack, U8("jedi"), 4) + * pack_obj_push(pack, U8("\xbe\xef"), 2); + * + * // Iterate length-value pairs + * uint8_t *it = pack_head(pack); + * while (it != pack_tail(pack)) { + * uint8_t *val = pack_obj_val(it); + * it = pack_obj_next(it); + * } + * + * // Remove object + * pack_obj_del(pack, U8("jedi"), 4); + * + * pack_clear(pack); + * @endcode + * + * \addtogroup generics + * @{ + */ + +#pragma once + +#include <stdint.h> +#include <string.h> +#include "array.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** Packed object length type. */ +typedef uint16_t pack_objlen_t; + +/** Pack is defined as an array of bytes */ +typedef array_t(uint8_t) pack_t; + +/** Zero-initialize the pack. */ +#define pack_init(pack) \ + array_init(pack) + +/** Make the pack empty and free pointed-to memory (plain malloc/free). */ +#define pack_clear(pack) \ + array_clear(pack) + +/** Make the pack empty and free pointed-to memory. + * Mempool usage: pass mm_free and a knot_mm_t* . */ +#define pack_clear_mm(pack, free, baton) \ + array_clear_mm((pack), (free), (baton)) + +/** Reserve space for *additional* objects in the pack (plain malloc/free). + * @return 0 if success, <0 on failure */ +#define pack_reserve(pack, objs_count, objs_len) \ + pack_reserve_mm((pack), (objs_count), (objs_len), array_std_reserve, NULL) + +/** Reserve space for *additional* objects in the pack. + * Mempool usage: pass kr_memreserve and a knot_mm_t* . + * @return 0 if success, <0 on failure */ +#define pack_reserve_mm(pack, objs_count, objs_len, reserve, baton) \ + array_reserve_mm((pack), (pack).len + (sizeof(pack_objlen_t)*(objs_count) + (objs_len)), (reserve), (baton)) + +/** Return pointer to first packed object. + * + * Recommended way to iterate: + * for (uint8_t *it = pack_head(pack); it != pack_tail(pack); it = pack_obj_next(it)) + */ +#define pack_head(pack) \ + ((pack).len > 0 ? &((pack).at[0]) : NULL) + +/** Return pack end pointer. */ +#define pack_tail(pack) \ + ((pack).len > 0 ? &((pack).at[(pack).len]) : NULL) + +/** Return packed object length. */ +static inline pack_objlen_t pack_obj_len(uint8_t *it) +{ + pack_objlen_t len = 0; + if (it != NULL) + memcpy(&len, it, sizeof(len)); + return len; +} + +/** Return packed object value. */ +static inline uint8_t *pack_obj_val(uint8_t *it) +{ + if (kr_fails_assert(it)) + return NULL; + return it + sizeof(pack_objlen_t); +} + +/** Return pointer to next packed object. */ +static inline uint8_t *pack_obj_next(uint8_t *it) +{ + if (kr_fails_assert(it)) + return NULL; + return pack_obj_val(it) + pack_obj_len(it); +} + +/** Return pointer to the last packed object. */ +static inline uint8_t *pack_last(pack_t pack) +{ + if (pack.len == 0) + return NULL; + uint8_t *it = pack_head(pack); + uint8_t *tail = pack_tail(pack); + while (true) { + uint8_t *next = pack_obj_next(it); + if (next == tail) + return it; + it = next; + } +} + +/** Push object to the end of the pack + * @return 0 on success, negative number on failure + */ +static inline int pack_obj_push(pack_t *pack, const uint8_t *obj, pack_objlen_t len) +{ + if (kr_fails_assert(pack && obj)) + return kr_error(EINVAL); + size_t packed_len = len + sizeof(len); + if (pack->len + packed_len > pack->cap) + return kr_error(ENOSPC); + + uint8_t *endp = pack->at + pack->len; + memcpy(endp, (char *)&len, sizeof(len)); + memcpy(endp + sizeof(len), obj, len); + pack->len += packed_len; + return 0; +} + +/** Returns a pointer to packed object. + * @return pointer to packed object or NULL + */ +static inline uint8_t *pack_obj_find(pack_t *pack, const uint8_t *obj, pack_objlen_t len) +{ + if (!pack || kr_fails_assert(obj)) + return NULL; + uint8_t *endp = pack_tail(*pack); + uint8_t *it = pack_head(*pack); + while (it != endp) { + uint8_t *val = pack_obj_val(it); + if (pack_obj_len(it) == len && memcmp(obj, val, len) == 0) + return it; + it = pack_obj_next(it); + } + return NULL; +} + +/** Delete object from the pack + * @return 0 on success, negative number on failure + */ +static inline int pack_obj_del(pack_t *pack, const uint8_t *obj, pack_objlen_t len) +{ + if (!pack || kr_fails_assert(obj)) + return kr_error(EINVAL); + uint8_t *endp = pack_tail(*pack); + uint8_t *it = pack_obj_find(pack, obj, len); + if (it) { + size_t packed_len = len + sizeof(len); + memmove(it, it + packed_len, endp - it - packed_len); + pack->len -= packed_len; + return 0; + } + return -1; +} + +/** Clone a pack, replacing destination pack; (*dst == NULL) is valid input. + * @return kr_error(ENOMEM) on allocation failure. */ +static inline int pack_clone(pack_t **dst, const pack_t *src, knot_mm_t *pool) +{ + if (kr_fails_assert(dst && src)) + return kr_error(EINVAL); + /* Get a valid pack_t. */ + if (!*dst) { + *dst = mm_alloc(pool, sizeof(pack_t)); + if (!*dst) return kr_error(ENOMEM); + pack_init(**dst); + /* Clone data only if needed */ + if (src->len == 0) return kr_ok(); + } + /* Replace the contents of the pack_t. */ + int ret = array_reserve_mm(**dst, src->len, kr_memreserve, pool); + if (ret < 0) { + return kr_error(ENOMEM); + } + memcpy((*dst)->at, src->at, src->len); + (*dst)->len = src->len; + return kr_ok(); +} + +#ifdef __cplusplus +} +#endif + +/** @} */ |