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 }