Bug Summary

File:src/bin/csh/set.c
Warning:line 507, column 13
Access to field 'vec' results in a dereference of a null pointer (loaded from variable 'p')

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 set.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/bin/csh/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/bin/csh -I . -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/bin/csh/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/bin/csh/set.c
1/* $OpenBSD: set.c,v 1.23 2019/07/03 03:24:01 deraadt Exp $ */
2/* $NetBSD: set.c,v 1.8 1995/03/21 18:35:52 mycroft Exp $ */
3
4/*-
5 * Copyright (c) 1980, 1991, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33#include <sys/types.h>
34#include <stdlib.h>
35#include <stdarg.h>
36
37#include "csh.h"
38#include "extern.h"
39
40static Char *getinx(Char *, int *);
41static void asx(Char *, int, Char *);
42static struct varent
43 *getvx(Char *, int);
44static Char *xset(Char *, Char ***);
45static Char *operate(int, Char *, Char *);
46static struct varent
47 *madrof(Char *, struct varent *);
48static void unsetv1(struct varent *);
49static void exportpath(Char **);
50static void balance(struct varent *, int, int);
51
52
53/*
54 * C Shell
55 */
56
57void
58/*ARGSUSED*/
59doset(Char **v, struct command *t)
60{
61 Char *p;
62 Char *vp, op;
63 Char **vecp;
64 bool hadsub;
65 int subscr;
66
67 v++;
68 p = *v++;
69 if (p == 0) {
70 prvars();
71 return;
72 }
73 do {
74 hadsub = 0;
75 vp = p;
76 if (letter(*p)(((*p) & 0100000U) ? 0 : (isalpha((unsigned char) (*p)) ||
(*p) == '_')))
77 for (; alnum(*p)(((*p) & 0100000U) ? 0 : (isalnum((unsigned char) (*p)) ||
(*p) == '_')); p++)
78 continue;
79 if (vp == p || !letter(*vp)(((*vp) & 0100000U) ? 0 : (isalpha((unsigned char) (*vp))
|| (*vp) == '_')))
80 stderror(ERR_NAME0x10000000 | ERR_VARBEGIN30);
81 if ((p - vp) > MAXVARLEN30) {
82 stderror(ERR_NAME0x10000000 | ERR_VARTOOLONG31);
83 return;
84 }
85 if (*p == '[') {
86 hadsub++;
87 p = getinx(p, &subscr);
88 }
89 if ((op = *p) != '\0') {
90 *p++ = 0;
91 if (*p == 0 && *v && **v == '(')
92 p = *v++;
93 }
94 else if (*v && eq(*v, STRequal)(Strcmp(*v, STRequal) == 0)) {
95 op = '=', v++;
96 if (*v)
97 p = *v++;
98 }
99 if (op && op != '=')
100 stderror(ERR_NAME0x10000000 | ERR_SYNTAX0);
101 if (eq(p, STRLparen)(Strcmp(p, STRLparen) == 0)) {
102 Char **e = v;
103
104 if (hadsub)
105 stderror(ERR_NAME0x10000000 | ERR_SYNTAX0);
106 for (;;) {
107 if (!*e)
108 stderror(ERR_NAME0x10000000 | ERR_MISSING51, ')');
109 if (**e == ')')
110 break;
111 e++;
112 }
113 p = *e;
114 *e = 0;
115 vecp = saveblk(v);
116 set1(vp, vecp, &shvhed);
117 *e = p;
118 v = e + 1;
119 }
120 else if (hadsub)
121 asx(vp, subscr, Strsave(p));
122 else
123 set(vp, Strsave(p));
124 if (eq(vp, STRpath)(Strcmp(vp, STRpath) == 0)) {
125 exportpath(adrof(STRpath)adrof1(STRpath, &shvhed)->vec);
126 dohash(NULL((void *)0), NULL((void *)0));
127 }
128 else if (eq(vp, STRhistchars)(Strcmp(vp, STRhistchars) == 0)) {
129 Char *pn = value(STRhistchars)value1(STRhistchars, &shvhed);
130
131 HIST = *pn++;
132 HISTSUB = *pn;
133 }
134 else if (eq(vp, STRuser)(Strcmp(vp, STRuser) == 0)) {
135 Setenv(STRUSER, value(vp)value1(vp, &shvhed));
136 Setenv(STRLOGNAME, value(vp)value1(vp, &shvhed));
137 }
138 else if (eq(vp, STRwordchars)(Strcmp(vp, STRwordchars) == 0)) {
139 word_chars = value(vp)value1(vp, &shvhed);
140 }
141 else if (eq(vp, STRterm)(Strcmp(vp, STRterm) == 0))
142 Setenv(STRTERM, value(vp)value1(vp, &shvhed));
143 else if (eq(vp, STRhome)(Strcmp(vp, STRhome) == 0)) {
144 Char *cp;
145
146 cp = Strsave(value(vp)value1(vp, &shvhed)); /* get the old value back */
147
148 /*
149 * convert to canonical pathname (possibly resolving symlinks)
150 */
151 cp = dcanon(cp, cp);
152
153 set(vp, Strsave(cp)); /* have to save the new val */
154
155 /* and now mirror home with HOME */
156 Setenv(STRHOME, cp);
157 /* fix directory stack for new tilde home */
158 dtilde();
159 free(cp);
160 }
161 else if (eq(vp, STRfilec)(Strcmp(vp, STRfilec) == 0))
162 filec = 1;
163 } while ((p = *v++) != NULL((void *)0));
164}
165
166static Char *
167getinx(Char *cp, int *ip)
168{
169
170 *ip = 0;
171 *cp++ = 0;
172 while (*cp && Isdigit(*cp)(((*cp) & 0100000U) ? 0 : isdigit((unsigned char) (*cp))))
173 *ip = *ip * 10 + *cp++ - '0';
174 if (*cp++ != ']')
175 stderror(ERR_NAME0x10000000 | ERR_SUBSCRIPT9);
176 return (cp);
177}
178
179static void
180asx(Char *vp, int subscr, Char *p)
181{
182 struct varent *v = getvx(vp, subscr);
183
184 free(v->vec[subscr - 1]);
185 v->vec[subscr - 1] = globone(p, G_APPEND2);
186}
187
188static struct varent *
189getvx(Char *vp, int subscr)
190{
191 struct varent *v = adrof(vp)adrof1(vp, &shvhed);
192
193 if (v == 0)
194 udvar(vp);
195 if (subscr < 1 || subscr > blklen(v->vec))
196 stderror(ERR_NAME0x10000000 | ERR_RANGE43);
197 return (v);
198}
199
200void
201/*ARGSUSED*/
202dolet(Char **v, struct command *t)
203{
204 Char *p;
205 Char *vp, c, op;
206 bool hadsub;
207 int subscr;
208
209 v++;
210 p = *v++;
211 if (p == 0) {
212 prvars();
213 return;
214 }
215 do {
216 hadsub = 0;
217 vp = p;
218 if (letter(*p)(((*p) & 0100000U) ? 0 : (isalpha((unsigned char) (*p)) ||
(*p) == '_')))
219 for (; alnum(*p)(((*p) & 0100000U) ? 0 : (isalnum((unsigned char) (*p)) ||
(*p) == '_')); p++)
220 continue;
221 if (vp == p || !letter(*vp)(((*vp) & 0100000U) ? 0 : (isalpha((unsigned char) (*vp))
|| (*vp) == '_')))
222 stderror(ERR_NAME0x10000000 | ERR_VARBEGIN30);
223 if ((p - vp) > MAXVARLEN30)
224 stderror(ERR_NAME0x10000000 | ERR_VARTOOLONG31);
225 if (*p == '[') {
226 hadsub++;
227 p = getinx(p, &subscr);
228 }
229 if (*p == 0 && *v)
230 p = *v++;
231 if ((op = *p) != '\0')
232 *p++ = 0;
233 else
234 stderror(ERR_NAME0x10000000 | ERR_ASSIGN38);
235
236 if (*p == '\0' && *v == NULL((void *)0))
237 stderror(ERR_NAME0x10000000 | ERR_ASSIGN38);
238
239 vp = Strsave(vp);
240 if (op == '=') {
241 c = '=';
242 p = xset(p, &v);
243 }
244 else {
245 c = *p++;
246 if (any("+-", c)) {
247 if (c != op || *p)
248 stderror(ERR_NAME0x10000000 | ERR_UNKNOWNOP39);
249 p = Strsave(STR1);
250 }
251 else {
252 if (any("<>", op)) {
253 if (c != op)
254 stderror(ERR_NAME0x10000000 | ERR_UNKNOWNOP39);
255 c = *p++;
256 stderror(ERR_NAME0x10000000 | ERR_SYNTAX0);
257 }
258 if (c != '=')
259 stderror(ERR_NAME0x10000000 | ERR_UNKNOWNOP39);
260 p = xset(p, &v);
261 }
262 }
263 if (op == '=')
264 if (hadsub)
265 asx(vp, subscr, p);
266 else
267 set(vp, p);
268 else if (hadsub) {
269 struct varent *gv = getvx(vp, subscr);
270
271 asx(vp, subscr, operate(op, gv->vec[subscr - 1], p));
272 }
273 else
274 set(vp, operate(op, value(vp)value1(vp, &shvhed), p));
275 if (eq(vp, STRpath)(Strcmp(vp, STRpath) == 0)) {
276 exportpath(adrof(STRpath)adrof1(STRpath, &shvhed)->vec);
277 dohash(NULL((void *)0), NULL((void *)0));
278 }
279 free(vp);
280 if (c != '=')
281 free(p);
282 } while ((p = *v++) != NULL((void *)0));
283}
284
285static Char *
286xset(Char *cp, Char ***vp)
287{
288 Char *dp;
289
290 if (*cp) {
291 dp = Strsave(cp);
292 --(*vp);
293 free(** vp);
294 **vp = dp;
295 }
296 return (putn(expr(vp)));
297}
298
299static Char *
300operate(int op, Char *vp, Char *p)
301{
302 Char opr[2];
303 Char *vec[5];
304 Char **v = vec;
305 Char **vecp = v;
306 int i;
307
308 if (op != '=') {
309 if (*vp)
310 *v++ = vp;
311 opr[0] = op;
312 opr[1] = 0;
313 *v++ = opr;
314 if (op == '<' || op == '>')
315 *v++ = opr;
316 }
317 *v++ = p;
318 *v++ = 0;
319 i = expr(&vecp);
320 if (*vecp)
321 stderror(ERR_NAME0x10000000 | ERR_EXPRESSION34);
322 return (putn(i));
323}
324
325Char *
326putn(int n)
327{
328 char number[15];
329 int i;
330
331 i = snprintf(number, sizeof(number), "%d", n);
332 if (i < 0 || i >= sizeof(number))
333 return (STRNULL);
334 return (SAVE(number)(Strsave(str2short(number))));
335}
336
337int
338getn(Char *cp)
339{
340 int n;
341 int sign;
342
343 sign = 0;
344 if (cp[0] == '+' && cp[1])
345 cp++;
346 if (*cp == '-') {
347 sign++;
348 cp++;
349 if (!Isdigit(*cp)(((*cp) & 0100000U) ? 0 : isdigit((unsigned char) (*cp))))
350 stderror(ERR_NAME0x10000000 | ERR_BADNUM10);
351 }
352 n = 0;
353 while (Isdigit(*cp)(((*cp) & 0100000U) ? 0 : isdigit((unsigned char) (*cp))))
354 n = n * 10 + *cp++ - '0';
355 if (*cp)
356 stderror(ERR_NAME0x10000000 | ERR_BADNUM10);
357 return (sign ? -n : n);
358}
359
360Char *
361value1(Char *var, struct varent *head)
362{
363 struct varent *vp;
364
365 vp = adrof1(var, head);
366 return (vp == 0 || vp->vec[0] == 0 ? STRNULL : vp->vec[0]);
367}
368
369static struct varent *
370madrof(Char *pat, struct varent *vp)
371{
372 struct varent *vp1;
373
374 for (; vp; vp = vp->v_rightv_link[1]) {
375 if (vp->v_leftv_link[0] && (vp1 = madrof(pat, vp->v_leftv_link[0])))
376 return vp1;
377 if (Gmatch(vp->v_name, pat))
378 return vp;
379 }
380 return vp;
381}
382
383struct varent *
384adrof1(Char *name, struct varent *v)
385{
386 int cmp;
387
388 v = v->v_leftv_link[0];
389 while (v && ((cmp = *name - *v->v_name) ||
390 (cmp = Strcmp(name, v->v_name))))
391 if (cmp < 0)
392 v = v->v_leftv_link[0];
393 else
394 v = v->v_rightv_link[1];
395 return v;
396}
397
398/*
399 * The caller is responsible for putting value in a safe place
400 */
401void
402set(Char *var, Char *val)
403{
404 Char **vec = xreallocarray(NULL((void *)0), 2, sizeof(*vec));
405
406 vec[0] = val;
407 vec[1] = 0;
408 set1(var, vec, &shvhed);
409}
410
411void
412set1(Char *var, Char **vec, struct varent *head)
413{
414 Char **oldv = vec;
415
416 gflag = 0;
417 tglob(oldv);
418 if (gflag) {
419 vec = globall(oldv);
420 if (vec == 0) {
421 blkfree(oldv);
422 stderror(ERR_NAME0x10000000 | ERR_NOMATCH50);
423 return;
424 }
425 blkfree(oldv);
426 gargv = 0;
427 }
428 setq(var, vec, head);
429}
430
431
432void
433setq(Char *name, Char **vec, struct varent *p)
434{
435 struct varent *c;
436 int f;
437
438 f = 0; /* tree hangs off the header's left link */
439 while ((c = p->v_link[f]) != NULL((void *)0)) {
440 if ((f = *name - *c->v_name) == 0 &&
441 (f = Strcmp(name, c->v_name)) == 0) {
442 blkfree(c->vec);
443 goto found;
444 }
445 p = c;
446 f = f > 0;
447 }
448 p->v_link[f] = c = (struct varent *) xmalloc((size_t) sizeof(struct varent));
449 c->v_name = Strsave(name);
450 c->v_bal = 0;
451 c->v_leftv_link[0] = c->v_rightv_link[1] = 0;
452 c->v_parentv_link[2] = p;
453 balance(p, f, 0);
454found:
455 trim(c->vec = vec);
456}
457
458void
459/*ARGSUSED*/
460unset(Char **v, struct command *t)
461{
462 unset1(v, &shvhed);
463 if (adrof(STRfilec)adrof1(STRfilec, &shvhed) == 0)
464 filec = 0;
465 if (adrof(STRhistchars)adrof1(STRhistchars, &shvhed) == 0) {
466 HIST = '!';
467 HISTSUB = '^';
468 }
469 if (adrof(STRwordchars)adrof1(STRwordchars, &shvhed) == 0)
470 word_chars = STR_WORD_CHARS;
471}
472
473void
474unset1(Char *v[], struct varent *head)
475{
476 struct varent *vp;
477 int cnt;
478
479 while (*++v) {
480 cnt = 0;
481 while ((vp = madrof(*v, head->v_leftv_link[0])) != NULL((void *)0))
482 unsetv1(vp), cnt++;
483 if (cnt == 0)
484 setname(vis_str(*v))(bname = (vis_str(*v)));
485 }
486}
487
488void
489unsetv(Char *var)
490{
491 struct varent *vp;
492
493 if ((vp = adrof1(var, &shvhed)) == 0)
1
Value assigned to 'vp'
→
2
←
Assuming pointer value is null
→
3
←
Taking true branch
→
494 udvar(var);
495 unsetv1(vp);
4
←
Passing null pointer value via 1st parameter 'p'
→
5
←
Calling 'unsetv1'
→
496}
497
498static void
499unsetv1(struct varent *p)
500{
501 struct varent *c, *pp;
502 int f;
503
504 /*
505 * Free associated memory first to avoid complications.
506 */
507 blkfree(p->vec);
6
←
Access to field 'vec' results in a dereference of a null pointer (loaded from variable 'p')
508 free(p->v_name);
509 /*
510 * If p is missing one child, then we can move the other into where p is.
511 * Otherwise, we find the predecessor of p, which is guaranteed to have no
512 * right child, copy it into p, and move it's left child into it.
513 */
514 if (p->v_rightv_link[1] == 0)
515 c = p->v_leftv_link[0];
516 else if (p->v_leftv_link[0] == 0)
517 c = p->v_rightv_link[1];
518 else {
519 for (c = p->v_leftv_link[0]; c->v_rightv_link[1]; c = c->v_rightv_link[1])
520 continue;
521 p->v_name = c->v_name;
522 p->vec = c->vec;
523 p = c;
524 c = p->v_leftv_link[0];
525 }
526 /*
527 * Move c into where p is.
528 */
529 pp = p->v_parentv_link[2];
530 f = pp->v_rightv_link[1] == p;
531 if ((pp->v_link[f] = c) != NULL((void *)0))
532 c->v_parentv_link[2] = pp;
533 /*
534 * Free the deleted node, and rebalance.
535 */
536 free(p);
537 balance(pp, f, 1);
538}
539
540void
541setNS(Char *cp)
542{
543 set(cp, Strsave(STRNULL));
544}
545
546void
547/*ARGSUSED*/
548shift(Char **v, struct command *t)
549{
550 struct varent *argv;
551 Char *name;
552
553 v++;
554 name = *v;
555 if (name == 0)
556 name = STRargv;
557 else
558 (void) strip(name);
559 argv = adrof(name)adrof1(name, &shvhed);
560 if (argv == 0)
561 udvar(name);
562 if (argv->vec[0] == 0)
563 stderror(ERR_NAME0x10000000 | ERR_NOMORE11);
564 lshift(argv->vec, 1);
565}
566
567static void
568exportpath(Char **val)
569{
570 Char exppath[BUFSIZ1024];
571
572 exppath[0] = 0;
573 if (val)
574 while (*val) {
575 if (Strlen(*val) + Strlen(exppath) + 2 > BUFSIZ1024) {
576 (void) fprintf(csherr,
577 "Warning: ridiculously long PATH truncated\n");
578 break;
579 }
580 (void) Strlcat(exppath, *val++, sizeof exppath/sizeof(Char));
581 if (*val == 0 || eq(*val, STRRparen)(Strcmp(*val, STRRparen) == 0))
582 break;
583 (void) Strlcat(exppath, STRcolon, sizeof exppath/sizeof(Char));
584 }
585 Setenv(STRPATH, exppath);
586}
587
588/* macros to do single rotations on node p */
589#define rright(p)( t = (p)->v_link[0], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[0] = t->v_link[1]) ? (t->v_link[1]->
v_link[2] = (p)) : 0, (t->v_link[1] = (p))->v_link[2] =
t, (p) = t) (\
590 t = (p)->v_leftv_link[0],\
591 (t)->v_parentv_link[2] = (p)->v_parentv_link[2],\
592 ((p)->v_leftv_link[0] = t->v_rightv_link[1]) ? (t->v_rightv_link[1]->v_parentv_link[2] = (p)) : 0,\
593 (t->v_rightv_link[1] = (p))->v_parentv_link[2] = t,\
594 (p) = t)
595#define rleft(p)( t = (p)->v_link[1], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[1] = t->v_link[0]) ? (t->v_link[0]->
v_link[2] = (p)) : 0, (t->v_link[0] = (p))->v_link[2] =
t, (p) = t) (\
596 t = (p)->v_rightv_link[1],\
597 (t)->v_parentv_link[2] = (p)->v_parentv_link[2],\
598 ((p)->v_rightv_link[1] = t->v_leftv_link[0]) ? (t->v_leftv_link[0]->v_parentv_link[2] = (p)) : 0,\
599 (t->v_leftv_link[0] = (p))->v_parentv_link[2] = t,\
600 (p) = t)
601
602/*
603 * Rebalance a tree, starting at p and up.
604 * F == 0 means we've come from p's left child.
605 * D == 1 means we've just done a delete, otherwise an insert.
606 */
607static void
608balance(struct varent *p, int f, int d)
609{
610 struct varent *pp;
611 struct varent *t; /* used by the rotate macros */
612 int ff;
613
614 /*
615 * Ok, from here on, p is the node we're operating on; pp is it's parent; f
616 * is the branch of p from which we have come; ff is the branch of pp which
617 * is p.
618 */
619 for (; (pp = p->v_parentv_link[2]) != NULL((void *)0); p = pp, f = ff) {
620 ff = pp->v_rightv_link[1] == p;
621 if (f ^ d) { /* right heavy */
622 switch (p->v_bal) {
623 case -1: /* was left heavy */
624 p->v_bal = 0;
625 break;
626 case 0: /* was balanced */
627 p->v_bal = 1;
628 break;
629 case 1: /* was already right heavy */
630 switch (p->v_rightv_link[1]->v_bal) {
631 case 1: /* single rotate */
632 pp->v_link[ff] = rleft(p)( t = (p)->v_link[1], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[1] = t->v_link[0]) ? (t->v_link[0]->
v_link[2] = (p)) : 0, (t->v_link[0] = (p))->v_link[2] =
t, (p) = t);
633 p->v_leftv_link[0]->v_bal = 0;
634 p->v_bal = 0;
635 break;
636 case 0: /* single rotate */
637 pp->v_link[ff] = rleft(p)( t = (p)->v_link[1], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[1] = t->v_link[0]) ? (t->v_link[0]->
v_link[2] = (p)) : 0, (t->v_link[0] = (p))->v_link[2] =
t, (p) = t);
638 p->v_leftv_link[0]->v_bal = 1;
639 p->v_bal = -1;
640 break;
641 case -1: /* double rotate */
642 (void) rright(p->v_right)( t = (p->v_link[1])->v_link[0], (t)->v_link[2] = (p
->v_link[1])->v_link[2], ((p->v_link[1])->v_link[
0] = t->v_link[1]) ? (t->v_link[1]->v_link[2] = (p->
v_link[1])) : 0, (t->v_link[1] = (p->v_link[1]))->v_link
[2] = t, (p->v_link[1]) = t);
643 pp->v_link[ff] = rleft(p)( t = (p)->v_link[1], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[1] = t->v_link[0]) ? (t->v_link[0]->
v_link[2] = (p)) : 0, (t->v_link[0] = (p))->v_link[2] =
t, (p) = t);
644 p->v_leftv_link[0]->v_bal =
645 p->v_bal < 1 ? 0 : -1;
646 p->v_rightv_link[1]->v_bal =
647 p->v_bal > -1 ? 0 : 1;
648 p->v_bal = 0;
649 break;
650 }
651 break;
652 }
653 }
654 else { /* left heavy */
655 switch (p->v_bal) {
656 case 1: /* was right heavy */
657 p->v_bal = 0;
658 break;
659 case 0: /* was balanced */
660 p->v_bal = -1;
661 break;
662 case -1: /* was already left heavy */
663 switch (p->v_leftv_link[0]->v_bal) {
664 case -1: /* single rotate */
665 pp->v_link[ff] = rright(p)( t = (p)->v_link[0], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[0] = t->v_link[1]) ? (t->v_link[1]->
v_link[2] = (p)) : 0, (t->v_link[1] = (p))->v_link[2] =
t, (p) = t);
666 p->v_rightv_link[1]->v_bal = 0;
667 p->v_bal = 0;
668 break;
669 case 0: /* single rotate */
670 pp->v_link[ff] = rright(p)( t = (p)->v_link[0], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[0] = t->v_link[1]) ? (t->v_link[1]->
v_link[2] = (p)) : 0, (t->v_link[1] = (p))->v_link[2] =
t, (p) = t);
671 p->v_rightv_link[1]->v_bal = -1;
672 p->v_bal = 1;
673 break;
674 case 1: /* double rotate */
675 (void) rleft(p->v_left)( t = (p->v_link[0])->v_link[1], (t)->v_link[2] = (p
->v_link[0])->v_link[2], ((p->v_link[0])->v_link[
1] = t->v_link[0]) ? (t->v_link[0]->v_link[2] = (p->
v_link[0])) : 0, (t->v_link[0] = (p->v_link[0]))->v_link
[2] = t, (p->v_link[0]) = t);
676 pp->v_link[ff] = rright(p)( t = (p)->v_link[0], (t)->v_link[2] = (p)->v_link[2
], ((p)->v_link[0] = t->v_link[1]) ? (t->v_link[1]->
v_link[2] = (p)) : 0, (t->v_link[1] = (p))->v_link[2] =
t, (p) = t);
677 p->v_leftv_link[0]->v_bal =
678 p->v_bal < 1 ? 0 : -1;
679 p->v_rightv_link[1]->v_bal =
680 p->v_bal > -1 ? 0 : 1;
681 p->v_bal = 0;
682 break;
683 }
684 break;
685 }
686 }
687 /*
688 * If from insert, then we terminate when p is balanced. If from
689 * delete, then we terminate when p is unbalanced.
690 */
691 if ((p->v_bal == 0) ^ d)
692 break;
693 }
694}
695
696void
697plist(struct varent *p)
698{
699 struct varent *c;
700 int len;
701 sigset_t sigset;
702
703 if (setintr) {
704 sigemptyset(&sigset);
705 sigaddset(&sigset, SIGINT2);
706 sigprocmask(SIG_UNBLOCK2, &sigset, NULL((void *)0));
707 }
708
709 for (;;) {
710 while (p->v_leftv_link[0])
711 p = p->v_leftv_link[0];
712x:
713 if (p->v_parentv_link[2] == 0) /* is it the header? */
714 return;
715 len = blklen(p->vec);
716 (void) fprintf(cshout, "%s\t", short2str(p->v_name));
717 if (len != 1)
718 (void) fputc('(', cshout);
719 blkpr(cshout, p->vec);
720 if (len != 1)
721 (void) fputc(')', cshout);
722 (void) fputc('\n', cshout);
723 if (p->v_rightv_link[1]) {
724 p = p->v_rightv_link[1];
725 continue;
726 }
727 do {
728 c = p;
729 p = p->v_parentv_link[2];
730 } while (p->v_rightv_link[1] == c);
731 goto x;
732 }
733}