1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause
47  * cset_alloc --
53 	struct cset *cs;  in cset_alloc()  local
55 	if ((cs = malloc(sizeof(*cs))) == NULL)  in cset_alloc()
57 	cs->cs_root = NULL;  in cset_alloc()
58 	cs->cs_classes = NULL;  in cset_alloc()
59 	cs->cs_havecache = false;  in cset_alloc()
60 	cs->cs_invert = false;  in cset_alloc()
61 	return (cs);  in cset_alloc()
65  * cset_add --
69 cset_add(struct cset *cs, wchar_t ch)  in cset_add()  argument
74 	cs->cs_havecache = false;  in cset_add()
79 	if (cs->cs_root == NULL) {  in cset_add()
80 		csn = malloc(sizeof(*cs->cs_root));  in cset_add()
83 		csn->csn_left = csn->csn_right = NULL;  in cset_add()
84 		csn->csn_min = csn->csn_max = ch;  in cset_add()
85 		cs->cs_root = csn;  in cset_add()
93 	csn = cs->cs_root = cset_splay(cs->cs_root, ch);  in cset_add()
98 	if (cset_rangecmp(csn, ch) == 0)  in cset_add()
107 	ncsn->csn_min = ncsn->csn_max = ch;  in cset_add()
108 	if (cset_rangecmp(csn, ch) < 0) {  in cset_add()
109 		ncsn->csn_left = csn->csn_left;  in cset_add()
110 		ncsn->csn_right = csn;  in cset_add()
111 		csn->csn_left = NULL;  in cset_add()
113 		ncsn->csn_right = csn->csn_right;  in cset_add()
114 		ncsn->csn_left = csn;  in cset_add()
115 		csn->csn_right = NULL;  in cset_add()
117 	cs->cs_root = ncsn;  in cset_add()
122 	if (ncsn->csn_left != NULL) {  in cset_add()
123 		ncsn->csn_left = cset_splay(ncsn->csn_left, ncsn->csn_min - 1);  in cset_add()
124 		if (ncsn->csn_left->csn_max == ncsn->csn_min - 1) {  in cset_add()
125 			oval = ncsn->csn_left->csn_min;  in cset_add()
126 			ncsn->csn_left = cset_delete(ncsn->csn_left,  in cset_add()
127 			    ncsn->csn_left->csn_min);  in cset_add()
128 			ncsn->csn_min = oval;  in cset_add()
131 	if (ncsn->csn_right != NULL) {  in cset_add()
132 		ncsn->csn_right = cset_splay(ncsn->csn_right,  in cset_add()
133 		    ncsn->csn_max + 1);  in cset_add()
134 		if (ncsn->csn_right->csn_min == ncsn->csn_max + 1) {  in cset_add()
135 			oval = ncsn->csn_right->csn_max;  in cset_add()
136 			ncsn->csn_right = cset_delete(ncsn->csn_right,  in cset_add()
137 			    ncsn->csn_right->csn_min);  in cset_add()
138 			ncsn->csn_max = oval;  in cset_add()
146  * cset_in_hard --
151 cset_in_hard(struct cset *cs, wchar_t ch)  in cset_in_hard()  argument
155 	for (csc = cs->cs_classes; csc != NULL; csc = csc->csc_next)  in cset_in_hard()
156 		if (csc->csc_invert ^ (iswctype(ch, csc->csc_type) != 0))  in cset_in_hard()
157 			return (cs->cs_invert ^ true);  in cset_in_hard()
158 	if (cs->cs_root != NULL) {  in cset_in_hard()
159 		cs->cs_root = cset_splay(cs->cs_root, ch);  in cset_in_hard()
160 		return (cs->cs_invert ^ (cset_rangecmp(cs->cs_root, ch) == 0));  in cset_in_hard()
162 	return (cs->cs_invert ^ false);  in cset_in_hard()
166  * cset_cache --
170 cset_cache(struct cset *cs)  in cset_cache()  argument
174 	for (i = 0; i < CS_CACHE_SIZE; i++)  in cset_cache()
175 		cs->cs_cache[i] = cset_in_hard(cs, i);  in cset_cache()
177 	cs->cs_havecache = true;  in cset_cache()
181  * cset_invert --
185 cset_invert(struct cset *cs)  in cset_invert()  argument
188 	cs->cs_invert ^= true;  in cset_invert()
189 	cs->cs_havecache = false;  in cset_invert()
193  * cset_addclass --
194  *	Add a wctype()-style character class to the set, optionally
198 cset_addclass(struct cset *cs, wctype_t type, bool invert)  in cset_addclass()  argument
205 	csc->csc_type = type;  in cset_addclass()
206 	csc->csc_invert = invert;  in cset_addclass()
207 	csc->csc_next = cs->cs_classes;  in cset_addclass()
208 	cs->cs_classes = csc;  in cset_addclass()
209 	cs->cs_havecache = false;  in cset_addclass()
217 	if (ch < t->csn_min)  in cset_rangecmp()
218 		return (-1);  in cset_rangecmp()
219 	if (ch > t->csn_max)  in cset_rangecmp()
221 	return (0);  in cset_rangecmp()
238 		if (cset_rangecmp(t, ch) < 0) {  in cset_splay()
239 			if (t->csn_left != NULL &&  in cset_splay()
240 			    cset_rangecmp(t->csn_left, ch) < 0) {  in cset_splay()
241 				y = t->csn_left;  in cset_splay()
242 				t->csn_left = y->csn_right;  in cset_splay()
243 				y->csn_right = t;  in cset_splay()
246 			if (t->csn_left == NULL)  in cset_splay()
248 			r->csn_left = t;  in cset_splay()
250 			t = t->csn_left;  in cset_splay()
251 		} else if (cset_rangecmp(t, ch) > 0) {  in cset_splay()
252 			if (t->csn_right != NULL &&  in cset_splay()
253 			    cset_rangecmp(t->csn_right, ch) > 0) {  in cset_splay()
254 				y = t->csn_right;  in cset_splay()
255 				t->csn_right = y->csn_left;  in cset_splay()
256 				y->csn_left = t;  in cset_splay()
259 			if (t->csn_right == NULL)  in cset_splay()
261 			l->csn_right = t;  in cset_splay()
263 			t = t->csn_right;  in cset_splay()
267 	l->csn_right = t->csn_left;  in cset_splay()
268 	r->csn_left = t->csn_right;  in cset_splay()
269 	t->csn_left = N.csn_right;  in cset_splay()
270 	t->csn_right = N.csn_left;  in cset_splay()
281 	assert(cset_rangecmp(t, ch) == 0);  in cset_delete()
282 	if (t->csn_left == NULL)  in cset_delete()
283 		x = t->csn_right;  in cset_delete()
285 		x = cset_splay(t->csn_left, ch);  in cset_delete()
286 		x->csn_right = t->csn_right;  in cset_delete()