summaryrefslogtreecommitdiff
path: root/web/noweb/src/c/modtrees.nw
blob: 1d5220c3cdf1c2df08938249b65a6f9804cca352 (plain)
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);
}