1214501Srpaulo// -*- C++ -*- 2214501Srpaulo/* Copyright (C) 1989, 1990, 1991, 1992, 2001, 2004 3214501Srpaulo Free Software Foundation, Inc. 4214501Srpaulo Written by James Clark (jjc@jclark.com) 5252726Srpaulo 6252726SrpauloThis file is part of groff. 7214501Srpaulo 8214501Srpaulogroff is free software; you can redistribute it and/or modify it under 9214501Srpaulothe terms of the GNU General Public License as published by the Free 10214501SrpauloSoftware Foundation; either version 2, or (at your option) any later 11214501Srpauloversion. 12214501Srpaulo 13214501Srpaulogroff is distributed in the hope that it will be useful, but WITHOUT ANY 14214501SrpauloWARRANTY; without even the implied warranty of MERCHANTABILITY or 15214501SrpauloFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16214501Srpaulofor more details. 17214501Srpaulo 18214501SrpauloYou should have received a copy of the GNU General Public License along 19214501Srpaulowith groff; see the file COPYING. If not, write to the Free Software 20214501SrpauloFoundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */ 21252726Srpaulo 22252726Srpaulo 23252726Srpaulo#include "troff.h" 24252726Srpaulo#include "dictionary.h" 25252726Srpaulo 26252726Srpaulo// is `p' a good size for a hash table 27252726Srpaulo 28252726Srpaulostatic int is_good_size(unsigned int p) 29252726Srpaulo{ 30252726Srpaulo const unsigned int SMALL = 10; 31252726Srpaulo unsigned int i; 32252726Srpaulo for (i = 2; i <= p/2; i++) 33214501Srpaulo if (p % i == 0) 34214501Srpaulo return 0; 35214501Srpaulo for (i = 0x100; i != 0; i <<= 8) 36214501Srpaulo if (i % p <= SMALL || i % p > p - SMALL) 37214501Srpaulo return 0; 38214501Srpaulo return 1; 39214501Srpaulo} 40214501Srpaulo 41214501Srpaulodictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5) 42214501Srpaulo{ 43214501Srpaulo table = new association[n]; 44214501Srpaulo} 45214501Srpaulo 46214501Srpaulo// see Knuth, Sorting and Searching, p518, Algorithm L 47214501Srpaulo// we can't use double-hashing because we want a remove function 48252726Srpaulo 49252726Srpaulovoid *dictionary::lookup(symbol s, void *v) 50252726Srpaulo{ 51252726Srpaulo int i; 52252726Srpaulo for (i = int(s.hash() % size); 53252726Srpaulo table[i].v != 0; 54252726Srpaulo i == 0 ? i = size - 1: --i) 55214501Srpaulo if (s == table[i].s) { 56214501Srpaulo if (v != 0) { 57214501Srpaulo void *temp = table[i].v; 58214501Srpaulo table[i].v = v; 59214501Srpaulo return temp; 60214501Srpaulo } 61214501Srpaulo else 62214501Srpaulo return table[i].v; 63214501Srpaulo } 64214501Srpaulo if (v == 0) 65214501Srpaulo return 0; 66214501Srpaulo ++used; 67214501Srpaulo table[i].v = v; 68214501Srpaulo table[i].s = s; 69214501Srpaulo if ((double)used/(double)size >= threshold || used + 1 >= size) { 70214501Srpaulo int old_size = size; 71214501Srpaulo size = int(size*factor); 72214501Srpaulo while (!is_good_size(size)) 73214501Srpaulo ++size; 74214501Srpaulo association *old_table = table; 75214501Srpaulo table = new association[size]; 76214501Srpaulo used = 0; 77214501Srpaulo for (i = 0; i < old_size; i++) 78214501Srpaulo if (old_table[i].v != 0) 79214501Srpaulo (void)lookup(old_table[i].s, old_table[i].v); 80214501Srpaulo a_delete old_table; 81214501Srpaulo } 82214501Srpaulo return 0; 83214501Srpaulo} 84214501Srpaulo 85214501Srpaulovoid *dictionary::lookup(const char *p) 86214501Srpaulo{ 87214501Srpaulo symbol s(p, MUST_ALREADY_EXIST); 88214501Srpaulo if (s.is_null()) 89214501Srpaulo return 0; 90214501Srpaulo else 91214501Srpaulo return lookup(s); 92214501Srpaulo} 93214501Srpaulo 94214501Srpaulo// see Knuth, Sorting and Searching, p527, Algorithm R 95214501Srpaulo 96214501Srpaulovoid *dictionary::remove(symbol s) 97214501Srpaulo{ 98214501Srpaulo // this relies on the fact that we are using linear probing 99214501Srpaulo int i; 100214501Srpaulo for (i = int(s.hash() % size); 101214501Srpaulo table[i].v != 0 && s != table[i].s; 102214501Srpaulo i == 0 ? i = size - 1: --i) 103214501Srpaulo ; 104214501Srpaulo void *p = table[i].v; 105214501Srpaulo while (table[i].v != 0) { 106214501Srpaulo table[i].v = 0; 107214501Srpaulo int j = i; 108214501Srpaulo int r; 109214501Srpaulo do { 110214501Srpaulo --i; 111214501Srpaulo if (i < 0) 112214501Srpaulo i = size - 1; 113214501Srpaulo if (table[i].v == 0) 114214501Srpaulo break; 115214501Srpaulo r = int(table[i].s.hash() % size); 116214501Srpaulo } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r)); 117214501Srpaulo table[j] = table[i]; 118214501Srpaulo } 119214501Srpaulo if (p != 0) 120214501Srpaulo --used; 121214501Srpaulo return p; 122214501Srpaulo} 123214501Srpaulo 124214501Srpaulodictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0) 125214501Srpaulo{ 126214501Srpaulo} 127214501Srpaulo 128214501Srpauloint dictionary_iterator::get(symbol *sp, void **vp) 129214501Srpaulo{ 130214501Srpaulo for (; i < dict->size; i++) 131214501Srpaulo if (dict->table[i].v) { 132214501Srpaulo *sp = dict->table[i].s; 133214501Srpaulo *vp = dict->table[i].v; 134214501Srpaulo i++; 135214501Srpaulo return 1; 136214501Srpaulo } 137214501Srpaulo return 0; 138214501Srpaulo} 139214501Srpaulo 140214501Srpauloobject_dictionary_iterator::object_dictionary_iterator(object_dictionary &od) 141252726Srpaulo: di(od.d) 142252726Srpaulo{ 143214501Srpaulo} 144214501Srpaulo 145214501Srpauloobject::object() : rcount(0) 146214501Srpaulo{ 147214501Srpaulo} 148214501Srpaulo 149214501Srpauloobject::~object() 150214501Srpaulo{ 151214501Srpaulo} 152214501Srpaulo 153214501Srpaulovoid object::add_reference() 154214501Srpaulo{ 155214501Srpaulo rcount += 1; 156214501Srpaulo} 157214501Srpaulo 158214501Srpaulovoid object::remove_reference() 159214501Srpaulo{ 160214501Srpaulo if (--rcount == 0) 161214501Srpaulo delete this; 162214501Srpaulo} 163214501Srpaulo 164214501Srpauloobject_dictionary::object_dictionary(int n) : d(n) 165214501Srpaulo{ 166214501Srpaulo} 167214501Srpaulo 168214501Srpauloobject *object_dictionary::lookup(symbol nm) 169214501Srpaulo{ 170214501Srpaulo return (object *)d.lookup(nm); 171252726Srpaulo} 172214501Srpaulo 173252726Srpaulovoid object_dictionary::define(symbol nm, object *obj) 174252726Srpaulo{ 175252726Srpaulo obj->add_reference(); 176252726Srpaulo obj = (object *)d.lookup(nm, obj); 177252726Srpaulo if (obj) 178252726Srpaulo obj->remove_reference(); 179252726Srpaulo} 180214501Srpaulo 181214501Srpaulovoid object_dictionary::rename(symbol oldnm, symbol newnm) 182214501Srpaulo{ 183214501Srpaulo object *obj = (object *)d.remove(oldnm); 184214501Srpaulo if (obj) { 185214501Srpaulo obj = (object *)d.lookup(newnm, obj); 186214501Srpaulo if (obj) 187252726Srpaulo obj->remove_reference(); 188214501Srpaulo } 189214501Srpaulo} 190214501Srpaulo 191214501Srpaulovoid object_dictionary::remove(symbol nm) 192214501Srpaulo{ 193214501Srpaulo object *obj = (object *)d.remove(nm); 194214501Srpaulo if (obj) 195252726Srpaulo obj->remove_reference(); 196214501Srpaulo} 197214501Srpaulo 198214501Srpaulo// Return non-zero if oldnm was defined. 199214501Srpaulo 200214501Srpauloint object_dictionary::alias(symbol newnm, symbol oldnm) 201214501Srpaulo{ 202214501Srpaulo object *obj = (object *)d.lookup(oldnm); 203214501Srpaulo if (obj) { 204214501Srpaulo obj->add_reference(); 205214501Srpaulo obj = (object *)d.lookup(newnm, obj); 206214501Srpaulo if (obj) 207214501Srpaulo obj->remove_reference(); 208214501Srpaulo return 1; 209214501Srpaulo } 210214501Srpaulo return 0; 211214501Srpaulo} 212214501Srpaulo