diff options
Diffstat (limited to 'fluent-bit/lib/librdkafka-2.1.0/src/rdlist.c')
-rw-r--r-- | fluent-bit/lib/librdkafka-2.1.0/src/rdlist.c | 546 |
1 files changed, 546 insertions, 0 deletions
diff --git a/fluent-bit/lib/librdkafka-2.1.0/src/rdlist.c b/fluent-bit/lib/librdkafka-2.1.0/src/rdlist.c new file mode 100644 index 000000000..c71e3004a --- /dev/null +++ b/fluent-bit/lib/librdkafka-2.1.0/src/rdlist.c @@ -0,0 +1,546 @@ +/* + * librdkafka - Apache Kafka C library + * + * Copyright (c) 2012-2015, Magnus Edenhill + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "rd.h" +#include "rdlist.h" + + +void rd_list_dump(const char *what, const rd_list_t *rl) { + int i; + printf("%s: (rd_list_t*)%p cnt %d, size %d, elems %p:\n", what, rl, + rl->rl_cnt, rl->rl_size, rl->rl_elems); + for (i = 0; i < rl->rl_cnt; i++) + printf(" #%d: %p at &%p\n", i, rl->rl_elems[i], + &rl->rl_elems[i]); +} + +void rd_list_grow(rd_list_t *rl, size_t size) { + rd_assert(!(rl->rl_flags & RD_LIST_F_FIXED_SIZE)); + rl->rl_size += (int)size; + if (unlikely(rl->rl_size == 0)) + return; /* avoid zero allocations */ + rl->rl_elems = + rd_realloc(rl->rl_elems, sizeof(*rl->rl_elems) * rl->rl_size); +} + +rd_list_t * +rd_list_init(rd_list_t *rl, int initial_size, void (*free_cb)(void *)) { + memset(rl, 0, sizeof(*rl)); + + if (initial_size > 0) + rd_list_grow(rl, initial_size); + + rl->rl_free_cb = free_cb; + + return rl; +} + +rd_list_t *rd_list_init_copy(rd_list_t *dst, const rd_list_t *src) { + + if (src->rl_flags & RD_LIST_F_FIXED_SIZE) { + /* Source was preallocated, prealloc new dst list */ + rd_list_init(dst, 0, src->rl_free_cb); + + rd_list_prealloc_elems(dst, src->rl_elemsize, src->rl_size, + 1 /*memzero*/); + } else { + /* Source is dynamic, initialize dst the same */ + rd_list_init(dst, rd_list_cnt(src), src->rl_free_cb); + } + + return dst; +} + +static RD_INLINE rd_list_t *rd_list_alloc(void) { + return rd_malloc(sizeof(rd_list_t)); +} + +rd_list_t *rd_list_new(int initial_size, void (*free_cb)(void *)) { + rd_list_t *rl = rd_list_alloc(); + rd_list_init(rl, initial_size, free_cb); + rl->rl_flags |= RD_LIST_F_ALLOCATED; + return rl; +} + + +void rd_list_prealloc_elems(rd_list_t *rl, + size_t elemsize, + size_t cnt, + int memzero) { + size_t allocsize; + char *p; + size_t i; + + rd_assert(!rl->rl_elems); + + /* Allocation layout: + * void *ptrs[cnt]; + * elems[elemsize][cnt]; + */ + + allocsize = (sizeof(void *) * cnt) + (elemsize * cnt); + if (memzero) + rl->rl_elems = rd_calloc(1, allocsize); + else + rl->rl_elems = rd_malloc(allocsize); + + /* p points to first element's memory, unless elemsize is 0. */ + if (elemsize > 0) + p = rl->rl_p = (char *)&rl->rl_elems[cnt]; + else + p = rl->rl_p = NULL; + + /* Pointer -> elem mapping */ + for (i = 0; i < cnt; i++, p += elemsize) + rl->rl_elems[i] = p; + + rl->rl_size = (int)cnt; + rl->rl_cnt = 0; + rl->rl_flags |= RD_LIST_F_FIXED_SIZE; + rl->rl_elemsize = (int)elemsize; +} + + +void rd_list_set_cnt(rd_list_t *rl, size_t cnt) { + rd_assert(rl->rl_flags & RD_LIST_F_FIXED_SIZE); + rd_assert((int)cnt <= rl->rl_size); + rl->rl_cnt = (int)cnt; +} + + +void rd_list_free_cb(rd_list_t *rl, void *ptr) { + if (rl->rl_free_cb && ptr) + rl->rl_free_cb(ptr); +} + + +void *rd_list_add(rd_list_t *rl, void *elem) { + if (rl->rl_cnt == rl->rl_size) + rd_list_grow(rl, rl->rl_size ? rl->rl_size * 2 : 16); + rl->rl_flags &= ~RD_LIST_F_SORTED; + if (elem) + rl->rl_elems[rl->rl_cnt] = elem; + return rl->rl_elems[rl->rl_cnt++]; +} + +void rd_list_set(rd_list_t *rl, int idx, void *ptr) { + if (idx >= rl->rl_size) + rd_list_grow(rl, idx + 1); + + if (idx >= rl->rl_cnt) { + memset(&rl->rl_elems[rl->rl_cnt], 0, + sizeof(*rl->rl_elems) * (idx - rl->rl_cnt)); + rl->rl_cnt = idx + 1; + } else { + /* Not allowed to replace existing element. */ + rd_assert(!rl->rl_elems[idx]); + } + + rl->rl_elems[idx] = ptr; +} + + + +void rd_list_remove_elem(rd_list_t *rl, int idx) { + rd_assert(idx < rl->rl_cnt); + + if (idx + 1 < rl->rl_cnt) + memmove(&rl->rl_elems[idx], &rl->rl_elems[idx + 1], + sizeof(*rl->rl_elems) * (rl->rl_cnt - (idx + 1))); + rl->rl_cnt--; +} + +void *rd_list_remove(rd_list_t *rl, void *match_elem) { + void *elem; + int i; + + RD_LIST_FOREACH(elem, rl, i) { + if (elem == match_elem) { + rd_list_remove_elem(rl, i); + return elem; + } + } + + return NULL; +} + + +void *rd_list_remove_cmp(rd_list_t *rl, + void *match_elem, + int (*cmp)(void *_a, void *_b)) { + void *elem; + int i; + + RD_LIST_FOREACH(elem, rl, i) { + if (elem == match_elem || !cmp(elem, match_elem)) { + rd_list_remove_elem(rl, i); + return elem; + } + } + + return NULL; +} + + +int rd_list_remove_multi_cmp(rd_list_t *rl, + void *match_elem, + int (*cmp)(void *_a, void *_b)) { + + void *elem; + int i; + int cnt = 0; + + /* Scan backwards to minimize memmoves */ + RD_LIST_FOREACH_REVERSE(elem, rl, i) { + if (match_elem == cmp || !cmp(elem, match_elem)) { + rd_list_remove_elem(rl, i); + cnt++; + } + } + + return cnt; +} + + +void *rd_list_pop(rd_list_t *rl) { + void *elem; + int idx = rl->rl_cnt - 1; + + if (idx < 0) + return NULL; + + elem = rl->rl_elems[idx]; + rd_list_remove_elem(rl, idx); + + return elem; +} + + +/** + * Trampoline to avoid the double pointers in callbacks. + * + * rl_elems is a **, but to avoid having the application do the cumbersome + * ** -> * casting we wrap this here and provide a simple * pointer to the + * the callbacks. + * + * This is true for all list comparator uses, i.e., both sort() and find(). + */ +static RD_TLS int (*rd_list_cmp_curr)(const void *, const void *); + +static RD_INLINE int rd_list_cmp_trampoline(const void *_a, const void *_b) { + const void *a = *(const void **)_a, *b = *(const void **)_b; + + return rd_list_cmp_curr(a, b); +} + +void rd_list_sort(rd_list_t *rl, int (*cmp)(const void *, const void *)) { + if (unlikely(rl->rl_elems == NULL)) + return; + + rd_list_cmp_curr = cmp; + qsort(rl->rl_elems, rl->rl_cnt, sizeof(*rl->rl_elems), + rd_list_cmp_trampoline); + rl->rl_flags |= RD_LIST_F_SORTED; +} + +static void rd_list_destroy_elems(rd_list_t *rl) { + int i; + + if (!rl->rl_elems) + return; + + if (rl->rl_free_cb) { + /* Free in reverse order to allow deletions */ + for (i = rl->rl_cnt - 1; i >= 0; i--) + if (rl->rl_elems[i]) + rl->rl_free_cb(rl->rl_elems[i]); + } + + rd_free(rl->rl_elems); + rl->rl_elems = NULL; + rl->rl_cnt = 0; + rl->rl_size = 0; + rl->rl_flags &= ~RD_LIST_F_SORTED; +} + + +void rd_list_clear(rd_list_t *rl) { + rd_list_destroy_elems(rl); +} + + +void rd_list_destroy(rd_list_t *rl) { + rd_list_destroy_elems(rl); + if (rl->rl_flags & RD_LIST_F_ALLOCATED) + rd_free(rl); +} + +void rd_list_destroy_free(void *rl) { + rd_list_destroy((rd_list_t *)rl); +} + +void *rd_list_elem(const rd_list_t *rl, int idx) { + if (likely(idx < rl->rl_cnt)) + return (void *)rl->rl_elems[idx]; + return NULL; +} + +int rd_list_index(const rd_list_t *rl, + const void *match, + int (*cmp)(const void *, const void *)) { + int i; + const void *elem; + + RD_LIST_FOREACH(elem, rl, i) { + if (!cmp(match, elem)) + return i; + } + + return -1; +} + + +void *rd_list_find(const rd_list_t *rl, + const void *match, + int (*cmp)(const void *, const void *)) { + int i; + const void *elem; + + if (rl->rl_flags & RD_LIST_F_SORTED) { + void **r; + rd_list_cmp_curr = cmp; + r = bsearch(&match /*ptrptr to match elems*/, rl->rl_elems, + rl->rl_cnt, sizeof(*rl->rl_elems), + rd_list_cmp_trampoline); + return r ? *r : NULL; + } + + RD_LIST_FOREACH(elem, rl, i) { + if (!cmp(match, elem)) + return (void *)elem; + } + + return NULL; +} + + +void *rd_list_first(const rd_list_t *rl) { + if (rl->rl_cnt == 0) + return NULL; + return rl->rl_elems[0]; +} + +void *rd_list_last(const rd_list_t *rl) { + if (rl->rl_cnt == 0) + return NULL; + return rl->rl_elems[rl->rl_cnt - 1]; +} + + +void *rd_list_find_duplicate(const rd_list_t *rl, + int (*cmp)(const void *, const void *)) { + int i; + + rd_assert(rl->rl_flags & RD_LIST_F_SORTED); + + for (i = 1; i < rl->rl_cnt; i++) { + if (!cmp(rl->rl_elems[i - 1], rl->rl_elems[i])) + return rl->rl_elems[i]; + } + + return NULL; +} + +int rd_list_cmp(const rd_list_t *a, + const rd_list_t *b, + int (*cmp)(const void *, const void *)) { + int i; + + i = RD_CMP(a->rl_cnt, b->rl_cnt); + if (i) + return i; + + for (i = 0; i < a->rl_cnt; i++) { + int r = cmp(a->rl_elems[i], b->rl_elems[i]); + if (r) + return r; + } + + return 0; +} + + +/** + * @brief Simple element pointer comparator + */ +int rd_list_cmp_ptr(const void *a, const void *b) { + return RD_CMP(a, b); +} + +int rd_list_cmp_str(const void *a, const void *b) { + return strcmp((const char *)a, (const char *)b); +} + +void rd_list_apply(rd_list_t *rl, + int (*cb)(void *elem, void *opaque), + void *opaque) { + void *elem; + int i; + + RD_LIST_FOREACH(elem, rl, i) { + if (!cb(elem, opaque)) { + rd_list_remove_elem(rl, i); + i--; + } + } + + return; +} + + +/** + * @brief Default element copier that simply assigns the original pointer. + */ +static void *rd_list_nocopy_ptr(const void *elem, void *opaque) { + return (void *)elem; +} + +rd_list_t * +rd_list_copy(const rd_list_t *src, rd_list_copy_cb_t *copy_cb, void *opaque) { + rd_list_t *dst; + + dst = rd_list_new(src->rl_cnt, src->rl_free_cb); + + rd_list_copy_to(dst, src, copy_cb, opaque); + return dst; +} + + +void rd_list_copy_to(rd_list_t *dst, + const rd_list_t *src, + void *(*copy_cb)(const void *elem, void *opaque), + void *opaque) { + void *elem; + int i; + + rd_assert(dst != src); + + if (!copy_cb) + copy_cb = rd_list_nocopy_ptr; + + RD_LIST_FOREACH(elem, src, i) { + void *celem = copy_cb(elem, opaque); + if (celem) + rd_list_add(dst, celem); + } +} + + +/** + * @brief Copy elements of preallocated \p src to preallocated \p dst. + * + * @remark \p dst will be overwritten and initialized, but its + * flags will be retained. + * + * @returns \p dst + */ +static rd_list_t *rd_list_copy_preallocated0(rd_list_t *dst, + const rd_list_t *src) { + int dst_flags = dst->rl_flags & RD_LIST_F_ALLOCATED; + + rd_assert(dst != src); + + rd_list_init_copy(dst, src); + dst->rl_flags |= dst_flags; + + rd_assert((dst->rl_flags & RD_LIST_F_FIXED_SIZE)); + rd_assert((src->rl_flags & RD_LIST_F_FIXED_SIZE)); + rd_assert(dst->rl_elemsize == src->rl_elemsize && + dst->rl_size == src->rl_size); + + memcpy(dst->rl_p, src->rl_p, src->rl_elemsize * src->rl_size); + dst->rl_cnt = src->rl_cnt; + + return dst; +} + +void *rd_list_copy_preallocated(const void *elem, void *opaque) { + return rd_list_copy_preallocated0(rd_list_new(0, NULL), + (const rd_list_t *)elem); +} + + + +void rd_list_move(rd_list_t *dst, rd_list_t *src) { + rd_list_init_copy(dst, src); + + if (src->rl_flags & RD_LIST_F_FIXED_SIZE) { + rd_list_copy_preallocated0(dst, src); + } else { + memcpy(dst->rl_elems, src->rl_elems, + src->rl_cnt * sizeof(*src->rl_elems)); + dst->rl_cnt = src->rl_cnt; + } + + src->rl_cnt = 0; +} + + +/** + * @name Misc helpers for common list types + * @{ + * + */ +rd_list_t *rd_list_init_int32(rd_list_t *rl, int max_size) { + int rl_flags = rl->rl_flags & RD_LIST_F_ALLOCATED; + rd_list_init(rl, 0, NULL); + rl->rl_flags |= rl_flags; + rd_list_prealloc_elems(rl, sizeof(int32_t), max_size, 1 /*memzero*/); + return rl; +} + +void rd_list_set_int32(rd_list_t *rl, int idx, int32_t val) { + rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) && + rl->rl_elemsize == sizeof(int32_t)); + rd_assert(idx < rl->rl_size); + + memcpy(rl->rl_elems[idx], &val, sizeof(int32_t)); + + if (rl->rl_cnt <= idx) + rl->rl_cnt = idx + 1; +} + +int32_t rd_list_get_int32(const rd_list_t *rl, int idx) { + rd_assert((rl->rl_flags & RD_LIST_F_FIXED_SIZE) && + rl->rl_elemsize == sizeof(int32_t) && idx < rl->rl_cnt); + return *(int32_t *)rl->rl_elems[idx]; +} + + + +/**@}*/ |