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 <assert.h> 33 #include <limits.h> 34 #include <stdbool.h> 35 #include <stdlib.h> 36 #include <wchar.h> 37 #include "cmap.h" 38 39 static struct cmapnode *cmap_splay(struct cmapnode *, wint_t); 40 41 /* 42 * cmap_alloc -- 43 * Allocate a character map. 44 */ 45 struct cmap * 46 cmap_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 */ 64 bool 65 cmap_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 */ 117 wint_t 118 cmap_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 */ 133 void 134 cmap_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 */ 150 wint_t 151 cmap_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 161 static struct cmapnode * 162 cmap_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