usr.sbin/sup/source/stree.c

   1 /*      $NetBSD: stree.c,v 1.14 2009/10/17 20:46:03 christos Exp $      */
   2
   3 /*
   4  * Copyright (c) 1992 Carnegie Mellon University
   5  * All Rights Reserved.
   6  *
   7  * Permission to use, copy, modify and distribute this software and its
   8  * documentation is hereby granted, provided that both the copyright
   9  * notice and this permission notice appear in all copies of the
  10  * software, derivative works or modified versions, and any portions
  11  * thereof, and that both notices appear in supporting documentation.
  12  *
  13  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  14  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  15  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  16  *
  17  * Carnegie Mellon requests users of this software to return to
  18  *
  19  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  20  *  School of Computer Science
  21  *  Carnegie Mellon University
  22  *  Pittsburgh PA 15213-3890
  23  *
  24  * any improvements or extensions that they make and grant Carnegie Mellon
  25  * the rights to redistribute these changes.
  26  */
  27 /*
  28  * stree.c -- SUP Tree Routines
  29  *
  30  **********************************************************************
  31  * HISTORY
  32  * Revision 1.4  92/08/11  12:06:32  mrt
  33  *      Added copyright. Delinted
  34  *      [92/08/10            mrt]
  35  *
  36  *
  37  * Revision 1.3  89/08/15  15:30:57  bww
  38  *      Changed code in Tlookup to Tsearch for each subpart of path.
  39  *      Added indent formatting code to Tprint.
  40  *      From "[89/06/24            gm0w]" at CMU.
  41  *      [89/08/15            bww]
  42  *
  43  * 20-May-87  Glenn Marcy (gm0w) at Carnegie-Mellon University
  44  *      Added code to please lint.
  45  *
  46  * 29-Dec-85  Glenn Marcy (gm0w) at Carnegie-Mellon University
  47  *      Added code to initialize new fields.  Added Tfree routine.
  48  *
  49  * 27-Sep-85  Glenn Marcy (gm0w) at Carnegie-Mellon University
  50  *      Created.
  51  *
  52  **********************************************************************
  53  */
  54
  55 #include <sys/param.h>
  56 #include <assert.h>
  57 #include "supcdefs.h"
  58 #include "supextern.h"
  59 #include "libc.h"
  60 #include "c.h"
  61
  62 static TREE *Tmake(const char *);
  63 static TREE *Trotll(TREE *, TREE *);
  64 static TREE *Trotlh(TREE *, TREE *);
  65 static TREE *Trothl(TREE *, TREE *);
  66 static TREE *Trothh(TREE *, TREE *);
  67 static void Tbalance(TREE **);
  68 static TREE *Tinsertavl(TREE **, const char *, int, int *);
  69 static int Tsubprocess(TREE *, int, int (*f) (TREE *, void *), void *);
  70 static int Tprintone(TREE *, void *);
  71
  72
  73 /*************************************************************
  74  ***    T R E E   P R O C E S S I N G   R O U T I N E S    ***
  75  *************************************************************/
  76
  77 void
  78 Tfree(TREE ** t)
  79 {
  80         if (*t == NULL)
  81                 return;
  82         Tfree(&((*t)->Tlink));
  83         Tfree(&((*t)->Texec));
  84         Tfree(&((*t)->Tlo));
  85         Tfree(&((*t)->Thi));
  86         if ((*t)->Tname)
  87                 free((*t)->Tname);
  88         if ((*t)->Tuser)
  89                 free((*t)->Tuser);
  90         if ((*t)->Tgroup)
  91                 free((*t)->Tgroup);
  92         free(*(char **) t);
  93         *t = NULL;
  94 }
  95
  96 static TREE *
  97 Tmake(const char *p)
  98 {
  99         TREE *t;
 100         t = (TREE *) malloc(sizeof(TREE));
 101         if (t == NULL)
 102                 goaway("Cannot allocate memory");
 103         t->Tname = (p == NULL) ? NULL : estrdup(p);
 104         t->Tflags = 0;
 105         t->Tuid = 0;
 106         t->Tgid = 0;
 107         t->Tuser = NULL;
 108         t->Tgroup = NULL;
 109         t->Tmode = 0;
 110         t->Tctime = 0;
 111         t->Tmtime = 0;
 112         t->Tlink = NULL;
 113         t->Texec = NULL;
 114         t->Tbf = 0;
 115         t->Tlo = NULL;
 116         t->Thi = NULL;
 117         return (t);
 118 }
 119
 120 static TREE *
 121 Trotll(TREE * tp, TREE * tl)
 122 {
 123         tp->Tlo = tl->Thi;
 124         tl->Thi = tp;
 125         tp->Tbf = tl->Tbf = 0;
 126         return (tl);
 127 }
 128
 129 static TREE *
 130 Trotlh(TREE * tp, TREE * tl)
 131 {
 132         TREE *th;
 133
 134         th = tl->Thi;
 135         tp->Tlo = th->Thi;
 136         tl->Thi = th->Tlo;
 137         th->Thi = tp;
 138         th->Tlo = tl;
 139         tp->Tbf = tl->Tbf = 0;
 140         if (th->Tbf == 1)
 141                 tp->Tbf = -1;
 142         else if (th->Tbf == -1)
 143                 tl->Tbf = 1;
 144         th->Tbf = 0;
 145         return (th);
 146 }
 147
 148 static TREE *
 149 Trothl(TREE * tp, TREE * th)
 150 {
 151         TREE *tl;
 152
 153         tl = th->Tlo;
 154         tp->Thi = tl->Tlo;
 155         th->Tlo = tl->Thi;
 156         tl->Tlo = tp;
 157         tl->Thi = th;
 158         tp->Tbf = th->Tbf = 0;
 159         if (tl->Tbf == -1)
 160                 tp->Tbf = 1;
 161         else if (tl->Tbf == 1)
 162                 th->Tbf = -1;
 163         tl->Tbf = 0;
 164         return (tl);
 165 }
 166
 167 static TREE *
 168 Trothh(TREE * tp, TREE * th)
 169 {
 170         tp->Thi = th->Tlo;
 171         th->Tlo = tp;
 172         tp->Tbf = th->Tbf = 0;
 173         return (th);
 174 }
 175
 176 static void
 177 Tbalance(TREE ** t)
 178 {
 179         if ((*t)->Tbf < 2 && (*t)->Tbf > -2)
 180                 return;
 181         if ((*t)->Tbf > 0) {
 182                 if ((*t)->Tlo->Tbf > 0)
 183                         *t = Trotll(*t, (*t)->Tlo);
 184                 else
 185                         *t = Trotlh(*t, (*t)->Tlo);
 186         } else {
 187                 if ((*t)->Thi->Tbf > 0)
 188                         *t = Trothl(*t, (*t)->Thi);
 189                 else
 190                         *t = Trothh(*t, (*t)->Thi);
 191         }
 192 }
 193
 194 static TREE *
 195 Tinsertavl(TREE ** t, const char *p, int find, int *dh)
 196 {
 197         TREE *newt;
 198         int cmp;
 199         int deltah;
 200
 201         if (*t == NULL) {
 202                 *t = Tmake(p);
 203                 *dh = 1;
 204                 return (*t);
 205         }
 206         if ((cmp = strcmp(p, (*t)->Tname)) == 0) {
 207                 if (!find)
 208                         return (NULL);  /* node already exists */
 209                 *dh = 0;
 210                 return (*t);
 211         } else if (cmp < 0) {
 212                 if ((newt = Tinsertavl(&((*t)->Tlo), p, find, &deltah)) == NULL)
 213                         return (NULL);
 214                 (*t)->Tbf += deltah;
 215         } else {
 216                 if ((newt = Tinsertavl(&((*t)->Thi), p, find, &deltah)) == NULL)
 217                         return (NULL);
 218                 (*t)->Tbf -= deltah;
 219         }
 220         Tbalance(t);
 221         if ((*t)->Tbf == 0)
 222                 deltah = 0;
 223         *dh = deltah;
 224         return (newt);
 225 }
 226
 227 TREE *
 228 Tinsert(TREE ** t, const char *p, int find)
 229 {
 230         int deltah;
 231
 232         if (p != NULL && p[0] == '.' && p[1] == '/') {
 233                 p += 2;
 234                 while (*p == '/')
 235                         p++;
 236                 if (*p == 0)
 237                         p = ".";
 238         }
 239         return (Tinsertavl(t, p, find, &deltah));
 240 }
 241
 242 TREE *
 243 Tsearch(TREE * t, const char *p)
 244 {
 245         TREE *x;
 246         int cmp;
 247
 248         x = t;
 249         while (x) {
 250                 cmp = strcmp(p, x->Tname);
 251                 if (cmp == 0)
 252                         return (x);
 253                 if (cmp < 0)
 254                         x = x->Tlo;
 255                 else
 256                         x = x->Thi;
 257         }
 258         return (NULL);
 259 }
 260
 261 TREE *
 262 Tlookup(TREE * t, const char *p)
 263 {
 264         TREE *x;
 265         char buf[MAXPATHLEN + 1];
 266         char *q;
 267
 268         if (p == NULL)
 269                 return (NULL);
 270         if (p[0] == '.' && p[1] == '/') {
 271                 p += 2;
 272                 while (*p == '/')
 273                         p++;
 274                 if (*p == 0)
 275                         p = ".";
 276         }
 277         if ((x = Tsearch(t, p)) != NULL)
 278                 return (x);
 279         if (*p != '/' && (x = Tsearch(t, ".")) != NULL)
 280                 return (x);
 281         (void) strncpy(buf, p, sizeof(buf) - 1);
 282         buf[MAXPATHLEN] = '\0';
 283         while ((q = strrchr(buf, '/')) != NULL) {
 284                 while (q >= buf && *(q - 1) == '/')
 285                         q--;
 286                 if (q == buf)
 287                         *(q + 1) = '\0';
 288                 else
 289                         *q = '\0';
 290                 if ((x = Tsearch(t, buf)) != NULL)
 291                         return (x);
 292                 if (q == buf)
 293                         break;
 294         }
 295         return (NULL);
 296 }
 297
 298 static int process_level;
 299
 300 static int
 301 Tsubprocess(TREE * t, int reverse, int (*f) (TREE *, void *), void *argp)
 302 {
 303         int x = SCMOK;
 304         process_level++;
 305         if (reverse ? t->Thi : t->Tlo)
 306                 x = Tsubprocess(reverse ? t->Thi : t->Tlo,
 307                     reverse, f, argp);
 308         if (x == SCMOK) {
 309                 x = (*f) (t, argp);
 310                 if (x == SCMOK) {
 311                         if (reverse ? t->Tlo : t->Thi)
 312                                 x = Tsubprocess(reverse ? t->Tlo : t->Thi,
 313                                     reverse, f, argp);
 314                 }
 315         }
 316         process_level--;
 317         return (x);
 318 }
 319
 320 /* VARARGS2 */
 321 int
 322 Trprocess(TREE * t, int (*f) (TREE *, void *), void *args)
 323 {
 324         if (t == NULL)
 325                 return (SCMOK);
 326         process_level = 0;
 327         return (Tsubprocess(t, TRUE, f, args));
 328 }
 329
 330 /* VARARGS2 */
 331 int
 332 Tprocess(TREE * t, int (*f) (TREE *, void *), void *args)
 333 {
 334         if (t == NULL)
 335                 return (SCMOK);
 336         process_level = 0;
 337         return (Tsubprocess(t, FALSE, f, args));
 338 }
 339
 340 static int
 341 /*ARGSUSED*/
 342 Tprintone(TREE * t, void *v __unused)
 343 {
 344         int i;
 345         for (i = 0; i < (process_level * 2); i++)
 346                 (void) putchar(' ');
 347         printf("Node at %p name '%s' flags %o hi %p lo %p\n", t, t->Tname, t->Tflags, t->Thi, t->Tlo);
 348         return (SCMOK);
 349 }
 350
 351 void
 352 Tprint(TREE * t, char *p)
 353 {                               /* print tree -- for debugging */
 354         printf("%s\n", p);
 355         (void) Tprocess(t, Tprintone, NULL);
 356         printf("End of tree\n");
 357         (void) fflush(stdout);
 358 }