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 8 This file is part of groff. 9 10 groff is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free 12 Software Foundation; either version 2, or (at your option) any later 13 version. 14 15 groff is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or 17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18 for more details. 19 20 You should have received a copy of the GNU General Public License along 21 with groff; see the file COPYING. If not, write to the Free Software 22 Foundation, 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 30 static 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 43 dictionary::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 51 void *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 87 void *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 98 void *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 126 dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0) 127 { 128 } 129 130 int 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 142 object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od) 143 : di(od.d) 144 { 145 } 146 147 object::object() : rcount(0) 148 { 149 } 150 151 object::~object() 152 { 153 } 154 155 void object::add_reference() 156 { 157 rcount += 1; 158 } 159 160 void object::remove_reference() 161 { 162 if (--rcount == 0) 163 delete this; 164 } 165 166 object_dictionary::object_dictionary(int n) : d(n) 167 { 168 } 169 170 object *object_dictionary::lookup(symbol nm) 171 { 172 return (object *)d.lookup(nm); 173 } 174 175 void 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 183 void 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 193 void 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 202 int 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