2 /* Copyright (C) 1989, 1990, 1991, 1992, 2001, 2004
3 Free Software Foundation, Inc.
4 Written by James Clark (jjc@jclark.com)
6 This file is part of groff.
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
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
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. */
24 #include "dictionary.h"
26 // is `p' a good size for a hash table
28 static int is_good_size(unsigned int p)
30 const unsigned int SMALL = 10;
32 for (i = 2; i <= p/2; i++)
35 for (i = 0x100; i != 0; i <<= 8)
36 if (i % p <= SMALL || i % p > p - SMALL)
41 dictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5)
43 table = new association[n];
46 // see Knuth, Sorting and Searching, p518, Algorithm L
47 // we can't use double-hashing because we want a remove function
49 void *dictionary::lookup(symbol s, void *v)
52 for (i = int(s.hash() % size);
54 i == 0 ? i = size - 1: --i)
55 if (s == table[i].s) {
57 void *temp = table[i].v;
69 if ((double)used/(double)size >= threshold || used + 1 >= size) {
71 size = int(size*factor);
72 while (!is_good_size(size))
74 association *old_table = table;
75 table = new association[size];
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);
85 void *dictionary::lookup(const char *p)
87 symbol s(p, MUST_ALREADY_EXIST);
94 // see Knuth, Sorting and Searching, p527, Algorithm R
96 void *dictionary::remove(symbol s)
98 // this relies on the fact that we are using linear probing
100 for (i = int(s.hash() % size);
101 table[i].v != 0 && s != table[i].s;
102 i == 0 ? i = size - 1: --i)
104 void *p = table[i].v;
105 while (table[i].v != 0) {
115 r = int(table[i].s.hash() % size);
116 } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
124 dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
128 int dictionary_iterator::get(symbol *sp, void **vp)
130 for (; i < dict->size; i++)
131 if (dict->table[i].v) {
132 *sp = dict->table[i].s;
133 *vp = dict->table[i].v;
140 object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
145 object::object() : rcount(0)
153 void object::add_reference()
158 void object::remove_reference()
164 object_dictionary::object_dictionary(int n) : d(n)
168 object *object_dictionary::lookup(symbol nm)
170 return (object *)d.lookup(nm);
173 void object_dictionary::define(symbol nm, object *obj)
175 obj->add_reference();
176 obj = (object *)d.lookup(nm, obj);
178 obj->remove_reference();
181 void object_dictionary::rename(symbol oldnm, symbol newnm)
183 object *obj = (object *)d.remove(oldnm);
185 obj = (object *)d.lookup(newnm, obj);
187 obj->remove_reference();
191 void object_dictionary::remove(symbol nm)
193 object *obj = (object *)d.remove(nm);
195 obj->remove_reference();
198 // Return non-zero if oldnm was defined.
200 int object_dictionary::alias(symbol newnm, symbol oldnm)
202 object *obj = (object *)d.lookup(oldnm);
204 obj->add_reference();
205 obj = (object *)d.lookup(newnm, obj);
207 obj->remove_reference();