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