Bug Summary

File:src/usr.sbin/npppd/npppd/../common/radish.c
Warning:line 450, column 7
Access to field 'rd_rtent' results in a dereference of a null pointer (loaded from variable 'target')

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 radish.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/npppd/npppd/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/usr.sbin/npppd/npppd/../common -I /usr/src/usr.sbin/npppd/npppd -I /usr/src/usr.sbin/npppd/npppd/../pptp -I /usr/src/usr.sbin/npppd/npppd/../l2tp -I /usr/src/usr.sbin/npppd/npppd/../pppoe -D USE_NPPPD_PPTP -D USE_NPPPD_L2TP -D USE_NPPPD_PPPOE -D __COPYRIGHT(x)= -D __RCSID(x)= -D NPPPD_MAX_IFACE=8 -D NPPPD_MAX_POOL=8 -D USE_NPPPD_MPPE -D USE_NPPPD_PIPEX -D USE_NPPPD_RADIUS -D USE_SA_COOKIE -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/usr.sbin/npppd/npppd/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/npppd/npppd/../common/radish.c
1/* $OpenBSD: radish.c,v 1.7 2021/03/29 03:54:39 yasuoka Exp $ */
2/*
3 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the project nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 *
30 */
31
32/*
33 * radish.c
34 *
35 * Version: 0.9
36 * Created: May 27, 1995
37 * Modified: January 28, 1997
38 * Author: Kazu YAMAMOTO
39 * Email: kazu@is.aist-nara.ac.jp
40 */
41
42#include <sys/types.h>
43#include <sys/socket.h>
44#include <string.h>
45#include <stdlib.h>
46#include <errno(*__errno()).h>
47
48#include "radish.h"
49
50#include <netinet/in.h>
51#include <string.h>
52#include <strings.h>
53#include <stdlib.h>
54#include <stdio.h>
55
56#define FATAL(x)do { fputs(x, (&__sF[2])); abort(); } while (0 ) \
57 do { \
58 fputs(x, stderr(&__sF[2])); \
59 abort(); \
60 } while (0/* CONSTCOND */)
61
62static u_char rd_bmask [] = {
63 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe,
64};
65
66static u_char rd_btest [] = {
67 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01,
68};
69
70u_char rd_deleted_km[1024];
71
72/*
73 * return 1 if success
74 * return 0 if error
75 */
76int
77rd_inithead(void **headp, int family, int slen, int off, int alen,
78 int (*match)(void *, void *))
79{
80 struct radish_head *head;
81 struct radish *new;
82 struct sockaddr *masks;
83 u_char *m;
84 int num = alen * 8 + 1, i, j, q, r;
85 int len = sizeof(*head) + sizeof(*new) + slen * num;
86
87 if (*headp) return (1);
88 R_Malloc(head, struct radish_head *, len)(head = (struct radish_head *) malloc((len)));
89 if (head == NULL((void *)0))
90 return 0;
91 Bzero(head, len)memset((char *)(head), 0, (size_t)(len));
92 new = (struct radish *)(head + 1);
93 masks = (struct sockaddr *)(new +1);
94 *headp = head;
95
96 /*
97 * prepare all continuous masks
98 */
99 m = (u_char *)masks;
100 for (i = 0; i < num; i++, m += slen) {
101 *m = slen;
102 *(m + 1) = family;
103 q = i >> 3;
104 r = i & 7;
105 for(j = 0; j < q; j++)
106 *(m + off + j) = 0xff;
107 *(m + off + j) = rd_bmask[r];
108 }
109
110 head->rdh_slen = slen;
111 head->rdh_offset = off;
112 head->rdh_alen = alen;
113 head->rdh_masks = masks;
114 head->rdh_match = match;
115 head->rdh_top = new;
116
117 new->rd_route = masks;
118 new->rd_mask = masks;
119 new->rd_btest = rd_btest[0];
120 /* other nembers are 0 */
121
122 return(1);
123}
124
125struct sockaddr *
126rd_mask(struct sockaddr *m_arg, struct radish_head *head, int *maskp)
127{
128 u_char *mp, *masks = (u_char *)head->rdh_masks;
129 int off = head->rdh_offset;
130 int slen = head->rdh_slen;
131 int alen = head->rdh_alen;
132 int i = 0, masklen = 0;
133
134 if (m_arg == NULL((void *)0)) {
135 masklen = alen * 8;
136 *maskp = masklen;
137 return((struct sockaddr *)(masks + slen * masklen));
138 }
139 mp = (u_char *)m_arg + off;
140 while ((i < alen) && (mp[i] == 0xff)) {
141 masklen += 8;
142 i++;
143 }
144 if (i < alen)
145 switch (mp[i]) {
146 case 0xfe: masklen += 7; break;
147 case 0xfc: masklen += 6; break;
148 case 0xf8: masklen += 5; break;
149 case 0xf0: masklen += 4; break;
150 case 0xe0: masklen += 3; break;
151 case 0xc0: masklen += 2; break;
152 case 0x80: masklen += 1; break;
153 case 0x00: break;
154 }
155 *maskp = masklen;
156 return((struct sockaddr *)(masks + slen * masklen));
157}
158
159int
160rd_insert(struct sockaddr *d_arg, struct sockaddr *m_arg,
161 struct radish_head *head, void *rt)
162{
163 struct radish *cur = head->rdh_top, *parent, *new;
164 int off = head->rdh_offset;
165 int slen = head->rdh_slen;
166 int alen = head->rdh_alen;
167 int i, lim, q, r, masklen;
168 u_char *dp, *np, *rp;
169 struct sockaddr *mask;
170
171 mask = rd_mask(m_arg, head, &masklen);
172 q = masklen >> 3;
173 r = masklen & 7;
174
175 /* Allocate a new radish.
176 * This may be overhead in the case that
177 * masklen == cur->rd_masklen
178 * and
179 * route == dest.
180 */
181 R_Malloc(new, struct radish *, sizeof(*new) + slen)(new = (struct radish *) malloc((sizeof(*new) + slen)));
182 if (new == NULL((void *)0))
183 return ENOBUFS55;
184 Bzero(new, sizeof(*new) + slen)memset((char *)(new), 0, (size_t)(sizeof(*new) + slen));
185 new->rd_route = (struct sockaddr *)(new + 1);
186 new->rd_mask = mask;
187 new->rd_masklen = masklen;
188 new->rd_masklim = q;
189 new->rd_bmask = rd_bmask[r];
190 new->rd_btest = rd_btest[r];
191 new->rd_rtent = rt;
192
193 /* masked copy from dest to route */
194 np = (u_char *)new->rd_route;
195 dp = (u_char *)d_arg;
196 *np = *dp; /* sa_len */
197 np[1] = dp[1]; /* sa_family */
198 dp += off;
199 np += off;
200 i = 0;
201 while (i < q) {
202 np[i] = dp[i];
203 i++;
204 }
205 np[i] = dp[i] & rd_bmask[r]; /* just in case */
206
207 while (cur) {
208 if (masklen == cur->rd_masklen) {
209 rp = (u_char *)cur->rd_route + off;
210 for (i = 0; i < alen; i++)
211 if (np[i] != rp[i]) {
212 /*
213 * masklen == cur->rd_masklen
214 * dest != route
215 */
216 return rd_glue(cur, new, i, head);
217 }
218 /*
219 * masklen == cur->rd_masklen
220 * dest == route
221 */
222 Free(new)free((char *)new);;
223 if (cur->rd_rtent != NULL((void *)0))
224 return EEXIST17;
225 cur->rd_rtent = rt;
226 return 0;
227 }
228 /*
229 * masklen != cur->rd_masklen
230 */
231 if (masklen > cur->rd_masklen) {
232 /*
233 * See if dest matches with cur node.
234 * (dest & mask) == route
235 */
236 rp = (u_char *)cur->rd_route + off;
237 lim = cur->rd_masklim;
238
239 /* mask is continuous, thus mask is 0xff here. */
240 for (i = 0; i < lim; i++)
241 if(np[i] != rp[i]) {
242 /*
243 * masklen > cur->rd_masklen
244 * (dest & mask) != route
245 */
246 return rd_glue(cur, new, i, head);
247 }
248 if (cur->rd_bmask)
249 if ((np[lim] & cur->rd_bmask) != rp[lim]) {
250 /*
251 * masklen > cur->rd_masklen
252 * (dest & mask) != route
253 */
254 return rd_glue(cur, new, lim, head);
255 }
256 /*
257 * masklen > cur->rd_masklen
258 * (dest & mask) == route
259 */
260 if (cur->rd_btest & np[cur->rd_masklim]) {
261 if (cur->rd_r != NULL((void *)0)) {
262 cur = cur->rd_r;
263 continue;
264 }
265 cur->rd_r = new;
266 new->rd_p = cur;
267 return 0;
268 } else {
269 if (cur->rd_l != NULL((void *)0)) {
270 cur = cur->rd_l;
271 continue;
272 }
273 cur->rd_l = new;
274 new->rd_p = cur;
275 return 0;
276 }
277 }
278 /*
279 * masklen < cur->rd_masklen
280 */
281
282 /* See if route matches with dest, be careful!
283 * dest == (route & dest_mask)
284 */
285 rp = (u_char *)cur->rd_route + off;
286 lim = new->rd_masklim;
287
288 /* mask is continuous, thus mask is 0xff here. */
289 for (i = 0; i < lim; i++)
290 if(np[i] != rp[i]) {
291 /*
292 * masklen < cur->rd_masklen
293 * dest != (route & dest_mask)
294 */
295 return rd_glue(cur, new, i, head);
296 }
297 if (new->rd_bmask)
298 if (np[lim] != (rp[lim] & new->rd_bmask)) {
299 /*
300 * masklen < cur->rd_masklen
301 * dest != (route & dest_mask)
302 */
303 return rd_glue(cur, new, lim, head);
304 }
305 /*
306 * masklen < cur->rd_masklen
307 * dest == (route & dest_mask)
308 */
309
310 /* put the new radish between cur and its parent */
311 parent = cur->rd_p;
312 new->rd_p = parent;
313 if (parent->rd_l == cur)
314 parent->rd_l = new;
315 else if (parent->rd_r == cur)
316 parent->rd_r = new;
317 else
318 FATAL("rd_insert")do { fputs("rd_insert", (&__sF[2])); abort(); } while (0 );
319 if (new->rd_btest & rp[new->rd_masklim])
320 new->rd_r = cur;
321 else
322 new->rd_l = cur;
323
324 cur->rd_p = new;
325 return 0;
326 }
327 return 1;
328}
329
330/*
331 * Insert a glue radish between the current and its parent.
332 * Let the current radish one child of glue radish.
333 * Let the new radish the other child of glue radish.
334 */
335int
336rd_glue(struct radish *cur, struct radish *new, int misbyte,
337 struct radish_head *head)
338{
339 struct radish *parent = cur->rd_p, *glue;
340 u_char *cp = (u_char *)cur->rd_route;
341 u_char *np = (u_char *)new->rd_route;
342 u_char *gp;
343 int off = head->rdh_offset, slen = head->rdh_slen;
344 int maskb, xor, i;
345
346 /*
347 * Glue radish
348 */
349 R_Malloc(glue, struct radish *, sizeof(*glue) + slen)(glue = (struct radish *) malloc((sizeof(*glue) + slen)));
350 if (glue == NULL((void *)0)) {
351 Free (new)free((char *)new);;
352 return ENOBUFS55;
353 }
354 Bzero(glue, sizeof(*glue) + slen)memset((char *)(glue), 0, (size_t)(sizeof(*glue) + slen));
355
356 /* calculate a bit to test */
357 xor = (*(cp + off + misbyte) ^ *(np + off + misbyte)) & 0xff;
358 maskb = 8;
359 while(xor) {
360 xor >>= 1;
361 maskb--;
362 }
363
364 glue->rd_route = (struct sockaddr *)(glue + 1);
365 glue->rd_masklen = 8 * misbyte + maskb;
366 glue->rd_masklim = misbyte;
367 glue->rd_bmask = rd_bmask[maskb];
368 glue->rd_btest = rd_btest[maskb];
369 glue->rd_rtent = NULL((void *)0);
370 glue->rd_p = parent;
371 glue->rd_mask = (struct sockaddr *)
372 ((u_char *)head->rdh_masks + slen * glue->rd_masklen);
373
374 /* masked copy of route */
375 gp = (u_char *)glue->rd_route;
376 *gp = *cp; /* sa_len */
377 *(gp + 1) = *(cp + 1); /* sa_family */
378 cp += off;
379 gp += off;
380 for(i = 0; i < misbyte; i++)
381 gp[i] = cp[i];
382 gp[misbyte] = cp[misbyte] & glue->rd_bmask;
383
384 if (glue->rd_btest & cp[misbyte]) {
385 glue->rd_r = cur;
386 glue->rd_l = new;
387 } else {
388 glue->rd_r = new;
389 glue->rd_l = cur;
390 }
391
392 /*
393 * Children
394 */
395 new->rd_p = cur->rd_p = glue;
396
397 /*
398 * Parent
399 */
400 if (parent->rd_l == cur)
401 parent->rd_l = glue;
402 else if (parent->rd_r == cur)
403 parent->rd_r = glue;
404 else
405 FATAL("rd_insert")do { fputs("rd_insert", (&__sF[2])); abort(); } while (0 );
406 return 0;
407}
408
409/*
410 * Find the longest-match radish with the destination.
411 * Return 1 if success, otherwise return 0.
412 */
413
414int
415rd_match(struct sockaddr *d_arg, struct radish_head *head, struct radish **rdp)
416{
417 return rd_match_next(d_arg, head, rdp, NULL((void *)0));
1
Calling 'rd_match_next'
→
418}
419
420int
421rd_match_next(struct sockaddr *d_arg, struct radish_head *head,
422 struct radish **rdp, struct radish *cur)
423{
424 struct radish *target = NULL((void *)0);
2
←
'target' initialized to a null pointer value
→
425 int off = head->rdh_offset, i, lim;
426 u_char *dp = (u_char *)d_arg + off, *cp;
427
428 if (cur
2.1
'cur' is equal to NULL
 == NULL((void *)0)) {
3
←
Taking true branch
→
429 cur = head->rdh_top;
430 while (cur) {
4
←
Loop condition is false. Execution continues on line 450
→
431 target = cur;
432 if (cur->rd_btest & *(dp + cur->rd_masklim))
433 cur = cur->rd_r;
434 else
435 cur = cur->rd_l;
436 }
437 } else {
438 target = cur->rd_p;
439 if (target == NULL((void *)0)) {
440 *rdp = NULL((void *)0);
441 return 0;
442 }
443 }
444
445 /* We are now on the leaf radish. Backtrace to find the radish
446 which contains route to match. */
447 do {
448 /* If this radish doesn't have route,
449 we skip it and chase the next parent. */
450 if (target->rd_rtent != NULL((void *)0)) {
5
←
Access to field 'rd_rtent' results in a dereference of a null pointer (loaded from variable 'target')
451 cp = (u_char *)target->rd_route + off;
452 lim = target->rd_masklim;
453
454 /* Check the edge for slight speed up */
455 if (target->rd_bmask)
456 if ((*(dp + lim) & target->rd_bmask)
457 != *(cp + lim)){
458 nextparent:
459 continue;
460 }
461
462 /* mask is always 0xff */
463 for (i = 0; i < lim; i++)
464 if(dp[i] != cp[i])
465 /* to break the for loop */
466 goto nextparent;
467 /* Matched to this radish! */
468 *rdp = target;
469 return 1;
470 }
471 } while ((target = target->rd_p));
472 *rdp = NULL((void *)0);
473 return 0;
474}
475
476/*
477 * Lookup the same radish according to a pair of destination and mask.
478 * Return a pointer to rtentry if exists. Otherwise, return NULL.
479 */
480
481void *
482rd_lookup(struct sockaddr *d_arg, struct sockaddr *m_arg,
483 struct radish_head *head)
484{
485 struct radish *cur = head->rdh_top;
486 int off = head->rdh_offset, i, lim, olim = 0, masklen;
487 u_char *dp = (u_char *)d_arg + off, *cp;
488
489 rd_mask(m_arg, head, &masklen);
490
491 /* Skipping forward search */
492 while (cur) {
493 /* Skip a radish if it doesn't have a route */
494 if (cur->rd_rtent != NULL((void *)0)) {
495 cp = (u_char *)(cur->rd_route) + off;
496 lim = cur->rd_masklim;
497 /* check the edge to speed up a bit */
498 if (cur->rd_bmask)
499 if ((*(dp + lim) & cur->rd_bmask)
500 != *(cp + lim))
501 return NULL((void *)0);
502 /* mask is always 0xff */
503 for (i = olim; i < lim; i++)
504 if(dp[i] != cp[i])
505 return NULL((void *)0);
506 if (masklen == cur->rd_masklen)
507 return cur->rd_rtent;
508 olim = lim;
509 }
510 if (cur->rd_btest & *(dp + cur->rd_masklim))
511 cur = cur->rd_r;
512 else
513 cur = cur->rd_l;
514 }
515 return NULL((void *)0);
516}
517
518/*
519 * Delete the radish for dest and mask.
520 * Return 0 if success.
521 * Return ENOENT if no such radish exists.
522 * Return EFAULT if try to delete intermediate radish which doesn't have route.
523 */
524
525int
526rd_delete(struct sockaddr *d_arg, struct sockaddr *m_arg,
527 struct radish_head *head, void **item)
528{
529 struct radish *cur = head->rdh_top;
530 int off = head->rdh_offset, i, lim, masklen;
531 u_char *dp = (u_char *)d_arg + off, *cp;
532
533 rd_mask(m_arg, head, &masklen);
534 *item = NULL((void *)0); /* just in case */
535
536 while (cur) {
537 /* exit loop if dest does not match with the current node
538 * (dest & mask) != route
539 */
540 cp = (u_char *)cur->rd_route + off;
541 /* check the edge to speed up */
542 if (cur->rd_bmask)
543 if ((*(dp + cur->rd_masklim) & cur->rd_bmask)
544 != *(cp + cur->rd_masklim))
545 return ENOENT2;
546 /* mask is always 0xff */
547 lim = cur->rd_masklim;
548 for (i = 0; i < lim; i++)
549 if(dp[i] != cp[i])
550 return ENOENT2;
551
552 /* See if cur is exactly what we delete */
553
554 /* Check mask to speed up */
555 if (cur->rd_masklen != masklen)
556 goto next;
557
558 cp = (u_char *)cur->rd_route + off;
559 lim = head->rdh_alen;
560 for (i = 0; i < lim; i++)
561 if (dp[i] != cp[i])
562 goto next;
563 /*
564 * Both route and mask are the same.
565 */
566 if (cur->rd_rtent == NULL((void *)0)) {
567 /* Leaf always has route, so this radish
568 * must be intermediate.
569 * Can't delete intermediate radish which
570 * doesn't have route.
571 */
572 return EFAULT14;
573 }
574 *item = cur->rd_rtent;
575 {
576 /* used to report the deleted entry back */
577 u_char rl = cur->rd_route->sa_len;
578 u_char ml = cur->rd_mask->sa_len;
579
580 bcopy(cur->rd_route, rd_deleted_km, rl);
581 bcopy(cur->rd_mask, rd_deleted_km + rl, ml);
582 }
583 if (cur->rd_l && cur->rd_r) {
584 /* This radish has two children */
585 cur->rd_rtent = NULL((void *)0);
586 return 0;
587 }
588 /* Unlink the radish that has 0 or 1 child
589 * and surely has a route.
590 */
591 rd_unlink(cur, head->rdh_top);
592 return 0;
593
594 next:
595 /* search corresponding subtree */
596 if (cur->rd_btest & *(dp + cur->rd_masklim)) {
597 if (cur->rd_r) {
598 cur = cur->rd_r;
599 continue;
600 } else
601 break;
602 } else {
603 if (cur->rd_l) {
604 cur = cur->rd_l;
605 continue;
606 } else
607 break;
608 }
609 }
610 return ENOENT2;
611}
612
613/*
614 * Free radish and refine radish tree.
615 * rd_unlink is called with radish which have 0 or 1 child and route.
616 * Error causes panic, so return only when success.
617 */
618
619void
620rd_unlink(struct radish *cur, struct radish *top)
621{
622 struct radish *parent, *child;
623
624 if (cur == top) {
625 cur->rd_rtent = NULL((void *)0);
626 return;
627 }
628
629 if ((cur->rd_l == 0) && (cur->rd_r == 0)) {
630 /* No child, just delete it. */
631 parent = cur->rd_p;
632 if (parent->rd_l == cur) {
633 parent->rd_l = NULL((void *)0);
634 Free(cur)free((char *)cur);;
635 } else if (parent->rd_r == cur) {
636 parent->rd_r = NULL((void *)0);
637 Free(cur)free((char *)cur);;
638 } else
639 FATAL("rd_unlink")do { fputs("rd_unlink", (&__sF[2])); abort(); } while (0 );
640 if (parent->rd_rtent == NULL((void *)0) && parent != top)
641 /* Parent is not necessary, refine radish. */
642 rd_unlink(parent, top);
643 } else {
644 /*
645 * There is one child, never two.
646 * Make its child its parent's child.
647 */
648 if (cur->rd_l)
649 child = cur->rd_l;
650 else
651 child = cur->rd_r;
652 parent = cur->rd_p;
653 child->rd_p = parent;
654 if (parent->rd_l == cur) {
655 parent->rd_l = child;
656 Free(cur)free((char *)cur);;
657 } else if (parent->rd_r == cur) {
658 parent->rd_r = child;
659 Free(cur)free((char *)cur);;
660 } else
661 FATAL("rd_unlink")do { fputs("rd_unlink", (&__sF[2])); abort(); } while (0 );
662 }
663}
664
665int
666rd_walktree(struct radish_head *h, register int (*f)(struct radish *, void *),
667 void *w)
668{
669 int error = 0;
670 struct radish *par = NULL((void *)0), *cur, *top = h->rdh_top;
671
672 cur = top;
673 for (;;) {
674 while (cur) {
675 if (cur->rd_rtent != NULL((void *)0))
676 if ((error = (*f)(cur, w)))
677 return error;
678 par = cur;
679 cur = cur->rd_l;
680 }
681 cur = par;
682 while (cur->rd_r == NULL((void *)0) || par == cur->rd_r) {
683 par = cur;
684 cur = cur->rd_p;
685 if (cur == NULL((void *)0)) return 0;
686 }
687 par = cur;
688 cur = cur->rd_r;
689 }
690}
691
692/* This function can be mush easier in the context of radish.
693 * For instance, using rd_mask. But we stay the original because
694 * it works.
695 */
696int
697rd_refines(void *m_arg, void *n_arg)
698{
699 register caddr_t m = m_arg, n = n_arg;
700 register caddr_t lim, lim2 = lim = n + *(u_char *)n;
701 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);
702 int masks_are_equal = 1;
703
704 if (longer > 0)
705 lim -= longer;
706 while (n < lim) {
707 if (*n & ~(*m))
708 return 0;
709 if (*n++ != *m++)
710 masks_are_equal = 0;
711
712 }
713 while (n < lim2)
714 if (*n++)
715 return 0;
716 if (masks_are_equal && (longer < 0))
717 for (lim2 = m - longer; m < lim2; )
718 if (*m++)
719 return 1;
720 return (!masks_are_equal);
721}