contrib/groff/src/roff/troff/dictionary.cpp

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