cmap.c revision 200420
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 * "Character map" ADT. Stores mappings between pairs of characters in a 28 * splay tree, with a lookup table cache to simplify looking up the first 29 * bunch of characters (which are presumably more common than others). 30 */ 31 32#include <sys/cdefs.h> 33__FBSDID("$FreeBSD: head/usr.bin/tr/cmap.c 200420 2009-12-11 23:35:38Z delphij $"); 34 35#include <assert.h> 36#include <stdlib.h> 37#include "cmap.h" 38 39static struct cmapnode *cmap_splay(struct cmapnode *, wint_t); 40 41/* 42 * cmap_alloc -- 43 * Allocate a character map. 44 */ 45struct cmap * 46cmap_alloc(void) 47{ 48 struct cmap *cm; 49 50 cm = malloc(sizeof(*cm)); 51 if (cm == NULL) 52 return (NULL); 53 cm->cm_root = NULL; 54 cm->cm_def = CM_DEF_SELF; 55 cm->cm_havecache = false; 56 cm->cm_min = cm->cm_max = 0; 57 return (cm); 58} 59 60/* 61 * cmap_add -- 62 * Add a mapping from "from" to "to" to the map. 63 */ 64bool 65cmap_add(struct cmap *cm, wint_t from, wint_t to) 66{ 67 struct cmapnode *cmn, *ncmn; 68 69 cm->cm_havecache = false; 70 71 if (cm->cm_root == NULL) { 72 cmn = malloc(sizeof(*cmn)); 73 if (cmn == NULL) 74 return (false); 75 cmn->cmn_from = from; 76 cmn->cmn_to = to; 77 cmn->cmn_left = cmn->cmn_right = NULL; 78 cm->cm_root = cmn; 79 cm->cm_min = cm->cm_max = from; 80 return (true); 81 } 82 83 cmn = cm->cm_root = cmap_splay(cm->cm_root, from); 84 85 if (cmn->cmn_from == from) { 86 cmn->cmn_to = to; 87 return (true); 88 } 89 90 ncmn = malloc(sizeof(*ncmn)); 91 if (ncmn == NULL) 92 return (false); 93 ncmn->cmn_from = from; 94 ncmn->cmn_to = to; 95 if (from < cmn->cmn_from) { 96 ncmn->cmn_left = cmn->cmn_left; 97 ncmn->cmn_right = cmn; 98 cmn->cmn_left = NULL; 99 } else { 100 ncmn->cmn_right = cmn->cmn_right; 101 ncmn->cmn_left = cmn; 102 cmn->cmn_right = NULL; 103 } 104 if (from < cm->cm_min) 105 cm->cm_min = from; 106 if (from > cm->cm_max) 107 cm->cm_max = from; 108 cm->cm_root = ncmn; 109 110 return (true); 111} 112 113/* 114 * cmap_lookup_hard -- 115 * Look up the mapping for a character without using the cache. 116 */ 117wint_t 118cmap_lookup_hard(struct cmap *cm, wint_t ch) 119{ 120 121 if (cm->cm_root != NULL) { 122 cm->cm_root = cmap_splay(cm->cm_root, ch); 123 if (cm->cm_root->cmn_from == ch) 124 return (cm->cm_root->cmn_to); 125 } 126 return (cm->cm_def == CM_DEF_SELF ? ch : cm->cm_def); 127} 128 129/* 130 * cmap_cache -- 131 * Update the cache. 132 */ 133void 134cmap_cache(struct cmap *cm) 135{ 136 wint_t ch; 137 138 for (ch = 0; ch < CM_CACHE_SIZE; ch++) 139 cm->cm_cache[ch] = cmap_lookup_hard(cm, ch); 140 141 cm->cm_havecache = true; 142} 143 144/* 145 * cmap_default -- 146 * Change the value that characters without mappings map to, and 147 * return the old value. The special character value CM_MAP_SELF 148 * means characters map to themselves. 149 */ 150wint_t 151cmap_default(struct cmap *cm, wint_t def) 152{ 153 wint_t old; 154 155 old = cm->cm_def; 156 cm->cm_def = def; 157 cm->cm_havecache = false; 158 return (old); 159} 160 161static struct cmapnode * 162cmap_splay(struct cmapnode *t, wint_t ch) 163{ 164 struct cmapnode N, *l, *r, *y; 165 166 /* 167 * Based on public domain code from Sleator. 168 */ 169 170 assert(t != NULL); 171 172 N.cmn_left = N.cmn_right = NULL; 173 l = r = &N; 174 for (;;) { 175 if (ch < t->cmn_from) { 176 if (t->cmn_left != NULL && 177 ch < t->cmn_left->cmn_from) { 178 y = t->cmn_left; 179 t->cmn_left = y->cmn_right; 180 y->cmn_right = t; 181 t = y; 182 } 183 if (t->cmn_left == NULL) 184 break; 185 r->cmn_left = t; 186 r = t; 187 t = t->cmn_left; 188 } else if (ch > t->cmn_from) { 189 if (t->cmn_right != NULL && 190 ch > t->cmn_right->cmn_from) { 191 y = t->cmn_right; 192 t->cmn_right = y->cmn_left; 193 y->cmn_left = t; 194 t = y; 195 } 196 if (t->cmn_right == NULL) 197 break; 198 l->cmn_right = t; 199 l = t; 200 t = t->cmn_right; 201 } else 202 break; 203 } 204 l->cmn_right = t->cmn_left; 205 r->cmn_left = t->cmn_right; 206 t->cmn_left = N.cmn_right; 207 t->cmn_right = N.cmn_left; 208 return (t); 209} 210