1 saw 1.1 /*-----------------------------------------------------------------------------
2 * Copyright (c) 1992 Southeastern Universities Research Association,
3 * Continuous Electron Beam Accelerator Facility
4 *
5 * This software was developed under a United States Government license
6 * described in the NOTICE file included as part of this distribution.
7 *
8 * Stephen A. Wood, 12000 Jefferson Ave., Newport News, VA 23606
9 * Email: saw@cebaf.gov Tel: (804) 249-7367 Fax: (804) 249-5800
10 *-----------------------------------------------------------------------------
11 *
12 * Description:
13 * C and Fortran routines for registering variables to be used by
14 * the test, histogram and parameter packages.
15 *
16 * Author: Stephen Wood, CEBAF HALL C
17 *
18 * Revision History:
19 * $Log: daVarRegister.c,v $
20 * Revision 1.10 1996/07/31 20:37:53 saw
21 * Use hash table for name storage.
22 saw 1.1 *
23 * Revision 1.9 1994/09/27 20:20:53 saw
24 * Remove linux dependencies, allow wild cards in daVarList
25 *
26 * Revision 1.8 1994/08/24 14:27:00 saw
27 * Have daVarLookupPWithClass return S_DAVAR_UNKNOWN if var not found
28 *
29 * Revision 1.7 1994/06/03 20:59:26 saw
30 * Replace stderr with STDERR
31 *
32 * Revision 1.6 1994/02/10 21:58:33 saw
33 * Change node variable name to nd to not conflict with node type.
34 *
35 * Revision 1.5 1994/02/10 18:34:05 saw
36 * Small fixes for SGI compatibility
37 *
38 * Revision 1.4 1993/11/24 21:37:39 saw
39 * Add fortran calls for registering double (REAL *8) variable type.
40 *
41 * Revision 1.3 1993/11/22 20:09:42 saw
42 * Add REGPARMSTRING fortran call for new Fortran string type DAVARFSTRING
43 saw 1.1 *
44 * Revision 1.2 1993/08/12 19:58:10 saw
45 * On HPUX don't use native tsearch.
46 *
47 * Revision 1.1 1993/05/10 20:05:09 saw
48 * Initial revision
49 *
50 *
51 * 18-dec-92 saw Original version
52 *
53 *
54 * Routines available to general users:
55 * --------
56 * daVarRegister(int flag, daVarStruct *args)
57 * daVarLookup(char *name, daVarStruct *results)
58 *
59 * Routines available to "friendly" packages (e.g.) RPC service routines
60 * --------
61 * daVarLookupP(char *name, daVarStruct **results)
62 * daVarList(char ***listp)
63 * daVarFreeList(char **list)
64 saw 1.1 *
65 *
66 */
67 #include "cfortran.h"
68 #include "daVar.h"
69
70 #define USEHASH
71 #ifdef USEHASH
72 #include "daVarHash.h"
73 #else
74 #if !defined(ultrix)
75 #define NO_TSEARCH
76 #endif
77
78 #include <stdio.h>
79 #ifdef NOFNMATCH
80 #include "fnmatch.h"
81 #else
82 #include <fnmatch.h>
83 #endif
84
85 saw 1.1 /* Stuff for Tsearch routines*/
86 typedef struct node_t
87 {
88 daVarStruct *key;
89 struct node_t *left, *right;
90 } node;
91
92 #ifdef NO_TSEARCH
93 typedef enum { preorder, postorder, endorder, leaf } VISIT;
94 node *mytsearch(void *key, node **rootp, int (* compar)());
95 node *mytfind(void *key, node **rootp, int (* compar)());
96 void mytwalk();
97 #else
98 #include <search.h>
99 #define mytsearch tsearch
100 #define mytfind tfind
101 #define mytwalk twalk
102 #endif
103 #endif
104
105 #ifdef USEHASH
106 saw 1.1 symbolEntry *hash_table[TABLE_SIZE];
107 int hashNotInited=1;
108 #else
109 node *daVarRoot=0;
110 #endif
111 int daVarCount=0; /* Used by daVarList */
112 char **daVarListGlob;
113 char *daVarListPattern;
114 int (*daVarListCompFunction)();
115 int daVarListPattern_length;
116
117 /* Local prototypes */
118 int daVarComp(daVarStruct *item1, daVarStruct *item2);
119
120 /* Code */
121 long daVarRegister(int flag, daVarStruct *args)
122 /* Should accept a title arg of zero and create a null string in that
123 case.
124 */
125 {
126 daVarStruct search, *new, **searchresult;
127 saw 1.1 int fullnamelen;
128
129 if(flag != 0) {
130 fprintf(STDERR,
131 "(daVarRegister) Only zero allowed for flag argument now.\n");
132 return(S_FAILURE);
133 }
134
135 search.name = args->name;
136 /* printf("Searching for %s\n",args->name);*/
137 #ifdef USEHASH
138 if(hashNotInited) {crlHashCreate(hash_table); hashNotInited = 0;}
139 if(searchresult = (daVarStruct **) crlHashFind((CrlSymbol) &search,hash_table)) {
140 #else
141 if(searchresult = (daVarStruct **) mytfind(&search,&daVarRoot,daVarComp)){
142 #endif
143 fprintf(STDERR,
144 "(daVar) Replacing definition of variable \"%s\" in table\n",
145 args->name);
146 free((*searchresult)->title);
147 if(args->title) {
148 saw 1.1 if(((*searchresult)->title = (char *) malloc(strlen(args->title)+1))
149 == NULL)
150 return(S_FAILURE);
151 strcpy((*searchresult)->title,args->title);
152 } else {
153 if(((*searchresult)->title = (char *) malloc(1))
154 == NULL)
155 return(S_FAILURE);
156 (*searchresult)->title[0] = '\0';
157 }
158 (*searchresult)->varptr = args->varptr;
159 (*searchresult)->size = (args->size<=0) ? 1 : args->size;
160 (*searchresult)->type = args->type;
161 (*searchresult)->flag = args->flag;
162 (*searchresult)->rhook = args->rhook;
163 (*searchresult)->whook = args->whook;
164 (*searchresult)->opaque = args->opaque;
165 return(S_DAVAR_REPLACED);
166 } else {
167 if((new = (daVarStruct *) malloc(sizeof(daVarStruct))) == NULL)
168 return(S_FAILURE);
169 saw 1.1 if((new->name = (char *) malloc(strlen(args->name)+1)) == NULL)
170 return(S_FAILURE);
171 strcpy(new->name,args->name);
172
173
174 if(args->title) {
175 if((new->title = (char *) malloc(strlen(args->title)+1)) == NULL)
176 return(S_FAILURE);
177 strcpy(new->title,args->title);
178 } else {
179 if((new->title = (char *) malloc(1)) == NULL)
180 return(S_FAILURE);
181 new->title[0] = '\0';
182 }
183 new->type = args->type;
184 new->varptr = args->varptr;
185 new->size = (args->size<=0) ? 1 : args->size;
186 new->flag = args->flag;
187 new->rhook = args->rhook;
188 new->whook = args->whook;
189 new->opaque = args->opaque;
190 saw 1.1
191 #ifdef USEHASH
192 if(crlHashAdd((CrlSymbol) new, hash_table))
193 #else
194 if(mytsearch((void *) new,&daVarRoot,daVarComp))
195 #endif
196 return(S_SUCCESS);
197 else
198 return(S_FAILURE);
199 }
200 }
201
202
203 long daVarLookup(char *name, daVarStruct *result)
204 {
205 daVarStruct search, **searchresult;
206 static char *namel=0; /* Pointers to static space for copies of */
207 static int namelsize=0;
208 static char *titlel=0; /* the name and title pointers */
209 static int titlelsize=0;
210 int len;
211 saw 1.1
212 search.name = name;
213 #ifdef USEHASH
214 if(searchresult = (daVarStruct **) crlHashFind((CrlSymbol) &search,hash_table)) {
215 #else
216 if(searchresult = (daVarStruct **) mytfind(&search,&daVarRoot,daVarComp)){
217 #endif
218
219 len=strlen((*searchresult)->name);
220 if(len >= namelsize) {
221 if(namel) free(namel);
222 namel = (char *) malloc(len+1);
223 namelsize = len+1;
224 }
225 strcpy(namel,(*searchresult)->name);
226 result->name = namel;
227
228 len=strlen((*searchresult)->title);
229 if(len >= titlelsize) {
230 if(titlel) free(titlel);
231 titlel = (char *) malloc(len + 1);
232 saw 1.1 titlelsize = len+1;
233 }
234 strcpy(titlel,(*searchresult)->title);
235 result->title = titlel;
236
237 result->type = (*searchresult)->type;
238 result->varptr = (*searchresult)->varptr;
239 result->size = (*searchresult)->size;
240 result->opaque = (*searchresult)->opaque;
241 result->rhook = (*searchresult)->rhook;
242 result->whook = (*searchresult)->whook;
243 return(S_SUCCESS);
244 } else
245 return(S_DAVAR_UNKNOWN);
246 }
247 long daVarStrcmp(register char *s1, register char *s2)
248 {
249 while(toupper(*s1) == toupper(*s2++))
250 if(*s1++ == '\0')
251 return(0);
252 return(toupper(*s1) - toupper(*--s2));
253 saw 1.1 }
254 int daVarFnmatch(register char *pattern, register char *s, register int n)
255 {
256 return(fnmatch(pattern,s,0));
257 }
258 int daVarStrncmp(register char *s1, register char *s2, register int n)
259 {
260 while(toupper(*s1) == toupper(*s2++))
261 if(*s1++ == '\0' || (--n) <= 0)
262 return(0);
263 return(toupper(*s1) - toupper(*--s2));
264 }
265
266 int daVarComp(daVarStruct *item1, daVarStruct *item2)
267 /* Do case insensitive comparisons of keys */
268 {
269 return(daVarStrcmp(item1->name,item2->name));
270 }
271
272 long daVarLookupP(char *name, daVarStruct **varstructptr)
273 {
274 saw 1.1 daVarStruct search, **searchresult;
275
276 search.name = name;
277 #ifdef USEHASH
278 if(searchresult = (daVarStruct **) crlHashFind((CrlSymbol) &search,hash_table)) {
279 #else
280 if(searchresult = (daVarStruct **) mytfind(&search,&daVarRoot,daVarComp)){
281 #endif
282 *varstructptr = *searchresult;
283 return(S_SUCCESS);
284 } else
285 return(S_DAVAR_UNKNOWN);
286 }
287
288 daVarLookupPWithClass(char *name, char **prefixlist, daVarStruct **varp)
289 {
290 int namlen,namtrylen;
291 char *namtry;
292
293 namlen = strlen(name);
294 if(daVarLookupP(name,varp)==S_SUCCESS) return(S_SUCCESS);
295 saw 1.1 namtrylen = namlen + 10;
296 namtry = (char *) malloc(namtrylen+1);
297 while(*prefixlist){
298 int thislen;
299 thislen = strlen(*prefixlist) + namlen + 1;
300 if(thislen > namtrylen) {
301 namtrylen = thislen;
302 namtry = (char *) realloc(namtry,namtrylen);
303 }
304 strcpy(namtry,*prefixlist);
305 strcat(namtry,".");
306 strcat(namtry,name);
307 if(daVarLookupP(namtry,varp)==S_SUCCESS) {
308 free(namtry);
309 return(S_SUCCESS);
310 }
311 prefixlist++;
312 }
313 free(namtry);
314 return(S_DAVAR_UNKNOWN); /* Variable not registered */
315 }
316 saw 1.1
317 daVarCount_node
318 #ifdef USEHASH
319 (void *entry)
320 {
321 #else
322 (node *nd,VISIT order, int level)
323 {
324 if(order==postorder || order == leaf)
325 #endif
326 daVarCount++;
327 }
328
329 daVarList_node
330 #ifdef USEHASH
331 (void *entry)
332 {
333 #else
334 (node *nd,VISIT order, int level)
335 {
336 if(order==postorder || order == leaf)
337 saw 1.1 #endif
338 {
339 char *name;
340
341 name = ((daVarStruct *) entry)->name;
342 if(daVarListPattern_length == 0 ||
343 (daVarListCompFunction)(daVarListPattern,name,daVarListPattern_length) == 0)
344 daVarListGlob[daVarCount++] = name;
345 }
346 }
347
348
349 long daVarList(char *pattern, char ***listp, int *count)
350 /* User is not allowed to muck with the strings pointed to in the list
351 because they are the actual strings in the tables. */
352 {
353
354 if(strchr(pattern,'*') || strchr(pattern,'?')) {
355 daVarListCompFunction = daVarFnmatch;
356 } else {
357 daVarListCompFunction = daVarStrncmp;
358 saw 1.1 }
359 if(pattern) {
360 daVarListPattern = pattern;
361 daVarListPattern_length = strlen(daVarListPattern);
362 } else
363 daVarListPattern_length = 0;
364 daVarCount = 0;
365 #ifdef USEHASH
366 crlHashWalk(hash_table,daVarCount_node);
367 #else
368 mytwalk(daVarRoot,daVarCount_node);/* Should make list only big enough
369 for what matches */
370 #endif
371
372 if((*listp = daVarListGlob =
373 (char **) malloc((daVarCount)*sizeof(char *))) == NULL)
374 return(S_FAILURE);
375 daVarCount = 0;
376 #ifdef USEHASH
377 crlHashWalk(hash_table,daVarList_node);
378 #else
379 saw 1.1 mytwalk(daVarRoot,daVarList_node);
380 #endif
381 *count = daVarCount;
382 return(S_SUCCESS);
383 }
384 #ifndef USEHASH
385 daVarPrint_node(node *nd,VISIT order, int level)
386 {
387 char *name,*title;
388
389 if(order==postorder || order == leaf) {
390 name = ((daVarStruct *) nd->key)->name;
391 title = ((daVarStruct *) nd->key)->title;
392 printf("XX: %s %s %x %x\n",name,title,nd,nd->key);
393 }
394 }
395
396 long daVarPrint()
397 {
398 mytwalk(daVarRoot,daVarPrint_node);
399 return(S_SUCCESS);
400 saw 1.1 }
401 #endif
402 long daVarFreeList(char **list)
403 /* Free's up the list of variables in listp */
404 {
405 int i;
406
407 free(list);
408 return(S_SUCCESS);
409 }
410
411 /* Fortran entry points */
412
413 #define LENDEFARRAY int *size,
414 #define LENDEFSCALER
415 #define LENARGARRAY *size
416 #define LENARGSCALER 1
417
418 #define MAKEFSUB(SUBNAME,CLASS,TYPENAME,DATYPE,ARRAY) \
419 long SUBNAME(char *name, TYPENAME *vptr, LENDEF##ARRAY char *title\
420 ,unsigned l_name, unsigned l_title)\
421 saw 1.1 {\
422 long A0;\
423 daVarStruct args;\
424 char *BN=0;\
425 char *BT=0;\
426 char *BF = 0;\
427 \
428 BF = malloc(strlen(CLASS)+l_name+1);\
429 strcpy(BF,CLASS);\
430 args.name = strcat(BF,((!*(int *)name)?0:memchr(name,'\0',l_name)?name:\
431 (memcpy(BN=(char *) malloc(l_name+1),name,l_name)\
432 ,BN[l_name]='\0',kill_trailing(BN,' '))));\
433 args.title = ((!*(int *)title)?0:memchr(title,'\0',l_title)?title:\
434 (memcpy(BT=(char *) malloc(l_title+1),title,l_title)\
435 ,BT[l_title]='\0',kill_trailing(BT,' ')));\
436 args.size = LENARG##ARRAY;\
437 args.varptr = (void *) vptr;\
438 args.flag = DAVAR_READWRITE;\
439 args.type = DATYPE;\
440 args.opaque = 0;\
441 args.rhook = args.whook = 0;\
442 saw 1.1 A0 = daVarRegister((int) 0, &args);\
443 if(BF) free(BF);\
444 if(BN) free(BN);\
445 if(BT) free(BT);\
446 return(A0);\
447 }
448
449 #ifdef NOF77extname
450 MAKEFSUB(regreal,"",float,DAVARFLOAT,SCALER)
451 MAKEFSUB(regdouble,"",double,DAVARDOUBLE,SCALER)
452 MAKEFSUB(regint,"",int,DAVARINT,SCALER)
453 MAKEFSUB(regrealarray,"",float,DAVARFLOAT,ARRAY)
454 MAKEFSUB(regdoublearray,"",double,DAVARDOUBLE,ARRAY)
455 MAKEFSUB(regintarray,"",int,DAVARINT,ARRAY)
456
457 MAKEFSUB(regparmreal,"parm.",float,DAVARFLOAT,SCALER)
458 MAKEFSUB(regparmdouble,"parm.",double,DAVARDOUBLE,SCALER)
459 MAKEFSUB(regeventreal,"event.",float,DAVARFLOAT,SCALER)
460 MAKEFSUB(regeventdouble,"event.",double,DAVARDOUBLE,SCALER)
461 MAKEFSUB(regparmint,"parm.",int,DAVARINT,SCALER)
462 MAKEFSUB(regeventint,"event.",int,DAVARINT,SCALER)
463 saw 1.1 MAKEFSUB(regparmrealarray,"parm.",float,DAVARFLOAT,ARRAY)
464 MAKEFSUB(regparmdoublearray,"parm.",double,DAVARDOUBLE,ARRAY)
465 MAKEFSUB(regeventrealarray,"event.",float,DAVARFLOAT,ARRAY)
466 MAKEFSUB(regeventdoublearray,"event.",double,DAVARDOUBLE,ARRAY)
467 MAKEFSUB(regparmintarray,"parm.",int,DAVARINT,ARRAY)
468 MAKEFSUB(regeventintarray,"event.",int,DAVARINT,ARRAY)
469
470 MAKEFSUB(regtestint,"test.",int,DAVARINT,SCALER)
471 MAKEFSUB(regtestintarray,"test.",int,DAVARINT,ARRAY)
472 #else
473 MAKEFSUB(regreal_,"",float,DAVARFLOAT,SCALER)
474 MAKEFSUB(regdouble_,"",double,DAVARDOUBLE,SCALER)
475 MAKEFSUB(regint_,"",int,DAVARINT,SCALER)
476 MAKEFSUB(regrealarray_,"",float,DAVARFLOAT,ARRAY)
477 MAKEFSUB(regdoublearray_,"",double,DAVARDOUBLE,ARRAY)
478 MAKEFSUB(regintarray_,"",int,DAVARINT,ARRAY)
479
480 MAKEFSUB(regparmreal_,"parm.",float,DAVARFLOAT,SCALER)
481 MAKEFSUB(regparmdouble_,"parm.",double,DAVARDOUBLE,SCALER)
482 MAKEFSUB(regeventreal_,"event.",float,DAVARFLOAT,SCALER)
483 MAKEFSUB(regeventdouble_,"event.",double,DAVARDOUBLE,SCALER)
484 saw 1.1 MAKEFSUB(regparmint_,"parm.",int,DAVARINT,SCALER)
485 MAKEFSUB(regeventint_,"event.",int,DAVARINT,SCALER)
486 MAKEFSUB(regparmrealarray_,"parm.",float,DAVARFLOAT,ARRAY)
487 MAKEFSUB(regparmdoublearray_,"parm.",double,DAVARDOUBLE,ARRAY)
488 MAKEFSUB(regeventrealarray_,"event.",float,DAVARFLOAT,ARRAY)
489 MAKEFSUB(regeventdoublearray_,"event.",double,DAVARDOUBLE,ARRAY)
490 MAKEFSUB(regparmintarray_,"parm.",int,DAVARINT,ARRAY)
491 MAKEFSUB(regeventintarray_,"event.",int,DAVARINT,ARRAY)
492
493 MAKEFSUB(regtestint_,"test.",int,DAVARINT,SCALER)
494 MAKEFSUB(regtestintarray_,"test.",int,DAVARINT,ARRAY)
495 #endif
496
497 /* Entry points for String registration. Do entry points for anything other
498 than parmameters make sense? */
499 #ifdef NOF77extname
500 long regparmstring
501 #else
502 long regparmstring_
503 #endif
504 (char *name, char *sptr, char *title
505 saw 1.1 ,unsigned l_name, unsigned l_sptr, unsigned l_title)
506 {
507 long A0;
508 daVarStruct args;
509 char *BN=0;
510
511 char *BT=0;
512 char *BF = 0;
513
514 BF = malloc(5+l_name+1);
515 strcpy(BF,"parm.");
516 args.name = strcat(BF,((!*(int *)name)?0:memchr(name,'\0',l_name)?name:
517 (memcpy(BN=(char *) malloc(l_name+1),name,l_name)
518 ,BN[l_name]='\0',kill_trailing(BN,' '))));
519 args.title = ((!*(int *)title)?0:memchr(title,'\0',l_title)?title:
520 (memcpy(BT=(char *) malloc(l_title+1),title,l_title)
521 ,BT[l_title]='\0',kill_trailing(BT,' ')));
522 args.size = l_sptr;
523 args.varptr = (void *) sptr;
524 args.flag = DAVAR_READWRITE;
525 args.type = DAVARFSTRING;
526 saw 1.1 args.opaque = 0;
527 args.rhook = args.whook = 0;
528 A0 = daVarRegister((int) 0, &args);
529 if(BF) free(BF);
530 if(BN) free(BN);
531 return(A0);
532 }
533
534 #ifdef NO_TSEARCH
535 /*
536 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
537 * the AT&T man page says.
538 *
539 * The node_t structure is for internal use only, lint doesn't grok it.
540 *
541 * Written by reading the System V Interface Definition, not the code.
542 *
543 * Totally public domain.
544 */
545 /*LINTLIBRARY*/
546
547 saw 1.1 /*
548 #include <search.h>
549
550 typedef struct node_t
551 {
552 char *key;
553 struct node_t *left, *right;
554 }
555 node;
556 */
557
558 node *mytsearch(key, rootp, compar)
559 /* find or insert datum into search tree */
560 void *key; /* key to be located */
561 register node **rootp; /* address of tree root */
562 int (*compar)(); /* ordering function */
563 {
564 register node *q;
565
566 if (rootp == (struct node_t **)0)
567 return ((struct node_t *)0);
568 saw 1.1 while (*rootp != (struct node_t *)0) /* Knuth's T1: */
569 {
570 int r;
571
572 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
573 return (*rootp); /* we found it! */
574 rootp = (r < 0) ?
575 &(*rootp)->left : /* T3: follow left branch */
576 &(*rootp)->right; /* T4: follow right branch */
577 }
578 q = (node *) malloc(sizeof(node)); /* T5: key not found */
579 if (q != (struct node_t *)0) /* make new node */
580 {
581 *rootp = q; /* link new node to old */
582 q->key = key; /* initialize new node */
583 q->left = q->right = (struct node_t *)0;
584 }
585 return (q);
586 }
587
588 node *mytdelete(key, rootp, compar)
589 saw 1.1 /* delete node with given key */
590 char *key; /* key to be deleted */
591 register node **rootp; /* address of the root of tree */
592 int (*compar)(); /* comparison function */
593 {
594 node *p;
595 register node *q;
596 register node *r;
597 int cmp;
598
599 if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
600 return ((struct node_t *)0);
601 while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
602 {
603 p = *rootp;
604 rootp = (cmp < 0) ?
605 &(*rootp)->left : /* follow left branch */
606 &(*rootp)->right; /* follow right branch */
607 if (*rootp == (struct node_t *)0)
608 return ((struct node_t *)0); /* key not found */
609 }
610 saw 1.1 r = (*rootp)->right; /* D1: */
611 if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */
612 q = r;
613 else if (r != (struct node_t *)0) /* Right link is null? */
614 {
615 if (r->left == (struct node_t *)0) /* D2: Find successor */
616 {
617 r->left = q;
618 q = r;
619 }
620 else
621 { /* D3: Find (struct node_t *)0 link */
622 for (q = r->left; q->left != (struct node_t *)0; q = r->left)
623 r = q;
624 r->left = q->right;
625 q->left = (*rootp)->left;
626 q->right = (*rootp)->right;
627 }
628 }
629 free((struct node_t *) *rootp); /* D4: Free node */
630 *rootp = q; /* link parent to new node */
631 saw 1.1 return(p);
632 }
633
634 static void trecurse(root, action, level)
635 /* Walk the nodes of a tree */
636 register node *root; /* Root of the tree to be walked */
637 register void (*action)(); /* Function to be called at each node */
638 register int level;
639 {
640 if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
641 (*action)(root, leaf, level);
642 else
643 {
644 (*action)(root, preorder, level);
645 if (root->left != (struct node_t *)0)
646 trecurse(root->left, action, level + 1);
647 (*action)(root, postorder, level);
648 if (root->right != (struct node_t *)0)
649 trecurse(root->right, action, level + 1);
650 (*action)(root, endorder, level);
651 }
652 saw 1.1 }
653
654 void mytwalk(root, action) /* Walk the nodes of a tree */
655 node *root; /* Root of the tree to be walked */
656 void (*action)(); /* Function to be called at each node */
657 {
658 if (root != (node *)0 && action != (void(*)())0)
659 trecurse(root, action, 0);
660 }
661
662 /* mytsearch.c ends here */
663 /*
664 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
665 * the AT&T man page says.
666 *
667 * The node_t structure is for internal use only, lint doesn't grok it.
668 *
669 * Written by reading the System V Interface Definition, not the code.
670 *
671 * Totally public domain.
672 */
673 saw 1.1 /*LINTLIBRARY*/
674 /*
675 #include <search.h>
676
677 typedef struct node_t
678 {
679 char *key;
680 struct node_t *left, *right;
681 } node;
682 */
683
684 node *mytfind(key, rootp, compar)
685 /* find a node, or return 0 */
686 void *key; /* key to be found */
687 register node **rootp; /* address of the tree root */
688 int (*compar)(); /* ordering function */
689 {
690 if (rootp == (struct node_t **)0)
691 return ((struct node_t *)0);
692 while (*rootp != (struct node_t *)0) /* T1: */
693 {
694 saw 1.1 int r;
695 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
696 return (*rootp); /* key found */
697 rootp = (r < 0) ?
698 &(*rootp)->left : /* T3: follow left branch */
699 &(*rootp)->right; /* T4: follow right branch */
700 }
701 return (node *)0;
702 }
703 #endif
|