File: [local] / src / usr.bin / sup / src / Attic / stree.c (download)
Revision 1.10, Sun Feb 17 19:42:33 2002 UTC (22 years, 3 months ago) by millert
Branch: MAIN
CVS Tags: OPENBSD_4_5_BASE, OPENBSD_4_5, OPENBSD_4_4_BASE, OPENBSD_4_4, OPENBSD_4_3_BASE, OPENBSD_4_3, OPENBSD_4_2_BASE, OPENBSD_4_2, OPENBSD_4_1_BASE, OPENBSD_4_1, OPENBSD_4_0_BASE, OPENBSD_4_0, OPENBSD_3_9_BASE, OPENBSD_3_9, OPENBSD_3_8_BASE, OPENBSD_3_8, OPENBSD_3_7_BASE, OPENBSD_3_7, OPENBSD_3_6_BASE, OPENBSD_3_6, OPENBSD_3_5_BASE, OPENBSD_3_5, OPENBSD_3_4_BASE, OPENBSD_3_4, OPENBSD_3_3_BASE, OPENBSD_3_3, OPENBSD_3_2_BASE, OPENBSD_3_2, OPENBSD_3_1_BASE, OPENBSD_3_1 Changes since 1.9: +2 -2 lines
Manual cleanup of remaining userland __P use (excluding packages maintained outside the tree)
|
/* $OpenBSD: stree.c,v 1.10 2002/02/17 19:42:33 millert Exp $ */
/*
* Copyright (c) 1992 Carnegie Mellon University
* All Rights Reserved.
*
* Permission to use, copy, modify and distribute this software and its
* documentation is hereby granted, provided that both the copyright
* notice and this permission notice appear in all copies of the
* software, derivative works or modified versions, and any portions
* thereof, and that both notices appear in supporting documentation.
*
* CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
* CONDITION. CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
* ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
*
* Carnegie Mellon requests users of this software to return to
*
* Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
* School of Computer Science
* Carnegie Mellon University
* Pittsburgh PA 15213-3890
*
* any improvements or extensions that they make and grant Carnegie Mellon
* the rights to redistribute these changes.
*/
/*
* stree.c -- SUP Tree Routines
*
**********************************************************************
* HISTORY
* Revision 1.4 92/08/11 12:06:32 mrt
* Added copyright. Delinted
* [92/08/10 mrt]
*
*
* Revision 1.3 89/08/15 15:30:57 bww
* Changed code in Tlookup to Tsearch for each subpart of path.
* Added indent formatting code to Tprint.
* From "[89/06/24 gm0w]" at CMU.
* [89/08/15 bww]
*
* 20-May-87 Glenn Marcy (gm0w) at Carnegie-Mellon University
* Added code to please lint.
*
* 29-Dec-85 Glenn Marcy (gm0w) at Carnegie-Mellon University
* Added code to initialize new fields. Added Tfree routine.
*
* 27-Sep-85 Glenn Marcy (gm0w) at Carnegie-Mellon University
* Created.
*
**********************************************************************
*/
#include <libc.h>
#include <c.h>
#include <sys/param.h>
#include "supcdefs.h"
#include "supextern.h"
#define Static static /* comment for debugging */
Static TREE *Tmake(char *);
Static TREE *Trotll(TREE *, TREE *);
Static TREE *Trotlh(TREE *, TREE *);
Static TREE *Trothl(TREE *, TREE *);
Static TREE *Trothh(TREE *, TREE *);
Static void Tbalance(TREE **);
Static TREE *Tinsertavl(TREE **, char *, int, int *);
Static int Tsubprocess(TREE *, int, int (*f )(TREE *, void *), void *);
Static int Tprintone(TREE *, void *);
/*************************************************************
*** T R E E P R O C E S S I N G R O U T I N E S ***
*************************************************************/
void
Tfree(t)
TREE **t;
{
if (*t == NULL)
return;
Tfree(&((*t)->Tlink));
Tfree(&((*t)->Texec));
Tfree(&((*t)->Tlo));
Tfree(&((*t)->Thi));
if ((*t)->Tname)
free((*t)->Tname);
if ((*t)->Tuser)
free((*t)->Tuser);
if ((*t)->Tgroup)
free((*t)->Tgroup);
free(*t);
*t = NULL;
}
Static TREE *
Tmake(p)
char *p;
{
TREE *t;
t = (TREE *) malloc(sizeof(TREE));
if (t != NULL) {
t->Tname = (p == NULL) ? NULL : strdup(p);
t->Tflags = 0;
t->Tuid = 0;
t->Tgid = 0;
t->Tuser = NULL;
t->Tgroup = NULL;
t->Tmode = 0;
t->Tctime = 0;
t->Tmtime = 0;
t->Tlink = NULL;
t->Texec = NULL;
t->Tbf = 0;
t->Tlo = NULL;
t->Thi = NULL;
}
return (t);
}
Static TREE *
Trotll(tp, tl)
TREE *tp, *tl;
{
tp->Tlo = tl->Thi;
tl->Thi = tp;
tp->Tbf = tl->Tbf = 0;
return(tl);
}
Static TREE *
Trotlh (tp,tl)
TREE *tp, *tl;
{
TREE *th;
th = tl->Thi;
tp->Tlo = th->Thi;
tl->Thi = th->Tlo;
th->Thi = tp;
th->Tlo = tl;
tp->Tbf = tl->Tbf = 0;
if (th->Tbf == 1)
tp->Tbf = -1;
else if (th->Tbf == -1)
tl->Tbf = 1;
th->Tbf = 0;
return (th);
}
Static TREE *
Trothl(tp, th)
TREE *tp, *th;
{
TREE *tl;
tl = th->Tlo;
tp->Thi = tl->Tlo;
th->Tlo = tl->Thi;
tl->Tlo = tp;
tl->Thi = th;
tp->Tbf = th->Tbf = 0;
if (tl->Tbf == -1)
tp->Tbf = 1;
else if (tl->Tbf == 1)
th->Tbf = -1;
tl->Tbf = 0;
return (tl);
}
Static TREE *
Trothh(tp, th)
TREE *tp, *th;
{
tp->Thi = th->Tlo;
th->Tlo = tp;
tp->Tbf = th->Tbf = 0;
return (th);
}
Static void
Tbalance(t)
TREE **t;
{
if ((*t)->Tbf < 2 && (*t)->Tbf > -2)
return;
if ((*t)->Tbf > 0) {
if ((*t)->Tlo->Tbf > 0)
*t = Trotll(*t, (*t)->Tlo);
else
*t = Trotlh(*t, (*t)->Tlo);
} else {
if ((*t)->Thi->Tbf > 0)
*t = Trothl(*t, (*t)->Thi);
else
*t = Trothh(*t, (*t)->Thi);
}
}
Static TREE *
Tinsertavl(t, p, find, dh)
TREE **t;
char *p;
int find;
int *dh;
{
TREE *newt;
int cmp;
int deltah;
if (*t == NULL) {
if ((*t = Tmake(p)) != NULL)
*dh = 1;
return (*t);
}
if ((cmp = strcmp(p, (*t)->Tname)) == 0) {
if (!find)
return (NULL); /* node already exists */
*dh = 0;
return (*t);
} else if (cmp < 0) {
if ((newt = Tinsertavl(&((*t)->Tlo), p, find, &deltah)) == NULL)
return (NULL);
(*t)->Tbf += deltah;
} else {
if ((newt = Tinsertavl(&((*t)->Thi), p, find, &deltah)) == NULL)
return (NULL);
(*t)->Tbf -= deltah;
}
Tbalance(t);
if ((*t)->Tbf == 0)
deltah = 0;
*dh = deltah;
return (newt);
}
TREE *
Tinsert(t, p, find)
TREE **t;
char *p;
int find;
{
int deltah;
if (p != NULL && p[0] == '.' && p[1] == '/') {
p += 2;
while (*p == '/')
p++;
if (*p == 0)
p = ".";
}
return (Tinsertavl(t, p, find, &deltah));
}
TREE *
Tsearch(t, p)
TREE *t;
char *p;
{
TREE *x;
int cmp;
x = t;
while (x) {
cmp = strcmp(p, x->Tname);
if (cmp == 0)
return (x);
if (cmp < 0)
x = x->Tlo;
else
x = x->Thi;
}
return (NULL);
}
TREE *
Tlookup (t, p)
TREE *t;
char *p;
{
TREE *x;
char buf[MAXPATHLEN];
if (p == NULL)
return (NULL);
if (p[0] == '.' && p[1] == '/') {
p += 2;
while (*p == '/')
p++;
if (*p == 0)
p = ".";
}
if ((x = Tsearch(t, p)) != NULL)
return (x);
if (*p != '/' && (x = Tsearch(t, ".")) != NULL)
return (x);
(void) strlcpy(buf, p, sizeof(buf));
while ((p = strrchr(buf, '/')) != NULL) {
while (p >= buf && *(p-1) == '/')
p--;
if (p == buf)
*(p+1) = '\0';
else
*p = '\0';
if ((x = Tsearch(t, buf)) != NULL)
return (x);
if (p == buf)
break;
}
return (NULL);
}
Static int process_level;
Static int
Tsubprocess (t, reverse, f, argp)
TREE *t;
int reverse;
int (*f)(TREE *, void *);
void *argp;
{
int x = SCMOK;
process_level++;
if (reverse ? t->Thi : t->Tlo)
x = Tsubprocess(reverse ? t->Thi : t->Tlo, reverse, f, argp);
if (x == SCMOK) {
x = (*f)(t, argp);
if (x == SCMOK) {
if (reverse ? t->Tlo : t->Thi)
x = Tsubprocess (reverse ? t->Tlo : t->Thi,
reverse, f, argp);
}
}
process_level--;
return (x);
}
/* VARARGS2 */
int
Trprocess(t, f, args)
TREE *t;
int (*f)(TREE *, void *);
void *args;
{
if (t == NULL)
return (SCMOK);
process_level = 0;
return (Tsubprocess(t, TRUE, f, args));
}
/* VARARGS2 */
int
Tprocess(t, f, args)
TREE *t;
int (*f)(TREE *, void *);
void *args;
{
if (t == NULL)
return (SCMOK);
process_level = 0;
return (Tsubprocess(t, FALSE, f, args));
}
Static int
Tprintone(t, v)
TREE *t;
void *v;
{
int i;
for (i = 0; i < (process_level*2); i++)
(void) putchar(' ');
printf("Node at %p name '%s' flags %o hi %p lo %p\n",
t, t->Tname, t->Tflags, t->Thi, t->Tlo);
return (SCMOK);
}
void
Tprint(t, p) /* print tree -- for debugging */
TREE *t;
char *p;
{
printf("%s\n",p);
(void) Tprocess(t,Tprintone, NULL);
printf("End of tree\n");
(void) fflush(stdout);
}