usr.bin/tr/cmap.c

   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 }