usr/src/cmd/sh/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 /*
  24  * Copyright 1990 Sun Microsystems, Inc.  All rights reserved.
  25  * Use is subject to license terms.
  26  */
  27
  28 /*      Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
  29 /*        All Rights Reserved   */
  30
  31
  32 #pragma ident   "%Z%%M% %I%     %E% SMI"
  33
  34 #include        "hash.h"
  35 #include        "defs.h"
  36
  37 #define STRCMP(A, B)    (cf(A, B) != 0)
  38 #define FACTOR                  035761254233    /* Magic multiplication factor */
  39 #define TABLENGTH               64                              /* must be multiple of 2 */
  40 #define LOG2LEN                 6                               /* log2 of TABLENGTH */
  41
  42 /*
  43     NOTE: The following algorithm only works on machines where
  44     the results of multiplying two integers is the least
  45     significant part of the double word integer required to hold
  46     the result.  It is adapted from Knuth, Volume 3, section 6.4.
  47 */
  48
  49 #define hash(str)               (int)(((unsigned)(crunch(str) * FACTOR)) >> shift)
  50 struct node
  51 {
  52         ENTRY item;
  53         struct node *next;
  54 };
  55
  56 static struct node      **last;
  57 static struct node      *next;
  58 static struct node      **table;
  59
  60 static unsigned int     bitsper;                /* Bits per byte */
  61 static unsigned int     shift;
  62
  63 static unsigned int crunch();
  64
  65 void
  66 hcreate(void)
  67 {
  68         unsigned char c = (unsigned char)~0;                    /* A byte full of 1's */
  69         int j;
  70
  71         table = (struct node **)alloc(TABLENGTH * sizeof(struct node *));
  72
  73         for (j=0; j < TABLENGTH; ++j)
  74         {
  75                 table[j] = 0;
  76         }
  77
  78         bitsper = 0;
  79
  80         while (c)
  81         {
  82                 c = (unsigned int)c >> 1;
  83                 bitsper++;
  84         }
  85
  86         shift = (bitsper * sizeof(int)) - LOG2LEN;
  87 }
  88
  89
  90 void hscan(uscan)
  91         void    (*uscan)();
  92 {
  93         struct node             *p, *nxt;
  94         int                             j;
  95
  96         for (j=0; j < TABLENGTH; ++j)
  97         {
  98                 p = table[j];
  99                 while (p)
 100                 {
 101                         nxt = p->next;
 102                         (*uscan)(&p->item);
 103                         p = nxt;
 104                 }
 105         }
 106 }
 107
 108
 109
 110 ENTRY *
 111 hfind(str)
 112         unsigned char   *str;
 113 {
 114         struct node     *p;
 115         struct node     **q;
 116         unsigned int    i;
 117         int                     res;
 118
 119         i = hash(str);
 120
 121         if(table[i] == 0)
 122         {
 123                 last = &table[i];
 124                 next = 0;
 125                 return(0);
 126         }
 127         else
 128         {
 129                 q = &table[i];
 130                 p = table[i];
 131                 while (p != 0 && (res = STRCMP(str, p->item.key)))
 132                 {
 133                         q = &(p->next);
 134                         p = p->next;
 135                 }
 136
 137                 if (p != 0 && res == 0)
 138                         return(&(p->item));
 139                 else
 140                 {
 141                         last = q;
 142                         next = p;
 143                         return(0);
 144                 }
 145         }
 146 }
 147
 148 ENTRY *
 149 henter(item)
 150         ENTRY item;
 151 {
 152         struct node     *p = (struct node *)alloc(sizeof(struct node));
 153
 154         p->item = item;
 155         *last = p;
 156         p->next = next;
 157         return(&(p->item));
 158 }
 159
 160
 161 static unsigned int
 162 crunch(key)
 163         unsigned char   *key;
 164 {
 165         unsigned int    sum = 0;
 166         int s;
 167
 168         for (s = 0; *key; s++)                          /* Simply add up the bytes */
 169                 sum += *key++;
 170
 171         return(sum + s);
 172 }
 173