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