1 // -*- C++ -*-
2 /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
3 Written by James Clark (jjc@jclark.com)
4
5 This file is part of groff.
6
7 groff is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 groff is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License along
18 with groff; see the file COPYING. If not, write to the Free Software
19 Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
20
21
22 #include "troff.h"
23 #include "symbol.h"
24 #include "dictionary.h"
25
26 // is `p' a good size for a hash table
27
is_good_size(int p)28 static int is_good_size(int p)
29 {
30 const int SMALL = 10;
31 for (unsigned i = 2; i <= p/2; i++)
32 if (p % i == 0)
33 return 0;
34 for (i = 0x100; i != 0; i <<= 8)
35 if (i % p <= SMALL || i % p > p - SMALL)
36 return 0;
37 return 1;
38 }
39
dictionary(int n)40 dictionary::dictionary(int n) : threshold(0.5), factor(1.5), used(0), size(n)
41 {
42 table = new association[n];
43 for (int i = 0; i < n; i++)
44 table[i].v = 0;
45 }
46
47 // see Knuth, Sorting and Searching, p518, Algorithm L
48 // we can't use double-hashing because we want a remove function
49
lookup(symbol s,void * v)50 void *dictionary::lookup(symbol s, void *v)
51 {
52 for (int 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
lookup(const char * p)85 void *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
remove(symbol s)96 void *dictionary::remove(symbol s)
97 {
98 // this relies on the fact that we are using linear probing
99 for (int i = int(s.hash() % size);
100 table[i].v != 0 && s != table[i].s;
101 i == 0 ? i = size - 1: --i)
102 ;
103 void *p = table[i].v;
104 while (table[i].v != 0) {
105 table[i].v = 0;
106 int j = i;
107 int r;
108 do {
109 --i;
110 if (i < 0)
111 i = size - 1;
112 if (table[i].v == 0)
113 break;
114 r = int(table[i].s.hash() % size);
115 } while ((i <= r && r < j) || (j < i && i <= r));
116 table[j] = table[i];
117 }
118 if (p != 0)
119 --used;
120 return p;
121 }
122
dictionary_iterator(dictionary & d)123 dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
124 {
125 }
126
get(symbol * sp,void ** vp)127 int dictionary_iterator::get(symbol *sp, void **vp)
128 {
129 for (; i < dict->size; i++)
130 if (dict->table[i].v) {
131 *sp = dict->table[i].s;
132 *vp = dict->table[i].v;
133 i++;
134 return 1;
135 }
136 return 0;
137 }
138
object_dictionary_iterator(object_dictionary & od)139 object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
140 : di(od.d)
141 {
142 }
143
object()144 object::object() : rcount(0)
145 {
146 }
147
~object()148 object::~object()
149 {
150 }
151
add_reference()152 void object::add_reference()
153 {
154 rcount += 1;
155 }
156
remove_reference()157 void object::remove_reference()
158 {
159 if (--rcount == 0)
160 delete this;
161 }
162
object_dictionary(int n)163 object_dictionary::object_dictionary(int n) : d(n)
164 {
165 }
166
lookup(symbol nm)167 object *object_dictionary::lookup(symbol nm)
168 {
169 return (object *)d.lookup(nm);
170 }
171
define(symbol nm,object * obj)172 void object_dictionary::define(symbol nm, object *obj)
173 {
174 obj->add_reference();
175 obj = (object *)d.lookup(nm, obj);
176 if (obj)
177 obj->remove_reference();
178 }
179
rename(symbol oldnm,symbol newnm)180 void object_dictionary::rename(symbol oldnm, symbol newnm)
181 {
182 object *obj = (object *)d.remove(oldnm);
183 if (obj) {
184 obj = (object *)d.lookup(newnm, obj);
185 if (obj)
186 obj->remove_reference();
187 }
188 }
189
remove(symbol nm)190 void object_dictionary::remove(symbol nm)
191 {
192 object *obj = (object *)d.remove(nm);
193 if (obj)
194 obj->remove_reference();
195 }
196
197 // Return non-zero if oldnm was defined.
198
alias(symbol newnm,symbol oldnm)199 int object_dictionary::alias(symbol newnm, symbol oldnm)
200 {
201 object *obj = (object *)d.lookup(oldnm);
202 if (obj) {
203 obj->add_reference();
204 obj = (object *)d.lookup(newnm, obj);
205 if (obj)
206 obj->remove_reference();
207 return 1;
208 }
209 return 0;
210 }
211
212