1/*
2 * librd - Rapid Development C library
3 *
4 * Copyright (c) 2012-2016, 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 "rdkafka_int.h"
30#include "rdavl.h"
31
32/*
33 * AVL tree.
34 * Inspired by Ian Piumarta's tree.h implementation.
35 */
36
37#define RD_AVL_NODE_HEIGHT(ran) ((ran) ? (ran)->ran_height : 0)
38
39#define RD_AVL_NODE_DELTA(ran) \
40 (RD_AVL_NODE_HEIGHT((ran)->ran_p[RD_AVL_LEFT]) - \
41 RD_AVL_NODE_HEIGHT((ran)->ran_p[RD_AVL_RIGHT]))
42
43#define RD_DELTA_MAX 1
44
45
46static rd_avl_node_t *rd_avl_balance_node (rd_avl_node_t *ran);
47
48static rd_avl_node_t *rd_avl_rotate (rd_avl_node_t *ran, rd_avl_dir_t dir) {
49 rd_avl_node_t *n;
50 static const rd_avl_dir_t odirmap[] = { /* opposite direction map */
51 [RD_AVL_RIGHT] = RD_AVL_LEFT,
52 [RD_AVL_LEFT] = RD_AVL_RIGHT
53 };
54 const int odir = odirmap[dir];
55
56 n = ran->ran_p[odir];
57 ran->ran_p[odir] = n->ran_p[dir];
58 n->ran_p[dir] = rd_avl_balance_node(ran);
59
60 return rd_avl_balance_node(n);
61}
62
63static rd_avl_node_t *rd_avl_balance_node (rd_avl_node_t *ran) {
64 const int d = RD_AVL_NODE_DELTA(ran);
65 int h;
66
67 if (d < -RD_DELTA_MAX) {
68 if (RD_AVL_NODE_DELTA(ran->ran_p[RD_AVL_RIGHT]) > 0)
69 ran->ran_p[RD_AVL_RIGHT] =
70 rd_avl_rotate(ran->ran_p[RD_AVL_RIGHT],
71 RD_AVL_RIGHT);
72 return rd_avl_rotate(ran, RD_AVL_LEFT);
73
74 } else if (d > RD_DELTA_MAX) {
75 if (RD_AVL_NODE_DELTA(ran->ran_p[RD_AVL_LEFT]) < 0)
76 ran->ran_p[RD_AVL_LEFT] =
77 rd_avl_rotate(ran->ran_p[RD_AVL_LEFT],
78 RD_AVL_LEFT);
79
80 return rd_avl_rotate(ran, RD_AVL_RIGHT);
81 }
82
83 ran->ran_height = 0;
84
85 if ((h = RD_AVL_NODE_HEIGHT(ran->ran_p[RD_AVL_LEFT])) > ran->ran_height)
86 ran->ran_height = h;
87
88 if ((h = RD_AVL_NODE_HEIGHT(ran->ran_p[RD_AVL_RIGHT])) >ran->ran_height)
89 ran->ran_height = h;
90
91 ran->ran_height++;
92
93 return ran;
94}
95
96rd_avl_node_t *rd_avl_insert_node (rd_avl_t *ravl,
97 rd_avl_node_t *parent,
98 rd_avl_node_t *ran,
99 rd_avl_node_t **existing) {
100 rd_avl_dir_t dir;
101 int r;
102
103 if (!parent)
104 return ran;
105
106 if ((r = ravl->ravl_cmp(ran->ran_elm, parent->ran_elm)) == 0) {
107 /* Replace existing node with new one. */
108 ran->ran_p[RD_AVL_LEFT] = parent->ran_p[RD_AVL_LEFT];
109 ran->ran_p[RD_AVL_RIGHT] = parent->ran_p[RD_AVL_RIGHT];
110 ran->ran_height = parent->ran_height;
111 *existing = parent;
112 return ran;
113 }
114
115 if (r < 0)
116 dir = RD_AVL_LEFT;
117 else
118 dir = RD_AVL_RIGHT;
119
120 parent->ran_p[dir] = rd_avl_insert_node(ravl, parent->ran_p[dir],
121 ran, existing);
122 return rd_avl_balance_node(parent);
123}
124
125
126static rd_avl_node_t *rd_avl_move (rd_avl_node_t *dst, rd_avl_node_t *src,
127 rd_avl_dir_t dir) {
128
129 if (!dst)
130 return src;
131
132 dst->ran_p[dir] = rd_avl_move(dst->ran_p[dir], src, dir);
133
134 return rd_avl_balance_node(dst);
135}
136
137static rd_avl_node_t *rd_avl_remove_node0 (rd_avl_node_t *ran) {
138 rd_avl_node_t *tmp;
139
140 tmp = rd_avl_move(ran->ran_p[RD_AVL_LEFT],
141 ran->ran_p[RD_AVL_RIGHT],
142 RD_AVL_RIGHT);
143
144 ran->ran_p[RD_AVL_LEFT] = ran->ran_p[RD_AVL_RIGHT] = NULL;
145 return tmp;
146}
147
148
149rd_avl_node_t *rd_avl_remove_elm0 (rd_avl_t *ravl, rd_avl_node_t *parent,
150 const void *elm) {
151 rd_avl_dir_t dir;
152 int r;
153
154 if (!parent)
155 return NULL;
156
157
158 if ((r = ravl->ravl_cmp(elm, parent->ran_elm)) == 0)
159 return rd_avl_remove_node0(parent);
160 else if (r < 0)
161 dir = RD_AVL_LEFT;
162 else /* > 0 */
163 dir = RD_AVL_RIGHT;
164
165 parent->ran_p[dir] =
166 rd_avl_remove_elm0(ravl, parent->ran_p[dir], elm);
167
168 return rd_avl_balance_node(parent);
169}
170
171
172
173rd_avl_node_t *rd_avl_find_node (const rd_avl_t *ravl,
174 const rd_avl_node_t *begin,
175 const void *elm) {
176 int r;
177
178 if (!begin)
179 return NULL;
180 else if (!(r = ravl->ravl_cmp(elm, begin->ran_elm)))
181 return (rd_avl_node_t *)begin;
182 else if (r < 0)
183 return rd_avl_find_node(ravl, begin->ran_p[RD_AVL_LEFT], elm);
184 else /* r > 0 */
185 return rd_avl_find_node(ravl, begin->ran_p[RD_AVL_RIGHT], elm);
186}
187
188
189
190void rd_avl_destroy (rd_avl_t *ravl) {
191 if (ravl->ravl_flags & RD_AVL_F_LOCKS)
192 rwlock_destroy(&ravl->ravl_rwlock);
193
194 if (ravl->ravl_flags & RD_AVL_F_OWNER)
195 free(ravl);
196}
197
198rd_avl_t *rd_avl_init (rd_avl_t *ravl, rd_avl_cmp_t cmp, int flags) {
199
200 if (!ravl) {
201 ravl = calloc(1, sizeof(*ravl));
202 flags |= RD_AVL_F_OWNER;
203 } else {
204 memset(ravl, 0, sizeof(*ravl));
205 }
206
207 ravl->ravl_flags = flags;
208 ravl->ravl_cmp = cmp;
209
210 if (flags & RD_AVL_F_LOCKS)
211 rwlock_init(&ravl->ravl_rwlock);
212
213 return ravl;
214}
215