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