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
rd_list_dump(const char * what,const rd_list_t * rl)33 void 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
rd_list_grow(rd_list_t * rl,size_t size)42 void 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
51 rd_list_t *
rd_list_init(rd_list_t * rl,int initial_size,void (* free_cb)(void *))52 rd_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
rd_list_init_copy(rd_list_t * dst,const rd_list_t * src)63 rd_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
rd_list_alloc(void)80 static RD_INLINE rd_list_t *rd_list_alloc (void) {
81 return rd_malloc(sizeof(rd_list_t));
82 }
83
rd_list_new(int initial_size,void (* free_cb)(void *))84 rd_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
rd_list_prealloc_elems(rd_list_t * rl,size_t elemsize,size_t cnt,int memzero)92 void 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
rd_list_set_cnt(rd_list_t * rl,size_t cnt)128 void 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
rd_list_free_cb(rd_list_t * rl,void * ptr)135 void 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
rd_list_add(rd_list_t * rl,void * elem)141 void *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
rd_list_set(rd_list_t * rl,int idx,void * ptr)150 void 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
rd_list_remove_elem(rd_list_t * rl,int idx)168 void 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
rd_list_remove(rd_list_t * rl,void * match_elem)178 void *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
rd_list_remove_cmp(rd_list_t * rl,void * match_elem,int (* cmp)(void * _a,void * _b))193 void *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
rd_list_remove_multi_cmp(rd_list_t * rl,void * match_elem,int (* cmp)(void * _a,void * _b))210 int 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
rd_list_pop(rd_list_t * rl)230 void *rd_list_pop (rd_list_t *rl) {
231 void *elem;
232 int idx = rl->rl_cnt - 1;
233
234 if (idx < 0)
235 return NULL;
236
237 elem = rl->rl_elems[idx];
238 rd_list_remove_elem(rl, idx);
239
240 return elem;
241 }
242
243
244 /**
245 * Trampoline to avoid the double pointers in callbacks.
246 *
247 * rl_elems is a **, but to avoid having the application do the cumbersome
248 * ** -> * casting we wrap this here and provide a simple * pointer to the
249 * the callbacks.
250 *
251 * This is true for all list comparator uses, i.e., both sort() and find().
252 */
253 static RD_TLS int (*rd_list_cmp_curr) (const void *, const void *);
254
255 static RD_INLINE
rd_list_cmp_trampoline(const void * _a,const void * _b)256 int rd_list_cmp_trampoline (const void *_a, const void *_b) {
257 const void *a = *(const void **)_a, *b = *(const void **)_b;
258
259 return rd_list_cmp_curr(a, b);
260 }
261
rd_list_sort(rd_list_t * rl,int (* cmp)(const void *,const void *))262 void rd_list_sort (rd_list_t *rl, int (*cmp) (const void *, const void *)) {
263 if (unlikely(rl->rl_elems == NULL))
264 return;
265
266 rd_list_cmp_curr = cmp;
267 qsort(rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems),
268 rd_list_cmp_trampoline);
269 rl->rl_flags |= RD_LIST_F_SORTED;
270 }
271
rd_list_destroy_elems(rd_list_t * rl)272 static void rd_list_destroy_elems (rd_list_t *rl) {
273 int i;
274
275 if (!rl->rl_elems)
276 return;
277
278 if (rl->rl_free_cb) {
279 /* Free in reverse order to allow deletions */
280 for (i = rl->rl_cnt - 1 ; i >= 0 ; i--)
281 if (rl->rl_elems[i])
282 rl->rl_free_cb(rl->rl_elems[i]);
283 }
284
285 rd_free(rl->rl_elems);
286 rl->rl_elems = NULL;
287 rl->rl_cnt = 0;
288 rl->rl_size = 0;
289 rl->rl_flags &= ~RD_LIST_F_SORTED;
290 }
291
292
rd_list_clear(rd_list_t * rl)293 void rd_list_clear (rd_list_t *rl) {
294 rd_list_destroy_elems(rl);
295 }
296
297
rd_list_destroy(rd_list_t * rl)298 void rd_list_destroy (rd_list_t *rl) {
299 rd_list_destroy_elems(rl);
300 if (rl->rl_flags & RD_LIST_F_ALLOCATED)
301 rd_free(rl);
302 }
303
rd_list_destroy_free(void * rl)304 void rd_list_destroy_free (void *rl) {
305 rd_list_destroy((rd_list_t *)rl);
306 }
307
rd_list_elem(const rd_list_t * rl,int idx)308 void *rd_list_elem (const rd_list_t *rl, int idx) {
309 if (likely(idx < rl->rl_cnt))
310 return (void *)rl->rl_elems[idx];
311 return NULL;
312 }
313
rd_list_index(const rd_list_t * rl,const void * match,int (* cmp)(const void *,const void *))314 int rd_list_index (const rd_list_t *rl, const void *match,
315 int (*cmp) (const void *, const void *)) {
316 int i;
317 const void *elem;
318
319 RD_LIST_FOREACH(elem, rl, i) {
320 if (!cmp(match, elem))
321 return i;
322 }
323
324 return -1;
325 }
326
327
rd_list_find(const rd_list_t * rl,const void * match,int (* cmp)(const void *,const void *))328 void *rd_list_find (const rd_list_t *rl, const void *match,
329 int (*cmp) (const void *, const void *)) {
330 int i;
331 const void *elem;
332
333 if (rl->rl_flags & RD_LIST_F_SORTED) {
334 void **r;
335 rd_list_cmp_curr = cmp;
336 r = bsearch(&match/*ptrptr to match elems*/,
337 rl->rl_elems, rl->rl_cnt,
338 sizeof(*rl->rl_elems), rd_list_cmp_trampoline);
339 return r ? *r : NULL;
340 }
341
342 RD_LIST_FOREACH(elem, rl, i) {
343 if (!cmp(match, elem))
344 return (void *)elem;
345 }
346
347 return NULL;
348 }
349
350
rd_list_first(const rd_list_t * rl)351 void *rd_list_first (const rd_list_t *rl) {
352 if (rl->rl_cnt == 0)
353 return NULL;
354 return rl->rl_elems[0];
355 }
356
rd_list_last(const rd_list_t * rl)357 void *rd_list_last (const rd_list_t *rl) {
358 if (rl->rl_cnt == 0)
359 return NULL;
360 return rl->rl_elems[rl->rl_cnt-1];
361 }
362
363
rd_list_find_duplicate(const rd_list_t * rl,int (* cmp)(const void *,const void *))364 void *rd_list_find_duplicate (const rd_list_t *rl,
365 int (*cmp) (const void *, const void *)) {
366 int i;
367
368 rd_assert(rl->rl_flags & RD_LIST_F_SORTED);
369
370 for (i = 1 ; i < rl->rl_cnt ; i++) {
371 if (!cmp(rl->rl_elems[i-1],
372 rl->rl_elems[i]))
373 return rl->rl_elems[i];
374 }
375
376 return NULL;
377 }
378
rd_list_cmp(const rd_list_t * a,const rd_list_t * b,int (* cmp)(const void *,const void *))379 int rd_list_cmp (const rd_list_t *a, const rd_list_t *b,
380 int (*cmp) (const void *, const void *)) {
381 int i;
382
383 i = RD_CMP(a->rl_cnt, b->rl_cnt);
384 if (i)
385 return i;
386
387 for (i = 0 ; i < a->rl_cnt ; i++) {
388 int r = cmp(a->rl_elems[i], b->rl_elems[i]);
389 if (r)
390 return r;
391 }
392
393 return 0;
394 }
395
396
397 /**
398 * @brief Simple element pointer comparator
399 */
rd_list_cmp_ptr(const void * a,const void * b)400 int rd_list_cmp_ptr (const void *a, const void *b) {
401 return RD_CMP(a, b);
402 }
403
rd_list_cmp_str(const void * a,const void * b)404 int rd_list_cmp_str (const void *a, const void *b) {
405 return strcmp((const char *)a, (const char *)b);
406 }
407
rd_list_apply(rd_list_t * rl,int (* cb)(void * elem,void * opaque),void * opaque)408 void rd_list_apply (rd_list_t *rl,
409 int (*cb) (void *elem, void *opaque), void *opaque) {
410 void *elem;
411 int i;
412
413 RD_LIST_FOREACH(elem, rl, i) {
414 if (!cb(elem, opaque)) {
415 rd_list_remove_elem(rl, i);
416 i--;
417 }
418 }
419
420 return;
421 }
422
423
424 /**
425 * @brief Default element copier that simply assigns the original pointer.
426 */
rd_list_nocopy_ptr(const void * elem,void * opaque)427 static void *rd_list_nocopy_ptr (const void *elem, void *opaque) {
428 return (void *)elem;
429 }
430
rd_list_copy(const rd_list_t * src,rd_list_copy_cb_t * copy_cb,void * opaque)431 rd_list_t *rd_list_copy (const rd_list_t *src,
432 rd_list_copy_cb_t *copy_cb, void *opaque) {
433 rd_list_t *dst;
434
435 dst = rd_list_new(src->rl_cnt, src->rl_free_cb);
436
437 rd_list_copy_to(dst, src, copy_cb, opaque);
438 return dst;
439 }
440
441
rd_list_copy_to(rd_list_t * dst,const rd_list_t * src,void * (* copy_cb)(const void * elem,void * opaque),void * opaque)442 void rd_list_copy_to (rd_list_t *dst, const rd_list_t *src,
443 void *(*copy_cb) (const void *elem, void *opaque),
444 void *opaque) {
445 void *elem;
446 int i;
447
448 rd_assert(dst != src);
449
450 if (!copy_cb)
451 copy_cb = rd_list_nocopy_ptr;
452
453 RD_LIST_FOREACH(elem, src, i) {
454 void *celem = copy_cb(elem, opaque);
455 if (celem)
456 rd_list_add(dst, celem);
457 }
458 }
459
460
461 /**
462 * @brief Copy elements of preallocated \p src to preallocated \p dst.
463 *
464 * @remark \p dst will be overwritten and initialized, but its
465 * flags will be retained.
466 *
467 * @returns \p dst
468 */
rd_list_copy_preallocated0(rd_list_t * dst,const rd_list_t * src)469 static rd_list_t *rd_list_copy_preallocated0 (rd_list_t *dst,
470 const rd_list_t *src) {
471 int dst_flags = dst->rl_flags & RD_LIST_F_ALLOCATED;
472
473 rd_assert(dst != src);
474
475 rd_list_init_copy(dst, src);
476 dst->rl_flags |= dst_flags;
477
478 rd_assert((dst->rl_flags & RD_LIST_F_FIXED_SIZE));
479 rd_assert((src->rl_flags & RD_LIST_F_FIXED_SIZE));
480 rd_assert(dst->rl_elemsize == src->rl_elemsize &&
481 dst->rl_size == src->rl_size);
482
483 memcpy(dst->rl_p, src->rl_p, src->rl_elemsize * src->rl_size);
484 dst->rl_cnt = src->rl_cnt;
485
486 return dst;
487 }
488
rd_list_copy_preallocated(const void * elem,void * opaque)489 void *rd_list_copy_preallocated (const void *elem, void *opaque) {
490 return rd_list_copy_preallocated0(rd_list_new(0, NULL),
491 (const rd_list_t *)elem);
492 }
493
494
495
rd_list_move(rd_list_t * dst,rd_list_t * src)496 void rd_list_move (rd_list_t *dst, rd_list_t *src) {
497 rd_list_init_copy(dst, src);
498
499 if (src->rl_flags & RD_LIST_F_FIXED_SIZE) {
500 rd_list_copy_preallocated0(dst, src);
501 } else {
502 memcpy(dst->rl_elems, src->rl_elems,
503 src->rl_cnt * sizeof(*src->rl_elems));
504 dst->rl_cnt = src->rl_cnt;
505 }
506
507 src->rl_cnt = 0;
508 }
509
510
511 /**
512 * @name Misc helpers for common list types
513 * @{
514 *
515 */
rd_list_init_int32(rd_list_t * rl,int max_size)516 rd_list_t *rd_list_init_int32 (rd_list_t *rl, int max_size) {
517 int rl_flags = rl->rl_flags & RD_LIST_F_ALLOCATED;
518 rd_list_init(rl, 0, NULL);
519 rl->rl_flags |= rl_flags;
520 rd_list_prealloc_elems(rl, sizeof(int32_t), max_size, 1/*memzero*/);
521 return rl;
522 }
523
rd_list_set_int32(rd_list_t * rl,int idx,int32_t val)524 void rd_list_set_int32 (rd_list_t *rl, int idx, int32_t val) {
525 rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) &&
526 rl->rl_elemsize == sizeof(int32_t));
527 rd_assert(idx < rl->rl_size);
528
529 memcpy(rl->rl_elems[idx], &val, sizeof(int32_t));
530
531 if (rl->rl_cnt <= idx)
532 rl->rl_cnt = idx+1;
533 }
534
rd_list_get_int32(const rd_list_t * rl,int idx)535 int32_t rd_list_get_int32 (const rd_list_t *rl, int idx) {
536 rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) &&
537 rl->rl_elemsize == sizeof(int32_t) &&
538 idx < rl->rl_cnt);
539 return *(int32_t *)rl->rl_elems[idx];
540 }
541
542
543
544
545 /**@}*/
546
547