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#include "rd.h"
30#include "rdlist.h"
31
32
33void rd_list_dump (const char *what, const rd_list_t *rl) {
34 int i;
35 printf("%s: (rd_list_t*)%p cnt %d, size %d, elems %p:\n",
36 what, rl, rl->rl_cnt, rl->rl_size, rl->rl_elems);
37 for (i = 0 ; i < rl->rl_cnt ; i++)
38 printf(" #%d: %p at &%p\n", i,
39 rl->rl_elems[i], &rl->rl_elems[i]);
40}
41
42void rd_list_grow (rd_list_t *rl, size_t size) {
43 rd_assert(!(rl->rl_flags & RD_LIST_F_FIXED_SIZE));
44 rl->rl_size += (int)size;
45 if (unlikely(rl->rl_size == 0))
46 return; /* avoid zero allocations */
47 rl->rl_elems = rd_realloc(rl->rl_elems,
48 sizeof(*rl->rl_elems) * rl->rl_size);
49}
50
51rd_list_t *
52rd_list_init (rd_list_t *rl, int initial_size, void (*free_cb) (void *)) {
53 memset(rl, 0, sizeof(*rl));
54
55 if (initial_size > 0)
56 rd_list_grow(rl, initial_size);
57
58 rl->rl_free_cb = free_cb;
59
60 return rl;
61}
62
63rd_list_t *rd_list_init_copy (rd_list_t *dst, const rd_list_t *src) {
64
65 if (src->rl_flags & RD_LIST_F_FIXED_SIZE) {
66 /* Source was preallocated, prealloc new dst list */
67 rd_list_init(dst, 0, src->rl_free_cb);
68
69 rd_list_prealloc_elems(dst, src->rl_elemsize, src->rl_size,
70 1/*memzero*/);
71 } else {
72 /* Source is dynamic, initialize dst the same */
73 rd_list_init(dst, rd_list_cnt(src), src->rl_free_cb);
74
75 }
76
77 return dst;
78}
79
80static RD_INLINE rd_list_t *rd_list_alloc (void) {
81 return malloc(sizeof(rd_list_t));
82}
83
84rd_list_t *rd_list_new (int initial_size, void (*free_cb) (void *)) {
85 rd_list_t *rl = rd_list_alloc();
86 rd_list_init(rl, initial_size, free_cb);
87 rl->rl_flags |= RD_LIST_F_ALLOCATED;
88 return rl;
89}
90
91
92void rd_list_prealloc_elems (rd_list_t *rl, size_t elemsize, size_t cnt,
93 int memzero) {
94 size_t allocsize;
95 char *p;
96 size_t i;
97
98 rd_assert(!rl->rl_elems);
99
100 /* Allocation layout:
101 * void *ptrs[cnt];
102 * elems[elemsize][cnt];
103 */
104
105 allocsize = (sizeof(void *) * cnt) + (elemsize * cnt);
106 if (memzero)
107 rl->rl_elems = rd_calloc(1, allocsize);
108 else
109 rl->rl_elems = rd_malloc(allocsize);
110
111 /* p points to first element's memory, unless elemsize is 0. */
112 if (elemsize > 0)
113 p = rl->rl_p = (char *)&rl->rl_elems[cnt];
114 else
115 p = rl->rl_p = NULL;
116
117 /* Pointer -> elem mapping */
118 for (i = 0 ; i < cnt ; i++, p += elemsize)
119 rl->rl_elems[i] = p;
120
121 rl->rl_size = (int)cnt;
122 rl->rl_cnt = 0;
123 rl->rl_flags |= RD_LIST_F_FIXED_SIZE;
124 rl->rl_elemsize = (int)elemsize;
125}
126
127
128void rd_list_set_cnt (rd_list_t *rl, size_t cnt) {
129 rd_assert(rl->rl_flags & RD_LIST_F_FIXED_SIZE);
130 rd_assert((int)cnt <= rl->rl_size);
131 rl->rl_cnt = (int)cnt;
132}
133
134
135void rd_list_free_cb (rd_list_t *rl, void *ptr) {
136 if (rl->rl_free_cb && ptr)
137 rl->rl_free_cb(ptr);
138}
139
140
141void *rd_list_add (rd_list_t *rl, void *elem) {
142 if (rl->rl_cnt == rl->rl_size)
143 rd_list_grow(rl, rl->rl_size ? rl->rl_size * 2 : 16);
144 rl->rl_flags &= ~RD_LIST_F_SORTED;
145 if (elem)
146 rl->rl_elems[rl->rl_cnt] = elem;
147 return rl->rl_elems[rl->rl_cnt++];
148}
149
150void rd_list_set (rd_list_t *rl, int idx, void *ptr) {
151 if (idx >= rl->rl_size)
152 rd_list_grow(rl, idx+1);
153
154 if (idx >= rl->rl_cnt) {
155 memset(&rl->rl_elems[rl->rl_cnt], 0,
156 sizeof(*rl->rl_elems) * (idx-rl->rl_cnt));
157 rl->rl_cnt = idx+1;
158 } else {
159 /* Not allowed to replace existing element. */
160 rd_assert(!rl->rl_elems[idx]);
161 }
162
163 rl->rl_elems[idx] = ptr;
164}
165
166
167
168void rd_list_remove_elem (rd_list_t *rl, int idx) {
169 rd_assert(idx < rl->rl_cnt);
170
171 if (idx + 1 < rl->rl_cnt)
172 memmove(&rl->rl_elems[idx],
173 &rl->rl_elems[idx+1],
174 sizeof(*rl->rl_elems) * (rl->rl_cnt - (idx+1)));
175 rl->rl_cnt--;
176}
177
178void *rd_list_remove (rd_list_t *rl, void *match_elem) {
179 void *elem;
180 int i;
181
182 RD_LIST_FOREACH(elem, rl, i) {
183 if (elem == match_elem) {
184 rd_list_remove_elem(rl, i);
185 return elem;
186 }
187 }
188
189 return NULL;
190}
191
192
193void *rd_list_remove_cmp (rd_list_t *rl, void *match_elem,
194 int (*cmp) (void *_a, void *_b)) {
195 void *elem;
196 int i;
197
198 RD_LIST_FOREACH(elem, rl, i) {
199 if (elem == match_elem ||
200 !cmp(elem, match_elem)) {
201 rd_list_remove_elem(rl, i);
202 return elem;
203 }
204 }
205
206 return NULL;
207}
208
209
210int rd_list_remove_multi_cmp (rd_list_t *rl, void *match_elem,
211 int (*cmp) (void *_a, void *_b)) {
212
213 void *elem;
214 int i;
215 int cnt = 0;
216
217 /* Scan backwards to minimize memmoves */
218 RD_LIST_FOREACH_REVERSE(elem, rl, i) {
219 if (match_elem == cmp ||
220 !cmp(elem, match_elem)) {
221 rd_list_remove_elem(rl, i);
222 cnt++;
223 }
224 }
225
226 return cnt;
227}
228
229
230/**
231 * Trampoline to avoid the double pointers in callbacks.
232 *
233 * rl_elems is a **, but to avoid having the application do the cumbersome
234 * ** -> * casting we wrap this here and provide a simple * pointer to the
235 * the callbacks.
236 *
237 * This is true for all list comparator uses, i.e., both sort() and find().
238 */
239static RD_TLS int (*rd_list_cmp_curr) (const void *, const void *);
240
241static RD_INLINE
242int rd_list_cmp_trampoline (const void *_a, const void *_b) {
243 const void *a = *(const void **)_a, *b = *(const void **)_b;
244
245 return rd_list_cmp_curr(a, b);
246}
247
248void rd_list_sort (rd_list_t *rl, int (*cmp) (const void *, const void *)) {
249 rd_list_cmp_curr = cmp;
250 qsort(rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems),
251 rd_list_cmp_trampoline);
252 rl->rl_flags |= RD_LIST_F_SORTED;
253}
254
255void rd_list_clear (rd_list_t *rl) {
256 rl->rl_cnt = 0;
257 rl->rl_flags &= ~RD_LIST_F_SORTED;
258}
259
260
261void rd_list_destroy (rd_list_t *rl) {
262
263 if (rl->rl_elems) {
264 int i;
265 if (rl->rl_free_cb) {
266 for (i = 0 ; i < rl->rl_cnt ; i++)
267 if (rl->rl_elems[i])
268 rl->rl_free_cb(rl->rl_elems[i]);
269 }
270
271 rd_free(rl->rl_elems);
272 }
273
274 if (rl->rl_flags & RD_LIST_F_ALLOCATED)
275 rd_free(rl);
276}
277
278void rd_list_destroy_free (void *rl) {
279 rd_list_destroy((rd_list_t *)rl);
280}
281
282void *rd_list_elem (const rd_list_t *rl, int idx) {
283 if (likely(idx < rl->rl_cnt))
284 return (void *)rl->rl_elems[idx];
285 return NULL;
286}
287
288int rd_list_index (const rd_list_t *rl, const void *match,
289 int (*cmp) (const void *, const void *)) {
290 int i;
291 const void *elem;
292
293 RD_LIST_FOREACH(elem, rl, i) {
294 if (!cmp(match, elem))
295 return i;
296 }
297
298 return -1;
299}
300
301
302void *rd_list_find (const rd_list_t *rl, const void *match,
303 int (*cmp) (const void *, const void *)) {
304 int i;
305 const void *elem;
306
307 if (rl->rl_flags & RD_LIST_F_SORTED) {
308 void **r;
309 rd_list_cmp_curr = cmp;
310 r = bsearch(&match/*ptrptr to match elems*/,
311 rl->rl_elems, rl->rl_cnt,
312 sizeof(*rl->rl_elems), rd_list_cmp_trampoline);
313 return r ? *r : NULL;
314 }
315
316 RD_LIST_FOREACH(elem, rl, i) {
317 if (!cmp(match, elem))
318 return (void *)elem;
319 }
320
321 return NULL;
322}
323
324
325int rd_list_cmp (const rd_list_t *a, rd_list_t *b,
326 int (*cmp) (const void *, const void *)) {
327 int i;
328
329 i = a->rl_cnt - b->rl_cnt;
330 if (i)
331 return i;
332
333 for (i = 0 ; i < a->rl_cnt ; i++) {
334 int r = cmp(a->rl_elems[i], b->rl_elems[i]);
335 if (r)
336 return r;
337 }
338
339 return 0;
340}
341
342
343/**
344 * @brief Simple element pointer comparator
345 */
346int rd_list_cmp_ptr (const void *a, const void *b) {
347 if (a < b)
348 return -1;
349 else if (a > b)
350 return 1;
351 return 0;
352}
353
354
355void rd_list_apply (rd_list_t *rl,
356 int (*cb) (void *elem, void *opaque), void *opaque) {
357 void *elem;
358 int i;
359
360 RD_LIST_FOREACH(elem, rl, i) {
361 if (!cb(elem, opaque)) {
362 rd_list_remove_elem(rl, i);
363 i--;
364 }
365 }
366
367 return;
368}
369
370
371/**
372 * @brief Default element copier that simply assigns the original pointer.
373 */
374static void *rd_list_nocopy_ptr (const void *elem, void *opaque) {
375 return (void *)elem;
376}
377
378rd_list_t *rd_list_copy (const rd_list_t *src,
379 void *(*copy_cb) (const void *elem, void *opaque),
380 void *opaque) {
381 rd_list_t *dst;
382
383 dst = rd_list_new(src->rl_cnt, src->rl_free_cb);
384
385 rd_list_copy_to(dst, src, copy_cb, opaque);
386 return dst;
387}
388
389
390void rd_list_copy_to (rd_list_t *dst, const rd_list_t *src,
391 void *(*copy_cb) (const void *elem, void *opaque),
392 void *opaque) {
393 void *elem;
394 int i;
395
396 rd_assert(dst != src);
397
398 if (!copy_cb)
399 copy_cb = rd_list_nocopy_ptr;
400
401 RD_LIST_FOREACH(elem, src, i) {
402 void *celem = copy_cb(elem, opaque);
403 if (celem)
404 rd_list_add(dst, celem);
405 }
406}
407
408
409/**
410 * @brief Copy elements of preallocated \p src to preallocated \p dst.
411 *
412 * @remark \p dst will be overwritten and initialized, but its
413 * flags will be retained.
414 *
415 * @returns \p dst
416 */
417static rd_list_t *rd_list_copy_preallocated0 (rd_list_t *dst,
418 const rd_list_t *src) {
419 int dst_flags = dst->rl_flags & RD_LIST_F_ALLOCATED;
420
421 rd_assert(dst != src);
422
423 rd_list_init_copy(dst, src);
424 dst->rl_flags |= dst_flags;
425
426 rd_assert((dst->rl_flags & RD_LIST_F_FIXED_SIZE));
427 rd_assert((src->rl_flags & RD_LIST_F_FIXED_SIZE));
428 rd_assert(dst->rl_elemsize == src->rl_elemsize &&
429 dst->rl_size == src->rl_size);
430
431 memcpy(dst->rl_p, src->rl_p, src->rl_elemsize * src->rl_size);
432 dst->rl_cnt = src->rl_cnt;
433
434 return dst;
435}
436
437void *rd_list_copy_preallocated (const void *elem, void *opaque) {
438 return rd_list_copy_preallocated0(rd_list_new(0, NULL),
439 (const rd_list_t *)elem);
440}
441
442
443/**
444 * @name Misc helpers for common list types
445 * @{
446 *
447 */
448rd_list_t *rd_list_init_int32 (rd_list_t *rl, int max_size) {
449 int rl_flags = rl->rl_flags & RD_LIST_F_ALLOCATED;
450 rd_list_init(rl, 0, NULL);
451 rl->rl_flags |= rl_flags;
452 rd_list_prealloc_elems(rl, sizeof(int32_t), max_size, 1/*memzero*/);
453 return rl;
454}
455
456void rd_list_set_int32 (rd_list_t *rl, int idx, int32_t val) {
457 rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) &&
458 rl->rl_elemsize == sizeof(int32_t));
459 rd_assert(idx < rl->rl_size);
460
461 memcpy(rl->rl_elems[idx], &val, sizeof(int32_t));
462
463 if (rl->rl_cnt <= idx)
464 rl->rl_cnt = idx+1;
465}
466
467int32_t rd_list_get_int32 (const rd_list_t *rl, int idx) {
468 rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) &&
469 rl->rl_elemsize == sizeof(int32_t) &&
470 idx < rl->rl_cnt);
471 return *(int32_t *)rl->rl_elems[idx];
472}
473
474
475
476
477/**@}*/
478
479