1114402Sru// -*- C++ -*- 2151497Sru/* Copyright (C) 1989, 1990, 1991, 1992, 2001, 2004 3151497Sru Free Software Foundation, Inc. 4114402Sru Written by James Clark (jjc@jclark.com) 5114402Sru 6114402SruThis file is part of groff. 7114402Sru 8114402Srugroff is free software; you can redistribute it and/or modify it under 9114402Sruthe terms of the GNU General Public License as published by the Free 10114402SruSoftware Foundation; either version 2, or (at your option) any later 11114402Sruversion. 12114402Sru 13114402Srugroff is distributed in the hope that it will be useful, but WITHOUT ANY 14114402SruWARRANTY; without even the implied warranty of MERCHANTABILITY or 15114402SruFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16114402Srufor more details. 17114402Sru 18114402SruYou should have received a copy of the GNU General Public License along 19114402Sruwith groff; see the file COPYING. If not, write to the Free Software 20151497SruFoundation, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA. */ 21114402Sru 22114402Sru 23114402Sru#include "troff.h" 24114402Sru#include "dictionary.h" 25114402Sru 26114402Sru// is `p' a good size for a hash table 27114402Sru 28114402Srustatic int is_good_size(unsigned int p) 29114402Sru{ 30114402Sru const unsigned int SMALL = 10; 31114402Sru unsigned int i; 32114402Sru for (i = 2; i <= p/2; i++) 33114402Sru if (p % i == 0) 34114402Sru return 0; 35114402Sru for (i = 0x100; i != 0; i <<= 8) 36114402Sru if (i % p <= SMALL || i % p > p - SMALL) 37114402Sru return 0; 38114402Sru return 1; 39114402Sru} 40114402Sru 41114402Srudictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5) 42114402Sru{ 43114402Sru table = new association[n]; 44114402Sru} 45114402Sru 46114402Sru// see Knuth, Sorting and Searching, p518, Algorithm L 47114402Sru// we can't use double-hashing because we want a remove function 48114402Sru 49114402Sruvoid *dictionary::lookup(symbol s, void *v) 50114402Sru{ 51114402Sru int i; 52114402Sru for (i = int(s.hash() % size); 53114402Sru table[i].v != 0; 54114402Sru i == 0 ? i = size - 1: --i) 55114402Sru if (s == table[i].s) { 56114402Sru if (v != 0) { 57114402Sru void *temp = table[i].v; 58114402Sru table[i].v = v; 59114402Sru return temp; 60114402Sru } 61114402Sru else 62114402Sru return table[i].v; 63114402Sru } 64114402Sru if (v == 0) 65114402Sru return 0; 66114402Sru ++used; 67114402Sru table[i].v = v; 68114402Sru table[i].s = s; 69114402Sru if ((double)used/(double)size >= threshold || used + 1 >= size) { 70114402Sru int old_size = size; 71114402Sru size = int(size*factor); 72114402Sru while (!is_good_size(size)) 73114402Sru ++size; 74114402Sru association *old_table = table; 75114402Sru table = new association[size]; 76114402Sru used = 0; 77114402Sru for (i = 0; i < old_size; i++) 78114402Sru if (old_table[i].v != 0) 79114402Sru (void)lookup(old_table[i].s, old_table[i].v); 80114402Sru a_delete old_table; 81114402Sru } 82114402Sru return 0; 83114402Sru} 84114402Sru 85114402Sruvoid *dictionary::lookup(const char *p) 86114402Sru{ 87114402Sru symbol s(p, MUST_ALREADY_EXIST); 88114402Sru if (s.is_null()) 89114402Sru return 0; 90114402Sru else 91114402Sru return lookup(s); 92114402Sru} 93114402Sru 94114402Sru// see Knuth, Sorting and Searching, p527, Algorithm R 95114402Sru 96114402Sruvoid *dictionary::remove(symbol s) 97114402Sru{ 98114402Sru // this relies on the fact that we are using linear probing 99114402Sru int i; 100114402Sru for (i = int(s.hash() % size); 101114402Sru table[i].v != 0 && s != table[i].s; 102114402Sru i == 0 ? i = size - 1: --i) 103114402Sru ; 104114402Sru void *p = table[i].v; 105114402Sru while (table[i].v != 0) { 106114402Sru table[i].v = 0; 107114402Sru int j = i; 108114402Sru int r; 109114402Sru do { 110114402Sru --i; 111114402Sru if (i < 0) 112114402Sru i = size - 1; 113114402Sru if (table[i].v == 0) 114114402Sru break; 115114402Sru r = int(table[i].s.hash() % size); 116114402Sru } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r)); 117114402Sru table[j] = table[i]; 118114402Sru } 119114402Sru if (p != 0) 120114402Sru --used; 121114402Sru return p; 122114402Sru} 123114402Sru 124114402Srudictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0) 125114402Sru{ 126114402Sru} 127114402Sru 128114402Sruint dictionary_iterator::get(symbol *sp, void **vp) 129114402Sru{ 130114402Sru for (; i < dict->size; i++) 131114402Sru if (dict->table[i].v) { 132114402Sru *sp = dict->table[i].s; 133114402Sru *vp = dict->table[i].v; 134114402Sru i++; 135114402Sru return 1; 136114402Sru } 137114402Sru return 0; 138114402Sru} 139114402Sru 140114402Sruobject_dictionary_iterator::object_dictionary_iterator(object_dictionary &od) 141114402Sru: di(od.d) 142114402Sru{ 143114402Sru} 144114402Sru 145114402Sruobject::object() : rcount(0) 146114402Sru{ 147114402Sru} 148114402Sru 149114402Sruobject::~object() 150114402Sru{ 151114402Sru} 152114402Sru 153114402Sruvoid object::add_reference() 154114402Sru{ 155114402Sru rcount += 1; 156114402Sru} 157114402Sru 158114402Sruvoid object::remove_reference() 159114402Sru{ 160114402Sru if (--rcount == 0) 161114402Sru delete this; 162114402Sru} 163114402Sru 164114402Sruobject_dictionary::object_dictionary(int n) : d(n) 165114402Sru{ 166114402Sru} 167114402Sru 168114402Sruobject *object_dictionary::lookup(symbol nm) 169114402Sru{ 170114402Sru return (object *)d.lookup(nm); 171114402Sru} 172114402Sru 173114402Sruvoid object_dictionary::define(symbol nm, object *obj) 174114402Sru{ 175114402Sru obj->add_reference(); 176114402Sru obj = (object *)d.lookup(nm, obj); 177114402Sru if (obj) 178114402Sru obj->remove_reference(); 179114402Sru} 180114402Sru 181114402Sruvoid object_dictionary::rename(symbol oldnm, symbol newnm) 182114402Sru{ 183114402Sru object *obj = (object *)d.remove(oldnm); 184114402Sru if (obj) { 185114402Sru obj = (object *)d.lookup(newnm, obj); 186114402Sru if (obj) 187114402Sru obj->remove_reference(); 188114402Sru } 189114402Sru} 190114402Sru 191114402Sruvoid object_dictionary::remove(symbol nm) 192114402Sru{ 193114402Sru object *obj = (object *)d.remove(nm); 194114402Sru if (obj) 195114402Sru obj->remove_reference(); 196114402Sru} 197114402Sru 198114402Sru// Return non-zero if oldnm was defined. 199114402Sru 200114402Sruint object_dictionary::alias(symbol newnm, symbol oldnm) 201114402Sru{ 202114402Sru object *obj = (object *)d.lookup(oldnm); 203114402Sru if (obj) { 204114402Sru obj->add_reference(); 205114402Sru obj = (object *)d.lookup(newnm, obj); 206114402Sru if (obj) 207114402Sru obj->remove_reference(); 208114402Sru return 1; 209114402Sru } 210114402Sru return 0; 211114402Sru} 212