external/ibm-public/postfix/dist/src/global/tok822_tree.c

   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
 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 }