← Back to branch summary

~ubuntu-branches/ubuntu/trusty/agrep/trusty

« back to all changes in this revision

Viewing changes to follow.c

  • Committer: Bazaar Package Importer
  • Author(s): Daniel Baumann
  • Date: 2006-07-05 13:29:00 UTC
  • mfrom: (3.1.1 dapper)
  • Revision ID: james.westby@ubuntu.com-20060705132900-j24rz8zdk4xqdmoz
Tags: 4.17-3
* New email address.
* Some packaging style changes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
follow.c
 
1
/* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
1
2
/* the functions in this file take a syntax tree for a regular
2
3
   expression and produce a DFA using the McNaughton-Yamada
3
4
   construction.                                                */
4
5
 
5
6
#include <stdio.h>
 
7
#include <string.h>
 
8
#include <stdlib.h>
 
9
#include <unistd.h>
6
10
#include "re.h"
7
11
 
8
 
extern char *strncpy(), *strcat(), *strcpy();
9
 
extern int  strlen();
10
 
 
11
12
#define TRUE    1
12
13
 
13
 
extern char *malloc();
14
14
extern Pset pset_union(); 
15
15
extern int pos_cnt;
16
16
extern Re_node parse();
19
19
 
20
20
 
21
21
/*  extend_re() extends the RE by adding a ".*(" at the front and a "("
22
 
    at the back.                                                        */
 
22
        at the back.                                                    */
23
23
 
24
24
char *extend_re(s)
25
25
char *s;
26
26
{
27
 
    char *s1;
28
 
 
29
 
    s1 = malloc((unsigned) strlen(s)+4+1);
30
 
    return strcat(strcat(strcpy(s1, ".*("), s), ")");
31
 
}
 
27
        char *s1;
 
28
 
 
29
        s1 = malloc((unsigned) strlen(s)+4+1);
 
30
        return strcat(strcat(strcpy(s1, ".*("), s), ")");
 
31
}
 
32
 
 
33
void free_pos(fpos, pos_cnt)
 
34
Pset_array fpos;
 
35
int pos_cnt;
 
36
{
 
37
        Pset tpos, pos;
 
38
        int i;
 
39
 
 
40
        if ((fpos == NULL) || (*fpos == NULL)) return;
 
41
        for (i=0; i<=pos_cnt; i++) {
 
42
                pos = (*fpos)[i];
 
43
                while (pos != NULL) {
 
44
                        tpos = pos;
 
45
                        pos = pos->nextpos;
 
46
                        free(tpos);
 
47
                }
 
48
        }
 
49
        free(fpos);
 
50
}
 
51
 
 
52
/* Function to clear out a Ch_Set */
 
53
void free_cset(cset)
 
54
Ch_Set cset;
 
55
{
 
56
        Ch_Set tset;
 
57
 
 
58
        while (cset != NULL) {
 
59
                tset = cset;
 
60
                cset = cset->rest;
 
61
                free(tset->elt);
 
62
                free(tset);
 
63
        }
 
64
}
 
65
 
 
66
/* Function to clear out the tree of re-nodes */
 
67
void free_re(e)
 
68
Re_node e;
 
69
{
 
70
        if (e == NULL) return;
 
71
 
 
72
/*
 
73
 * Was creating "reading freed memory", "freeing unallocated/freed memory"
 
74
 * errors. So abandoned it. Leaks are now up by 60B/call to 80B/call
 
75
 * -bg
 
76
 * Enabled on 26/Aug/1996 after changing pos routines to copy stuff rather than link up parents/children/etc.
 
77
 */
 
78
        {
 
79
        Pset tpos, pos;
 
80
        int tofree = 0;
 
81
 
 
82
        if ((Lastpos(e)) != (Firstpos(e))) tofree = 1;
 
83
        pos = Lastpos(e);
 
84
        while (pos != NULL) {
 
85
                tpos = pos;
 
86
                pos = pos->nextpos;
 
87
                free(tpos);
 
88
        }
 
89
        Lastpos(e) = NULL;
 
90
 
 
91
        if (tofree) {
 
92
                pos = Firstpos(e);
 
93
                while (pos != NULL) {
 
94
                        tpos = pos;
 
95
                        pos = pos->nextpos;
 
96
                        free(tpos);
 
97
                }
 
98
                Firstpos(e) = NULL;
 
99
        }
 
100
        }
 
101
/*
 
102
 Enabled on 26/Aug/1996 after changing pos routines to copy stuff rather than link up parents/children/etc.
 
103
 */
 
104
 
 
105
        switch (Op(e)) {
 
106
        case EOS:
 
107
                if (lit_type(Lit(e)) == C_SET) free_cset(lit_cset(Lit(e)));
 
108
                free(Lit(e));
 
109
                break;
 
110
        case OPSTAR:
 
111
                free_re(Child(e));
 
112
                break;
 
113
        case OPCAT:
 
114
                free_re(Lchild(e));
 
115
                free_re(Rchild(e));
 
116
                break;
 
117
        case OPOPT:
 
118
                free_re(Child(e));
 
119
                break;
 
120
        case OPALT:
 
121
                free_re(Lchild(e));
 
122
                free_re(Rchild(e));
 
123
                break;
 
124
        case LITERAL:
 
125
                if (lit_type(Lit(e)) == C_SET) free_cset(lit_cset(Lit(e)));
 
126
                free(Lit(e));
 
127
                break;
 
128
        default: 
 
129
                fprintf(stderr, "free_re: unknown node type %d\n", Op(e));
 
130
        }
 
131
        free(e);
 
132
        return;
 
133
}
 
134
 
32
135
 
33
136
/* mk_followpos() takes a syntax tree for a regular expression and
34
137
   traverses it once, computing the followpos function at each node
40
143
Re_node e;
41
144
Pset_array fpos;
42
145
{
43
 
    Pset pos;
44
 
    int i;
 
146
        Pset pos;
 
147
        int i;
45
148
 
46
 
    switch (Op(e)) {
47
 
        case EOS: break;
 
149
        switch (Op(e)) {
 
150
        case EOS: 
 
151
                break;
48
152
        case OPSTAR:
49
 
            pos = Lastpos(e);
50
 
            while (pos != NULL) {
51
 
                i = pos->posnum;
52
 
                (*fpos)[i] = pset_union(Firstpos(e), (*fpos)[i]);
53
 
                pos = pos->nextpos;
54
 
            }
55
 
            mk_followpos_1(Child(e), fpos);
56
 
            break;
 
153
                pos = Lastpos(e);
 
154
                while (pos != NULL) {
 
155
                        i = pos->posnum;
 
156
                        (*fpos)[i] = pset_union(Firstpos(e), (*fpos)[i], 1);
 
157
                        pos = pos->nextpos;
 
158
                }
 
159
                mk_followpos_1(Child(e), fpos);
 
160
                break;
57
161
        case OPCAT:
58
 
            pos = Lastpos(Lchild(e));
59
 
            while (pos != NULL) {
60
 
                i = pos->posnum;
61
 
                (*fpos)[i] = pset_union(Firstpos(Rchild(e)), (*fpos)[i]);
62
 
                pos = pos->nextpos;
63
 
            }
64
 
            mk_followpos_1(Lchild(e), fpos);
65
 
            mk_followpos_1(Rchild(e), fpos);
66
 
            break;
 
162
                pos = Lastpos(Lchild(e));
 
163
                while (pos != NULL) {
 
164
                        i = pos->posnum;
 
165
                        (*fpos)[i] = pset_union(Firstpos(Rchild(e)), (*fpos)[i], 1);
 
166
                        pos = pos->nextpos;
 
167
                }
 
168
                mk_followpos_1(Lchild(e), fpos);
 
169
                mk_followpos_1(Rchild(e), fpos);
 
170
                break;
67
171
        case OPOPT:
68
 
            mk_followpos_1(Child(e), fpos);
69
 
            break;
 
172
                mk_followpos_1(Child(e), fpos);
 
173
                break;
70
174
        case OPALT:
71
 
            mk_followpos_1(Lchild(e), fpos);
72
 
            mk_followpos_1(Rchild(e), fpos);
73
 
            break;
 
175
                mk_followpos_1(Lchild(e), fpos);
 
176
                mk_followpos_1(Rchild(e), fpos);
 
177
                break;
74
178
        case LITERAL:
75
 
            break;
76
 
        default: printf("mk_followpos: unknown node type %d\n", Op(e));
77
 
    }
78
 
    return;
 
179
                break;
 
180
        default: 
 
181
                fprintf(stderr, "mk_followpos: unknown node type %d\n", Op(e));
 
182
        }
 
183
        return;
79
184
}
80
185
 
81
186
Pset_array mk_followpos(tree, npos)
82
187
Re_node tree;
83
188
int npos;
84
189
{
85
 
    int i;
86
 
    Pset_array fpos;
 
190
        int i;
 
191
        Pset_array fpos;
87
192
 
88
 
    if (tree == NULL || npos < 0) return NULL;
89
 
    fpos = (Pset_array) malloc((unsigned) (npos+1)*sizeof(Pset));
90
 
    if (fpos == NULL) return NULL;
91
 
    for (i = 0; i <= npos; i++) (*fpos)[i] = NULL;
92
 
    mk_followpos_1(tree, fpos);
93
 
    return fpos;
 
193
        if (tree == NULL || npos < 0) return NULL;
 
194
        fpos = (Pset_array) malloc((unsigned) (npos+1)*sizeof(Pset));
 
195
        if (fpos == NULL) return NULL;
 
196
        for (i = 0; i <= npos; i++) (*fpos)[i] = NULL;
 
197
        mk_followpos_1(tree, fpos);
 
198
        return fpos;
94
199
}
95
200
 
96
201
/* mk_poslist() sets a static array whose i_th element is a pointer to
101
206
   0 if everything goes OK.                                             */
102
207
 
103
208
int init(s, table)
104
 
char *s; int table[32][32];
 
209
char *s; 
 
210
int table[32][32];
105
211
{
106
 
    Pset_array fpos;
107
 
    Re_node e;
108
 
    Pset l;
109
 
    int i, j;
 
212
        Pset_array fpos;
 
213
        Re_node e;
 
214
        Pset l;
 
215
        int i, j;
 
216
        char *s1;
110
217
 
111
 
    if ((e = parse(extend_re(s))) == NULL) return -1;
112
 
    if ((fpos = mk_followpos(e, pos_cnt)) == NULL) return -1;
113
 
    for (i = 0; i <= pos_cnt; i += 1) {
114
 
#ifdef Debug
115
 
        printf("followpos[%d] = ", i);
116
 
#endif
117
 
        l = (*fpos)[i];
118
 
        j = 0;
119
 
        for ( ; l != NULL; l = l->nextpos)  {
120
 
#ifdef Debug
121
 
            printf("%d ", l->posnum);
122
 
#endif
123
 
            table[i][j] = l->posnum;
124
 
            j++;
125
 
        } 
126
 
#ifdef Debug
127
 
        printf("\n");
128
 
#endif
129
 
    }
130
 
#ifdef Debug
131
 
    for (i=0; i <= pos_cnt; i += 1)  {
132
 
       j = 0;
133
 
       while (table[i][j] != 0) {
134
 
          printf(" %d ", table[i][j]);
135
 
          j++;
136
 
      }
137
 
      printf("\n");
138
 
   }
139
 
#endif
140
 
    return (pos_cnt);
 
218
        if ((s1 = extend_re(s)) == NULL) return -1;
 
219
        if ((e = parse(s1)) == NULL) {
 
220
                free(s1);
 
221
                return -1;
 
222
        }
 
223
        free(s1);
 
224
        if ((fpos = mk_followpos(e, pos_cnt)) == NULL) {
 
225
                free_re(e);
 
226
                return -1;
 
227
        }
 
228
        for (i = 0; i <= pos_cnt; i += 1) {
 
229
#ifdef Debug
 
230
                printf("followpos[%d] = ", i);
 
231
#endif
 
232
                l = (*fpos)[i];
 
233
                j = 0;
 
234
                for ( ; l != NULL; l = l->nextpos)  {
 
235
#ifdef Debug
 
236
                        printf("%d ", l->posnum);
 
237
#endif
 
238
                        table[i][j] = l->posnum;
 
239
                        j++;
 
240
                } 
 
241
#ifdef Debug
 
242
                printf("\n");
 
243
#endif
 
244
        }
 
245
#ifdef Debug
 
246
        for (i=0; i <= pos_cnt; i += 1)  {
 
247
                j = 0;
 
248
                while (table[i][j] != 0) {
 
249
                        printf(" %d ", table[i][j]);
 
250
                        j++;
 
251
                }
 
252
                printf("\n");
 
253
        }
 
254
#endif
 
255
        free_pos(fpos, pos_cnt);
 
256
        free_re(e);
 
257
        return (pos_cnt);
141
258
}
142
259