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 <sys/cdefs.h> 33 __FBSDID("$FreeBSD$"); 34 35 #include <assert.h> 36 #include <stdbool.h> 37 #include <stdlib.h> 38 #include <wchar.h> 39 #include <wctype.h> 40 #include "cset.h" 41 42 static struct csnode * cset_delete(struct csnode *, wchar_t); 43 static __inline int cset_rangecmp(struct csnode *, wchar_t); 44 static struct csnode * cset_splay(struct csnode *, wchar_t); 45 46 /* 47 * cset_alloc -- 48 * Allocate a set of characters. 49 */ 50 struct cset * 51 cset_alloc(void) 52 { 53 struct cset *cs; 54 55 if ((cs = malloc(sizeof(*cs))) == NULL) 56 return (NULL); 57 cs->cs_root = NULL; 58 cs->cs_classes = NULL; 59 cs->cs_havecache = false; 60 cs->cs_invert = false; 61 return (cs); 62 } 63 64 /* 65 * cset_add -- 66 * Add a character to the set. 67 */ 68 bool 69 cset_add(struct cset *cs, wchar_t ch) 70 { 71 struct csnode *csn, *ncsn; 72 wchar_t oval; 73 74 cs->cs_havecache = false; 75 76 /* 77 * Inserting into empty tree; new item becomes the root. 78 */ 79 if (cs->cs_root == NULL) { 80 csn = malloc(sizeof(*cs->cs_root)); 81 if (csn == NULL) 82 return (false); 83 csn->csn_left = csn->csn_right = NULL; 84 csn->csn_min = csn->csn_max = ch; 85 cs->cs_root = csn; 86 return (true); 87 } 88 89 /* 90 * Splay to check whether the item already exists, and otherwise, 91 * where we should put it. 92 */ 93 csn = cs->cs_root = cset_splay(cs->cs_root, ch); 94 95 /* 96 * Avoid adding duplicate nodes. 97 */ 98 if (cset_rangecmp(csn, ch) == 0) 99 return (true); 100 101 /* 102 * Allocate a new node and make it the new root. 103 */ 104 ncsn = malloc(sizeof(*ncsn)); 105 if (ncsn == NULL) 106 return (false); 107 ncsn->csn_min = ncsn->csn_max = ch; 108 if (cset_rangecmp(csn, ch) < 0) { 109 ncsn->csn_left = csn->csn_left; 110 ncsn->csn_right = csn; 111 csn->csn_left = NULL; 112 } else { 113 ncsn->csn_right = csn->csn_right; 114 ncsn->csn_left = csn; 115 csn->csn_right = NULL; 116 } 117 cs->cs_root = ncsn; 118 119 /* 120 * Coalesce with left and right neighbours if possible. 121 */ 122 if (ncsn->csn_left != NULL) { 123 ncsn->csn_left = cset_splay(ncsn->csn_left, ncsn->csn_min - 1); 124 if (ncsn->csn_left->csn_max == ncsn->csn_min - 1) { 125 oval = ncsn->csn_left->csn_min; 126 ncsn->csn_left = cset_delete(ncsn->csn_left, 127 ncsn->csn_left->csn_min); 128 ncsn->csn_min = oval; 129 } 130 } 131 if (ncsn->csn_right != NULL) { 132 ncsn->csn_right = cset_splay(ncsn->csn_right, 133 ncsn->csn_max + 1); 134 if (ncsn->csn_right->csn_min == ncsn->csn_max + 1) { 135 oval = ncsn->csn_right->csn_max; 136 ncsn->csn_right = cset_delete(ncsn->csn_right, 137 ncsn->csn_right->csn_min); 138 ncsn->csn_max = oval; 139 } 140 } 141 142 return (true); 143 } 144 145 /* 146 * cset_in_hard -- 147 * Determine whether a character is in the set without using 148 * the cache. 149 */ 150 bool 151 cset_in_hard(struct cset *cs, wchar_t ch) 152 { 153 struct csclass *csc; 154 155 for (csc = cs->cs_classes; csc != NULL; csc = csc->csc_next) 156 if (csc->csc_invert ^ (iswctype(ch, csc->csc_type) != 0)) 157 return (cs->cs_invert ^ true); 158 if (cs->cs_root != NULL) { 159 cs->cs_root = cset_splay(cs->cs_root, ch); 160 return (cs->cs_invert ^ (cset_rangecmp(cs->cs_root, ch) == 0)); 161 } 162 return (cs->cs_invert ^ false); 163 } 164 165 /* 166 * cset_cache -- 167 * Update the cache. 168 */ 169 void 170 cset_cache(struct cset *cs) 171 { 172 wchar_t i; 173 174 for (i = 0; i < CS_CACHE_SIZE; i++) 175 cs->cs_cache[i] = cset_in_hard(cs, i); 176 177 cs->cs_havecache = true; 178 } 179 180 /* 181 * cset_invert -- 182 * Invert the character set. 183 */ 184 void 185 cset_invert(struct cset *cs) 186 { 187 188 cs->cs_invert ^= true; 189 cs->cs_havecache = false; 190 } 191 192 /* 193 * cset_addclass -- 194 * Add a wctype()-style character class to the set, optionally 195 * inverting it. 196 */ 197 bool 198 cset_addclass(struct cset *cs, wctype_t type, bool invert) 199 { 200 struct csclass *csc; 201 202 csc = malloc(sizeof(*csc)); 203 if (csc == NULL) 204 return (false); 205 csc->csc_type = type; 206 csc->csc_invert = invert; 207 csc->csc_next = cs->cs_classes; 208 cs->cs_classes = csc; 209 cs->cs_havecache = false; 210 return (true); 211 } 212 213 static __inline int 214 cset_rangecmp(struct csnode *t, wchar_t ch) 215 { 216 217 if (ch < t->csn_min) 218 return (-1); 219 if (ch > t->csn_max) 220 return (1); 221 return (0); 222 } 223 224 static struct csnode * 225 cset_splay(struct csnode *t, wchar_t ch) 226 { 227 struct csnode N, *l, *r, *y; 228 229 /* 230 * Based on public domain code from Sleator. 231 */ 232 233 assert(t != NULL); 234 235 N.csn_left = N.csn_right = NULL; 236 l = r = &N; 237 for (;;) { 238 if (cset_rangecmp(t, ch) < 0) { 239 if (t->csn_left != NULL && 240 cset_rangecmp(t->csn_left, ch) < 0) { 241 y = t->csn_left; 242 t->csn_left = y->csn_right; 243 y->csn_right = t; 244 t = y; 245 } 246 if (t->csn_left == NULL) 247 break; 248 r->csn_left = t; 249 r = t; 250 t = t->csn_left; 251 } else if (cset_rangecmp(t, ch) > 0) { 252 if (t->csn_right != NULL && 253 cset_rangecmp(t->csn_right, ch) > 0) { 254 y = t->csn_right; 255 t->csn_right = y->csn_left; 256 y->csn_left = t; 257 t = y; 258 } 259 if (t->csn_right == NULL) 260 break; 261 l->csn_right = t; 262 l = t; 263 t = t->csn_right; 264 } else 265 break; 266 } 267 l->csn_right = t->csn_left; 268 r->csn_left = t->csn_right; 269 t->csn_left = N.csn_right; 270 t->csn_right = N.csn_left; 271 return (t); 272 } 273 274 static struct csnode * 275 cset_delete(struct csnode *t, wchar_t ch) 276 { 277 struct csnode *x; 278 279 assert(t != NULL); 280 t = cset_splay(t, ch); 281 assert(cset_rangecmp(t, ch) == 0); 282 if (t->csn_left == NULL) 283 x = t->csn_right; 284 else { 285 x = cset_splay(t->csn_left, ch); 286 x->csn_right = t->csn_right; 287 } 288 free(t); 289 return x; 290 } 291