SecuritySNACCRuntime/c++-lib/c++/hash.cpp

   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 // file: .../c++-lib/src/hash.C
  20 //
  21 // This was borrowed from Don Acton and Terry Coatta's Raven Code.
  22 // It has been modified somewhat.
  23 //    - Mike Sample 92
  24 //
  25 // This is a set or routines that implements an extensible hashing
  26 // algorithm. At the moment it assumes that all the hash codes are unique
  27 // (ie. there are no collisions). For the way hash codes are currently being
  28 // supplied this is not a bad assumption.
  29 // The extensible hashing routine used is based on a multiway tree with
  30 // each node in the tree being a fixed array of (2^n) size. At a given
  31 // level, i, in the tree with the first level being level 0, bits
  32 // i*n through i*n through (i+1)*n-1 are used as the index into the table.
  33 // Each entry in the table is either NULL (unused) or a pointer to an
  34 // object of type entry. The entry contains all the information about a
  35 // hash entry. The entry also contains a field indicating whether or not this
  36 // is a leaf node. If an entry isn't a leaf node then it references a table at
  37 // at the next level and not a value. With the current implementation
  38 // a 32 hash value is used and table sizes are 256. The algorithm used
  39 // here is the same as the one used in the Set class of the Raven
  40 // class system.
  41 //
  42 // Copyright (C) 1992 the University of British Columbia
  43 //
  44 // This library is free software; you can redistribute it and/or
  45 // modify it provided that this copyright/license information is retained
  46 // in original form.
  47 //
  48 // If you modify this file, you must clearly indicate your changes.
  49 //
  50 // This source code is distributed in the hope that it will be
  51 // useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  52 // of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  53 //
  54 // $Header: /cvs/Darwin/src/live/Security/SecuritySNACCRuntime/c++-lib/c++/hash.cpp,v 1.1.1.1 2001/05/18 23:14:06 mb Exp $
  55 // $Log: hash.cpp,v $
  56 // Revision 1.1.1.1  2001/05/18 23:14:06  mb
  57 // Move from private repository to open source repository
  58 //
  59 // Revision 1.2  2001/05/05 00:59:17  rmurphy
  60 // Adding darwin license headers
  61 //
  62 // Revision 1.1  2000/06/15 18:44:58  dmitch
  63 // These snacc-generated source files are now checked in to allow cross-platform build.
  64 //
  65 // Revision 1.2  2000/06/08 20:05:36  dmitch
  66 // Mods for X port. These files are actually machine generated and probably don't need to be in CVS....
  67 //
  68 // Revision 1.1.1.1  2000/03/09 01:00:06  rmurphy
  69 // Base Fortissimo Tree
  70 //
  71 // Revision 1.1  1999/02/25 05:21:56  mb
  72 // Added snacc c++ library
  73 //
  74 // Revision 1.7  1997/02/28 13:39:46  wan
  75 // Modifications collected for new version 1.3: Bug fixes, tk4.2.
  76 //
  77 // Revision 1.6  1997/02/16 20:26:08  rj
  78 // check-in of a few cosmetic changes
  79 //
  80 // Revision 1.5  1995/07/24  20:34:07  rj
  81 // use memzero that is defined in .../snacc.h to use either memset or bzero.
  82 //
  83 // changed `_' to `-' in file names.
  84 //
  85 // Revision 1.4  1994/10/08  04:18:32  rj
  86 // code for meta structures added (provides information about the generated code itself).
  87 //
  88 // code for Tcl interface added (makes use of the above mentioned meta code).
  89 //
  90 // virtual inline functions (the destructor, the Clone() function, BEnc(), BDec() and Print()) moved from inc/*.h to src/*.C because g++ turns every one of them into a static non-inline function in every file where the .h file gets included.
  91 //
  92 // made Print() const (and some other, mainly comparison functions).
  93 //
  94 // several `unsigned long int' turned into `size_t'.
  95 //
  96 // Revision 1.3  1994/08/31  23:43:05  rj
  97 // FALSE/TRUE turned into false/true
  98 //
  99 // Revision 1.2  1994/08/28  10:01:21  rj
 100 // comment leader fixed.
 101 //
 102 // Revision 1.1  1994/08/28  09:21:11  rj
 103 // first check-in. for a list of changes to the snacc-1.1 distribution please refer to the ChangeLog.
 104
 105 #include "asn-config.h"
 106 #include "hash.h"
 107
 108
 109 /*
 110  *
 111  * From sdbm, an ndbm work-alike hashed database library
 112  * Author: oz@nexus.yorku.ca
 113  * Status: public domain.
 114  *
 115  * polynomial conversion ignoring overflows
 116  * [this seems to work remarkably well, in fact better
 117  * then the ndbm hash function. Replace at your own risk]
 118  * use: 65599   nice.
 119  *      65587   even better.
 120  *
 121  * [In one experiment, this function hashed 84165 symbols (English words
 122  * plus symbol table values) with no collisions. -bjb]
 123  *
 124  */
 125
 126 Hash
 127 MakeHash (const char *str, size_t len)
 128 {
 129     register Hash n = 0;
 130
 131 #define HASHC   n = *str++ + 65587 * n
 132
 133     if (len > 0)
 134     {
 135         int loop;
 136         loop = (len + 8 - 1) >> 3;
 137         switch (len & (8 - 1))
 138         {
 139           case 0:            /* very strange! - switch labels in do loop */
 140             do
 141             {
 142                 HASHC;
 143               case 7: HASHC;
 144               case 6: HASHC;
 145               case 5: HASHC;
 146               case 4: HASHC;
 147               case 3: HASHC;
 148               case 2: HASHC;
 149               case 1: HASHC;
 150             } while (--loop);
 151         }
 152     }
 153     return n;
 154 }
 155
 156
 157 /* Creates and clears a new hash slot */
 158 static HashSlot *
 159 NewHashSlot()
 160 {
 161   HashSlot *foo;
 162
 163   foo =  new HashSlot;
 164   if (foo == NULL)
 165       return NULL;
 166   memzero (foo, sizeof (HashSlot));
 167   return foo;
 168 }
 169
 170 /* Create a new cleared hash table */
 171 static Table *
 172 NewTable()
 173 {
 174   Table *new_table;
 175
 176 //  new_table = new Table;
 177 // whose bug is it that gcc won't compile the above line?
 178   new_table = (Table *) new Table;
 179   if (new_table == NULL)
 180       return NULL;
 181   memzero (new_table, sizeof (Table));
 182   return new_table;
 183 }
 184
 185 /* This routine is used to initialize the hash tables. When it is called
 186  * it returns a value which is used to identify which hash table
 187  * a particular request is to operate on.
 188  */
 189 Table *
 190 InitHash()
 191 {
 192   Table *table;
 193   table = NewTable();
 194   if (table == NULL)
 195       return 0;
 196   else
 197       return table;
 198 }
 199
 200 /* When a hash collision occurs at a leaf slot this routine is called to
 201  * split the entry and add a new level to the tree at this point.
 202  */
 203 static int
 204 SplitAndInsert (HashSlot *entry, void *element, Hash hash_value)
 205 {
 206
 207   if (((entry->table = NewTable()) == NULL) ||
 208       !Insert (entry->table, entry->value, entry->hash >> INDEXSHIFT) ||
 209       !Insert (entry->table, element, hash_value >> INDEXSHIFT))
 210     return false;
 211
 212   entry->leaf = false;
 213   return true;
 214 }
 215
 216 /* This routine takes a hash table identifier, an element (value) and the
 217  * coresponding hash value for that element and enters it into the table
 218  * assuming it isn't already there.
 219  */
 220 int
 221 Insert (Table *table, void *element, Hash hash_value)
 222 {
 223   HashSlot *entry;
 224
 225   entry = (HashSlot *) (*table)[hash_value & INDEXMASK];
 226
 227   if (entry == NULL) {
 228     /* Need to add this element here */
 229     entry = NewHashSlot();
 230     if (entry == NULL)
 231         return false;
 232     entry->leaf = true;
 233     entry->value = element;
 234     entry->hash = hash_value;
 235     (*table)[hash_value & INDEXMASK] = entry;
 236     return true;
 237   }
 238
 239   if (hash_value == entry->hash)
 240       return true;
 241
 242   if (entry->leaf)
 243       return SplitAndInsert (entry, element, hash_value);
 244
 245   return Insert (entry->table, element, hash_value >> INDEXSHIFT);
 246 }
 247
 248
 249 /* This routine looks to see if a particular hash value is already stored in
 250  * the table. It returns true if it is and false otherwise.
 251  */
 252 int
 253 CheckFor (Table *table, Hash hash)
 254 {
 255   HashSlot *entry;
 256
 257   entry = (HashSlot *) table[hash & INDEXMASK];
 258
 259   if (entry == NULL)
 260       return false;
 261   if (entry->leaf)
 262       return entry->hash == hash;
 263   return CheckFor (entry->table, hash >> INDEXSHIFT);
 264 }
 265
 266 /* In addition to checking for a hash value in the tree this function also
 267  * returns the coresponding element value into the space pointed to by
 268  * the value parameter. If the hash value isn't found false is returned
 269  * the the space pointed to by value is not changed.
 270  */
 271 int
 272 CheckForAndReturnValue (Table *table, Hash hash, void **value)
 273 {
 274   HashSlot *entry;
 275   entry = (HashSlot *) (*table)[hash & INDEXMASK];
 276
 277   if (entry == NULL)
 278       return false;
 279
 280   if (entry->leaf)
 281   {
 282       if (entry->hash == hash)
 283       {
 284           *value = entry->value;
 285           return true;
 286       }
 287       else
 288           return false;
 289   }
 290   return CheckForAndReturnValue (entry->table, hash >> INDEXSHIFT, value);
 291 }