home *** CD-ROM | disk | FTP | other *** search
/ Aminet 10 / aminetcdnumber101996.iso / Aminet / util / gnu / groff_src.lha / groff-1.10src / troff / dictionary.cc < prev    next >
C/C++ Source or Header  |  1995-06-22  |  5KB  |  213 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  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 2, 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 COPYING.  If not, write to the Free Software
  19. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
  20.  
  21.  
  22. #include "troff.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.   unsigned 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.  
  41. dictionary::dictionary(int n) : threshold(0.5), factor(1.5), used(0), size(n)
  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.  
  49. void *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.  
  85. void *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.   
  96. void *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.  
  124. dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
  125. {
  126. }
  127.  
  128. int 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.  
  140. object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
  141.      : di(od.d)
  142. {
  143. }
  144.  
  145. object::object() : rcount(0)
  146. {
  147. }
  148.  
  149. object::~object()
  150. {
  151. }
  152.  
  153. void object::add_reference()
  154. {
  155.   rcount += 1;
  156. }
  157.  
  158. void object::remove_reference()
  159. {
  160.   if (--rcount == 0)
  161.     delete this;
  162. }
  163.  
  164. object_dictionary::object_dictionary(int n) : d(n)
  165. {
  166. }
  167.  
  168. object *object_dictionary::lookup(symbol nm)
  169. {
  170.   return (object *)d.lookup(nm);
  171. }
  172.  
  173. void 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.  
  181. void 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.  
  191. void 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.  
  200. int 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.  
  213.