src/roff/troff/dictionary.cpp

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989-2014  Free Software Foundation, Inc.
   3      Written by James Clark (jjc@jclark.com)
   4
   5 This file is part of groff.
   6
   7 groff is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation, either version 3 of the License, or
  10 (at your option) any later version.
  11
  12 groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
  19
  20
  21 #include "troff.h"
  22 #include "dictionary.h"
  23
  24 // is `p' a good size for a hash table
  25
  26 static int is_good_size(unsigned int p)
  27 {
  28   const unsigned int SMALL = 10;
  29   unsigned int i;
  30   for (i = 2; i <= p/2; i++)
  31     if (p % i == 0)
  32       return 0;
  33   for (i = 0x100; i != 0; i <<= 8)
  34     if (i % p <= SMALL || i % p > p - SMALL)
  35       return 0;
  36   return 1;
  37 }
  38
  39 dictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5)
  40 {
  41   table = new association[n];
  42 }
  43
  44 // see Knuth, Sorting and Searching, p518, Algorithm L
  45 // we can't use double-hashing because we want a remove function
  46
  47 void *dictionary::lookup(symbol s, void *v)
  48 {
  49   int i;
  50   for (i = int(s.hash() % size);
  51        table[i].v != 0;
  52        i == 0 ? i = size - 1: --i)
  53     if (s == table[i].s) {
  54       if (v != 0) {
  55         void *temp = table[i].v;
  56         table[i].v = v;
  57         return temp;
  58       }
  59       else
  60         return table[i].v;
  61     }
  62   if (v == 0)
  63     return 0;
  64   ++used;
  65   table[i].v = v;
  66   table[i].s = s;
  67   if ((double)used/(double)size >= threshold || used + 1 >= size) {
  68     int old_size = size;
  69     size = int(size*factor);
  70     while (!is_good_size(size))
  71       ++size;
  72     association *old_table = table;
  73     table = new association[size];
  74     used = 0;
  75     for (i = 0; i < old_size; i++)
  76       if (old_table[i].v != 0)
  77         (void)lookup(old_table[i].s, old_table[i].v);
  78     a_delete old_table;
  79   }
  80   return 0;
  81 }
  82
  83 void *dictionary::lookup(const char *p)
  84 {
  85   symbol s(p, MUST_ALREADY_EXIST);
  86   if (s.is_null())
  87     return 0;
  88   else
  89     return lookup(s);
  90 }
  91
  92 // see Knuth, Sorting and Searching, p527, Algorithm R
  93
  94 void *dictionary::remove(symbol s)
  95 {
  96   // this relies on the fact that we are using linear probing
  97   int i;
  98   for (i = int(s.hash() % size);
  99        table[i].v != 0 && s != table[i].s;
 100        i == 0 ? i = size - 1: --i)
 101     ;
 102   void *p = table[i].v;
 103   while (table[i].v != 0) {
 104     table[i].v = 0;
 105     int j = i;
 106     int r;
 107     do {
 108       --i;
 109       if (i < 0)
 110         i = size - 1;
 111       if (table[i].v == 0)
 112         break;
 113       r = int(table[i].s.hash() % size);
 114     } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
 115     table[j] = table[i];
 116   }
 117   if (p != 0)
 118     --used;
 119   return p;
 120 }
 121
 122 dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
 123 {
 124 }
 125
 126 int dictionary_iterator::get(symbol *sp, void **vp)
 127 {
 128   for (; i < dict->size; i++)
 129     if (dict->table[i].v) {
 130       *sp = dict->table[i].s;
 131       *vp = dict->table[i].v;
 132       i++;
 133       return 1;
 134     }
 135   return 0;
 136 }
 137
 138 object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
 139 : di(od.d)
 140 {
 141 }
 142
 143 object::object() : rcount(0)
 144 {
 145 }
 146
 147 object::~object()
 148 {
 149 }
 150
 151 void object::add_reference()
 152 {
 153   rcount += 1;
 154 }
 155
 156 void object::remove_reference()
 157 {
 158   if (--rcount == 0)
 159     delete this;
 160 }
 161
 162 object_dictionary::object_dictionary(int n) : d(n)
 163 {
 164 }
 165
 166 object *object_dictionary::lookup(symbol nm)
 167 {
 168   return (object *)d.lookup(nm);
 169 }
 170
 171 void object_dictionary::define(symbol nm, object *obj)
 172 {
 173   obj->add_reference();
 174   obj = (object *)d.lookup(nm, obj);
 175   if (obj)
 176     obj->remove_reference();
 177 }
 178
 179 void object_dictionary::rename(symbol oldnm, symbol newnm)
 180 {
 181   object *obj = (object *)d.remove(oldnm);
 182   if (obj) {
 183     obj = (object *)d.lookup(newnm, obj);
 184     if (obj)
 185       obj->remove_reference();
 186   }
 187 }
 188
 189 void object_dictionary::remove(symbol nm)
 190 {
 191   object *obj = (object *)d.remove(nm);
 192   if (obj)
 193     obj->remove_reference();
 194 }
 195
 196 // Return non-zero if oldnm was defined.
 197
 198 int object_dictionary::alias(symbol newnm, symbol oldnm)
 199 {
 200   object *obj = (object *)d.lookup(oldnm);
 201   if (obj) {
 202     obj->add_reference();
 203     obj = (object *)d.lookup(newnm, obj);
 204     if (obj)
 205       obj->remove_reference();
 206     return 1;
 207   }
 208   return 0;
 209 }