cmd/tr/cset.c

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