diff options
Diffstat (limited to 'web/noweb/src/c/modtrees.nw')
-rw-r--r-- | web/noweb/src/c/modtrees.nw | 100 |
1 files changed, 100 insertions, 0 deletions
diff --git a/web/noweb/src/c/modtrees.nw b/web/noweb/src/c/modtrees.nw new file mode 100644 index 0000000000..1d5220c3cd --- /dev/null +++ b/web/noweb/src/c/modtrees.nw @@ -0,0 +1,100 @@ +% Copyright 1991 by Norman Ramsey. All rights reserved. +% See file COPYRIGHT for more information. +@ +\subsection{Support for looking up modules by name} +Trees of modules. +A table of modules with insert and lookup, but no delete. +The key is the module name. +<<header>>= +Module insert (char *modname); /* add a module to the world */ +Module lookup (char *modname); /* return ptr to module or NULL */ +void apply_each_module(void (*fun)(Module)); + /* apply [[fun]] to each module in the tree */ +<<*>>= +static char rcsid[] = "$Id: modtrees.nw,v 2.24 2008/10/06 01:03:05 nr Exp nr $"; +static char rcsname[] = "$Name: v2_12 $"; +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include "strsave.h" +#include "modules.h" +#include "modtrees.h" +#include "errors.h" + +typedef struct tnode { /* tree node */ + struct tnode *left, *right; + Module data; +} TNODE; + +static struct tnode *root=NULL; + +<<Function declarations>> +<<*>>= +Module insert (char *modname) { + (void)rcsid; /* avoid a warning */ + (void)rcsname; /* avoid a warning */ + return insert_tree (&root, modname); +} + +static Module +insert_tree(TNODE **rootptr, char *modname) { + if (*rootptr==NULL) { + <<Allocate new tnode in **rootptr>> + return (*rootptr)->data = newmodule(modname); + } + if (strcmp((*rootptr)->data->name,modname)==0) { + return (*rootptr)->data; + } else if (strcmp((*rootptr)->data->name,modname)<0) { + return insert_tree(&((*rootptr)->left),modname); + } else /* >0 */ { + return insert_tree(&((*rootptr)->right),modname); + } + +} +@ + +Node allocation is perfectly standard. +<<Allocate new tnode in **rootptr>>= + checkptr(*rootptr=(struct tnode *) malloc (sizeof(struct tnode))); + (*rootptr)->left = (*rootptr)->right = NULL; +@ +<<Function declarations>>= +static Module insert_tree(TNODE **rootptr, char *modname); +static Module lookup_tree(TNODE **rootptr, char *modname); +@ +<<*>>= +Module lookup (char *modname) { + return lookup_tree (&root, modname); +} + +static Module +lookup_tree(TNODE **rootptr, char *modname) { + if (*rootptr==NULL) { + return NULL; + } + if (strcmp((*rootptr)->data->name,modname)==0) { + return (*rootptr)->data; + } else if (strcmp((*rootptr)->data->name,modname)<0) { + return lookup_tree(&((*rootptr)->left),modname); + } else /* >0 */ { + return lookup_tree(&((*rootptr)->right),modname); + } +} +@ + +[[apply_each_module]] takes as argument a function and applies +it to each module in the tree. +This makes it easy to, for example, remove trailing newlines +from each module. +<<*>>= +static +void apply_to_tree(TNODE *p, void (*fun)(Module)) { + if (p != NULL) { + apply_to_tree(p->left,fun); + (*fun)(p->data); + apply_to_tree(p->right,fun); + } +} +void apply_each_module(void (*fun)(Module)) { + apply_to_tree(root,fun); +} |