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