/*
* 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_new (int initial_size, void (*free_cb) (void *)) {
rd_list_t *rl = malloc(sizeof(*rl));
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 size) {
size_t allocsize;
char *p;
size_t i;
rd_assert(!rl->rl_elems);
/* Allocation layout:
* void *ptrs[cnt];
* elems[elemsize][cnt];
*/
allocsize = (sizeof(void *) * size) + (elemsize * size);
rl->rl_elems = rd_malloc(allocsize);
/* p points to first element's memory. */
p = (char *)&rl->rl_elems[size];
/* Pointer -> elem mapping */
for (i = 0 ; i < size ; i++, p += elemsize)
rl->rl_elems[i] = p;
rl->rl_size = (int)size;
rl->rl_cnt = 0;
rl->rl_flags |= RD_LIST_F_FIXED_SIZE;
}
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_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;
}
/**
* 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 *)) {
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;
}
void rd_list_clear (rd_list_t *rl) {
rl->rl_cnt = 0;
rl->rl_flags &= ~RD_LIST_F_SORTED;
}
void rd_list_destroy (rd_list_t *rl) {
if (rl->rl_elems) {
int i;
if (rl->rl_free_cb) {
for (i = 0 ; i < rl->rl_cnt ; i++)
if (rl->rl_elems[i])
rl->rl_free_cb(rl->rl_elems[i]);
}
rd_free(rl->rl_elems);
}
if (rl->rl_flags & RD_LIST_F_ALLOCATED)
rd_free(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;
}
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;
}
int rd_list_cmp (const rd_list_t *a, rd_list_t *b,
int (*cmp) (const void *, const void *)) {
int i;
i = 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) {
if (a < b)
return -1;
else if (a > b)
return 1;
return 0;
}
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,
void *(*copy_cb) (const void *elem, void *opaque),
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;
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);
}
}