usr/src/cmd/spell/hash.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License, Version 1.0 only
   6  * (the "License").  You may not use this file except in compliance
   7  * with the License.
   8  *
   9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  10  * or http://www.opensolaris.org/os/licensing.
  11  * See the License for the specific language governing permissions
  12  * and limitations under the License.
  13  *
  14  * When distributing Covered Code, include this CDDL HEADER in each
  15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  16  * If applicable, add the following below this CDDL HEADER, with the
  17  * fields enclosed by brackets "[]" replaced with your own identifying
  18  * information: Portions Copyright [yyyy] [name of copyright owner]
  19  *
  20  * CDDL HEADER END
  21  */
  22 /*
  23  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
  24  * Use is subject to license terms.
  25  */
  26
  27 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  28 /*        All Rights Reserved   */
  29
  30 #pragma ident   "%Z%%M% %I%     %E% SMI"
  31
  32
  33 #include <stdlib.h>
  34 #include "hash.h"
  35
  36 #define LOCHWIDTH 3
  37 #define HICHWIDTH 3
  38 #define CHARWIDTH (LOCHWIDTH+HICHWIDTH)
  39 #define LOCHMASK ((1<<LOCHWIDTH)-1)
  40
  41 /*
  42  * if HASHWIDTH + CHARWIDTH < bitsizeof(long)
  43  * one could make LOCHWIDTH=6 and HICHWIDTH=0
  44  * and simplify accordingly; the hanky-panky
  45  * is to avoid overflow in long multiplication
  46  */
  47 #define NC 30
  48
  49 static long hashsize = HASHSIZE;
  50 static long pow2[NC*2];
  51
  52 static signed char hashtab[] = {
  53 -1,     -1,     -1,     -1,     -1,     -1,     0,      31,     /*  &' */
  54 -1,     -1,     -1,     -1,     68,     -1,     65,     -1,
  55 2,      25,     20,     35,     54,     61,     40,     39,     /* 0-7 */
  56 42,     33,     64,     67,     -1,     -1,     -1,     66,
  57 -1,     60,     43,     30,     5,      16,     47,     18,     /* A-G */
  58 41,     36,     51,     6,      13,     56,     55,     58,
  59 49,     12,     59,     46,     21,     32,     63,     34,
  60 57,     52,     3,      -1,     -1,     -1,     -1,     -1,
  61 -1,     22,     29,     8,      7,      10,     1,      28,     /* a-g */
  62 11,     62,     37,     48,     15,     50,     9,      4,
  63 19,     38,     45,     24,     23,     26,     17,     44,
  64 27,     14,     53,     -1,     -1,     -1,     -1,     -1
  65 };
  66
  67
  68 unsigned long
  69 hash(char *s)
  70 {
  71         int c;
  72         long *lp;
  73         unsigned long h = 0;
  74         for (lp = pow2; (c = *s++) != 0; ) {
  75                 c = hashtab[c-' '];
  76                 h += (c&LOCHMASK) * *lp++;
  77                 h += (c>>LOCHWIDTH) * *lp++;
  78                 h %= hashsize;
  79         }
  80         return (h);
  81 }
  82
  83 void
  84 hashinit(void)
  85 {
  86 #if ((1L << (HASHWIDTH+LOCHWIDTH) == 0) || (1L << (HASHWIDTH+HICHWIDTH) == 0))
  87         abort();        /* overflow is imminent */
  88 #else
  89         int i;
  90
  91         pow2[0] = 1L<<(HASHWIDTH-CHARWIDTH-2);
  92         for (i = 0; i < 2*NC-3; i += 2) {
  93                 pow2[i+1] = (pow2[i]<<LOCHWIDTH) % hashsize;
  94                 pow2[i+2] = (pow2[i+1]<<HICHWIDTH) % hashsize;
  95         }
  96 #endif
  97 }