home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / usr.bin / groff / troff / dictionary.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-30  |  4.3 KB  |  211 lines

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