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 6This file is part of groff. 7 8groff is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13groff is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License along 19with groff; see the file COPYING. If not, write to the Free Software 20Foundation, 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 28static 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 41dictionary::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 49void *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 85void *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 96void *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 124dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0) 125{ 126} 127 128int 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 140object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od) 141: di(od.d) 142{ 143} 144 145object::object() : rcount(0) 146{ 147} 148 149object::~object() 150{ 151} 152 153void object::add_reference() 154{ 155 rcount += 1; 156} 157 158void object::remove_reference() 159{ 160 if (--rcount == 0) 161 delete this; 162} 163 164object_dictionary::object_dictionary(int n) : d(n) 165{ 166} 167 168object *object_dictionary::lookup(symbol nm) 169{ 170 return (object *)d.lookup(nm); 171} 172 173void 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 181void 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 191void 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 200int 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} 212