src/troff/dictionary.cpp

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