File: | src/usr.sbin/smtpd/smtpd/../expand.c |
Warning: | line 100, column 3 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: expand.c,v 1.32 2021/06/14 17:58:15 eric Exp $ */ | |||
2 | ||||
3 | /* | |||
4 | * Copyright (c) 2009 Gilles Chehade <gilles@poolp.org> | |||
5 | * Copyright (c) 2012 Eric Faurot <eric@openbsd.org> | |||
6 | * | |||
7 | * Permission to use, copy, modify, and distribute this software for any | |||
8 | * purpose with or without fee is hereby granted, provided that the above | |||
9 | * copyright notice and this permission notice appear in all copies. | |||
10 | * | |||
11 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |||
12 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |||
13 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |||
14 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |||
15 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |||
16 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |||
17 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |||
18 | */ | |||
19 | ||||
20 | #include <stdlib.h> | |||
21 | #include <string.h> | |||
22 | ||||
23 | #include "smtpd.h" | |||
24 | ||||
25 | static const char *expandnode_info(struct expandnode *); | |||
26 | ||||
27 | struct expandnode * | |||
28 | expand_lookup(struct expand *expand, struct expandnode *key) | |||
29 | { | |||
30 | return RB_FIND(expandtree, &expand->tree, key)expandtree_RB_FIND(&expand->tree, key); | |||
31 | } | |||
32 | ||||
33 | int | |||
34 | expand_to_text(struct expand *expand, char *buf, size_t sz) | |||
35 | { | |||
36 | struct expandnode *xn; | |||
37 | ||||
38 | buf[0] = '\0'; | |||
39 | ||||
40 | RB_FOREACH(xn, expandtree, &expand->tree)for ((xn) = expandtree_RB_MINMAX(&expand->tree, -1); ( xn) != ((void *)0); (xn) = expandtree_RB_NEXT(xn)) { | |||
41 | if (buf[0]) | |||
42 | (void)strlcat(buf, ", ", sz); | |||
43 | if (strlcat(buf, expandnode_to_text(xn), sz) >= sz) | |||
44 | return 0; | |||
45 | } | |||
46 | ||||
47 | return 1; | |||
48 | } | |||
49 | ||||
50 | void | |||
51 | expand_insert(struct expand *expand, struct expandnode *node) | |||
52 | { | |||
53 | struct expandnode *xn; | |||
54 | ||||
55 | node->rule = expand->rule; | |||
56 | node->parent = expand->parent; | |||
57 | ||||
58 | log_trace(TRACE_EXPAND, "expand: %p: expand_insert() called for %s",do { if (tracing & (0x1000)) log_trace0("expand: %p: expand_insert() called for %s" , expand, expandnode_info(node)); } while (0) | |||
59 | expand, expandnode_info(node))do { if (tracing & (0x1000)) log_trace0("expand: %p: expand_insert() called for %s" , expand, expandnode_info(node)); } while (0); | |||
60 | if (node->type == EXPAND_USERNAME && | |||
61 | expand->parent && | |||
62 | expand->parent->type == EXPAND_USERNAME && | |||
63 | !strcmp(expand->parent->u.user, node->u.user)) { | |||
64 | log_trace(TRACE_EXPAND, "expand: %p: setting sameuser = 1",do { if (tracing & (0x1000)) log_trace0("expand: %p: setting sameuser = 1" , expand); } while (0) | |||
65 | expand)do { if (tracing & (0x1000)) log_trace0("expand: %p: setting sameuser = 1" , expand); } while (0); | |||
66 | node->sameuser = 1; | |||
67 | } | |||
68 | ||||
69 | if (expand_lookup(expand, node)) { | |||
70 | log_trace(TRACE_EXPAND, "expand: %p: node found, discarding",do { if (tracing & (0x1000)) log_trace0("expand: %p: node found, discarding" , expand); } while (0) | |||
71 | expand)do { if (tracing & (0x1000)) log_trace0("expand: %p: node found, discarding" , expand); } while (0); | |||
72 | return; | |||
73 | } | |||
74 | ||||
75 | xn = xmemdup(node, sizeof *xn); | |||
76 | xn->rule = expand->rule; | |||
77 | xn->parent = expand->parent; | |||
78 | if (xn->parent) | |||
79 | xn->depth = xn->parent->depth + 1; | |||
80 | else | |||
81 | xn->depth = 0; | |||
82 | RB_INSERT(expandtree, &expand->tree, xn)expandtree_RB_INSERT(&expand->tree, xn); | |||
83 | if (expand->queue) | |||
84 | TAILQ_INSERT_TAIL(expand->queue, xn, tq_entry)do { (xn)->tq_entry.tqe_next = ((void *)0); (xn)->tq_entry .tqe_prev = (expand->queue)->tqh_last; *(expand->queue )->tqh_last = (xn); (expand->queue)->tqh_last = & (xn)->tq_entry.tqe_next; } while (0); | |||
85 | expand->nb_nodes++; | |||
86 | log_trace(TRACE_EXPAND, "expand: %p: inserted node %p", expand, xn)do { if (tracing & (0x1000)) log_trace0("expand: %p: inserted node %p" , expand, xn); } while (0); | |||
87 | } | |||
88 | ||||
89 | void | |||
90 | expand_clear(struct expand *expand) | |||
91 | { | |||
92 | struct expandnode *xn; | |||
93 | ||||
94 | log_trace(TRACE_EXPAND, "expand: %p: clearing expand tree", expand)do { if (tracing & (0x1000)) log_trace0("expand: %p: clearing expand tree" , expand); } while (0); | |||
95 | if (expand->queue) | |||
96 | while ((xn = TAILQ_FIRST(expand->queue)((expand->queue)->tqh_first))) | |||
97 | TAILQ_REMOVE(expand->queue, xn, tq_entry)do { if (((xn)->tq_entry.tqe_next) != ((void *)0)) (xn)-> tq_entry.tqe_next->tq_entry.tqe_prev = (xn)->tq_entry.tqe_prev ; else (expand->queue)->tqh_last = (xn)->tq_entry.tqe_prev ; *(xn)->tq_entry.tqe_prev = (xn)->tq_entry.tqe_next; ; ; } while (0); | |||
98 | ||||
99 | while ((xn = RB_ROOT(&expand->tree)(&expand->tree)->rbh_root) != NULL((void *)0)) { | |||
100 | RB_REMOVE(expandtree, &expand->tree, xn)expandtree_RB_REMOVE(&expand->tree, xn); | |||
| ||||
101 | free(xn); | |||
102 | } | |||
103 | } | |||
104 | ||||
105 | void | |||
106 | expand_free(struct expand *expand) | |||
107 | { | |||
108 | expand_clear(expand); | |||
| ||||
109 | ||||
110 | log_trace(TRACE_EXPAND, "expand: %p: freeing expand tree", expand)do { if (tracing & (0x1000)) log_trace0("expand: %p: freeing expand tree" , expand); } while (0); | |||
111 | free(expand); | |||
112 | } | |||
113 | ||||
114 | int | |||
115 | expand_cmp(struct expandnode *e1, struct expandnode *e2) | |||
116 | { | |||
117 | struct expandnode *p1, *p2; | |||
118 | int r; | |||
119 | ||||
120 | if (e1->type < e2->type) | |||
121 | return -1; | |||
122 | if (e1->type > e2->type) | |||
123 | return 1; | |||
124 | if (e1->sameuser < e2->sameuser) | |||
125 | return -1; | |||
126 | if (e1->sameuser > e2->sameuser) | |||
127 | return 1; | |||
128 | if (e1->realuser < e2->realuser) | |||
129 | return -1; | |||
130 | if (e1->realuser > e2->realuser) | |||
131 | return 1; | |||
132 | ||||
133 | r = memcmp(&e1->u, &e2->u, sizeof(e1->u)); | |||
134 | if (r) | |||
135 | return (r); | |||
136 | ||||
137 | if (e1->parent == e2->parent) | |||
138 | return (0); | |||
139 | ||||
140 | if (e1->parent == NULL((void *)0)) | |||
141 | return (-1); | |||
142 | if (e2->parent == NULL((void *)0)) | |||
143 | return (1); | |||
144 | ||||
145 | /* | |||
146 | * The same node can be expanded in for different dest context. | |||
147 | * Wen need to distinguish between those. | |||
148 | */ | |||
149 | for(p1 = e1->parent; p1->type != EXPAND_ADDRESS; p1 = p1->parent) | |||
150 | ; | |||
151 | for(p2 = e2->parent; p2->type != EXPAND_ADDRESS; p2 = p2->parent) | |||
152 | ; | |||
153 | if (p1 < p2) | |||
154 | return (-1); | |||
155 | if (p1 > p2) | |||
156 | return (1); | |||
157 | ||||
158 | if (e1->type != EXPAND_FILENAME && e1->type != EXPAND_FILTER) | |||
159 | return (0); | |||
160 | ||||
161 | /* | |||
162 | * For external delivery, we need to distinguish between users. | |||
163 | * If we can't find a username, we assume it is _smtpd. | |||
164 | */ | |||
165 | for(p1 = e1->parent; p1 && p1->type != EXPAND_USERNAME; p1 = p1->parent) | |||
166 | ; | |||
167 | for(p2 = e2->parent; p2 && p2->type != EXPAND_USERNAME; p2 = p2->parent) | |||
168 | ; | |||
169 | if (p1 < p2) | |||
170 | return (-1); | |||
171 | if (p1 > p2) | |||
172 | return (1); | |||
173 | ||||
174 | return (0); | |||
175 | } | |||
176 | ||||
177 | static int | |||
178 | expand_line_split(char **line, char **ret) | |||
179 | { | |||
180 | static char buffer[LINE_MAX2048]; | |||
181 | int esc, dq, sq; | |||
182 | size_t i; | |||
183 | char *s; | |||
184 | ||||
185 | memset(buffer, 0, sizeof buffer); | |||
186 | esc = dq = sq = 0; | |||
187 | i = 0; | |||
188 | for (s = *line; (*s) && (i < sizeof(buffer)); ++s) { | |||
189 | if (esc) { | |||
190 | buffer[i++] = *s; | |||
191 | esc = 0; | |||
192 | continue; | |||
193 | } | |||
194 | if (*s == '\\') { | |||
195 | esc = 1; | |||
196 | continue; | |||
197 | } | |||
198 | if (*s == ',' && !dq && !sq) { | |||
199 | *ret = buffer; | |||
200 | *line = s+1; | |||
201 | return (1); | |||
202 | } | |||
203 | ||||
204 | buffer[i++] = *s; | |||
205 | esc = 0; | |||
206 | ||||
207 | if (*s == '"' && !sq) | |||
208 | dq ^= 1; | |||
209 | if (*s == '\'' && !dq) | |||
210 | sq ^= 1; | |||
211 | } | |||
212 | ||||
213 | if (esc || dq || sq || i == sizeof(buffer)) | |||
214 | return (-1); | |||
215 | ||||
216 | *ret = buffer; | |||
217 | *line = s; | |||
218 | return (i ? 1 : 0); | |||
219 | } | |||
220 | ||||
221 | int | |||
222 | expand_line(struct expand *expand, const char *s, int do_includes) | |||
223 | { | |||
224 | struct expandnode xn; | |||
225 | char buffer[LINE_MAX2048]; | |||
226 | char *p, *subrcpt; | |||
227 | int ret; | |||
228 | ||||
229 | memset(buffer, 0, sizeof buffer); | |||
230 | if (strlcpy(buffer, s, sizeof buffer) >= sizeof buffer) | |||
231 | return 0; | |||
232 | ||||
233 | p = buffer; | |||
234 | while ((ret = expand_line_split(&p, &subrcpt)) > 0) { | |||
235 | subrcpt = strip(subrcpt); | |||
236 | if (subrcpt[0] == '\0') | |||
237 | continue; | |||
238 | if (!text_to_expandnode(&xn, subrcpt)) | |||
239 | return 0; | |||
240 | if (!do_includes) | |||
241 | if (xn.type == EXPAND_INCLUDE) | |||
242 | continue; | |||
243 | expand_insert(expand, &xn); | |||
244 | } | |||
245 | ||||
246 | if (ret >= 0) | |||
247 | return 1; | |||
248 | ||||
249 | /* expand_line_split() returned < 0 */ | |||
250 | return 0; | |||
251 | } | |||
252 | ||||
253 | static const char * | |||
254 | expandnode_info(struct expandnode *e) | |||
255 | { | |||
256 | static char buffer[1024]; | |||
257 | const char *type = NULL((void *)0); | |||
258 | const char *value = NULL((void *)0); | |||
259 | char tmp[64]; | |||
260 | ||||
261 | switch (e->type) { | |||
262 | case EXPAND_FILTER: | |||
263 | type = "filter"; | |||
264 | break; | |||
265 | case EXPAND_FILENAME: | |||
266 | type = "filename"; | |||
267 | break; | |||
268 | case EXPAND_INCLUDE: | |||
269 | type = "include"; | |||
270 | break; | |||
271 | case EXPAND_USERNAME: | |||
272 | type = "username"; | |||
273 | break; | |||
274 | case EXPAND_ADDRESS: | |||
275 | type = "address"; | |||
276 | break; | |||
277 | case EXPAND_ERROR: | |||
278 | type = "error"; | |||
279 | break; | |||
280 | case EXPAND_INVALID: | |||
281 | default: | |||
282 | return NULL((void *)0); | |||
283 | } | |||
284 | ||||
285 | if ((value = expandnode_to_text(e)) == NULL((void *)0)) | |||
286 | return NULL((void *)0); | |||
287 | ||||
288 | (void)strlcpy(buffer, type, sizeof buffer); | |||
289 | (void)strlcat(buffer, ":", sizeof buffer); | |||
290 | if (strlcat(buffer, value, sizeof buffer) >= sizeof buffer) | |||
291 | return NULL((void *)0); | |||
292 | ||||
293 | (void)snprintf(tmp, sizeof(tmp), "[parent=%p", e->parent); | |||
294 | if (strlcat(buffer, tmp, sizeof buffer) >= sizeof buffer) | |||
295 | return NULL((void *)0); | |||
296 | ||||
297 | (void)snprintf(tmp, sizeof(tmp), ", rule=%p", e->rule); | |||
298 | if (strlcat(buffer, tmp, sizeof buffer) >= sizeof buffer) | |||
299 | return NULL((void *)0); | |||
300 | ||||
301 | if (e->rule) { | |||
302 | (void)snprintf(tmp, sizeof(tmp), ", dispatcher=%p", e->rule->dispatcher); | |||
303 | if (strlcat(buffer, tmp, sizeof buffer) >= sizeof buffer) | |||
304 | return NULL((void *)0); | |||
305 | } | |||
306 | ||||
307 | if (strlcat(buffer, "]", sizeof buffer) >= sizeof buffer) | |||
308 | return NULL((void *)0); | |||
309 | ||||
310 | return buffer; | |||
311 | } | |||
312 | ||||
313 | RB_GENERATE(expandtree, expandnode, entry, expand_cmp)void expandtree_RB_INSERT_COLOR(struct expandtree *head, struct expandnode *elm) { struct expandnode *parent, *gparent, *tmp ; while ((parent = (elm)->entry.rbe_parent) && (parent )->entry.rbe_color == 1) { gparent = (parent)->entry.rbe_parent ; if (parent == (gparent)->entry.rbe_left) { tmp = (gparent )->entry.rbe_right; if (tmp && (tmp)->entry.rbe_color == 1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry .rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0 ); elm = gparent; continue; } if ((parent)->entry.rbe_right == elm) { do { (tmp) = (parent)->entry.rbe_right; if (((parent )->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)-> entry.rbe_left)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent )) { if ((parent) == ((parent)->entry.rbe_parent)->entry .rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while ( 0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->entry.rbe_left; if (((gparent)->entry.rbe_left = (tmp)->entry.rbe_right )) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (gparent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent )->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry .rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_right = (gparent); (gparent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); } else { tmp = (gparent)-> entry.rbe_left; if (tmp && (tmp)->entry.rbe_color == 1) { (tmp)->entry.rbe_color = 0; do { (parent)->entry. rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0) ; elm = gparent; continue; } if ((parent)->entry.rbe_left == elm) { do { (tmp) = (parent)->entry.rbe_left; if (((parent )->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)-> entry.rbe_right)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent )) { if ((parent) == ((parent)->entry.rbe_parent)->entry .rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_right = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->entry.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->entry.rbe_right ; if (((gparent)->entry.rbe_right = (tmp)->entry.rbe_left )) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (gparent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent )->entry.rbe_parent)) { if ((gparent) == ((gparent)->entry .rbe_parent)->entry.rbe_left) ((gparent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_left = (gparent); (gparent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); } } (head->rbh_root)-> entry.rbe_color = 0; } void expandtree_RB_REMOVE_COLOR(struct expandtree *head, struct expandnode *parent, struct expandnode *elm) { struct expandnode *tmp; while ((elm == ((void *)0) || (elm)->entry.rbe_color == 0) && elm != (head)-> rbh_root) { if ((parent)->entry.rbe_left == elm) { tmp = ( parent)->entry.rbe_right; if ((tmp)->entry.rbe_color == 1) { do { (tmp)->entry.rbe_color = 0; (parent)->entry. rbe_color = 1; } while (0); do { (tmp) = (parent)->entry.rbe_right ; if (((parent)->entry.rbe_right = (tmp)->entry.rbe_left )) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent )->entry.rbe_parent)) { if ((parent) == ((parent)->entry .rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); tmp = (parent)->entry.rbe_right ; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)-> entry.rbe_left)->entry.rbe_color == 0) && ((tmp)-> entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right) ->entry.rbe_color == 0)) { (tmp)->entry.rbe_color = 1; elm = parent; parent = (elm)->entry.rbe_parent; } else { if ( (tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry. rbe_right)->entry.rbe_color == 0) { struct expandnode *oleft ; if ((oleft = (tmp)->entry.rbe_left)) (oleft)->entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oleft) = (tmp)-> entry.rbe_left; if (((tmp)->entry.rbe_left = (oleft)->entry .rbe_right)) { ((oleft)->entry.rbe_right)->entry.rbe_parent = (tmp); } do {} while (0); if (((oleft)->entry.rbe_parent = (tmp)->entry.rbe_parent)) { if ((tmp) == ((tmp)->entry .rbe_parent)->entry.rbe_left) ((tmp)->entry.rbe_parent) ->entry.rbe_left = (oleft); else ((tmp)->entry.rbe_parent )->entry.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (oleft)->entry.rbe_right = (tmp); (tmp)->entry .rbe_parent = (oleft); do {} while (0); if (((oleft)->entry .rbe_parent)) do {} while (0); } while (0); tmp = (parent)-> entry.rbe_right; } (tmp)->entry.rbe_color = (parent)->entry .rbe_color; (parent)->entry.rbe_color = 0; if ((tmp)->entry .rbe_right) ((tmp)->entry.rbe_right)->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_right; if (((parent)-> entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->entry .rbe_left)->entry.rbe_parent = (parent); } do {} while (0) ; if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent )) { if ((parent) == ((parent)->entry.rbe_parent)->entry .rbe_left) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while ( 0); } while (0); elm = (head)->rbh_root; break; } } else { tmp = (parent)->entry.rbe_left; if ((tmp)->entry.rbe_color == 1) { do { (tmp)->entry.rbe_color = 0; (parent)->entry .rbe_color = 1; } while (0); do { (tmp) = (parent)->entry. rbe_left; if (((parent)->entry.rbe_left = (tmp)->entry. rbe_right)) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent) == ((parent )->entry.rbe_parent)->entry.rbe_left) ((parent)->entry .rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry .rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent); (parent)-> entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry .rbe_parent)) do {} while (0); } while (0); tmp = (parent)-> entry.rbe_left; } if (((tmp)->entry.rbe_left == ((void *)0 ) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry .rbe_right)->entry.rbe_color == 0)) { (tmp)->entry.rbe_color = 1; elm = parent; parent = (elm)->entry.rbe_parent; } else { if ((tmp)->entry.rbe_left == ((void *)0) || ((tmp)-> entry.rbe_left)->entry.rbe_color == 0) { struct expandnode *oright; if ((oright = (tmp)->entry.rbe_right)) (oright)-> entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oright ) = (tmp)->entry.rbe_right; if (((tmp)->entry.rbe_right = (oright)->entry.rbe_left)) { ((oright)->entry.rbe_left )->entry.rbe_parent = (tmp); } do {} while (0); if (((oright )->entry.rbe_parent = (tmp)->entry.rbe_parent)) { if (( tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left) ((tmp )->entry.rbe_parent)->entry.rbe_left = (oright); else ( (tmp)->entry.rbe_parent)->entry.rbe_right = (oright); } else (head)->rbh_root = (oright); (oright)->entry.rbe_left = (tmp); (tmp)->entry.rbe_parent = (oright); do {} while ( 0); if (((oright)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left; } (tmp)->entry.rbe_color = (parent)->entry.rbe_color; (parent)->entry.rbe_color = 0; if ((tmp)->entry.rbe_left) ((tmp)->entry.rbe_left )->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_left ; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right )) { ((tmp)->entry.rbe_right)->entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent )->entry.rbe_parent)) { if ((parent) == ((parent)->entry .rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_right = (parent); (parent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); elm = (head)->rbh_root; break ; } } } if (elm) (elm)->entry.rbe_color = 0; } struct expandnode * expandtree_RB_REMOVE(struct expandtree *head, struct expandnode *elm) { struct expandnode *child, *parent, *old = elm; int color ; if ((elm)->entry.rbe_left == ((void *)0)) child = (elm)-> entry.rbe_right; else if ((elm)->entry.rbe_right == ((void *)0)) child = (elm)->entry.rbe_left; else { struct expandnode *left; elm = (elm)->entry.rbe_right; while ((left = (elm) ->entry.rbe_left)) elm = left; child = (elm)->entry.rbe_right ; parent = (elm)->entry.rbe_parent; color = (elm)->entry .rbe_color; if (child) (child)->entry.rbe_parent = parent; if (parent) { if ((parent)->entry.rbe_left == elm) (parent )->entry.rbe_left = child; else (parent)->entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child ; if ((elm)->entry.rbe_parent == old) parent = elm; (elm)-> entry = (old)->entry; if ((old)->entry.rbe_parent) { if (((old)->entry.rbe_parent)->entry.rbe_left == old) ((old )->entry.rbe_parent)->entry.rbe_left = elm; else ((old) ->entry.rbe_parent)->entry.rbe_right = elm; do {} while (0); } else (head)->rbh_root = elm; ((old)->entry.rbe_left )->entry.rbe_parent = elm; if ((old)->entry.rbe_right) ( (old)->entry.rbe_right)->entry.rbe_parent = elm; if (parent ) { left = parent; do { do {} while (0); } while ((left = (left )->entry.rbe_parent)); } goto color; } parent = (elm)-> entry.rbe_parent; color = (elm)->entry.rbe_color; if (child ) (child)->entry.rbe_parent = parent; if (parent) { if ((parent )->entry.rbe_left == elm) (parent)->entry.rbe_left = child ; else (parent)->entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; color: if (color == 0) expandtree_RB_REMOVE_COLOR (head, parent, child); return (old); } struct expandnode * expandtree_RB_INSERT (struct expandtree *head, struct expandnode *elm) { struct expandnode *tmp; struct expandnode *parent = ((void *)0); int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (expand_cmp)(elm, parent); if (comp < 0) tmp = (tmp)-> entry.rbe_left; else if (comp > 0) tmp = (tmp)->entry.rbe_right ; else return (tmp); } do { (elm)->entry.rbe_parent = parent ; (elm)->entry.rbe_left = (elm)->entry.rbe_right = ((void *)0); (elm)->entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0) (parent)->entry.rbe_left = elm; else (parent)->entry.rbe_right = elm; do {} while ( 0); } else (head)->rbh_root = elm; expandtree_RB_INSERT_COLOR (head, elm); return (((void *)0)); } struct expandnode * expandtree_RB_FIND (struct expandtree *head, struct expandnode *elm) { struct expandnode *tmp = (head)->rbh_root; int comp; while (tmp) { comp = expand_cmp (elm, tmp); if (comp < 0) tmp = (tmp)->entry.rbe_left; else if (comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp); } return (((void *)0)); } struct expandnode * expandtree_RB_NFIND (struct expandtree *head, struct expandnode *elm) { struct expandnode *tmp = (head)->rbh_root; struct expandnode *res = ((void * )0); int comp; while (tmp) { comp = expand_cmp(elm, tmp); if ( comp < 0) { res = tmp; tmp = (tmp)->entry.rbe_left; } else if (comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp); } return (res); } struct expandnode * expandtree_RB_NEXT (struct expandnode *elm) { if ((elm)->entry.rbe_right) { elm = (elm)->entry.rbe_right; while ((elm)->entry.rbe_left ) elm = (elm)->entry.rbe_left; } else { if ((elm)->entry .rbe_parent && (elm == ((elm)->entry.rbe_parent)-> entry.rbe_left)) elm = (elm)->entry.rbe_parent; else { while ((elm)->entry.rbe_parent && (elm == ((elm)->entry .rbe_parent)->entry.rbe_right)) elm = (elm)->entry.rbe_parent ; elm = (elm)->entry.rbe_parent; } } return (elm); } struct expandnode * expandtree_RB_PREV(struct expandnode *elm) { if ((elm)->entry.rbe_left) { elm = (elm)->entry.rbe_left; while ((elm)->entry.rbe_right) elm = (elm)->entry.rbe_right ; } else { if ((elm)->entry.rbe_parent && (elm == ( (elm)->entry.rbe_parent)->entry.rbe_right)) elm = (elm) ->entry.rbe_parent; else { while ((elm)->entry.rbe_parent && (elm == ((elm)->entry.rbe_parent)->entry.rbe_left )) elm = (elm)->entry.rbe_parent; elm = (elm)->entry.rbe_parent ; } } return (elm); } struct expandnode * expandtree_RB_MINMAX (struct expandtree *head, int val) { struct expandnode *tmp = (head)->rbh_root; struct expandnode *parent = ((void *)0) ; while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)-> entry.rbe_left; else tmp = (tmp)->entry.rbe_right; } return (parent); }; | |||