usr/src/cmd/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 <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 }