diff options
Diffstat (limited to 'fluent-bit/lib/librdkafka-2.1.0/src/rdavl.c')
| -rw-r--r-- | fluent-bit/lib/librdkafka-2.1.0/src/rdavl.c | 210 |
1 files changed, 210 insertions, 0 deletions
diff --git a/fluent-bit/lib/librdkafka-2.1.0/src/rdavl.c b/fluent-bit/lib/librdkafka-2.1.0/src/rdavl.c new file mode 100644 index 000000000..f25251de8 --- /dev/null +++ b/fluent-bit/lib/librdkafka-2.1.0/src/rdavl.c @@ -0,0 +1,210 @@ +/* + * librd - Rapid Development C library + * + * Copyright (c) 2012-2016, 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 "rdkafka_int.h" +#include "rdavl.h" + +/* + * AVL tree. + * Inspired by Ian Piumarta's tree.h implementation. + */ + +#define RD_AVL_NODE_HEIGHT(ran) ((ran) ? (ran)->ran_height : 0) + +#define RD_AVL_NODE_DELTA(ran) \ + (RD_AVL_NODE_HEIGHT((ran)->ran_p[RD_AVL_LEFT]) - \ + RD_AVL_NODE_HEIGHT((ran)->ran_p[RD_AVL_RIGHT])) + +#define RD_DELTA_MAX 1 + + +static rd_avl_node_t *rd_avl_balance_node(rd_avl_node_t *ran); + +static rd_avl_node_t *rd_avl_rotate(rd_avl_node_t *ran, rd_avl_dir_t dir) { + rd_avl_node_t *n; + static const rd_avl_dir_t odirmap[] = {/* opposite direction map */ + [RD_AVL_RIGHT] = RD_AVL_LEFT, + [RD_AVL_LEFT] = RD_AVL_RIGHT}; + const int odir = odirmap[dir]; + + n = ran->ran_p[odir]; + ran->ran_p[odir] = n->ran_p[dir]; + n->ran_p[dir] = rd_avl_balance_node(ran); + + return rd_avl_balance_node(n); +} + +static rd_avl_node_t *rd_avl_balance_node(rd_avl_node_t *ran) { + const int d = RD_AVL_NODE_DELTA(ran); + int h; + + if (d < -RD_DELTA_MAX) { + if (RD_AVL_NODE_DELTA(ran->ran_p[RD_AVL_RIGHT]) > 0) + ran->ran_p[RD_AVL_RIGHT] = rd_avl_rotate( + ran->ran_p[RD_AVL_RIGHT], RD_AVL_RIGHT); + return rd_avl_rotate(ran, RD_AVL_LEFT); + + } else if (d > RD_DELTA_MAX) { + if (RD_AVL_NODE_DELTA(ran->ran_p[RD_AVL_LEFT]) < 0) + ran->ran_p[RD_AVL_LEFT] = + rd_avl_rotate(ran->ran_p[RD_AVL_LEFT], RD_AVL_LEFT); + + return rd_avl_rotate(ran, RD_AVL_RIGHT); + } + + ran->ran_height = 0; + + if ((h = RD_AVL_NODE_HEIGHT(ran->ran_p[RD_AVL_LEFT])) > ran->ran_height) + ran->ran_height = h; + + if ((h = RD_AVL_NODE_HEIGHT(ran->ran_p[RD_AVL_RIGHT])) > + ran->ran_height) + ran->ran_height = h; + + ran->ran_height++; + + return ran; +} + +rd_avl_node_t *rd_avl_insert_node(rd_avl_t *ravl, + rd_avl_node_t *parent, + rd_avl_node_t *ran, + rd_avl_node_t **existing) { + rd_avl_dir_t dir; + int r; + + if (!parent) + return ran; + + if ((r = ravl->ravl_cmp(ran->ran_elm, parent->ran_elm)) == 0) { + /* Replace existing node with new one. */ + ran->ran_p[RD_AVL_LEFT] = parent->ran_p[RD_AVL_LEFT]; + ran->ran_p[RD_AVL_RIGHT] = parent->ran_p[RD_AVL_RIGHT]; + ran->ran_height = parent->ran_height; + *existing = parent; + return ran; + } + + if (r < 0) + dir = RD_AVL_LEFT; + else + dir = RD_AVL_RIGHT; + + parent->ran_p[dir] = + rd_avl_insert_node(ravl, parent->ran_p[dir], ran, existing); + return rd_avl_balance_node(parent); +} + + +static rd_avl_node_t * +rd_avl_move(rd_avl_node_t *dst, rd_avl_node_t *src, rd_avl_dir_t dir) { + + if (!dst) + return src; + + dst->ran_p[dir] = rd_avl_move(dst->ran_p[dir], src, dir); + + return rd_avl_balance_node(dst); +} + +static rd_avl_node_t *rd_avl_remove_node0(rd_avl_node_t *ran) { + rd_avl_node_t *tmp; + + tmp = rd_avl_move(ran->ran_p[RD_AVL_LEFT], ran->ran_p[RD_AVL_RIGHT], + RD_AVL_RIGHT); + + ran->ran_p[RD_AVL_LEFT] = ran->ran_p[RD_AVL_RIGHT] = NULL; + return tmp; +} + + +rd_avl_node_t * +rd_avl_remove_elm0(rd_avl_t *ravl, rd_avl_node_t *parent, const void *elm) { + rd_avl_dir_t dir; + int r; + + if (!parent) + return NULL; + + + if ((r = ravl->ravl_cmp(elm, parent->ran_elm)) == 0) + return rd_avl_remove_node0(parent); + else if (r < 0) + dir = RD_AVL_LEFT; + else /* > 0 */ + dir = RD_AVL_RIGHT; + + parent->ran_p[dir] = rd_avl_remove_elm0(ravl, parent->ran_p[dir], elm); + + return rd_avl_balance_node(parent); +} + + + +rd_avl_node_t *rd_avl_find_node(const rd_avl_t *ravl, + const rd_avl_node_t *begin, + const void *elm) { + int r; + + if (!begin) + return NULL; + else if (!(r = ravl->ravl_cmp(elm, begin->ran_elm))) + return (rd_avl_node_t *)begin; + else if (r < 0) + return rd_avl_find_node(ravl, begin->ran_p[RD_AVL_LEFT], elm); + else /* r > 0 */ + return rd_avl_find_node(ravl, begin->ran_p[RD_AVL_RIGHT], elm); +} + + + +void rd_avl_destroy(rd_avl_t *ravl) { + if (ravl->ravl_flags & RD_AVL_F_LOCKS) + rwlock_destroy(&ravl->ravl_rwlock); + + if (ravl->ravl_flags & RD_AVL_F_OWNER) + rd_free(ravl); +} + +rd_avl_t *rd_avl_init(rd_avl_t *ravl, rd_avl_cmp_t cmp, int flags) { + + if (!ravl) { + ravl = rd_calloc(1, sizeof(*ravl)); + flags |= RD_AVL_F_OWNER; + } else { + memset(ravl, 0, sizeof(*ravl)); + } + + ravl->ravl_flags = flags; + ravl->ravl_cmp = cmp; + + if (flags & RD_AVL_F_LOCKS) + rwlock_init(&ravl->ravl_rwlock); + + return ravl; +} |