xref: /openbsd-src/bin/csh/set.c (revision a28daedfc357b214be5c701aa8ba8adb29a7f1c2) 
1 /*	$OpenBSD: set.c,v 1.10 2003/06/11 21:09:50 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 #ifndef lint
34 #if 0
35 static char sccsid[] = "@(#)set.c	8.1 (Berkeley) 5/31/93";
36 #else
37 static char rcsid[] = "$OpenBSD: set.c,v 1.10 2003/06/11 21:09:50 deraadt Exp $";
38 #endif
39 #endif /* not lint */
40 
41 #include <sys/types.h>
42 #include <stdlib.h>
43 #ifndef SHORT_STRINGS
44 #include <string.h>
45 #endif /* SHORT_STRINGS */
46 #include <stdarg.h>
47 
48 #include "csh.h"
49 #include "extern.h"
50 
51 static Char	*getinx(Char *, int *);
52 static void	 asx(Char *, int, Char *);
53 static struct varent
54 		*getvx(Char *, int);
55 static Char	*xset(Char *, Char ***);
56 static Char	*operate(int, Char *, Char *);
57 static void	 putn1(int);
58 static struct varent
59 		*madrof(Char *, struct varent *);
60 static void	 unsetv1(struct varent *);
61 static void	 exportpath(Char **);
62 static void	 balance(struct varent *, int, int);
63 
64 
65 /*
66  * C Shell
67  */
68 
69 void
70 /*ARGSUSED*/
71 doset(Char **v, struct command *t)
72 {
73     Char *p;
74     Char   *vp, op;
75     Char  **vecp;
76     bool    hadsub;
77     int     subscr;
78 
79     v++;
80     p = *v++;
81     if (p == 0) {
82 	prvars();
83 	return;
84     }
85     do {
86 	hadsub = 0;
87 	vp = p;
88 	if (letter(*p))
89 	    for (; alnum(*p); p++)
90 		continue;
91 	if (vp == p || !letter(*vp))
92 	    stderror(ERR_NAME | ERR_VARBEGIN);
93 	if ((p - vp) > MAXVARLEN) {
94 	    stderror(ERR_NAME | ERR_VARTOOLONG);
95 	    return;
96 	}
97 	if (*p == '[') {
98 	    hadsub++;
99 	    p = getinx(p, &subscr);
100 	}
101 	if ((op = *p) != '\0') {
102 	    *p++ = 0;
103 	    if (*p == 0 && *v && **v == '(')
104 		p = *v++;
105 	}
106 	else if (*v && eq(*v, STRequal)) {
107 	    op = '=', v++;
108 	    if (*v)
109 		p = *v++;
110 	}
111 	if (op && op != '=')
112 	    stderror(ERR_NAME | ERR_SYNTAX);
113 	if (eq(p, STRLparen)) {
114 	    Char **e = v;
115 
116 	    if (hadsub)
117 		stderror(ERR_NAME | ERR_SYNTAX);
118 	    for (;;) {
119 		if (!*e)
120 		    stderror(ERR_NAME | ERR_MISSING, ')');
121 		if (**e == ')')
122 		    break;
123 		e++;
124 	    }
125 	    p = *e;
126 	    *e = 0;
127 	    vecp = saveblk(v);
128 	    set1(vp, vecp, &shvhed);
129 	    *e = p;
130 	    v = e + 1;
131 	}
132 	else if (hadsub)
133 	    asx(vp, subscr, Strsave(p));
134 	else
135 	    set(vp, Strsave(p));
136 	if (eq(vp, STRpath)) {
137 	    exportpath(adrof(STRpath)->vec);
138 	    dohash(NULL, NULL);
139 	}
140 	else if (eq(vp, STRhistchars)) {
141 	    Char *pn = value(STRhistchars);
142 
143 	    HIST = *pn++;
144 	    HISTSUB = *pn;
145 	}
146 	else if (eq(vp, STRuser)) {
147 	    Setenv(STRUSER, value(vp));
148 	    Setenv(STRLOGNAME, value(vp));
149 	}
150 	else if (eq(vp, STRwordchars)) {
151 	    word_chars = value(vp);
152 	}
153 	else if (eq(vp, STRterm))
154 	    Setenv(STRTERM, value(vp));
155 	else if (eq(vp, STRhome)) {
156 	    Char *cp;
157 
158 	    cp = Strsave(value(vp));	/* get the old value back */
159 
160 	    /*
161 	     * convert to canonical pathname (possibly resolving symlinks)
162 	     */
163 	    cp = dcanon(cp, cp);
164 
165 	    set(vp, Strsave(cp));	/* have to save the new val */
166 
167 	    /* and now mirror home with HOME */
168 	    Setenv(STRHOME, cp);
169 	    /* fix directory stack for new tilde home */
170 	    dtilde();
171 	    xfree((ptr_t) cp);
172 	}
173 #ifdef FILEC
174 	else if (eq(vp, STRfilec))
175 	    filec = 1;
176 #endif
177     } while ((p = *v++) != NULL);
178 }
179 
180 static Char *
181 getinx(Char *cp, int *ip)
182 {
183 
184     *ip = 0;
185     *cp++ = 0;
186     while (*cp && Isdigit(*cp))
187 	*ip = *ip * 10 + *cp++ - '0';
188     if (*cp++ != ']')
189 	stderror(ERR_NAME | ERR_SUBSCRIPT);
190     return (cp);
191 }
192 
193 static void
194 asx(Char *vp, int subscr, Char *p)
195 {
196     struct varent *v = getvx(vp, subscr);
197 
198     xfree((ptr_t) v->vec[subscr - 1]);
199     v->vec[subscr - 1] = globone(p, G_APPEND);
200 }
201 
202 static struct varent *
203 getvx(Char *vp, int subscr)
204 {
205     struct varent *v = adrof(vp);
206 
207     if (v == 0)
208 	udvar(vp);
209     if (subscr < 1 || subscr > blklen(v->vec))
210 	stderror(ERR_NAME | ERR_RANGE);
211     return (v);
212 }
213 
214 void
215 /*ARGSUSED*/
216 dolet(Char **v, struct command *t)
217 {
218     Char *p;
219     Char   *vp, c, op;
220     bool    hadsub;
221     int     subscr;
222 
223     v++;
224     p = *v++;
225     if (p == 0) {
226 	prvars();
227 	return;
228     }
229     do {
230 	hadsub = 0;
231 	vp = p;
232 	if (letter(*p))
233 	    for (; alnum(*p); p++)
234 		continue;
235 	if (vp == p || !letter(*vp))
236 	    stderror(ERR_NAME | ERR_VARBEGIN);
237 	if ((p - vp) > MAXVARLEN)
238 	    stderror(ERR_NAME | ERR_VARTOOLONG);
239 	if (*p == '[') {
240 	    hadsub++;
241 	    p = getinx(p, &subscr);
242 	}
243 	if (*p == 0 && *v)
244 	    p = *v++;
245 	if ((op = *p) != '\0')
246 	    *p++ = 0;
247 	else
248 	    stderror(ERR_NAME | ERR_ASSIGN);
249 
250 	if (*p == '\0' && *v == NULL)
251 	    stderror(ERR_NAME | ERR_ASSIGN);
252 
253 	vp = Strsave(vp);
254 	if (op == '=') {
255 	    c = '=';
256 	    p = xset(p, &v);
257 	}
258 	else {
259 	    c = *p++;
260 	    if (any("+-", c)) {
261 		if (c != op || *p)
262 		    stderror(ERR_NAME | ERR_UNKNOWNOP);
263 		p = Strsave(STR1);
264 	    }
265 	    else {
266 		if (any("<>", op)) {
267 		    if (c != op)
268 			stderror(ERR_NAME | ERR_UNKNOWNOP);
269 		    c = *p++;
270 		    stderror(ERR_NAME | ERR_SYNTAX);
271 		}
272 		if (c != '=')
273 		    stderror(ERR_NAME | ERR_UNKNOWNOP);
274 		p = xset(p, &v);
275 	    }
276 	}
277 	if (op == '=')
278 	    if (hadsub)
279 		asx(vp, subscr, p);
280 	    else
281 		set(vp, p);
282 	else if (hadsub) {
283 	    struct varent *gv = getvx(vp, subscr);
284 
285 	    asx(vp, subscr, operate(op, gv->vec[subscr - 1], p));
286 	}
287 	else
288 	    set(vp, operate(op, value(vp), p));
289 	if (eq(vp, STRpath)) {
290 	    exportpath(adrof(STRpath)->vec);
291 	    dohash(NULL, NULL);
292 	}
293 	xfree((ptr_t) vp);
294 	if (c != '=')
295 	    xfree((ptr_t) p);
296     } while ((p = *v++) != NULL);
297 }
298 
299 static Char *
300 xset(Char *cp, Char ***vp)
301 {
302     Char *dp;
303 
304     if (*cp) {
305 	dp = Strsave(cp);
306 	--(*vp);
307 	xfree((ptr_t) ** vp);
308 	**vp = dp;
309     }
310     return (putn(expr(vp)));
311 }
312 
313 static Char *
314 operate(int op, Char *vp, Char *p)
315 {
316     Char    opr[2];
317     Char   *vec[5];
318     Char **v = vec;
319     Char  **vecp = v;
320     int i;
321 
322     if (op != '=') {
323 	if (*vp)
324 	    *v++ = vp;
325 	opr[0] = op;
326 	opr[1] = 0;
327 	*v++ = opr;
328 	if (op == '<' || op == '>')
329 	    *v++ = opr;
330     }
331     *v++ = p;
332     *v++ = 0;
333     i = expr(&vecp);
334     if (*vecp)
335 	stderror(ERR_NAME | ERR_EXPRESSION);
336     return (putn(i));
337 }
338 
339 static Char *putp;
340 
341 Char   *
342 putn(int n)
343 {
344     int     num;
345     static Char number[15];
346 
347     putp = number;
348     if (n < 0) {
349 	n = -n;
350 	*putp++ = '-';
351     }
352     num = 2;			/* confuse lint */
353     if (sizeof(int) == num && ((unsigned int) n) == 0x8000) {
354 	*putp++ = '3';
355 	n = 2768;
356 #ifdef pdp11
357     }
358 #else
359     }
360     else {
361 	num = 4;		/* confuse lint */
362 	if (sizeof(int) == num && ((unsigned int) n) == 0x80000000) {
363 	    *putp++ = '2';
364 	    n = 147483648;
365 	}
366     }
367 #endif
368     putn1(n);
369     *putp = 0;
370     return (Strsave(number));
371 }
372 
373 static void
374 putn1(int n)
375 {
376     if (n > 9)
377 	putn1(n / 10);
378     *putp++ = n % 10 + '0';
379 }
380 
381 int
382 getn(Char *cp)
383 {
384     int n;
385     int     sign;
386 
387     sign = 0;
388     if (cp[0] == '+' && cp[1])
389 	cp++;
390     if (*cp == '-') {
391 	sign++;
392 	cp++;
393 	if (!Isdigit(*cp))
394 	    stderror(ERR_NAME | ERR_BADNUM);
395     }
396     n = 0;
397     while (Isdigit(*cp))
398 	n = n * 10 + *cp++ - '0';
399     if (*cp)
400 	stderror(ERR_NAME | ERR_BADNUM);
401     return (sign ? -n : n);
402 }
403 
404 Char   *
405 value1(Char *var, struct varent *head)
406 {
407     struct varent *vp;
408 
409     vp = adrof1(var, head);
410     return (vp == 0 || vp->vec[0] == 0 ? STRNULL : vp->vec[0]);
411 }
412 
413 static struct varent *
414 madrof(Char *pat, struct varent *vp)
415 {
416     struct varent *vp1;
417 
418     for (; vp; vp = vp->v_right) {
419 	if (vp->v_left && (vp1 = madrof(pat, vp->v_left)))
420 	    return vp1;
421 	if (Gmatch(vp->v_name, pat))
422 	    return vp;
423     }
424     return vp;
425 }
426 
427 struct varent *
428 adrof1(Char *name, struct varent *v)
429 {
430     int cmp;
431 
432     v = v->v_left;
433     while (v && ((cmp = *name - *v->v_name) ||
434 		 (cmp = Strcmp(name, v->v_name))))
435 	if (cmp < 0)
436 	    v = v->v_left;
437 	else
438 	    v = v->v_right;
439     return v;
440 }
441 
442 /*
443  * The caller is responsible for putting value in a safe place
444  */
445 void
446 set(Char *var, Char *val)
447 {
448     Char **vec = (Char **) xmalloc((size_t) (2 * sizeof(Char **)));
449 
450     vec[0] = val;
451     vec[1] = 0;
452     set1(var, vec, &shvhed);
453 }
454 
455 void
456 set1(Char *var, Char **vec, struct varent *head)
457 {
458     Char **oldv = vec;
459 
460     gflag = 0;
461     tglob(oldv);
462     if (gflag) {
463 	vec = globall(oldv);
464 	if (vec == 0) {
465 	    blkfree(oldv);
466 	    stderror(ERR_NAME | ERR_NOMATCH);
467 	    return;
468 	}
469 	blkfree(oldv);
470 	gargv = 0;
471     }
472     setq(var, vec, head);
473 }
474 
475 
476 void
477 setq(Char *name, Char **vec, struct varent *p)
478 {
479     struct varent *c;
480     int f;
481 
482     f = 0;			/* tree hangs off the header's left link */
483     while ((c = p->v_link[f]) != NULL) {
484 	if ((f = *name - *c->v_name) == 0 &&
485 	    (f = Strcmp(name, c->v_name)) == 0) {
486 	    blkfree(c->vec);
487 	    goto found;
488 	}
489 	p = c;
490 	f = f > 0;
491     }
492     p->v_link[f] = c = (struct varent *) xmalloc((size_t) sizeof(struct varent));
493     c->v_name = Strsave(name);
494     c->v_bal = 0;
495     c->v_left = c->v_right = 0;
496     c->v_parent = p;
497     balance(p, f, 0);
498 found:
499     trim(c->vec = vec);
500 }
501 
502 void
503 /*ARGSUSED*/
504 unset(Char **v, struct command *t)
505 {
506     unset1(v, &shvhed);
507 #ifdef FILEC
508     if (adrof(STRfilec) == 0)
509 	filec = 0;
510 #endif
511     if (adrof(STRhistchars) == 0) {
512 	HIST = '!';
513 	HISTSUB = '^';
514     }
515     if (adrof(STRwordchars) == 0)
516 	word_chars = STR_WORD_CHARS;
517 }
518 
519 void
520 unset1(Char *v[], struct varent *head)
521 {
522     struct varent *vp;
523     int cnt;
524 
525     while (*++v) {
526 	cnt = 0;
527 	while ((vp = madrof(*v, head->v_left)) != NULL)
528 	    unsetv1(vp), cnt++;
529 	if (cnt == 0)
530 	    setname(vis_str(*v));
531     }
532 }
533 
534 void
535 unsetv(Char *var)
536 {
537     struct varent *vp;
538 
539     if ((vp = adrof1(var, &shvhed)) == 0)
540 	udvar(var);
541     unsetv1(vp);
542 }
543 
544 static void
545 unsetv1(struct varent *p)
546 {
547     struct varent *c, *pp;
548     int f;
549 
550     /*
551      * Free associated memory first to avoid complications.
552      */
553     blkfree(p->vec);
554     xfree((ptr_t) p->v_name);
555     /*
556      * If p is missing one child, then we can move the other into where p is.
557      * Otherwise, we find the predecessor of p, which is guaranteed to have no
558      * right child, copy it into p, and move it's left child into it.
559      */
560     if (p->v_right == 0)
561 	c = p->v_left;
562     else if (p->v_left == 0)
563 	c = p->v_right;
564     else {
565 	for (c = p->v_left; c->v_right; c = c->v_right)
566 	    continue;
567 	p->v_name = c->v_name;
568 	p->vec = c->vec;
569 	p = c;
570 	c = p->v_left;
571     }
572     /*
573      * Move c into where p is.
574      */
575     pp = p->v_parent;
576     f = pp->v_right == p;
577     if ((pp->v_link[f] = c) != NULL)
578 	c->v_parent = pp;
579     /*
580      * Free the deleted node, and rebalance.
581      */
582     xfree((ptr_t) p);
583     balance(pp, f, 1);
584 }
585 
586 void
587 setNS(Char *cp)
588 {
589     set(cp, Strsave(STRNULL));
590 }
591 
592 void
593 /*ARGSUSED*/
594 shift(Char **v, struct command *t)
595 {
596     struct varent *argv;
597     Char *name;
598 
599     v++;
600     name = *v;
601     if (name == 0)
602 	name = STRargv;
603     else
604 	(void) strip(name);
605     argv = adrof(name);
606     if (argv == 0)
607 	udvar(name);
608     if (argv->vec[0] == 0)
609 	stderror(ERR_NAME | ERR_NOMORE);
610     lshift(argv->vec, 1);
611 }
612 
613 static void
614 exportpath(Char **val)
615 {
616     Char    exppath[BUFSIZ];
617 
618     exppath[0] = 0;
619     if (val)
620 	while (*val) {
621 	    if (Strlen(*val) + Strlen(exppath) + 2 > BUFSIZ) {
622 		(void) fprintf(csherr,
623 			       "Warning: ridiculously long PATH truncated\n");
624 		break;
625 	    }
626 	    (void) Strlcat(exppath, *val++, sizeof exppath/sizeof(Char));
627 	    if (*val == 0 || eq(*val, STRRparen))
628 		break;
629 	    (void) Strlcat(exppath, STRcolon, sizeof exppath/sizeof(Char));
630 	}
631     Setenv(STRPATH, exppath);
632 }
633 
634 #ifndef lint
635  /*
636   * Lint thinks these have null effect
637   */
638  /* macros to do single rotations on node p */
639 #define rright(p) (\
640 	t = (p)->v_left,\
641 	(t)->v_parent = (p)->v_parent,\
642 	((p)->v_left = t->v_right) ? (t->v_right->v_parent = (p)) : 0,\
643 	(t->v_right = (p))->v_parent = t,\
644 	(p) = t)
645 #define rleft(p) (\
646 	t = (p)->v_right,\
647 	(t)->v_parent = (p)->v_parent,\
648 	((p)->v_right = t->v_left) ? (t->v_left->v_parent = (p)) : 0,\
649 	(t->v_left = (p))->v_parent = t,\
650 	(p) = t)
651 #else
652 struct varent *
653 rleft(struct varent *p)
654 {
655     return (p);
656 }
657 struct varent *
658 rright(struct varent *p)
659 {
660     return (p);
661 }
662 
663 #endif				/* ! lint */
664 
665 
666 /*
667  * Rebalance a tree, starting at p and up.
668  * F == 0 means we've come from p's left child.
669  * D == 1 means we've just done a delete, otherwise an insert.
670  */
671 static void
672 balance(struct varent *p, int f, int d)
673 {
674     struct varent *pp;
675 
676 #ifndef lint
677     struct varent *t;	/* used by the rotate macros */
678 
679 #endif
680     int ff;
681 
682     /*
683      * Ok, from here on, p is the node we're operating on; pp is it's parent; f
684      * is the branch of p from which we have come; ff is the branch of pp which
685      * is p.
686      */
687     for (; (pp = p->v_parent) != NULL; p = pp, f = ff) {
688 	ff = pp->v_right == p;
689 	if (f ^ d) {		/* right heavy */
690 	    switch (p->v_bal) {
691 	    case -1:		/* was left heavy */
692 		p->v_bal = 0;
693 		break;
694 	    case 0:		/* was balanced */
695 		p->v_bal = 1;
696 		break;
697 	    case 1:		/* was already right heavy */
698 		switch (p->v_right->v_bal) {
699 		case 1:	/* single rotate */
700 		    pp->v_link[ff] = rleft(p);
701 		    p->v_left->v_bal = 0;
702 		    p->v_bal = 0;
703 		    break;
704 		case 0:	/* single rotate */
705 		    pp->v_link[ff] = rleft(p);
706 		    p->v_left->v_bal = 1;
707 		    p->v_bal = -1;
708 		    break;
709 		case -1:	/* double rotate */
710 		    (void) rright(p->v_right);
711 		    pp->v_link[ff] = rleft(p);
712 		    p->v_left->v_bal =
713 			p->v_bal < 1 ? 0 : -1;
714 		    p->v_right->v_bal =
715 			p->v_bal > -1 ? 0 : 1;
716 		    p->v_bal = 0;
717 		    break;
718 		}
719 		break;
720 	    }
721 	}
722 	else {			/* left heavy */
723 	    switch (p->v_bal) {
724 	    case 1:		/* was right heavy */
725 		p->v_bal = 0;
726 		break;
727 	    case 0:		/* was balanced */
728 		p->v_bal = -1;
729 		break;
730 	    case -1:		/* was already left heavy */
731 		switch (p->v_left->v_bal) {
732 		case -1:	/* single rotate */
733 		    pp->v_link[ff] = rright(p);
734 		    p->v_right->v_bal = 0;
735 		    p->v_bal = 0;
736 		    break;
737 		case 0:	/* single rotate */
738 		    pp->v_link[ff] = rright(p);
739 		    p->v_right->v_bal = -1;
740 		    p->v_bal = 1;
741 		    break;
742 		case 1:	/* double rotate */
743 		    (void) rleft(p->v_left);
744 		    pp->v_link[ff] = rright(p);
745 		    p->v_left->v_bal =
746 			p->v_bal < 1 ? 0 : -1;
747 		    p->v_right->v_bal =
748 			p->v_bal > -1 ? 0 : 1;
749 		    p->v_bal = 0;
750 		    break;
751 		}
752 		break;
753 	    }
754 	}
755 	/*
756 	 * If from insert, then we terminate when p is balanced. If from
757 	 * delete, then we terminate when p is unbalanced.
758 	 */
759 	if ((p->v_bal == 0) ^ d)
760 	    break;
761     }
762 }
763 
764 void
765 plist(struct varent *p)
766 {
767     struct varent *c;
768     int len;
769     sigset_t sigset;
770 
771     if (setintr) {
772 	sigemptyset(&sigset);
773 	sigaddset(&sigset, SIGINT);
774 	sigprocmask(SIG_UNBLOCK, &sigset, NULL);
775     }
776 
777     for (;;) {
778 	while (p->v_left)
779 	    p = p->v_left;
780 x:
781 	if (p->v_parent == 0)	/* is it the header? */
782 	    return;
783 	len = blklen(p->vec);
784 	(void) fprintf(cshout, "%s\t", short2str(p->v_name));
785 	if (len != 1)
786 	    (void) fputc('(', cshout);
787 	blkpr(cshout, p->vec);
788 	if (len != 1)
789 	    (void) fputc(')', cshout);
790 	(void) fputc('\n', cshout);
791 	if (p->v_right) {
792 	    p = p->v_right;
793 	    continue;
794 	}
795 	do {
796 	    c = p;
797 	    p = p->v_parent;
798 	} while (p->v_right == c);
799 	goto x;
800     }
801 }
802