Security-28.tar.gz

[apple/security.git] / SecuritySNACCRuntime / c-lib / src / hash.c

/*
 * 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.
 */


/*
 * 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 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/Darwin/Security/SecuritySNACCRuntime/c-lib/src/hash.c,v 1.1.1.1 2001/05/18 23:14:08 mb Exp $
 * $Log: hash.c,v $
 * Revision 1.1.1.1  2001/05/18 23:14:08  mb
 * Move from private repository to open source repository
 *
 * Revision 1.2  2001/05/05 00:59:25  rmurphy
 * Adding darwin license headers
 *
 * Revision 1.1.1.1  1999/03/16 18:06:32  aram
 * Originals from SMIME Free Library.
 *
 * Revision 1.3  1997/02/28 13:39:51  wan
 * Modifications collected for new version 1.3: Bug fixes, tk4.2.
 *
 * Revision 1.2  1995/07/27 09:05:54  rj
 * use memzero that is defined in .../snacc.h to use either memset or bzero.
 *
 * changed `_' to `-' in file names.
 *
 * Revision 1.1  1994/08/28  09:46:06  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 PARAMS ((str, len),
    char *str _AND_
    unsigned long int len)
{
    register Hash n;
    n = 0;

#define HASHC   n = *str++ + 65587 * n

    if (len > 0)
    {
        int loop;
        loop = (len + 8 - 1) >> 3;
        switch (len & (8 - 1))
	{
          case 0:
            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 = (HashSlot *) malloc (sizeof (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 = (Table *) malloc (sizeof (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 PARAMS ((entry, element, hash_value),
    HashSlot *entry _AND_
    void *element _AND_
    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 PARAMS ((table, element, hash_value),
    Table *table _AND_
    void *element _AND_
    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] = (void*)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 PARAMS ((table, hash),
    Table *table _AND_
    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 PARAMS ((table, hash, value),
    Table *table _AND_
    Hash hash _AND_
    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);
}