+++ /dev/null
-/*
- * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
- *
- * The contents of this file constitute Original Code as defined in and are
- * subject to the Apple Public Source License Version 1.2 (the 'License').
- * You may not use this file except in compliance with the License. Please obtain
- * a copy of the License at http://www.apple.com/publicsource and read it before
- * using this file.
- *
- * This Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
- * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
- * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
- * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
- * specific language governing rights and limitations under the License.
- */
-
-
-// file: .../c++-lib/src/hash.C
-//
-// This was borrowed from Don Acton and Terry Coatta's Raven Code.
-// It has been modified somewhat.
-// - Mike Sample 92
-//
-// This is a set or routines that implements an extensible hashing
-// algorithm. At the moment it assumes that all the hash codes are unique
-// (ie. there are no collisions). For the way hash codes are currently being
-// supplied this is not a bad assumption.
-// The extensible hashing routine used is based on a multiway tree with
-// each node in the tree being a fixed array of (2^n) size. At a given
-// level, i, in the tree with the first level being level 0, bits
-// i*n through i*n through (i+1)*n-1 are used as the index into the table.
-// Each entry in the table is either NULL (unused) or a pointer to an
-// object of type entry. The entry contains all the information about a
-// hash entry. The entry also contains a field indicating whether or not this
-// is a leaf node. If an entry isn't a leaf node then it references a table at
-// at the next level and not a value. With the current implementation
-// a 32 hash value is used and table sizes are 256. The algorithm used
-// here is the same as the one used in the Set class of the Raven
-// class system.
-//
-// Copyright (C) 1992 the University of British Columbia
-//
-// This library is free software; you can redistribute it and/or
-// modify it provided that this copyright/license information is retained
-// in original form.
-//
-// If you modify this file, you must clearly indicate your changes.
-//
-// This source code is distributed in the hope that it will be
-// useful, but WITHOUT ANY WARRANTY; without even the implied warranty
-// of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
-//
-// $Header: /cvs/root/Security/SecuritySNACCRuntime/c++-lib/c++/Attic/hash.cpp,v 1.1.1.1 2001/05/18 23:14:06 mb Exp $
-// $Log: hash.cpp,v $
-// Revision 1.1.1.1 2001/05/18 23:14:06 mb
-// Move from private repository to open source repository
-//
-// Revision 1.2 2001/05/05 00:59:17 rmurphy
-// Adding darwin license headers
-//
-// Revision 1.1 2000/06/15 18:44:58 dmitch
-// These snacc-generated source files are now checked in to allow cross-platform build.
-//
-// Revision 1.2 2000/06/08 20:05:36 dmitch
-// Mods for X port. These files are actually machine generated and probably don't need to be in CVS....
-//
-// Revision 1.1.1.1 2000/03/09 01:00:06 rmurphy
-// Base Fortissimo Tree
-//
-// Revision 1.1 1999/02/25 05:21:56 mb
-// Added snacc c++ library
-//
-// Revision 1.7 1997/02/28 13:39:46 wan
-// Modifications collected for new version 1.3: Bug fixes, tk4.2.
-//
-// Revision 1.6 1997/02/16 20:26:08 rj
-// check-in of a few cosmetic changes
-//
-// Revision 1.5 1995/07/24 20:34:07 rj
-// use memzero that is defined in .../snacc.h to use either memset or bzero.
-//
-// changed `_' to `-' in file names.
-//
-// Revision 1.4 1994/10/08 04:18:32 rj
-// code for meta structures added (provides information about the generated code itself).
-//
-// code for Tcl interface added (makes use of the above mentioned meta code).
-//
-// 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.
-//
-// made Print() const (and some other, mainly comparison functions).
-//
-// several `unsigned long int' turned into `size_t'.
-//
-// Revision 1.3 1994/08/31 23:43:05 rj
-// FALSE/TRUE turned into false/true
-//
-// Revision 1.2 1994/08/28 10:01:21 rj
-// comment leader fixed.
-//
-// Revision 1.1 1994/08/28 09:21:11 rj
-// first check-in. for a list of changes to the snacc-1.1 distribution please refer to the ChangeLog.
-
-#include "asn-config.h"
-#include "hash.h"
-
-
-/*
- *
- * From sdbm, an ndbm work-alike hashed database library
- * Author: oz@nexus.yorku.ca
- * Status: public domain.
- *
- * polynomial conversion ignoring overflows
- * [this seems to work remarkably well, in fact better
- * then the ndbm hash function. Replace at your own risk]
- * use: 65599 nice.
- * 65587 even better.
- *
- * [In one experiment, this function hashed 84165 symbols (English words
- * plus symbol table values) with no collisions. -bjb]
- *
- */
-
-Hash
-MakeHash (const char *str, size_t len)
-{
- register Hash n = 0;
-
-#define HASHC n = *str++ + 65587 * n
-
- if (len > 0)
- {
- int loop;
- loop = (len + 8 - 1) >> 3;
- switch (len & (8 - 1))
- {
- case 0: /* very strange! - switch labels in do loop */
- do
- {
- HASHC;
- case 7: HASHC;
- case 6: HASHC;
- case 5: HASHC;
- case 4: HASHC;
- case 3: HASHC;
- case 2: HASHC;
- case 1: HASHC;
- } while (--loop);
- }
- }
- return n;
-}
-
-
-/* Creates and clears a new hash slot */
-static HashSlot *
-NewHashSlot()
-{
- HashSlot *foo;
-
- foo = new HashSlot;
- if (foo == NULL)
- return NULL;
- memzero (foo, sizeof (HashSlot));
- return foo;
-}
-
-/* Create a new cleared hash table */
-static Table *
-NewTable()
-{
- Table *new_table;
-
-// new_table = new Table;
-// whose bug is it that gcc won't compile the above line?
- new_table = (Table *) new Table;
- if (new_table == NULL)
- return NULL;
- memzero (new_table, sizeof (Table));
- return new_table;
-}
-
-/* This routine is used to initialize the hash tables. When it is called
- * it returns a value which is used to identify which hash table
- * a particular request is to operate on.
- */
-Table *
-InitHash()
-{
- Table *table;
- table = NewTable();
- if (table == NULL)
- return 0;
- else
- return table;
-}
-
-/* When a hash collision occurs at a leaf slot this routine is called to
- * split the entry and add a new level to the tree at this point.
- */
-static int
-SplitAndInsert (HashSlot *entry, void *element, Hash hash_value)
-{
-
- if (((entry->table = NewTable()) == NULL) ||
- !Insert (entry->table, entry->value, entry->hash >> INDEXSHIFT) ||
- !Insert (entry->table, element, hash_value >> INDEXSHIFT))
- return false;
-
- entry->leaf = false;
- return true;
-}
-
-/* This routine takes a hash table identifier, an element (value) and the
- * coresponding hash value for that element and enters it into the table
- * assuming it isn't already there.
- */
-int
-Insert (Table *table, void *element, Hash hash_value)
-{
- HashSlot *entry;
-
- entry = (HashSlot *) (*table)[hash_value & INDEXMASK];
-
- if (entry == NULL) {
- /* Need to add this element here */
- entry = NewHashSlot();
- if (entry == NULL)
- return false;
- entry->leaf = true;
- entry->value = element;
- entry->hash = hash_value;
- (*table)[hash_value & INDEXMASK] = entry;
- return true;
- }
-
- if (hash_value == entry->hash)
- return true;
-
- if (entry->leaf)
- return SplitAndInsert (entry, element, hash_value);
-
- return Insert (entry->table, element, hash_value >> INDEXSHIFT);
-}
-
-
-/* This routine looks to see if a particular hash value is already stored in
- * the table. It returns true if it is and false otherwise.
- */
-int
-CheckFor (Table *table, Hash hash)
-{
- HashSlot *entry;
-
- entry = (HashSlot *) table[hash & INDEXMASK];
-
- if (entry == NULL)
- return false;
- if (entry->leaf)
- return entry->hash == hash;
- return CheckFor (entry->table, hash >> INDEXSHIFT);
-}
-
-/* In addition to checking for a hash value in the tree this function also
- * returns the coresponding element value into the space pointed to by
- * the value parameter. If the hash value isn't found false is returned
- * the the space pointed to by value is not changed.
- */
-int
-CheckForAndReturnValue (Table *table, Hash hash, void **value)
-{
- HashSlot *entry;
- entry = (HashSlot *) (*table)[hash & INDEXMASK];
-
- if (entry == NULL)
- return false;
-
- if (entry->leaf)
- {
- if (entry->hash == hash)
- {
- *value = entry->value;
- return true;
- }
- else
- return false;
- }
- return CheckForAndReturnValue (entry->table, hash >> INDEXSHIFT, value);
-}
projects / apple / security.git / blobdiff