1 /* Copyright (C) 2015-2017 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
2 * SPDX-License-Identifier: GPL-3.0-or-later
3 */
4
5 /**
6 * @file pack.h
7 * @brief A length-prefixed list of objects, also an array list.
8 *
9 * Each object is prefixed by item length, unlike array this structure
10 * permits variable-length data. It is also equivalent to forward-only list
11 * backed by an array.
12 *
13 * @note Maximum object size is 2^16 bytes, see ::pack_objlen_t
14 * @todo If some mistake happens somewhere, the access may end up in an infinite loop.
15 * (equality comparison on pointers)
16 *
17 * # Example usage:
18 *
19 * @code{.c}
20 * pack_t pack;
21 * pack_init(pack);
22 *
23 * // Reserve 2 objects, 6 bytes total
24 * pack_reserve(pack, 2, 4 + 2);
25 *
26 * // Push 2 objects
27 * pack_obj_push(pack, U8("jedi"), 4)
28 * pack_obj_push(pack, U8("\xbe\xef"), 2);
29 *
30 * // Iterate length-value pairs
31 * uint8_t *it = pack_head(pack);
32 * while (it != pack_tail(pack)) {
33 * uint8_t *val = pack_obj_val(it);
34 * it = pack_obj_next(it);
35 * }
36 *
37 * // Remove object
38 * pack_obj_del(pack, U8("jedi"), 4);
39 *
40 * pack_clear(pack);
41 * @endcode
42 *
43 * \addtogroup generics
44 * @{
45 */
46
47 #pragma once
48
49 #include <stdint.h>
50 #include <string.h>
51 #include "array.h"
52
53 #ifdef __cplusplus
54 extern "C" {
55 #endif
56
57 /** Packed object length type. */
58 typedef uint16_t pack_objlen_t;
59
60 /** Pack is defined as an array of bytes */
61 typedef array_t(uint8_t) pack_t;
62
63 /** Zero-initialize the pack. */
64 #define pack_init(pack) \
65 array_init(pack)
66
67 /** Make the pack empty and free pointed-to memory (plain malloc/free). */
68 #define pack_clear(pack) \
69 array_clear(pack)
70
71 /** Make the pack empty and free pointed-to memory.
72 * Mempool usage: pass mm_free and a knot_mm_t* . */
73 #define pack_clear_mm(pack, free, baton) \
74 array_clear_mm((pack), (free), (baton))
75
76 /** Reserve space for *additional* objects in the pack (plain malloc/free).
77 * @return 0 if success, <0 on failure */
78 #define pack_reserve(pack, objs_count, objs_len) \
79 pack_reserve_mm((pack), (objs_count), (objs_len), array_std_reserve, NULL)
80
81 /** Reserve space for *additional* objects in the pack.
82 * Mempool usage: pass kr_memreserve and a knot_mm_t* .
83 * @return 0 if success, <0 on failure */
84 #define pack_reserve_mm(pack, objs_count, objs_len, reserve, baton) \
85 array_reserve_mm((pack), (pack).len + (sizeof(pack_objlen_t)*(objs_count) + (objs_len)), (reserve), (baton))
86
87 /** Return pointer to first packed object.
88 *
89 * Recommended way to iterate:
90 * for (uint8_t *it = pack_head(pack); it != pack_tail(pack); it = pack_obj_next(it))
91 */
92 #define pack_head(pack) \
93 ((pack).len > 0 ? &((pack).at[0]) : NULL)
94
95 /** Return pack end pointer. */
96 #define pack_tail(pack) \
97 ((pack).len > 0 ? &((pack).at[(pack).len]) : NULL)
98
99 /** Return packed object length. */
pack_obj_len(uint8_t * it)100 static inline pack_objlen_t pack_obj_len(uint8_t *it)
101 {
102 pack_objlen_t len = 0;
103 if (it != NULL)
104 memcpy(&len, it, sizeof(len));
105 return len;
106 }
107
108 /** Return packed object value. */
pack_obj_val(uint8_t * it)109 static inline uint8_t *pack_obj_val(uint8_t *it)
110 {
111 if (kr_fails_assert(it))
112 return NULL;
113 return it + sizeof(pack_objlen_t);
114 }
115
116 /** Return pointer to next packed object. */
pack_obj_next(uint8_t * it)117 static inline uint8_t *pack_obj_next(uint8_t *it)
118 {
119 if (kr_fails_assert(it))
120 return NULL;
121 return pack_obj_val(it) + pack_obj_len(it);
122 }
123
124 /** Return pointer to the last packed object. */
pack_last(pack_t pack)125 static inline uint8_t *pack_last(pack_t pack)
126 {
127 if (pack.len == 0)
128 return NULL;
129 uint8_t *it = pack_head(pack);
130 uint8_t *tail = pack_tail(pack);
131 while (true) {
132 uint8_t *next = pack_obj_next(it);
133 if (next == tail)
134 return it;
135 it = next;
136 }
137 }
138
139 /** Push object to the end of the pack
140 * @return 0 on success, negative number on failure
141 */
pack_obj_push(pack_t * pack,const uint8_t * obj,pack_objlen_t len)142 static inline int pack_obj_push(pack_t *pack, const uint8_t *obj, pack_objlen_t len)
143 {
144 if (kr_fails_assert(pack && obj))
145 return kr_error(EINVAL);
146 size_t packed_len = len + sizeof(len);
147 if (pack->len + packed_len > pack->cap)
148 return kr_error(ENOSPC);
149
150 uint8_t *endp = pack->at + pack->len;
151 memcpy(endp, (char *)&len, sizeof(len));
152 memcpy(endp + sizeof(len), obj, len);
153 pack->len += packed_len;
154 return 0;
155 }
156
157 /** Returns a pointer to packed object.
158 * @return pointer to packed object or NULL
159 */
pack_obj_find(pack_t * pack,const uint8_t * obj,pack_objlen_t len)160 static inline uint8_t *pack_obj_find(pack_t *pack, const uint8_t *obj, pack_objlen_t len)
161 {
162 if (!pack || kr_fails_assert(obj))
163 return NULL;
164 uint8_t *endp = pack_tail(*pack);
165 uint8_t *it = pack_head(*pack);
166 while (it != endp) {
167 uint8_t *val = pack_obj_val(it);
168 if (pack_obj_len(it) == len && memcmp(obj, val, len) == 0)
169 return it;
170 it = pack_obj_next(it);
171 }
172 return NULL;
173 }
174
175 /** Delete object from the pack
176 * @return 0 on success, negative number on failure
177 */
pack_obj_del(pack_t * pack,const uint8_t * obj,pack_objlen_t len)178 static inline int pack_obj_del(pack_t *pack, const uint8_t *obj, pack_objlen_t len)
179 {
180 if (!pack || kr_fails_assert(obj))
181 return kr_error(EINVAL);
182 uint8_t *endp = pack_tail(*pack);
183 uint8_t *it = pack_obj_find(pack, obj, len);
184 if (it) {
185 size_t packed_len = len + sizeof(len);
186 memmove(it, it + packed_len, endp - it - packed_len);
187 pack->len -= packed_len;
188 return 0;
189 }
190 return -1;
191 }
192
193 /** Clone a pack, replacing destination pack; (*dst == NULL) is valid input.
194 * @return kr_error(ENOMEM) on allocation failure. */
pack_clone(pack_t ** dst,const pack_t * src,knot_mm_t * pool)195 static inline int pack_clone(pack_t **dst, const pack_t *src, knot_mm_t *pool)
196 {
197 if (kr_fails_assert(dst && src))
198 return kr_error(EINVAL);
199 /* Get a valid pack_t. */
200 if (!*dst) {
201 *dst = mm_alloc(pool, sizeof(pack_t));
202 if (!*dst) return kr_error(ENOMEM);
203 pack_init(**dst);
204 /* Clone data only if needed */
205 if (src->len == 0) return kr_ok();
206 }
207 /* Replace the contents of the pack_t. */
208 int ret = array_reserve_mm(**dst, src->len, kr_memreserve, pool);
209 if (ret < 0) {
210 return kr_error(ENOMEM);
211 }
212 memcpy((*dst)->at, src->at, src->len);
213 (*dst)->len = src->len;
214 return kr_ok();
215 }
216
217 #ifdef __cplusplus
218 }
219 #endif
220
221 /** @} */
222