SecuritySNACCRuntime/c-lib/src/hash.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 /*
  20  * This was borrowed from Don Acton and Terry Coatta's Raven Code.
  21  * It has been modified somewhat.
  22  *    - Mike Sample 92
  23  *
  24  * This is a set or routines that implements an extensible hashing
  25  * algorithm. At the moment it assumes that all the hash codes are unique
  26  * (ie. there are no collisions). For the way hash codes are currently being
  27  * supplied this is not a bad assumption.
  28  * The extensible hashing routine used is based on a multiway tree with
  29  * each node in the tree being a fixed array of (2^n) size. At a given
  30  * level, i, in the tree with the first level being level 0, bits
  31  * i*n through i*n through (i+1)*n-1 are used as the index into the table.
  32  * Each entry in the table is either NULL (unused) or a pointer to an
  33  * object of type entry. The entry contains all the information about a
  34  * hash entry. The entry also contains a field indicating whether or not this
  35  * is a leaf node. If an entry isn't a leaf node then it references a table at
  36  * at the next level and not a value. With the current implementation
  37  * a 32 hash value is used and table sizes are 256. The algorithm used
  38  * here is the same as the one used in the Set class of the Raven
  39  * class system.
  40  *
  41  * Copyright (C) 1992 University of British Columbia
  42  *
  43  * This library is free software; you can redistribute it and/or
  44  * modify it provided that this copyright/license information is retained
  45  * in original form.
  46  *
  47  * If you modify this file, you must clearly indicate your changes.
  48  *
  49  * This source code is distributed in the hope that it will be
  50  * useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  51  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  52  *
  53  * $Header: /cvs/Darwin/Security/SecuritySNACCRuntime/c-lib/src/hash.c,v 1.1.1.1 2001/05/18 23:14:08 mb Exp $
  54  * $Log: hash.c,v $
  55  * Revision 1.1.1.1  2001/05/18 23:14:08  mb
  56  * Move from private repository to open source repository
  57  *
  58  * Revision 1.2  2001/05/05 00:59:25  rmurphy
  59  * Adding darwin license headers
  60  *
  61  * Revision 1.1.1.1  1999/03/16 18:06:32  aram
  62  * Originals from SMIME Free Library.
  63  *
  64  * Revision 1.3  1997/02/28 13:39:51  wan
  65  * Modifications collected for new version 1.3: Bug fixes, tk4.2.
  66  *
  67  * Revision 1.2  1995/07/27 09:05:54  rj
  68  * use memzero that is defined in .../snacc.h to use either memset or bzero.
  69  *
  70  * changed `_' to `-' in file names.
  71  *
  72  * Revision 1.1  1994/08/28  09:46:06  rj
  73  * first check-in. for a list of changes to the snacc-1.1 distribution please refer to the ChangeLog.
  74  *
  75  */
  76
  77 #include "asn-config.h"
  78 #include "hash.h"
  79
  80
  81 /*
  82  *
  83  * From sdbm, an ndbm work-alike hashed database library
  84  * Author: oz@nexus.yorku.ca
  85  * Status: public domain.
  86  *
  87  * polynomial conversion ignoring overflows
  88  * [this seems to work remarkably well, in fact better
  89  * then the ndbm hash function. Replace at your own risk]
  90  * use: 65599   nice.
  91  *      65587   even better.
  92  *
  93  * [In one experiment, this function hashed 84165 symbols (English words
  94  * plus symbol table values) with no collisions. -bjb]
  95  *
  96  */
  97
  98 Hash
  99 MakeHash PARAMS ((str, len),
 100     char *str _AND_
 101     unsigned long int len)
 102 {
 103     register Hash n;
 104     n = 0;
 105
 106 #define HASHC   n = *str++ + 65587 * n
 107
 108     if (len > 0)
 109     {
 110         int loop;
 111         loop = (len + 8 - 1) >> 3;
 112         switch (len & (8 - 1))
 113         {
 114           case 0:
 115             do
 116             {
 117                 HASHC;
 118               case 7: HASHC;
 119               case 6: HASHC;
 120               case 5: HASHC;
 121               case 4: HASHC;
 122               case 3: HASHC;
 123               case 2: HASHC;
 124               case 1: HASHC;
 125             } while (--loop);
 126         }
 127     }
 128     return n;
 129 }
 130
 131 /* Creates and clears a new hash slot */
 132 static HashSlot*
 133 NewHashSlot()
 134 {
 135   HashSlot *foo;
 136
 137   foo = (HashSlot *) malloc (sizeof (HashSlot));
 138   if (foo == NULL)
 139       return NULL;
 140   memzero (foo, sizeof (HashSlot));
 141   return foo;
 142 }
 143
 144 /* Create a new cleared hash table */
 145 static Table*
 146 NewTable()
 147 {
 148   Table *new_table;
 149
 150   new_table = (Table *) malloc (sizeof (Table));
 151   if (new_table == NULL)
 152       return NULL;
 153   memzero (new_table, sizeof (Table));
 154   return new_table;
 155 }
 156
 157 /* This routine is used to initialize the hash tables. When it is called
 158  * it returns a value which is used to identify which hash table
 159  * a particular request is to operate on.
 160  */
 161 Table*
 162 InitHash()
 163 {
 164   Table *table;
 165   table = NewTable();
 166   if (table == NULL)
 167       return 0;
 168   else
 169       return table;
 170 }
 171
 172 /* When a hash collision occurs at a leaf slot this routine is called to
 173  * split the entry and add a new level to the tree at this point.
 174  */
 175 static int
 176 SplitAndInsert PARAMS ((entry, element, hash_value),
 177     HashSlot *entry _AND_
 178     void *element _AND_
 179     Hash hash_value)
 180 {
 181
 182   if (((entry->table = NewTable()) == NULL) ||
 183       !Insert (entry->table, entry->value, entry->hash >> INDEXSHIFT) ||
 184       !Insert (entry->table, element, hash_value >> INDEXSHIFT))
 185     return FALSE;
 186
 187   entry->leaf = FALSE;
 188   return TRUE;
 189 }
 190
 191 /* This routine takes a hash table identifier, an element (value) and the
 192  * coresponding hash value for that element and enters it into the table
 193  * assuming it isn't already there.
 194  */
 195 int
 196 Insert PARAMS ((table, element, hash_value),
 197     Table *table _AND_
 198     void *element _AND_
 199     Hash hash_value)
 200 {
 201   HashSlot *entry;
 202
 203   entry = (HashSlot *) (*table)[hash_value & INDEXMASK];
 204
 205   if (entry == NULL) {
 206     /* Need to add this element here */
 207     entry = NewHashSlot();
 208     if (entry == NULL)
 209         return FALSE;
 210     entry->leaf = TRUE;
 211     entry->value = element;
 212     entry->hash = hash_value;
 213     (*table)[hash_value & INDEXMASK] = (void*)entry;
 214     return TRUE;
 215   }
 216
 217   if (hash_value == entry->hash)
 218       return TRUE;
 219
 220   if (entry->leaf)
 221       return SplitAndInsert (entry, element, hash_value);
 222
 223   return Insert (entry->table, element, hash_value >> INDEXSHIFT);
 224 }
 225
 226
 227 /* This routine looks to see if a particular hash value is already stored in
 228  * the table. It returns true if it is and false otherwise.
 229  */
 230 int
 231 CheckFor PARAMS ((table, hash),
 232     Table *table _AND_
 233     Hash hash)
 234 {
 235   HashSlot *entry;
 236
 237   entry = (HashSlot *) table[hash & INDEXMASK];
 238
 239   if (entry == NULL)
 240       return FALSE;
 241   if (entry->leaf)
 242       return entry->hash == hash;
 243   return CheckFor (entry->table, hash >> INDEXSHIFT);
 244 }
 245
 246 /* In addition to checking for a hash value in the tree this function also
 247  * returns the coresponding element value into the space pointed to by
 248  * the value parameter. If the hash value isn't found FALSE is returned
 249  * the the space pointed to by value is not changed.
 250  */
 251 int
 252 CheckForAndReturnValue PARAMS ((table, hash, value),
 253     Table *table _AND_
 254     Hash hash _AND_
 255     void **value)
 256 {
 257   HashSlot *entry;
 258   entry = (HashSlot *) (*table)[hash & INDEXMASK];
 259
 260   if (entry == NULL)
 261       return FALSE;
 262
 263   if (entry->leaf)
 264   {
 265       if (entry->hash == hash)
 266       {
 267           *value = entry->value;
 268           return TRUE;
 269       }
 270       else
 271           return FALSE;
 272   }
 273   return CheckForAndReturnValue (entry->table, hash >> INDEXSHIFT, value);
 274 }