1 /* $NetBSD: tok822_tree.c,v 1.2 2017/02/14 01:16:45 christos 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 t2->owner = t1; 215 while (t2->next) 216 (t2 = t2->next)->owner = t1; 217 return (t1->tail = t2); 218 } 219 } 220 221 /* tok822_sub_prepend - prepend sublist, return end of prepended list */ 222 223 TOK822 *tok822_sub_prepend(TOK822 *t1, TOK822 *t2) 224 { 225 TOK822 *tp; 226 227 if (t1->head) { 228 tp = tok822_prepend(t1->head, t2); 229 t1->head = t2; 230 return (tp); 231 } else { 232 t1->head = t2; 233 t2->owner = t1; 234 while (t2->next) 235 (t2 = t2->next)->owner = t1; 236 return (t1->tail = t2); 237 } 238 } 239 240 /* tok822_sub_keep_before - cut sublist, return tail of disconnected list */ 241 242 TOK822 *tok822_sub_keep_before(TOK822 *t1, TOK822 *t2) 243 { 244 TOK822 *tail = t1->tail; 245 246 if ((t1->tail = tok822_cut_before(t2)) == 0) 247 t1->head = 0; 248 return (tail); 249 } 250 251 /* tok822_sub_keep_after - cut sublist, return head of disconnected list */ 252 253 TOK822 *tok822_sub_keep_after(TOK822 *t1, TOK822 *t2) 254 { 255 TOK822 *head = t1->head; 256 257 if ((t1->head = tok822_cut_after(t2)) == 0) 258 t1->tail = 0; 259 return (head); 260 } 261 262 /* tok822_free_tree - destroy token tree */ 263 264 TOK822 *tok822_free_tree(TOK822 *tp) 265 { 266 TOK822 *next; 267 268 for (/* void */; tp != 0; tp = next) { 269 if (tp->head) 270 tok822_free_tree(tp->head); 271 next = tp->next; 272 tok822_free(tp); 273 } 274 return (0); 275 } 276 277 /* tok822_apply - apply action to specified tokens */ 278 279 int tok822_apply(TOK822 *tree, int type, TOK822_ACTION action) 280 { 281 TOK822 *tp; 282 int result = 0; 283 284 for (tp = tree; tp; tp = tp->next) { 285 if (type == 0 || tp->type == type) 286 if ((result = action(tp)) != 0) 287 break; 288 } 289 return (result); 290 } 291 292 /* tok822_grep - list matching tokens */ 293 294 TOK822 **tok822_grep(TOK822 *tree, int type) 295 { 296 TOK822 **list; 297 TOK822 *tp; 298 int count; 299 300 for (count = 0, tp = tree; tp; tp = tp->next) 301 if (type == 0 || tp->type == type) 302 count++; 303 304 list = (TOK822 **) mymalloc(sizeof(*list) * (count + 1)); 305 306 for (count = 0, tp = tree; tp; tp = tp->next) 307 if (type == 0 || tp->type == type) 308 list[count++] = tp; 309 310 list[count] = 0; 311 return (list); 312 } 313