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