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