usr/src/cmd/tr/cset.c

   1 /*
   2  * Copyright (c) 2004 Tim J. Robbins.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26 /*
  27  * "Set of characters" ADT implemented as a splay tree of extents, with
  28  * a lookup table cache to simplify looking up the first bunch of
  29  * characters (which are presumably more common than others).
  30  */
  31
  32 #include <assert.h>
  33 #include <stdbool.h>
  34 #include <stdlib.h>
  35 #include <wchar.h>
  36 #include <wctype.h>
  37 #include "cset.h"
  38
  39 static struct csnode    *cset_delete(struct csnode *, wchar_t);
  40 static int              cset_rangecmp(struct csnode *, wchar_t);
  41 static struct csnode    *cset_splay(struct csnode *, wchar_t);
  42
  43 /*
  44  * cset_alloc --
  45  *      Allocate a set of characters.
  46  */
  47 struct cset *
  48 cset_alloc(void)
  49 {
  50         struct cset *cs;
  51
  52         if ((cs = malloc(sizeof (*cs))) == NULL)
  53                 return (NULL);
  54         cs->cs_root = NULL;
  55         cs->cs_classes = NULL;
  56         cs->cs_havecache = false;
  57         cs->cs_invert = false;
  58         return (cs);
  59 }
  60
  61 /*
  62  * cset_add --
  63  *      Add a character to the set.
  64  */
  65 bool
  66 cset_add(struct cset *cs, wchar_t ch)
  67 {
  68         struct csnode *csn, *ncsn;
  69         wchar_t oval;
  70
  71         cs->cs_havecache = false;
  72
  73         /*
  74          * Inserting into empty tree; new item becomes the root.
  75          */
  76         if (cs->cs_root == NULL) {
  77                 csn = malloc(sizeof (*cs->cs_root));
  78                 if (csn == NULL)
  79                         return (false);
  80                 csn->csn_left = csn->csn_right = NULL;
  81                 csn->csn_min = csn->csn_max = ch;
  82                 cs->cs_root = csn;
  83                 return (true);
  84         }
  85
  86         /*
  87          * Splay to check whether the item already exists, and otherwise,
  88          * where we should put it.
  89          */
  90         csn = cs->cs_root = cset_splay(cs->cs_root, ch);
  91
  92         /*
  93          * Avoid adding duplicate nodes.
  94          */
  95         if (cset_rangecmp(csn, ch) == 0)
  96                 return (true);
  97
  98         /*
  99          * Allocate a new node and make it the new root.
 100          */
 101         ncsn = malloc(sizeof (*ncsn));
 102         if (ncsn == NULL)
 103                 return (false);
 104         ncsn->csn_min = ncsn->csn_max = ch;
 105         if (cset_rangecmp(csn, ch) < 0) {
 106                 ncsn->csn_left = csn->csn_left;
 107                 ncsn->csn_right = csn;
 108                 csn->csn_left = NULL;
 109         } else {
 110                 ncsn->csn_right = csn->csn_right;
 111                 ncsn->csn_left = csn;
 112                 csn->csn_right = NULL;
 113         }
 114         cs->cs_root = ncsn;
 115
 116         /*
 117          * Coalesce with left and right neighbours if possible.
 118          */
 119         if (ncsn->csn_left != NULL) {
 120                 ncsn->csn_left = cset_splay(ncsn->csn_left, ncsn->csn_min - 1);
 121                 if (ncsn->csn_left->csn_max == ncsn->csn_min - 1) {
 122                         oval = ncsn->csn_left->csn_min;
 123                         ncsn->csn_left = cset_delete(ncsn->csn_left,
 124                             ncsn->csn_left->csn_min);
 125                         ncsn->csn_min = oval;
 126                 }
 127         }
 128         if (ncsn->csn_right != NULL) {
 129                 ncsn->csn_right = cset_splay(ncsn->csn_right,
 130                     ncsn->csn_max + 1);
 131                 if (ncsn->csn_right->csn_min == ncsn->csn_max + 1) {
 132                         oval = ncsn->csn_right->csn_max;
 133                         ncsn->csn_right = cset_delete(ncsn->csn_right,
 134                             ncsn->csn_right->csn_min);
 135                         ncsn->csn_max = oval;
 136                 }
 137         }
 138
 139         return (true);
 140 }
 141
 142 /*
 143  * cset_in_hard --
 144  *      Determine whether a character is in the set without using
 145  *      the cache.
 146  */
 147 bool
 148 cset_in_hard(struct cset *cs, wchar_t ch)
 149 {
 150         struct csclass *csc;
 151
 152         for (csc = cs->cs_classes; csc != NULL; csc = csc->csc_next)
 153                 if (csc->csc_invert ^ (iswctype(ch, csc->csc_type) != 0))
 154                         return (cs->cs_invert ^ true);
 155         if (cs->cs_root != NULL) {
 156                 cs->cs_root = cset_splay(cs->cs_root, ch);
 157                 return (cs->cs_invert ^ (cset_rangecmp(cs->cs_root, ch) == 0));
 158         }
 159         return (cs->cs_invert ^ false);
 160 }
 161
 162 /*
 163  * cset_cache --
 164  *      Update the cache.
 165  */
 166 void
 167 cset_cache(struct cset *cs)
 168 {
 169         wchar_t i;
 170
 171         for (i = 0; i < CS_CACHE_SIZE; i++)
 172                 cs->cs_cache[i] = cset_in_hard(cs, i);
 173
 174         cs->cs_havecache = true;
 175 }
 176
 177 /*
 178  * cset_invert --
 179  *      Invert the character set.
 180  */
 181 void
 182 cset_invert(struct cset *cs)
 183 {
 184
 185         cs->cs_invert ^= true;
 186         cs->cs_havecache = false;
 187 }
 188
 189 /*
 190  * cset_addclass --
 191  *      Add a wctype()-style character class to the set, optionally
 192  *      inverting it.
 193  */
 194 bool
 195 cset_addclass(struct cset *cs, wctype_t type, bool invert)
 196 {
 197         struct csclass *csc;
 198
 199         csc = malloc(sizeof (*csc));
 200         if (csc == NULL)
 201                 return (false);
 202         csc->csc_type = type;
 203         csc->csc_invert = invert;
 204         csc->csc_next = cs->cs_classes;
 205         cs->cs_classes = csc;
 206         cs->cs_havecache = false;
 207         return (true);
 208 }
 209
 210 static int
 211 cset_rangecmp(struct csnode *t, wchar_t ch)
 212 {
 213
 214         if (ch < t->csn_min)
 215                 return (-1);
 216         if (ch > t->csn_max)
 217                 return (1);
 218         return (0);
 219 }
 220
 221 static struct csnode *
 222 cset_splay(struct csnode *t, wchar_t ch)
 223 {
 224         struct csnode N, *l, *r, *y;
 225
 226         /*
 227          * Based on public domain code from Sleator.
 228          */
 229
 230         assert(t != NULL);
 231
 232         N.csn_left = N.csn_right = NULL;
 233         l = r = &N;
 234         for (;;) {
 235                 if (cset_rangecmp(t, ch) < 0) {
 236                         if (t->csn_left != NULL &&
 237                             cset_rangecmp(t->csn_left, ch) < 0) {
 238                                 y = t->csn_left;
 239                                 t->csn_left = y->csn_right;
 240                                 y->csn_right = t;
 241                                 t = y;
 242                         }
 243                         if (t->csn_left == NULL)
 244                                 break;
 245                         r->csn_left = t;
 246                         r = t;
 247                         t = t->csn_left;
 248                 } else if (cset_rangecmp(t, ch) > 0) {
 249                         if (t->csn_right != NULL &&
 250                             cset_rangecmp(t->csn_right, ch) > 0) {
 251                                 y = t->csn_right;
 252                                 t->csn_right = y->csn_left;
 253                                 y->csn_left = t;
 254                                 t = y;
 255                         }
 256                         if (t->csn_right == NULL)
 257                                 break;
 258                         l->csn_right = t;
 259                         l = t;
 260                         t = t->csn_right;
 261                 } else
 262                         break;
 263         }
 264         l->csn_right = t->csn_left;
 265         r->csn_left = t->csn_right;
 266         t->csn_left = N.csn_right;
 267         t->csn_right = N.csn_left;
 268         return (t);
 269 }
 270
 271 static struct csnode *
 272 cset_delete(struct csnode *t, wchar_t ch)
 273 {
 274         struct csnode *x;
 275
 276         assert(t != NULL);
 277         t = cset_splay(t, ch);
 278         assert(cset_rangecmp(t, ch) == 0);
 279         if (t->csn_left == NULL)
 280                 x = t->csn_right;
 281         else {
 282                 x = cset_splay(t->csn_left, ch);
 283                 x->csn_right = t->csn_right;
 284         }
 285         free(t);
 286         return (x);
 287 }