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