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, 0 insertions, 210 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 deleted file mode 100644 index f25251de8..000000000 --- a/fluent-bit/lib/librdkafka-2.1.0/src/rdavl.c +++ /dev/null @@ -1,210 +0,0 @@ -/* - * 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; -} |