1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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);
}
|