1 /*++
2 /* NAME
3 /* tok822_tree 3
4 /* SUMMARY
5 /* assorted token tree operators
6 /* SYNOPSIS
7 /* #include <tok822.h>
8 /*
9 /* TOK822 *tok822_append(t1, t2)
10 /* TOK822 *t1;
11 /* TOK822 *t2;
12 /*
13 /* TOK822 *tok822_prepend(t1, t2)
14 /* TOK822 *t1;
15 /* TOK822 *t2;
16 /*
17 /* TOK822 *tok822_cut_before(tp)
18 /* TOK822 *tp;
19 /*
20 /* TOK822 *tok822_cut_after(tp)
21 /* TOK822 *tp;
22 /*
23 /* TOK822 *tok822_unlink(tp)
24 /* TOK822 *tp;
25 /*
26 /* TOK822 *tok822_sub_append(t1, t2)
27 /* TOK822 *t1;
28 /*
29 /* TOK822 *tok822_sub_prepend(t1, t2)
30 /* TOK822 *t1;
31 /* TOK822 *t2;
32 /*
33 /* TOK822 *tok822_sub_keep_before(t1, t2)
34 /* TOK822 *tp;
35 /*
36 /* TOK822 *tok822_sub_keep_after(t1, t2)
37 /* TOK822 *tp;
38 /*
39 /* int tok822_apply(list, type, action)
40 /* TOK822 *list;
41 /* int type;
42 /* int (*action)(TOK822 *token);
43 /*
44 /* int tok822_grep(list, type)
45 /* TOK822 *list;
46 /* int type;
47 /*
48 /* TOK822 *tok822_free_tree(tp)
49 /* TOK822 *tp;
50 /* DESCRIPTION
51 /* This module manipulates trees of token structures. Trees grow
52 /* to the right or downwards. Operators are provided to cut and
53 /* combine trees in various manners.
54 /*
55 /* tok822_append() appends the token list \fIt2\fR to the right
56 /* of token list \fIt1\fR. The result is the last token in \fIt2\fR.
57 /* The appended list inherits the \fIowner\fR attribute from \fIt1\fR.
58 /* The parent node, if any, is not updated.
59 /*
60 /* tok822_prepend() inserts the token list \fIt2\fR to the left
61 /* of token \fIt1\fR. The result is the last token in \fIt2\fR.
62 /* The appended list inherits the \fIowner\fR attribute from \fIt1\fR.
63 /* The parent node, if any, is not updated.
64 /*
65 /* tok822_cut_before() breaks a token list on the left side of \fItp\fR
66 /* and returns the left neighbor of \tItp\fR.
67 /*
68 /* tok822_cut_after() breaks a token list on the right side of \fItp\fR
69 /* and returns the right neighbor of \tItp\fR.
70 /*
71 /* tok822_unlink() disconnects a token from its left and right neighbors
72 /* and returns the left neighbor of \tItp\fR.
73 /*
74 /* tok822_sub_append() appends the token list \fIt2\fR to the right
75 /* of the token list below \fIt1\fR. The result is the last token
76 /* in \fIt2\fR.
77 /*
78 /* tok822_sub_prepend() prepends the token list \fIt2\fR to the left
79 /* of the token list below \fIt1\fR. The result is the last token
80 /* in \fIt2\fR.
81 /*
82 /* tok822_sub_keep_before() keeps the token list below \fIt1\fR on the
83 /* left side of \fIt2\fR and returns the tail of the disconnected list.
84 /*
85 /* tok822_sub_keep_after() keeps the token list below \fIt1\fR on the
86 /* right side of \fIt2\fR and returns the head of the disconnected list.
87 /*
88 /* tok822_apply() applies the specified action routine to all tokens
89 /* matching the given type (to all tokens when a null type is given).
90 /* Processing terminates when the action routine returns a non-zero
91 /* value. The result is the last result returned by the action routine.
92 /* tok822_apply() does not traverse vertical links.
93 /*
94 /* tok822_grep() returns a null-terminated array of pointers to tokens
95 /* matching the specified type (all tokens when a null type is given).
96 /* tok822_grep() does not traverse vertical links. The result must be
97 /* given to myfree().
98 /*
99 /* tok822_free_tree() destroys a tree of token structures and
100 /* conveniently returns a null pointer.
101 /* LICENSE
102 /* .ad
103 /* .fi
104 /* The Secure Mailer license must be distributed with this software.
105 /* AUTHOR(S)
106 /* Wietse Venema
107 /* IBM T.J. Watson Research
108 /* P.O. Box 704
109 /* Yorktown Heights, NY 10598, USA
110 /*--*/
111
112 /* System library. */
113
114 #include <sys_defs.h>
115
116 /* Utility library. */
117
118 #include <mymalloc.h>
119 #include <vstring.h>
120
121 /* Global library. */
122
123 #include "tok822.h"
124
125 /* tok822_append - insert token list, return end of inserted list */
126
tok822_append(TOK822 * t1,TOK822 * t2)127 TOK822 *tok822_append(TOK822 *t1, TOK822 *t2)
128 {
129 TOK822 *next = t1->next;
130
131 t1->next = t2;
132 t2->prev = t1;
133
134 t2->owner = t1->owner;
135 while (t2->next)
136 (t2 = t2->next)->owner = t1->owner;
137
138 t2->next = next;
139 if (next)
140 next->prev = t2;
141 return (t2);
142 }
143
144 /* tok822_prepend - insert token list, return end of inserted list */
145
tok822_prepend(TOK822 * t1,TOK822 * t2)146 TOK822 *tok822_prepend(TOK822 *t1, TOK822 *t2)
147 {
148 TOK822 *prev = t1->prev;
149
150 if (prev)
151 prev->next = t2;
152 t2->prev = prev;
153
154 t2->owner = t1->owner;
155 while (t2->next)
156 (t2 = t2->next)->owner = t1->owner;
157
158 t2->next = t1;
159 t1->prev = t2;
160 return (t2);
161 }
162
163 /* tok822_cut_before - split list before token, return predecessor token */
164
tok822_cut_before(TOK822 * tp)165 TOK822 *tok822_cut_before(TOK822 *tp)
166 {
167 TOK822 *prev = tp->prev;
168
169 if (prev) {
170 prev->next = 0;
171 tp->prev = 0;
172 }
173 return (prev);
174 }
175
176 /* tok822_cut_after - split list after token, return successor token */
177
tok822_cut_after(TOK822 * tp)178 TOK822 *tok822_cut_after(TOK822 *tp)
179 {
180 TOK822 *next = tp->next;
181
182 if (next) {
183 next->prev = 0;
184 tp->next = 0;
185 }
186 return (next);
187 }
188
189 /* tok822_unlink - take token away from list, return predecessor token */
190
tok822_unlink(TOK822 * tp)191 TOK822 *tok822_unlink(TOK822 *tp)
192 {
193 TOK822 *prev = tp->prev;
194 TOK822 *next = tp->next;
195
196 if (prev)
197 prev->next = next;
198 if (next)
199 next->prev = prev;
200 tp->prev = tp->next = 0;
201 return (prev);
202 }
203
204 /* tok822_sub_append - append sublist, return end of appended list */
205
tok822_sub_append(TOK822 * t1,TOK822 * t2)206 TOK822 *tok822_sub_append(TOK822 *t1, TOK822 *t2)
207 {
208 if (t1->head) {
209 return (t1->tail = tok822_append(t1->tail, t2));
210 } else {
211 t1->head = t2;
212 t2->owner = t1;
213 while (t2->next)
214 (t2 = t2->next)->owner = t1;
215 return (t1->tail = t2);
216 }
217 }
218
219 /* tok822_sub_prepend - prepend sublist, return end of prepended list */
220
tok822_sub_prepend(TOK822 * t1,TOK822 * t2)221 TOK822 *tok822_sub_prepend(TOK822 *t1, TOK822 *t2)
222 {
223 TOK822 *tp;
224
225 if (t1->head) {
226 tp = tok822_prepend(t1->head, t2);
227 t1->head = t2;
228 return (tp);
229 } else {
230 t1->head = t2;
231 t2->owner = t1;
232 while (t2->next)
233 (t2 = t2->next)->owner = t1;
234 return (t1->tail = t2);
235 }
236 }
237
238 /* tok822_sub_keep_before - cut sublist, return tail of disconnected list */
239
tok822_sub_keep_before(TOK822 * t1,TOK822 * t2)240 TOK822 *tok822_sub_keep_before(TOK822 *t1, TOK822 *t2)
241 {
242 TOK822 *tail = t1->tail;
243
244 if ((t1->tail = tok822_cut_before(t2)) == 0)
245 t1->head = 0;
246 return (tail);
247 }
248
249 /* tok822_sub_keep_after - cut sublist, return head of disconnected list */
250
tok822_sub_keep_after(TOK822 * t1,TOK822 * t2)251 TOK822 *tok822_sub_keep_after(TOK822 *t1, TOK822 *t2)
252 {
253 TOK822 *head = t1->head;
254
255 if ((t1->head = tok822_cut_after(t2)) == 0)
256 t1->tail = 0;
257 return (head);
258 }
259
260 /* tok822_free_tree - destroy token tree */
261
tok822_free_tree(TOK822 * tp)262 TOK822 *tok822_free_tree(TOK822 *tp)
263 {
264 TOK822 *next;
265
266 for (/* void */; tp != 0; tp = next) {
267 if (tp->head)
268 tok822_free_tree(tp->head);
269 next = tp->next;
270 tok822_free(tp);
271 }
272 return (0);
273 }
274
275 /* tok822_apply - apply action to specified tokens */
276
tok822_apply(TOK822 * tree,int type,TOK822_ACTION action)277 int tok822_apply(TOK822 *tree, int type, TOK822_ACTION action)
278 {
279 TOK822 *tp;
280 int result = 0;
281
282 for (tp = tree; tp; tp = tp->next) {
283 if (type == 0 || tp->type == type)
284 if ((result = action(tp)) != 0)
285 break;
286 }
287 return (result);
288 }
289
290 /* tok822_grep - list matching tokens */
291
tok822_grep(TOK822 * tree,int type)292 TOK822 **tok822_grep(TOK822 *tree, int type)
293 {
294 TOK822 **list;
295 TOK822 *tp;
296 int count;
297
298 for (count = 0, tp = tree; tp; tp = tp->next)
299 if (type == 0 || tp->type == type)
300 count++;
301
302 list = (TOK822 **) mymalloc(sizeof(*list) * (count + 1));
303
304 for (count = 0, tp = tree; tp; tp = tp->next)
305 if (type == 0 || tp->type == type)
306 list[count++] = tp;
307
308 list[count] = 0;
309 return (list);
310 }
311