1131846Stjr/*- 2131846Stjr * Copyright (c) 2004 Tim J. Robbins. 3131846Stjr * All rights reserved. 4131846Stjr * 5131846Stjr * Redistribution and use in source and binary forms, with or without 6131846Stjr * modification, are permitted provided that the following conditions 7131846Stjr * are met: 8131846Stjr * 1. Redistributions of source code must retain the above copyright 9131846Stjr * notice, this list of conditions and the following disclaimer. 10131846Stjr * 2. Redistributions in binary form must reproduce the above copyright 11131846Stjr * notice, this list of conditions and the following disclaimer in the 12131846Stjr * documentation and/or other materials provided with the distribution. 13131846Stjr * 14131846Stjr * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15131846Stjr * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16131846Stjr * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17131846Stjr * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18131846Stjr * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19131846Stjr * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20131846Stjr * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21131846Stjr * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22131846Stjr * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23131846Stjr * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24131846Stjr * SUCH DAMAGE. 25131846Stjr */ 26131846Stjr/* 27131846Stjr * "Character map" ADT. Stores mappings between pairs of characters in a 28131846Stjr * splay tree, with a lookup table cache to simplify looking up the first 29131846Stjr * bunch of characters (which are presumably more common than others). 30131846Stjr */ 31131846Stjr 32131846Stjr#include <sys/cdefs.h> 33131846Stjr__FBSDID("$FreeBSD$"); 34131846Stjr 35131846Stjr#include <assert.h> 36200462Sdelphij#include <limits.h> 37200462Sdelphij#include <stdbool.h> 38131846Stjr#include <stdlib.h> 39200462Sdelphij#include <wchar.h> 40131846Stjr#include "cmap.h" 41131846Stjr 42131846Stjrstatic struct cmapnode *cmap_splay(struct cmapnode *, wint_t); 43131846Stjr 44131846Stjr/* 45131846Stjr * cmap_alloc -- 46131846Stjr * Allocate a character map. 47131846Stjr */ 48131846Stjrstruct cmap * 49131846Stjrcmap_alloc(void) 50131846Stjr{ 51131846Stjr struct cmap *cm; 52131846Stjr 53131846Stjr cm = malloc(sizeof(*cm)); 54131846Stjr if (cm == NULL) 55131846Stjr return (NULL); 56131846Stjr cm->cm_root = NULL; 57131846Stjr cm->cm_def = CM_DEF_SELF; 58131846Stjr cm->cm_havecache = false; 59131846Stjr cm->cm_min = cm->cm_max = 0; 60131846Stjr return (cm); 61131846Stjr} 62131846Stjr 63131846Stjr/* 64131846Stjr * cmap_add -- 65131846Stjr * Add a mapping from "from" to "to" to the map. 66131846Stjr */ 67131846Stjrbool 68131846Stjrcmap_add(struct cmap *cm, wint_t from, wint_t to) 69131846Stjr{ 70131846Stjr struct cmapnode *cmn, *ncmn; 71131846Stjr 72131846Stjr cm->cm_havecache = false; 73131846Stjr 74131846Stjr if (cm->cm_root == NULL) { 75131846Stjr cmn = malloc(sizeof(*cmn)); 76131846Stjr if (cmn == NULL) 77131846Stjr return (false); 78131846Stjr cmn->cmn_from = from; 79131846Stjr cmn->cmn_to = to; 80131846Stjr cmn->cmn_left = cmn->cmn_right = NULL; 81131846Stjr cm->cm_root = cmn; 82131846Stjr cm->cm_min = cm->cm_max = from; 83131846Stjr return (true); 84131846Stjr } 85131846Stjr 86131846Stjr cmn = cm->cm_root = cmap_splay(cm->cm_root, from); 87131846Stjr 88131846Stjr if (cmn->cmn_from == from) { 89131846Stjr cmn->cmn_to = to; 90131846Stjr return (true); 91131846Stjr } 92131846Stjr 93131846Stjr ncmn = malloc(sizeof(*ncmn)); 94131846Stjr if (ncmn == NULL) 95131846Stjr return (false); 96131846Stjr ncmn->cmn_from = from; 97131846Stjr ncmn->cmn_to = to; 98131846Stjr if (from < cmn->cmn_from) { 99131846Stjr ncmn->cmn_left = cmn->cmn_left; 100131846Stjr ncmn->cmn_right = cmn; 101131846Stjr cmn->cmn_left = NULL; 102131846Stjr } else { 103131846Stjr ncmn->cmn_right = cmn->cmn_right; 104131846Stjr ncmn->cmn_left = cmn; 105131846Stjr cmn->cmn_right = NULL; 106131846Stjr } 107131846Stjr if (from < cm->cm_min) 108131846Stjr cm->cm_min = from; 109131846Stjr if (from > cm->cm_max) 110131846Stjr cm->cm_max = from; 111131846Stjr cm->cm_root = ncmn; 112131846Stjr 113131846Stjr return (true); 114131846Stjr} 115131846Stjr 116131846Stjr/* 117131846Stjr * cmap_lookup_hard -- 118132144Stjr * Look up the mapping for a character without using the cache. 119131846Stjr */ 120131846Stjrwint_t 121131846Stjrcmap_lookup_hard(struct cmap *cm, wint_t ch) 122131846Stjr{ 123131846Stjr 124131846Stjr if (cm->cm_root != NULL) { 125131846Stjr cm->cm_root = cmap_splay(cm->cm_root, ch); 126131846Stjr if (cm->cm_root->cmn_from == ch) 127131846Stjr return (cm->cm_root->cmn_to); 128131846Stjr } 129131846Stjr return (cm->cm_def == CM_DEF_SELF ? ch : cm->cm_def); 130131846Stjr} 131131846Stjr 132131846Stjr/* 133131846Stjr * cmap_cache -- 134131846Stjr * Update the cache. 135131846Stjr */ 136131846Stjrvoid 137131846Stjrcmap_cache(struct cmap *cm) 138131846Stjr{ 139131846Stjr wint_t ch; 140131846Stjr 141131846Stjr for (ch = 0; ch < CM_CACHE_SIZE; ch++) 142131846Stjr cm->cm_cache[ch] = cmap_lookup_hard(cm, ch); 143131846Stjr 144131846Stjr cm->cm_havecache = true; 145131846Stjr} 146131846Stjr 147131846Stjr/* 148131846Stjr * cmap_default -- 149131846Stjr * Change the value that characters without mappings map to, and 150131846Stjr * return the old value. The special character value CM_MAP_SELF 151131846Stjr * means characters map to themselves. 152131846Stjr */ 153131846Stjrwint_t 154131846Stjrcmap_default(struct cmap *cm, wint_t def) 155131846Stjr{ 156131846Stjr wint_t old; 157131846Stjr 158131846Stjr old = cm->cm_def; 159131846Stjr cm->cm_def = def; 160131846Stjr cm->cm_havecache = false; 161131846Stjr return (old); 162131846Stjr} 163131846Stjr 164131846Stjrstatic struct cmapnode * 165131846Stjrcmap_splay(struct cmapnode *t, wint_t ch) 166131846Stjr{ 167131846Stjr struct cmapnode N, *l, *r, *y; 168131846Stjr 169131846Stjr /* 170131846Stjr * Based on public domain code from Sleator. 171131846Stjr */ 172131846Stjr 173131846Stjr assert(t != NULL); 174131846Stjr 175131846Stjr N.cmn_left = N.cmn_right = NULL; 176131846Stjr l = r = &N; 177131846Stjr for (;;) { 178131846Stjr if (ch < t->cmn_from) { 179131846Stjr if (t->cmn_left != NULL && 180131846Stjr ch < t->cmn_left->cmn_from) { 181131846Stjr y = t->cmn_left; 182131846Stjr t->cmn_left = y->cmn_right; 183131846Stjr y->cmn_right = t; 184131846Stjr t = y; 185131846Stjr } 186131846Stjr if (t->cmn_left == NULL) 187131846Stjr break; 188131846Stjr r->cmn_left = t; 189131846Stjr r = t; 190131846Stjr t = t->cmn_left; 191131846Stjr } else if (ch > t->cmn_from) { 192131846Stjr if (t->cmn_right != NULL && 193131846Stjr ch > t->cmn_right->cmn_from) { 194131846Stjr y = t->cmn_right; 195131846Stjr t->cmn_right = y->cmn_left; 196131846Stjr y->cmn_left = t; 197131846Stjr t = y; 198131846Stjr } 199131846Stjr if (t->cmn_right == NULL) 200131846Stjr break; 201131846Stjr l->cmn_right = t; 202131846Stjr l = t; 203131846Stjr t = t->cmn_right; 204131846Stjr } else 205131846Stjr break; 206131846Stjr } 207131846Stjr l->cmn_right = t->cmn_left; 208131846Stjr r->cmn_left = t->cmn_right; 209131846Stjr t->cmn_left = N.cmn_right; 210131846Stjr t->cmn_right = N.cmn_left; 211131846Stjr return (t); 212131846Stjr} 213