1 /* $NetBSD: tok822_tree.c,v 1.1.1.1 2009/06/23 10:08:48 tron Exp $ */ 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 129 TOK822 *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 148 TOK822 *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 167 TOK822 *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 180 TOK822 *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 193 TOK822 *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 208 TOK822 *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 222 TOK822 *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 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 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 262 TOK822 *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 276 int 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 291 TOK822 **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