usr/src/cmd/tic/tic_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 /*      Copyright (c) 1988 AT&T */
  27 /*        All Rights Reserved   */
  28
  29 /*
  30  * University Copyright- Copyright (c) 1982, 1986, 1988
  31  * The Regents of the University of California
  32  * All Rights Reserved
  33  *
  34  * University Acknowledgment- Portions of this document are derived from
  35  * software developed by the University of California, Berkeley, and its
  36  * contributors.
  37  */
  38
  39 #pragma ident   "%Z%%M% %I%     %E% SMI"
  40
  41 /*
  42 *************************************************************************
  43 *                       COPYRIGHT NOTICE                                *
  44 *************************************************************************
  45 *       This software is copyright(C) 1982 by Pavel Curtis              *
  46 *                                                                       *
  47 *       Permission is granted to reproduce and distribute               *
  48 *       this file by any means so long as no fee is charged             *
  49 *       above a nominal handling fee and so long as this                *
  50 *       notice is always included in the copies.                        *
  51 *                                                                       *
  52 *       Other rights are reserved except as explicitly granted          *
  53 *       by written permission of the author.                            *
  54 *               Pavel Curtis                                            *
  55 *               Computer Science Dept.                                  *
  56 *               405 Upson Hall                                          *
  57 *               Cornell University                                      *
  58 *               Ithaca, NY 14853                                        *
  59 *                                                                       *
  60 *               Ph- (607) 256-4934                                      *
  61 *                                                                       *
  62 *               Pavel.Cornell@Udel-Relay(ARPAnet)                       *
  63 *               decvax!cornell!pavel(UUCPnet)                           *
  64 *********************************************************************** */
  65
  66 /*
  67  *      comp_hash.c --- Routines to deal with the hashtable of capability
  68  *                      names.
  69  *
  70  *  $Log:       RCS/comp_hash.v $
  71  * Revision 2.1  82/10/25  14:45:34  pavel
  72  * Added Copyright Notice
  73  *
  74  * Revision 2.0  82/10/24  15:16:34  pavel
  75  * Beta-one Test Release
  76  *
  77  * Revision 1.3  82/08/23  22:29:33  pavel
  78  * The REAL Alpha-one Release Version
  79  *
  80  * Revision 1.2  82/08/19  19:09:46  pavel
  81  * Alpha Test Release One
  82  *
  83  * Revision 1.1  82/08/12  18:36:23  pavel
  84  * Initial revision
  85  *
  86  *
  87  */
  88
  89 #include <strings.h>
  90 #include "curses_inc.h"
  91 #include "compiler.h"
  92
  93 static void make_nte(void);
  94 static int hash_function(char *);
  95
  96 /*
  97  *      make_hash_table()
  98  *
  99  *      Takes the entries in cap_table[] and hashes them into cap_hash_table[]
 100  *      by name.  There are Captabsize entries in cap_table[] and Hashtabsize
 101  *      slots in cap_hash_table[].
 102  *
 103  */
 104
 105 void
 106 make_hash_table()
 107 {
 108         int     i;
 109         int     hashvalue;
 110         int     collisions = 0;
 111
 112         make_nte();
 113         for (i = 0; i < Captabsize; i++) {
 114                 hashvalue = hash_function(cap_table[i].nte_name);
 115                 DEBUG(9, "%d\n", hashvalue);
 116
 117                 if (cap_hash_table[hashvalue] != (struct name_table_entry *) 0)
 118                         collisions++;
 119
 120                 cap_table[i].nte_link = cap_hash_table[hashvalue];
 121                 cap_hash_table[hashvalue] = &cap_table[i];
 122         }
 123
 124         DEBUG(3, "Hash table complete\n%d collisions ", collisions);
 125         DEBUG(3, "out of %d entries\n", Captabsize);
 126         return;
 127 }
 128
 129 /*
 130  * Make the name_table_entry from the capnames.c set of tables.
 131  */
 132 static void
 133 make_nte(void)
 134 {
 135         int i, n;
 136         extern char *boolnames[], *numnames[], *strnames[];
 137
 138         n = 0;
 139
 140         for (i = 0; boolnames[i]; i++) {
 141                 cap_table[n].nte_link = NULL;
 142                 cap_table[n].nte_name = boolnames[i];
 143                 cap_table[n].nte_type = BOOLEAN;
 144                 cap_table[n].nte_index = i;
 145                 n++;
 146         }
 147         BoolCount = i;
 148
 149         for (i = 0; numnames[i]; i++) {
 150                 cap_table[n].nte_link = NULL;
 151                 cap_table[n].nte_name = numnames[i];
 152                 cap_table[n].nte_type = NUMBER;
 153                 cap_table[n].nte_index = i;
 154                 n++;
 155         }
 156         NumCount = i;
 157
 158         for (i  = 0; strnames[i]; i++) {
 159                 cap_table[n].nte_link = NULL;
 160                 cap_table[n].nte_name = strnames[i];
 161                 cap_table[n].nte_type = STRING;
 162                 cap_table[n].nte_index = i;
 163                 n++;
 164         }
 165         StrCount = i;
 166
 167         Captabsize = n;
 168 }
 169
 170
 171 /*
 172  *      int hash_function(string)
 173  *
 174  *      Computes the hashing function on the given string.
 175  *
 176  *      The current hash function is the sum of each consectutive pair
 177  *      of characters, taken as two-byte integers, mod Hashtabsize.
 178  *
 179  */
 180
 181 static int
 182 hash_function(char *string)
 183 {
 184         long    sum = 0;
 185
 186         while (*string) {
 187                 sum += *string + (*(string + 1) << 8);
 188                 string++;
 189         }
 190
 191         return (sum % Hashtabsize);
 192 }
 193
 194
 195
 196 /*
 197  *      struct name_table_entry *
 198  *      find_entry(string)
 199  *
 200  *      Finds the entry for the given string in the hash table if present.
 201  *      Returns a pointer to the entry in the table or 0 if not found.
 202  *
 203  */
 204
 205 struct name_table_entry *
 206 find_entry(char *string)
 207 {
 208         int     hashvalue;
 209         struct name_table_entry *ptr;
 210
 211         hashvalue = hash_function(string);
 212
 213         ptr = cap_hash_table[hashvalue];
 214
 215         while (ptr != (struct name_table_entry *) 0 &&
 216             strcmp(ptr->nte_name, string) != 0)
 217                 ptr = ptr->nte_link;
 218
 219         return (ptr);
 220 }