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