1/*
2 * librdkafka - Apache Kafka C library
3 *
4 * Copyright (c) 2012-2015, Magnus Edenhill
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef _RDLIST_H_
30#define _RDLIST_H_
31
32
33/**
34 *
35 * Simple light-weight append-only list to be used as a collection convenience.
36 *
37 */
38
39typedef struct rd_list_s {
40 int rl_size;
41 int rl_cnt;
42 void **rl_elems;
43 void (*rl_free_cb) (void *);
44 int rl_flags;
45#define RD_LIST_F_ALLOCATED 0x1 /* The rd_list_t is allocated,
46 * will be free on destroy() */
47#define RD_LIST_F_SORTED 0x2 /* Set by sort(), cleared by any mutations.
48 * When this flag is set bsearch() is used
49 * by find(), otherwise a linear search. */
50#define RD_LIST_F_FIXED_SIZE 0x4 /* Assert on grow, when prealloc()ed */
51#define RD_LIST_F_UNIQUE 0x8 /* Don't allow duplicates:
52 * ONLY ENFORCED BY CALLER. */
53 int rl_elemsize; /**< Element size (when prealloc()ed) */
54 void *rl_p; /**< Start of prealloced elements,
55 * the allocation itself starts at rl_elems
56 */
57} rd_list_t;
58
59
60/**
61 * @brief Initialize a list, prepare for 'initial_size' elements
62 * (optional optimization).
63 * List elements will optionally be freed by \p free_cb.
64 *
65 * @returns \p rl
66 */
67rd_list_t *
68rd_list_init (rd_list_t *rl, int initial_size, void (*free_cb) (void *));
69
70
71/**
72 * @brief Same as rd_list_init() but uses initial_size and free_cb
73 * from the provided \p src list.
74 */
75rd_list_t *rd_list_init_copy (rd_list_t *rl, const rd_list_t *src);
76
77/**
78 * @brief Allocate a new list pointer and initialize
79 * it according to rd_list_init().
80 *
81 * This is the same as calling \c rd_list_init(rd_list_alloc(), ..));
82 *
83 * Use rd_list_destroy() to free.
84 */
85rd_list_t *rd_list_new (int initial_size, void (*free_cb) (void *));
86
87
88/**
89 * @brief Prepare list to for an additional \p size elements.
90 * This is an optimization to avoid incremental grows.
91 */
92void rd_list_grow (rd_list_t *rl, size_t size);
93
94/**
95 * @brief Preallocate elements to avoid having to pass an allocated pointer to
96 * rd_list_add(), instead pass NULL to rd_list_add() and use the returned
97 * pointer as the element.
98 *
99 * @param elemsize element size, or 0 if elements are allocated separately.
100 * @param size number of elements
101 * @param memzero initialize element memory to zeros.
102 *
103 * @remark Preallocated element lists can't grow past \p size.
104 */
105void rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t size,
106 int memzero);
107
108/**
109 * @brief Set the number of valid elements, this must only be used
110 * with prealloc_elems() to make the preallocated elements directly
111 * usable.
112 */
113void rd_list_set_cnt (rd_list_t *rl, size_t cnt);
114
115
116/**
117 * @brief Free a pointer using the list's free_cb
118 *
119 * @remark If no free_cb is set, or \p ptr is NULL, dont do anything
120 *
121 * Typical use is rd_list_free_cb(rd_list_remove_cmp(....));
122 */
123void rd_list_free_cb (rd_list_t *rl, void *ptr);
124
125
126/**
127 * @brief Append element to list
128 *
129 * @returns \p elem. If \p elem is NULL the default element for that index
130 * will be returned (for use with set_elems).
131 */
132void *rd_list_add (rd_list_t *rl, void *elem);
133
134
135/**
136 * @brief Set element at \p idx to \p ptr.
137 *
138 * @remark MUST NOT overwrite an existing element.
139 * @remark The list will be grown, if needed, any gaps between the current
140 * highest element and \p idx will be set to NULL.
141 */
142void rd_list_set (rd_list_t *rl, int idx, void *ptr);
143
144
145/**
146 * Remove element from list.
147 * This is a slow O(n) + memmove operation.
148 * Returns the removed element.
149 */
150void *rd_list_remove (rd_list_t *rl, void *match_elem);
151
152/**
153 * Remove element from list using comparator.
154 * See rd_list_remove()
155 */
156void *rd_list_remove_cmp (rd_list_t *rl, void *match_elem,
157 int (*cmp) (void *_a, void *_b));
158
159
160/**
161 * @brief Remove element at index \p idx.
162 *
163 * This is a O(1) + memmove operation
164 */
165void rd_list_remove_elem (rd_list_t *rl, int idx);
166
167
168/**
169 * @brief Remove all elements matching comparator.
170 *
171 * @returns the number of elements removed.
172 *
173 * @sa rd_list_remove()
174 */
175int rd_list_remove_multi_cmp (rd_list_t *rl, void *match_elem,
176 int (*cmp) (void *_a, void *_b));
177
178
179/**
180 * Sort list using comparator
181 */
182void rd_list_sort (rd_list_t *rl, int (*cmp) (const void *, const void *));
183
184
185/**
186 * Empties the list (but does not free any memory)
187 */
188void rd_list_clear (rd_list_t *rl);
189
190
191/**
192 * Empties the list, frees the element array, and optionally frees
193 * each element using the registered \c rl->rl_free_cb.
194 *
195 * If the list was previously allocated with rd_list_new() it will be freed.
196 */
197void rd_list_destroy (rd_list_t *rl);
198
199/**
200 * @brief Wrapper for rd_list_destroy() that has same signature as free(3),
201 * allowing it to be used as free_cb for nested lists.
202 */
203void rd_list_destroy_free (void *rl);
204
205
206/**
207 * Returns the element at index 'idx', or NULL if out of range.
208 *
209 * Typical iteration is:
210 * int i = 0;
211 * my_type_t *obj;
212 * while ((obj = rd_list_elem(rl, i++)))
213 * do_something(obj);
214 */
215void *rd_list_elem (const rd_list_t *rl, int idx);
216
217#define RD_LIST_FOREACH(elem,listp,idx) \
218 for (idx = 0 ; (elem = rd_list_elem(listp, idx)) ; idx++)
219
220#define RD_LIST_FOREACH_REVERSE(elem,listp,idx) \
221 for (idx = (listp)->rl_cnt-1 ; \
222 idx >= 0 && (elem = rd_list_elem(listp, idx)) ; idx--)
223
224/**
225 * Returns the number of elements in list.
226 */
227static RD_INLINE RD_UNUSED int rd_list_cnt (const rd_list_t *rl) {
228 return rl->rl_cnt;
229}
230
231
232/**
233 * Returns true if list is empty
234 */
235#define rd_list_empty(rl) (rd_list_cnt(rl) == 0)
236
237
238/**
239 * @brief Find element index using comparator.
240 *
241 * \p match is the first argument to \p cmp, and each element (up to a match)
242 * is the second argument to \p cmp.
243 *
244 * @remark this is a O(n) scan.
245 * @returns the first matching element or NULL.
246 */
247int rd_list_index (const rd_list_t *rl, const void *match,
248 int (*cmp) (const void *, const void *));
249
250/**
251 * @brief Find element using comparator
252 *
253 * \p match is the first argument to \p cmp, and each element (up to a match)
254 * is the second argument to \p cmp.
255 *
256 * @remark if the list is sorted bsearch() is used, otherwise an O(n) scan.
257 *
258 * @returns the first matching element or NULL.
259 */
260void *rd_list_find (const rd_list_t *rl, const void *match,
261 int (*cmp) (const void *, const void *));
262
263
264
265/**
266 * @brief Compare list \p a to \p b.
267 *
268 * @returns < 0 if a was "lesser" than b,
269 * > 0 if a was "greater" than b,
270 * 0 if a and b are equal.
271 */
272int rd_list_cmp (const rd_list_t *a, rd_list_t *b,
273 int (*cmp) (const void *, const void *));
274
275/**
276 * @brief Simple element pointer comparator
277 */
278int rd_list_cmp_ptr (const void *a, const void *b);
279
280
281/**
282 * @brief Apply \p cb to each element in list, if \p cb returns 0
283 * the element will be removed (but not freed).
284 */
285void rd_list_apply (rd_list_t *rl,
286 int (*cb) (void *elem, void *opaque), void *opaque);
287
288
289
290/**
291 * @brief Copy list \p src, returning a new list,
292 * using optional \p copy_cb (per elem)
293 */
294rd_list_t *rd_list_copy (const rd_list_t *src,
295 void *(*copy_cb) (const void *elem, void *opaque),
296 void *opaque);
297
298
299/**
300 * @brief Copy list \p src to \p dst using optional \p copy_cb (per elem)
301 * @remark The destination list is not initialized or copied by this function.
302 * @remark copy_cb() may return NULL in which case no element is added,
303 * but the copy callback might have done so itself.
304 */
305void rd_list_copy_to (rd_list_t *dst, const rd_list_t *src,
306 void *(*copy_cb) (const void *elem, void *opaque),
307 void *opaque);
308
309
310/**
311 * @brief Copy callback to copy elements that are preallocated lists.
312 */
313void *rd_list_copy_preallocated (const void *elem, void *opaque);
314
315
316/**
317 * @brief String copier for rd_list_copy()
318 */
319static RD_UNUSED
320void *rd_list_string_copy (const void *elem, void *opaque) {
321 return rd_strdup((const char *)elem);
322}
323
324
325
326/**
327 * @name Misc helpers for common list types
328 * @{
329 *
330 */
331
332/**
333 * @brief Init a new list of int32_t's of maximum size \p max_size
334 * where each element is pre-allocated.
335 *
336 * @remark The allocation flag of the original \p rl is retained,
337 * do not pass an uninitialized \p rl to this function.
338 */
339rd_list_t *rd_list_init_int32 (rd_list_t *rl, int max_size);
340
341
342/**
343 * Debugging: Print list to stdout.
344 */
345void rd_list_dump (const char *what, const rd_list_t *rl);
346
347
348
349/**
350 * @brief Set element at index \p idx to value \p val.
351 *
352 * @remark Must only be used with preallocated int32_t lists.
353 * @remark Allows values to be overwritten.
354 */
355void rd_list_set_int32 (rd_list_t *rl, int idx, int32_t val);
356
357/**
358 * @returns the int32_t element value at index \p idx
359 *
360 * @remark Must only be used with preallocated int32_t lists.
361 */
362int32_t rd_list_get_int32 (const rd_list_t *rl, int idx);
363
364/**@}*/
365
366#endif /* _RDLIST_H_ */
367