Line data    Source code

       1             : /* Copyright 1989-2020 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 "ptable.h"
      24             : #include "errarg.h"
      25             : #include "error.h"
      26             : 
      27    14198687 : unsigned long hash_string(const char *s)
      28             : {
      29             :   // This is the mythical Aho-Hopcroft-Ullman hash function.
      30             :   // TODO: Improve.  See http://www.haible.de/bruno/hashfunc.html
      31    14198687 :   assert(s != 0);
      32    14198687 :   unsigned long h = 0, g;
      33    67336737 :   while (*s != 0) {
      34    53138050 :     h <<= 4;
      35    53138050 :     h += *s++;
      36    53138050 :     if ((g = h & 0xf0000000) != 0) {
      37     2787459 :       h ^= g >> 24;
      38     2787459 :       h ^= g;
      39             :     }
      40             :   }
      41    14198687 :   return h;
      42             : }
      43             : 
      44             : static const unsigned table_sizes[] = {
      45             :   101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009,
      46             :   80021, 160001, 500009, 1000003, 2000003, 4000037, 8000009,
      47             :   16000057, 32000011, 64000031, 128000003, 0
      48             : };
      49             : 
      50       36359 : unsigned next_ptable_size(unsigned n)
      51             : {
      52             :   const unsigned *p;
      53      110605 :   for (p = table_sizes; *p <= n; p++)
      54       74246 :     if (*p == 0)
      55           0 :       fatal("cannot expand table");
      56       36359 :   return *p;
      57             : }
      58             : 
      59             : // Local Variables:
      60             : // fill-column: 72
      61             : // mode: C++
      62             : // End:
      63             : // vim: set cindent noexpandtab shiftwidth=2 textwidth=72: