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  * $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 }