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