Line data    Source code

       1             : /* Copyright 1989-2024 Free Software Foundation, Inc.
       2             :      Written by James Clark (jjc@jclark.com)
       3             : 
       4             : This file is part of groff, the GNU roff typesetting system.
       5             : 
       6             : groff is free software; you can redistribute it and/or modify it under
       7             : the terms of the GNU General Public License as published by the Free
       8             : Software Foundation, either version 3 of the License, or
       9             : (at your option) any later version.
      10             : 
      11             : groff is distributed in the hope that it will be useful, but WITHOUT ANY
      12             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14             : for more details.
      15             : 
      16             : You should have received a copy of the GNU General Public License
      17             : along with this program.  If not, see <http://www.gnu.org/licenses/>. */
      18             : 
      19             : #ifdef HAVE_CONFIG_H
      20             : #include <config.h>
      21             : #endif
      22             : 
      23             : #include "troff.h"
      24             : #include "dictionary.h"
      25             : 
      26             : // is 'p' a good size for a hash table
      27             : 
      28      113181 : static bool is_good_size(unsigned int p)
      29             : {
      30      113181 :   const unsigned int SMALL = 10;
      31             :   unsigned int i;
      32     6477064 :   for (i = 2; i <= (p / 2); i++)
      33     6446415 :     if (p % i == 0)
      34       82532 :       return false;
      35       81195 :   for (i = 0x100; i != 0; i <<= 8)
      36       66407 :     if ((i % p) <= SMALL || (i % p) > (p - SMALL))
      37       15861 :       return false;
      38       14788 :   return true;
      39             : }
      40             : 
      41       19972 : dictionary::dictionary(int n) : size(n), used(0), threshold(0.5), factor(1.5)
      42             : {
      43     3958284 :   table = new association[n];
      44       19972 : }
      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    47145113 : void *dictionary::lookup(symbol s, void *v)
      50             : {
      51             :   int i;
      52    65239583 :   for (i = int(s.hash() % size);
      53    65239583 :        table[i].v != 0 /* nullptr */;
      54        7043 :        i == 0 ? i = size - 1: --i)
      55    56491408 :     if (s == table[i].s) {
      56    38396938 :       if (v != 0 /* nullptr */) {
      57       11497 :         void *temp = table[i].v;
      58       11497 :         table[i].v = v;
      59       11497 :         return temp;
      60             :       }
      61             :       else
      62    38385441 :         return table[i].v;
      63             :     }
      64     8748175 :   if (v == 0 /* nullptr */)
      65     2204815 :     return 0 /* nullptr */;
      66     6543360 :   ++used;
      67     6543360 :   table[i].v = v;
      68     6543360 :   table[i].s = s;
      69     6543360 :   if ((double(used) / double(size) >= threshold) || used + 1 >= size) {
      70       14788 :     int old_size = size;
      71       14788 :     size = int(size * factor);
      72      113181 :     while (!is_good_size(size))
      73       98393 :       ++size;
      74       14788 :     association *old_table = table;
      75    11848992 :     table = new association[size];
      76       14788 :     used = 0;
      77     7843499 :     for (i = 0; i < old_size; i++)
      78     7828711 :       if (old_table[i].v != 0 /* nullptr */)
      79     3921611 :         (void) lookup(old_table[i].s, old_table[i].v);
      80       14788 :     delete[] old_table;
      81             :   }
      82     6543360 :   return 0 /* nullptr */;
      83             : }
      84             : 
      85       38397 : void *dictionary::lookup(const char *p)
      86             : {
      87       38397 :   symbol s(p, MUST_ALREADY_EXIST);
      88       38397 :   if (s.is_null())
      89       37006 :     return 0 /* nullptr */;
      90             :   else
      91        1391 :     return lookup(s);
      92             : }
      93             : 
      94             : // see Knuth, Sorting and Searching, p527, Algorithm R
      95             : 
      96      289939 : void *dictionary::remove(symbol s)
      97             : {
      98             :   // this relies on the fact that we are using linear probing
      99             :   int i;
     100      773617 :   for (i = int(s.hash() % size);
     101      773617 :        table[i].v != 0 /* nullptr */ && s != table[i].s;
     102          98 :        i == 0 ? i = size - 1: --i)
     103             :     ;
     104      289939 :   void *p = table[i].v;
     105      556665 :   while (table[i].v != 0 /* nullptr */) {
     106      266726 :     table[i].v = 0 /* nullptr */;
     107      266726 :     int j = i;
     108             :     int r;
     109      214210 :     do {
     110      480936 :       --i;
     111      480936 :       if (i < 0)
     112         202 :         i = size - 1;
     113      480936 :       if (table[i].v == 0 /* nullptr */)
     114      262361 :         break;
     115      218575 :       r = int(table[i].s.hash() % size);
     116      218575 :     } while ((i <= r && r < j) || (r < j && j < i) || (j < i && i <= r));
     117      266726 :     table[j] = table[i];
     118             :   }
     119      289939 :   if (p != 0 /* nullptr */)
     120      262361 :     --used;
     121      289939 :   return p;
     122             : }
     123             : 
     124     1393135 : dictionary_iterator::dictionary_iterator(dictionary &d) : dict(&d), i(0)
     125             : {
     126     1393135 : }
     127             : 
     128   690097795 : bool dictionary_iterator::get(symbol *sp, void **vp)
     129             : {
     130   690097795 :   for (; i < dict->size; i++)
     131   688704660 :     if (dict->table[i].v) {
     132       46458 :       *sp = dict->table[i].s;
     133       46458 :       *vp = dict->table[i].v;
     134       46458 :       i++;
     135       46458 :       return true;
     136             :     }
     137     1393135 :   return false;
     138             : }
     139             : 
     140        1403 : object_dictionary_iterator::object_dictionary_iterator(object_dictionary &od)
     141        1403 : : di(od.d)
     142             : {
     143        1403 : }
     144             : 
     145    16280039 : object::object() : refcount(0)
     146             : {
     147    16280039 : }
     148             : 
     149    15114546 : object::~object()
     150             : {
     151    15114546 : }
     152             : 
     153     1093694 : void object::add_reference()
     154             : {
     155     1093694 :   refcount += 1;
     156     1093694 : }
     157             : 
     158      264255 : void object::remove_reference()
     159             : {
     160      264255 :   if (--refcount == 0)
     161      255120 :     delete this;
     162      264255 : }
     163             : 
     164        4260 : object_dictionary::object_dictionary(int n) : d(n)
     165             : {
     166        4260 : }
     167             : 
     168    31335625 : object *object_dictionary::lookup(symbol nm)
     169             : {
     170    31335625 :   return (object *)d.lookup(nm);
     171             : }
     172             : 
     173     1046318 : void object_dictionary::define(symbol nm, object *obj)
     174             : {
     175     1046318 :   obj->add_reference();
     176     1046318 :   obj = static_cast<object *>(d.lookup(nm, obj));
     177     1046318 :   if (obj)
     178         417 :     obj->remove_reference();
     179     1046318 : }
     180             : 
     181         722 : void object_dictionary::rename(symbol oldnm, symbol newnm)
     182             : {
     183         722 :   object *obj = static_cast<object *>(d.remove(oldnm));
     184         722 :   if (obj) {
     185         716 :     obj = (object *)d.lookup(newnm, obj);
     186         716 :     if (obj)
     187          89 :       obj->remove_reference();
     188             :   }
     189         722 : }
     190             : 
     191      286346 : void object_dictionary::remove(symbol nm)
     192             : {
     193      286346 :   object *obj = static_cast<object *>(d.remove(nm));
     194      286346 :   if (obj)
     195      258774 :     obj->remove_reference();
     196      286346 : }
     197             : 
     198             : // Return non-zero if oldnm was defined.
     199             : 
     200       47376 : bool object_dictionary::alias(symbol newnm, symbol oldnm)
     201             : {
     202       47376 :   object *obj = static_cast<object *>(d.lookup(oldnm));
     203       47376 :   if (obj) {
     204       47376 :     obj->add_reference();
     205       47376 :     obj = static_cast<object *>(d.lookup(newnm, obj));
     206       47376 :     if (obj)
     207        4975 :       obj->remove_reference();
     208       47376 :     return true;
     209             :   }
     210           0 :   return false;
     211             : }
     212             : 
     213             : // Local Variables:
     214             : // fill-column: 72
     215             : // mode: C++
     216             : // End:
     217             : // vim: set cindent noexpandtab shiftwidth=2 textwidth=72: