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