src/roff/troff/dictionary.cpp

   1 // -*- C++ -*-
   2 /* Copyright (C) 1989, 1990, 1991, 1992, 2001, 2004
   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 2, or (at your option) any later
  11 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 along
  19 with groff; see the file COPYING.  If not, write to the Free Software
  20 Foundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */
  21
  22
  23 #include "troff.h"
  24 #include "dictionary.h"
  25
  26 // is `p' a good size for a hash table
  27
  28 static int is_good_size(unsigned int p)
  29 {
  30   const unsigned int SMALL = 10;
  31   unsigned int i;
  32   for (i = 2; i <= p/2; i++)
  33     if (p % i == 0)
  34       return 0;
  35   for (i = 0x100; i != 0; i <<= 8)
  36     if (i % p <= SMALL || i % p > p - SMALL)
  37       return 0;
  38   return 1;
  39 }
  40
  41 dictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5)
  42 {
  43   table = new association[n];
  44 }
  45
  46 // see Knuth, Sorting and Searching, p518, Algorithm L
  47 // we can't use double-hashing because we want a remove function
  48
  49 void *dictionary::lookup(symbol s, void *v)
  50 {
  51   int i;
  52   for (i = int(s.hash() % size);
  53        table[i].v != 0;
  54        i == 0 ? i = size - 1: --i)
  55     if (s == table[i].s) {
  56       if (v != 0) {
  57         void *temp = table[i].v;
  58         table[i].v = v;
  59         return temp;
  60       }
  61       else
  62         return table[i].v;
  63     }
  64   if (v == 0)
  65     return 0;
  66   ++used;
  67   table[i].v = v;
  68   table[i].s = s;
  69   if ((double)used/(double)size >= threshold || used + 1 >= size) {
  70     int old_size = size;
  71     size = int(size*factor);
  72     while (!is_good_size(size))
  73       ++size;
  74     association *old_table = table;
  75     table = new association[size];
  76     used = 0;
  77     for (i = 0; i < old_size; i++)
  78       if (old_table[i].v != 0)
  79         (void)lookup(old_table[i].s, old_table[i].v);
  80     a_delete old_table;
  81   }
  82   return 0;
  83 }
  84
  85 void *dictionary::lookup(const char *p)
  86 {
  87   symbol s(p, MUST_ALREADY_EXIST);
  88   if (s.is_null())
  89     return 0;
  90   else
  91     return lookup(s);
  92 }
  93
  94 // see Knuth, Sorting and Searching, p527, Algorithm R
  95
  96 void *dictionary::remove(symbol s)
  97 {
  98   // this relies on the fact that we are using linear probing
  99   int i;
 100   for (i = int(s.hash() % size);
 101        table[i].v != 0 && s != table[i].s;
 102        i == 0 ? i = size - 1: --i)
 103     ;
 104   void *p = table[i].v;
 105   while (table[i].v != 0) {
 106     table[i].v = 0;
 107     int j = i;
 108     int r;
 109     do {
 110       --i;
 111       if (i < 0)
 112         i = size - 1;
 113       if (table[i].v == 0)
 114         break;
 115       r = int(table[i].s.hash() % size);
 116     } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
 117     table[j] = table[i];
 118   }
 119   if (p != 0)
 120     --used;
 121   return p;
 122 }
 123
 124 dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
 125 {
 126 }
 127
 128 int dictionary_iterator::get(symbol *sp, void **vp)
 129 {
 130   for (; i < dict->size; i++)
 131     if (dict->table[i].v) {
 132       *sp = dict->table[i].s;
 133       *vp = dict->table[i].v;
 134       i++;
 135       return 1;
 136     }
 137   return 0;
 138 }
 139
 140 object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
 141 : di(od.d)
 142 {
 143 }
 144
 145 object::object() : rcount(0)
 146 {
 147 }
 148
 149 object::~object()
 150 {
 151 }
 152
 153 void object::add_reference()
 154 {
 155   rcount += 1;
 156 }
 157
 158 void object::remove_reference()
 159 {
 160   if (--rcount == 0)
 161     delete this;
 162 }
 163
 164 object_dictionary::object_dictionary(int n) : d(n)
 165 {
 166 }
 167
 168 object *object_dictionary::lookup(symbol nm)
 169 {
 170   return (object *)d.lookup(nm);
 171 }
 172
 173 void object_dictionary::define(symbol nm, object *obj)
 174 {
 175   obj->add_reference();
 176   obj = (object *)d.lookup(nm, obj);
 177   if (obj)
 178     obj->remove_reference();
 179 }
 180
 181 void object_dictionary::rename(symbol oldnm, symbol newnm)
 182 {
 183   object *obj = (object *)d.remove(oldnm);
 184   if (obj) {
 185     obj = (object *)d.lookup(newnm, obj);
 186     if (obj)
 187       obj->remove_reference();
 188   }
 189 }
 190
 191 void object_dictionary::remove(symbol nm)
 192 {
 193   object *obj = (object *)d.remove(nm);
 194   if (obj)
 195     obj->remove_reference();
 196 }
 197
 198 // Return non-zero if oldnm was defined.
 199
 200 int object_dictionary::alias(symbol newnm, symbol oldnm)
 201 {
 202   object *obj = (object *)d.lookup(oldnm);
 203   if (obj) {
 204     obj->add_reference();
 205     obj = (object *)d.lookup(newnm, obj);
 206     if (obj)
 207       obj->remove_reference();
 208     return 1;
 209   }
 210   return 0;
 211 }