« back to all changes in this revision
Viewing changes to trampoline/norm.c
- browse files at revision 335
- compare with another revision
- compare with revision 1099.1.114
- download diff
- download tarball
- view history from revision 335
- Committer: drtomc
- Date: 2008-01-30 20:52:30 UTC
- Revision ID: svn-v3-trunk0:2b9c9e99-6f39-0410-b283-7f802c844ae2:trunk:335
Log live pushdown automata! Sat down and *thought*, then cast the normalization
as a pushdown automaton. Easy! Worked first shot.
as a pushdown automaton. Easy! Worked first shot.
- files added:
- trampoline/norm.dot
- files modified:
- trampoline/main.c
added
removed
trampoline/norm.c
5
5
#include <unistd.h>
6
6
#include "norm.h"
7
7
8
#if 0
9
struct stack_t
10
{
11
const char** items;
12
size_t capacity;
13
size_t top;
14
};
15
typedef stack_t Stack;
16
17
Stack* new_stack()
18
{
19
Stack* s = (Stack*) malloc(sizeof(Stack));
20
if (!s)
21
{
22
fprintf(stderr, "new_stack: Memory allocation failure! (1)\n");
23
exit(1);
24
}
25
s->items = (const char**) malloc(16 * sizeof(const char*));
26
if (!s->items)
27
{
28
fprintf(stderr, "new_stack: Memory allocation failure! (2)\n");
29
exit(1);
30
}
31
s->capacity = 16;
32
s->top = 0;
33
return s;
34
}
35
36
void stack_push(Stack* s,const char* itm)
37
{
38
if (s->top == s->capacity)
39
{
40
int c = s->capacity * 2;
41
const char** itms = (const char**) malloc(c * sizeof(const char*));
42
if (!itms)
43
{
44
fprintf(stderr, "stack_push: Memory allocation failure! (1)\n");
45
exit(1);
46
}
47
memcpy(itms, s->items, s->capacity * sizeof(const char*));
48
free(s->items);
49
s->items = itms;
50
s->capacity = c;
51
}
52
s->items[s->top++] = itm;
53
}
54
55
const char* stack_pop(Stack* s)
56
{
57
if (s->top == 0)
58
{
59
fprintf(stderr, "stack_pop: underflow!\n");
60
exit(1);
61
}
62
return s->items[--(s->top)];
63
}
64
65
void old_stack(Stack* s)
66
{
67
free(s->items);
68
free(s);
69
}
70
#endif 0
71
8
#define SKP() \
9
do { \
10
s++; \
11
} while (0)
12
13
#define CPY() \
14
do { \
15
*d++ = *s++; \
16
} while (0)
17
18
#define MRK() \
19
do { \
20
PUSH(); \
21
} while (0)
22
23
#define BKP() \
24
do { \
25
POP(); \
26
} while (0)
27
28
#define BKP2() \
29
do { \
30
POP(); \
31
POP(); \
32
} while (0)
33
34
#define PUSH() \
35
do { \
36
stk[top++] = d; \
37
} while (0)
38
39
#define POP() \
40
do { \
41
if (top == 0) \
42
{ \
43
dest[0] = '\0'; \
44
return -1; \
45
} \
46
d = stk[--top]; \
47
} while (0)
72
48
73
49
/*
74
50
* Normalize the unix pathname in src eliminating .. sequences
78
54
int norm(char* dest, int len, const char* src)
79
55
{
80
56
const char* s = src;
81
int l = strlen(src);
82
57
char* d = dest;
83
assert(l <= len);
58
char* stk[256];
59
int top = 0;
60
enum { L0, L1, L2, L3, L4 } state = L0;
61
assert(strlen(src) <= len);
84
62
85
if (!*s || (*d++ = *s++) != '/')
86
{
87
dest[0] = '\0';
88
return -1;
89
}
90
63
while (*s)
91
64
{
92
const char* t;
93
int l;
94
t = s;
95
while (*s && (*d++ = *s++) != '/') ;
96
l = s - t - 1;
97
if (1) {
98
char x[128];
99
printf("%d\n",l);
100
strncpy(x,t,l);
101
x[l] = 0;
102
fprintf(stderr,"%s\n",x);
65
char c = *s;
66
enum { slash, dot, other } cls;
67
switch (c)
68
{
69
case '/':
70
{
71
cls = slash;
72
break;
73
}
74
case '.':
75
{
76
cls = dot;
77
break;
78
}
79
default:
80
{
81
cls = other;
82
}
103
83
}
104
if (strncmp(t, "..", l) == 0)
84
switch (state)
105
85
{
106
fprintf(stderr,"backtracking...\n");
107
d -= 4; /* /../ */
108
while (d > dest && *--d != '/')
109
{
110
d--;
111
}
112
if (d < dest)
113
{
114
/* underflow: too many .. sequences */
115
dest[0] = '\0';
116
return -1;
86
case L0:
87
{
88
switch (cls)
89
{
90
case slash:
91
{
92
CPY();
93
state = L1;
94
break;
95
}
96
case dot:
97
case other:
98
{
99
dest[0] = '\0';
100
return -1;
101
}
102
}
103
break;
104
}
105
case L1:
106
{
107
switch (cls)
108
{
109
case slash:
110
{
111
SKP();
112
break;
113
}
114
case dot:
115
{
116
MRK();
117
CPY();
118
state = L2;
119
break;
120
}
121
case other:
122
{
123
MRK();
124
CPY();
125
state = L4;
126
break;
127
}
128
}
129
break;
130
}
131
case L2:
132
{
133
switch (cls)
134
{
135
case slash:
136
{
137
BKP();
138
state = L1;
139
break;
140
}
141
case dot:
142
{
143
CPY();
144
state = L3;
145
break;
146
}
147
case other:
148
{
149
CPY();
150
state = L4;
151
break;
152
}
153
}
154
break;
155
}
156
case L3:
157
{
158
switch (cls)
159
{
160
case slash:
161
{
162
BKP2();
163
state = L1;
164
break;
165
}
166
case dot:
167
case other:
168
{
169
CPY();
170
state = L4;
171
break;
172
}
173
}
174
break;
175
}
176
case L4:
177
{
178
switch (cls)
179
{
180
case slash:
181
{
182
CPY();
183
state = L1;
184
break;
185
}
186
case dot:
187
case other:
188
{
189
CPY();
190
break;
191
}
192
}
193
break;
117
194
}
118
195
}
119
196
}
120
197
*d = '\0';
121
fprintf(stderr, "returning: '%s'\n", dest);
122
198
return 0;
123
199
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1