src/lib-roff/ptable.cpp

   1 /*@
   2  * Copyright (c) 2014 - 2017 Steffen (Daode) Nurpmeso <steffen@sdaoden.eu>.
   3  *
   4  * Copyright (C) 1989 - 1992, 2006 Free Software Foundation, Inc.
   5  *      Written by James Clark (jjc@jclark.com)
   6  *
   7  * This 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  * This 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, 51 Franklin St - Fifth Floor, Boston, MA 02110-1301, USA.
  20  */
  21
  22 #include "config.h"
  23 #include "lib.h"
  24
  25 #include "errarg.h"
  26 #include "error.h"
  27 #include "ptable.h"
  28
  29 unsigned long hash_string(const char *s) /* FIXME Torek's hash */
  30 {
  31   // This is the mythical Aho-Hopcroft-Ullman hash function.
  32   // TODO: Improve.  See http://www.haible.de/bruno/hashfunc.html
  33   assert(s != 0);
  34   unsigned long h = 0, g;
  35   while (*s != 0) {
  36     h <<= 4;
  37     h += *s++;
  38     if ((g = h & 0xf0000000) != 0) {
  39       h ^= g >> 24;
  40       h ^= g;
  41     }
  42   }
  43   return h;
  44 }
  45
  46 static const unsigned table_sizes[] = {
  47   101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009,
  48   80021, 160001, 500009, 1000003, 2000003, 4000037, 8000009,
  49   16000057, 32000011, 64000031, 128000003, 0
  50 };
  51
  52 unsigned next_ptable_size(unsigned n)
  53 {
  54   const unsigned *p;
  55   for (p = table_sizes; *p <= n; p++)
  56     if (*p == 0)
  57       fatal("cannot expand table");
  58   return *p;
  59 }
  60
  61 // s-it2-mode