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