cset.c revision 84cf253f8f6b41850d9fd9d5c853b30ce633bb40
/*
* Copyright (c) 2004 Tim J. Robbins.
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/*
* "Set of characters" ADT implemented as a splay tree of extents, with
* a lookup table cache to simplify looking up the first bunch of
* characters (which are presumably more common than others).
*/
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
#include <wchar.h>
#include <wctype.h>
#include "cset.h"
static struct csnode *cset_delete(struct csnode *, wchar_t);
static int cset_rangecmp(struct csnode *, wchar_t);
static struct csnode *cset_splay(struct csnode *, wchar_t);
/*
* cset_alloc --
* Allocate a set of characters.
*/
struct cset *
cset_alloc(void)
{
struct cset *cs;
if ((cs = malloc(sizeof (*cs))) == NULL)
return (NULL);
cs->cs_root = NULL;
cs->cs_classes = NULL;
cs->cs_havecache = false;
cs->cs_invert = false;
return (cs);
}
/*
* cset_add --
* Add a character to the set.
*/
bool
cset_add(struct cset *cs, wchar_t ch)
{
struct csnode *csn, *ncsn;
wchar_t oval;
cs->cs_havecache = false;
/*
* Inserting into empty tree; new item becomes the root.
*/
if (cs->cs_root == NULL) {
csn = malloc(sizeof (*cs->cs_root));
if (csn == NULL)
return (false);
csn->csn_left = csn->csn_right = NULL;
csn->csn_min = csn->csn_max = ch;
cs->cs_root = csn;
return (true);
}
/*
* Splay to check whether the item already exists, and otherwise,
* where we should put it.
*/
csn = cs->cs_root = cset_splay(cs->cs_root, ch);
/*
* Avoid adding duplicate nodes.
*/
if (cset_rangecmp(csn, ch) == 0)
return (true);
/*
* Allocate a new node and make it the new root.
*/
ncsn = malloc(sizeof (*ncsn));
if (ncsn == NULL)
return (false);
ncsn->csn_min = ncsn->csn_max = ch;
if (cset_rangecmp(csn, ch) < 0) {
ncsn->csn_left = csn->csn_left;
ncsn->csn_right = csn;
csn->csn_left = NULL;
} else {
ncsn->csn_right = csn->csn_right;
ncsn->csn_left = csn;
csn->csn_right = NULL;
}
cs->cs_root = ncsn;
/*
* Coalesce with left and right neighbours if possible.
*/
if (ncsn->csn_left != NULL) {
ncsn->csn_left = cset_splay(ncsn->csn_left, ncsn->csn_min - 1);
if (ncsn->csn_left->csn_max == ncsn->csn_min - 1) {
oval = ncsn->csn_left->csn_min;
ncsn->csn_left = cset_delete(ncsn->csn_left,
ncsn->csn_left->csn_min);
ncsn->csn_min = oval;
}
}
if (ncsn->csn_right != NULL) {
ncsn->csn_right = cset_splay(ncsn->csn_right,
ncsn->csn_max + 1);
if (ncsn->csn_right->csn_min == ncsn->csn_max + 1) {
oval = ncsn->csn_right->csn_max;
ncsn->csn_right = cset_delete(ncsn->csn_right,
ncsn->csn_right->csn_min);
ncsn->csn_max = oval;
}
}
return (true);
}
/*
* cset_in_hard --
* Determine whether a character is in the set without using
* the cache.
*/
bool
cset_in_hard(struct cset *cs, wchar_t ch)
{
struct csclass *csc;
for (csc = cs->cs_classes; csc != NULL; csc = csc->csc_next)
if (csc->csc_invert ^ (iswctype(ch, csc->csc_type) != 0))
return (cs->cs_invert ^ true);
if (cs->cs_root != NULL) {
cs->cs_root = cset_splay(cs->cs_root, ch);
return (cs->cs_invert ^ (cset_rangecmp(cs->cs_root, ch) == 0));
}
return (cs->cs_invert ^ false);
}
/*
* cset_cache --
* Update the cache.
*/
void
cset_cache(struct cset *cs)
{
wchar_t i;
for (i = 0; i < CS_CACHE_SIZE; i++)
cs->cs_cache[i] = cset_in_hard(cs, i);
cs->cs_havecache = true;
}
/*
* cset_invert --
* Invert the character set.
*/
void
cset_invert(struct cset *cs)
{
cs->cs_invert ^= true;
cs->cs_havecache = false;
}
/*
* cset_addclass --
* Add a wctype()-style character class to the set, optionally
* inverting it.
*/
bool
cset_addclass(struct cset *cs, wctype_t type, bool invert)
{
struct csclass *csc;
csc = malloc(sizeof (*csc));
if (csc == NULL)
return (false);
csc->csc_type = type;
csc->csc_invert = invert;
csc->csc_next = cs->cs_classes;
cs->cs_classes = csc;
cs->cs_havecache = false;
return (true);
}
static int
cset_rangecmp(struct csnode *t, wchar_t ch)
{
if (ch < t->csn_min)
return (-1);
if (ch > t->csn_max)
return (1);
return (0);
}
static struct csnode *
cset_splay(struct csnode *t, wchar_t ch)
{
struct csnode N, *l, *r, *y;
/*
* Based on public domain code from Sleator.
*/
assert(t != NULL);
N.csn_left = N.csn_right = NULL;
l = r = &N;
for (;;) {
if (cset_rangecmp(t, ch) < 0) {
if (t->csn_left != NULL &&
cset_rangecmp(t->csn_left, ch) < 0) {
y = t->csn_left;
t->csn_left = y->csn_right;
y->csn_right = t;
t = y;
}
if (t->csn_left == NULL)
break;
r->csn_left = t;
r = t;
t = t->csn_left;
} else if (cset_rangecmp(t, ch) > 0) {
if (t->csn_right != NULL &&
cset_rangecmp(t->csn_right, ch) > 0) {
y = t->csn_right;
t->csn_right = y->csn_left;
y->csn_left = t;
t = y;
}
if (t->csn_right == NULL)
break;
l->csn_right = t;
l = t;
t = t->csn_right;
} else
break;
}
l->csn_right = t->csn_left;
r->csn_left = t->csn_right;
t->csn_left = N.csn_right;
t->csn_right = N.csn_left;
return (t);
}
static struct csnode *
cset_delete(struct csnode *t, wchar_t ch)
{
struct csnode *x;
assert(t != NULL);
t = cset_splay(t, ch);
assert(cset_rangecmp(t, ch) == 0);
if (t->csn_left == NULL)
x = t->csn_right;
else {
x = cset_splay(t->csn_left, ch);
x->csn_right = t->csn_right;
}
free(t);
return (x);
}