Bug Summary

File:src/usr.sbin/smtpd/smtpctl/../expand.c
Warning:line 100, column 3
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name expand.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/usr.sbin/smtpd/smtpctl/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/usr.sbin/smtpd/smtpctl/.. -D NO_IO -D CONFIG_MINIMUM -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/smtpd/smtpctl/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c /usr/src/usr.sbin/smtpd/smtpctl/../expand.c
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
25static const char *expandnode_info(struct expandnode *);
26
27struct expandnode *
28expand_lookup(struct expand *expand, struct expandnode *key)
29{
30 return RB_FIND(expandtree, &expand->tree, key)expandtree_RB_FIND(&expand->tree, key);
31}
32
33int
34expand_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
50void
51expand_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
89void
90expand_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);
2
←
Assuming the condition is false
→
3
←
Taking false branch
→
4
←
Loop condition is false. Exiting loop
→
95 if (expand->queue)
5
←
Assuming field 'queue' is null
→
6
←
Taking false branch
→
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)) {
7
←
Assuming the condition is true
→
8
←
Loop condition is true. Entering loop body
→
23
←
Loop condition is true. Entering loop body
→
100 RB_REMOVE(expandtree, &expand->tree, xn)expandtree_RB_REMOVE(&expand->tree, xn);
9
←
Calling 'expandtree_RB_REMOVE'
→
21
←
Returning from 'expandtree_RB_REMOVE'
→
24
←
Use of memory after it is freed
101 free(xn);
22
←
Memory is released
→
102 }
103}
104
105void
106expand_free(struct expand *expand)
107{
108 expand_clear(expand);
1
Calling 'expand_clear'
→
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
114int
115expand_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
177static int
178expand_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
221int
222expand_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
253static const char *
254expandnode_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
313RB_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); };
10
←
Assuming field 'rbe_left' is equal to null
→
11
←
Taking true branch
→
12
←
Assuming 'child' is null
→
13
←
Taking false branch
→
14
←
Assuming 'parent' is non-null
→
15
←
Taking true branch
→
16
←
Assuming 'elm' is not equal to field 'rbe_left'
→
17
←
Taking false branch
→
18
←
Loop condition is false. Exiting loop
→
19
←
Assuming 'color' is not equal to 0
→
20
←
Taking false branch
→