Import from 1.9a8 tarball

[mozilla-nss.git] / security / nss / lib / libpkix / pkix_pl_nss / system / pkix_pl_primhash.c

/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is the Netscape security libraries.
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1994-2000
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Sun Microsystems
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */
/*
 * pkix_pl_primhash.c
 *
 * Primitive (non-object) Hashtable Functions
 *
 */

#include "pkix_pl_primhash.h"

/* --Private-Functions---------------------------------------- */

/*
 * FUNCTION: pkix_pl_KeyComparator_Default
 * DESCRIPTION:
 *
 *  Compares the integer pointed to by "firstKey" with the integer pointed to
 *  by "secondKey" for equality and stores the Boolean result at "pResult".
 *  This default key comparator assumes each key is a PKIX_UInt32, and it
 *  simply tests them for equality.
 *
 * PARAMETERS:
 *  "firstKey"
 *      Address of the first integer key to compare. Must be non-NULL.
 *      The EqualsCallback for this Object will be called.
 *  "secondKey"
 *      Address of the second integer key to compare. Must be non-NULL.
 *  "pResult"
 *      Address where Boolean will be stored. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Thread Safe (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
static PKIX_Error *
pkix_pl_KeyComparator_Default(
        PKIX_UInt32 *firstKey,
        PKIX_UInt32 *secondKey,
        PKIX_Boolean *pResult,
        void *plContext)
{
        /* Assume both keys are pointers to PKIX_UInt32 */
        PKIX_UInt32 firstInt, secondInt;

        PKIX_ENTER(HASHTABLE, "pkix_pl_KeyComparator_Default");
        PKIX_NULLCHECK_THREE(firstKey, secondKey, pResult);

        firstInt = *firstKey;
        secondInt = *secondKey;

        *pResult = (firstInt == secondInt)?PKIX_TRUE:PKIX_FALSE;

        PKIX_RETURN(HASHTABLE);
}


/*
 * FUNCTION: pkix_pl_PrimHashTable_Create
 * DESCRIPTION:
 *
 *  Creates a new PrimHashtable object with a number of buckets equal to
 *  "numBuckets" and stores the result at "pResult".
 *
 * PARAMETERS:
 *  "numBuckets"
 *      The number of hash table buckets. Must be non-zero.
 *  "pResult"
 *      Address where PrimHashTable pointer will be stored. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Thread Safe (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_Create(
        PKIX_UInt32 numBuckets,
        pkix_pl_PrimHashTable **pResult,
        void *plContext)
{
        pkix_pl_PrimHashTable *primHashTable = NULL;
        PKIX_UInt32 i;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_Create");
        PKIX_NULLCHECK_ONE(pResult);

        if (numBuckets == 0) {
                PKIX_ERROR(PKIX_NUMBUCKETSEQUALSZERO);
        }

        /* Allocate a new hashtable */
        PKIX_CHECK(PKIX_PL_Malloc
                    (sizeof (pkix_pl_PrimHashTable),
                    (void **)&primHashTable,
                    plContext),
                    PKIX_MALLOCFAILED);

        primHashTable->size = numBuckets;

        /* Allocate space for the buckets */
        PKIX_CHECK(PKIX_PL_Malloc
                    (numBuckets * sizeof (pkix_pl_HT_Elem*),
                    (void **)&primHashTable->buckets,
                    plContext),
                    PKIX_MALLOCFAILED);

        for (i = 0; i < numBuckets; i++) {
                primHashTable->buckets[i] = NULL;
        }

        *pResult = primHashTable;

cleanup:

        if (PKIX_ERROR_RECEIVED){
                PKIX_FREE(primHashTable);
        }

        PKIX_RETURN(HASHTABLE);
}

/*
 * FUNCTION: pkix_pl_PrimHashTable_Add
 * DESCRIPTION:
 *
 *  Adds the value pointed to by "value" to the PrimHashTable pointed to by
 *  "ht" using the key pointed to by "key" and the hashCode value equal to
 *  "hashCode", using the function pointed to by "keyComp" to compare keys.
 *  Assumes the key is either a PKIX_UInt32 or a PKIX_PL_Object. If the value
 *  already exists in the hashtable, this function returns a non-fatal error.
 *
 * PARAMETERS:
 *  "ht"
 *      Address of PrimHashtable to insert into. Must be non-NULL.
 *  "key"
 *      Address of key. Typically a PKIX_UInt32 or PKIX_PL_Object.
 *      Must be non-NULL.
 *  "value"
 *      Address of Object to be added to PrimHashtable. Must be non-NULL.
 *  "hashCode"
 *      Hashcode value of the key.
 *  "keyComp"
 *      Address of function used to determine if two keys are equal.
 *      If NULL, pkix_pl_KeyComparator_Default is used.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Not Thread Safe - assumes exclusive access to "ht"
 *  (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a HashTable Error if the function fails in a non-fatal way.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_Add(
        pkix_pl_PrimHashTable *ht,
        void *key,
        void *value,
        PKIX_UInt32 hashCode,
        PKIX_PL_EqualsCallback keyComp,
        void *plContext)
{
        pkix_pl_HT_Elem **elemPtr = NULL;
        pkix_pl_HT_Elem *element = NULL;
        PKIX_Boolean compResult = PKIX_FALSE;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_Add");
        PKIX_NULLCHECK_THREE(ht, key, value);

        for (elemPtr = &((ht->buckets)[hashCode%ht->size]), element = *elemPtr;
            element != NULL; elemPtr = &(element->next), element = *elemPtr) {

                if (element->hashCode != hashCode){
                        /* no possibility of a match */
                        continue;
                }

                if (keyComp == NULL){
                        PKIX_CHECK(pkix_pl_KeyComparator_Default
                                ((PKIX_UInt32 *)key,
                                (PKIX_UInt32 *)(element->key),
                                &compResult,
                                plContext),
                                PKIX_COULDNOTTESTWHETHERKEYSEQUAL);
                } else {
                        PKIX_CHECK(keyComp
                                ((PKIX_PL_Object *)key,
                                (PKIX_PL_Object *)(element->key),
                                &compResult,
                                plContext),
                                PKIX_COULDNOTTESTWHETHERKEYSEQUAL);
                }

                if ((element->hashCode == hashCode) &&
                    (compResult == PKIX_TRUE)){
                        /* Same key already exists in the table */
                        PKIX_ERROR(PKIX_ATTEMPTTOADDDUPLICATEKEY);
                }
        }

        /* Next Element should be NULL at this point */
        if (element != NULL) {
                PKIX_ERROR(PKIX_ERRORTRAVERSINGBUCKET);
        }

        /* Create a new HT_Elem */
        PKIX_CHECK(PKIX_PL_Malloc
                    (sizeof (pkix_pl_HT_Elem), (void **)elemPtr, plContext),
                    PKIX_MALLOCFAILED);

        element = *elemPtr;

        element->key = key;
        element->value = value;
        element->hashCode = hashCode;
        element->next = NULL;

cleanup:

        PKIX_RETURN(HASHTABLE);
}

/*
 * FUNCTION: pkix_pl_PrimHashTable_Remove
 * DESCRIPTION:
 *
 *  Removes any objects with the key pointed to by "key" and hashCode value
 *  equal to "hashCode" from the PrimHashtable pointed to by "ht", using the
 *  function pointed to by "keyComp" to compare keys, and stores the object's
 *  value at "pResult". Assumes "key" is a PKIX_UInt32 or a PKIX_PL_Object.
 *  This function sets "pResult" to NULL if the key is not in the hashtable.
 *
 * PARAMETERS:
 *  "ht"
 *      Address of PrimHashtable to remove object. Must be non-NULL.
 *  "key"
 *      Address of key for lookup. Typically a PKIX_UInt32 or PKIX_PL_Object.
 *      Must be non-NULL.
 *  "value"
 *      Address of Object to be added to PrimHashtable. Must be non-NULL.
 *  "hashCode"
 *      Hashcode value of the key.
 *  "keyComp"
 *      Address of function used to determine if two keys are equal.
 *      If NULL, pkix_pl_KeyComparator_Default is used.
 *  "pResult"
 *      Address where value will be stored. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Not Thread Safe - assumes exclusive access to "ht"
 *  (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a HashTable Error if the function fails in a non-fatal way.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_Remove(
        pkix_pl_PrimHashTable *ht,
        void *key,
        PKIX_UInt32 hashCode,
        PKIX_PL_EqualsCallback keyComp,
        void **pResult,
        void *plContext)
{
        pkix_pl_HT_Elem *element = NULL;
        pkix_pl_HT_Elem *prior = NULL;
        PKIX_Boolean compResult;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_Remove");
        PKIX_NULLCHECK_THREE(ht, key, pResult);

        for (element = ht->buckets[hashCode%ht->size], prior = element;
            (element != NULL);
            prior = element, element = element->next) {

                if (element->hashCode != hashCode){
                        /* no possibility of a match */
                        continue;
                }

                if (keyComp == NULL){
                        PKIX_CHECK(pkix_pl_KeyComparator_Default
                                ((PKIX_UInt32 *)key,
                                (PKIX_UInt32 *)(element->key),
                                &compResult,
                                plContext),
                                PKIX_COULDNOTTESTWHETHERKEYSEQUAL);
                } else {
                        PKIX_CHECK(keyComp
                                ((PKIX_PL_Object *)key,
                                (PKIX_PL_Object *)(element->key),
                                &compResult,
                                plContext),
                                PKIX_COULDNOTTESTWHETHERKEYSEQUAL);
                }

                if ((element->hashCode == hashCode) &&
                    (compResult == PKIX_TRUE)){
                        if (element != prior) {
                                prior->next = element->next;
                        } else {
                                ht->buckets[hashCode%ht->size] = element->next;
                        }
                        *pResult = element->value;
                        element->key = NULL;
                        element->value = NULL;
                        element->next = NULL;
                        PKIX_FREE(element);
                        goto cleanup;
                }
        }

        /* if we've reached here, specified key doesn't exist in hashtable */
        *pResult = NULL;

cleanup:

        PKIX_RETURN(HASHTABLE);
}


/*
 * FUNCTION: pkix_pl_HashTableLookup
 * DESCRIPTION:
 *
 *  Looks up object using the key pointed to by "key" and hashCode value
 *  equal to "hashCode" from the PrimHashtable pointed to by "ht", using the
 *  function pointed to by "keyComp" to compare keys, and stores the object's
 *  value at "pResult". Assumes "key" is a PKIX_UInt32 or a PKIX_PL_Object.
 *  This function sets "pResult" to NULL if the key is not in the hashtable.
 *
 * PARAMETERS:
 *  "ht"
 *      Address of PrimHashtable to lookup object from. Must be non-NULL.
 *  "key"
 *      Address of key for lookup. Typically a PKIX_UInt32 or PKIX_PL_Object.
 *      Must be non-NULL.
 *  "keyComp"
 *      Address of function used to determine if two keys are equal.
 *      If NULL, pkix_pl_KeyComparator_Default is used.
 *  "hashCode"
 *      Hashcode value of the key.
 *  "pResult"
 *      Address where value will be stored. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Conditionally Thread Safe
 *      (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_Lookup(
        pkix_pl_PrimHashTable *ht,
        void *key,
        PKIX_UInt32 hashCode,
        PKIX_PL_EqualsCallback keyComp,
        void **pResult,
        void *plContext)
{
        pkix_pl_HT_Elem *element = NULL;
        PKIX_Boolean compResult = PKIX_FALSE;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_Lookup");
        PKIX_NULLCHECK_THREE(ht, key, pResult);

        *pResult = NULL;

        for (element = (ht->buckets)[hashCode%ht->size];
            (element != NULL) && (*pResult == NULL);
            element = element->next) {

                if (element->hashCode != hashCode){
                        /* no possibility of a match */
                        continue;
                }

                if (keyComp == NULL){
                        PKIX_CHECK(pkix_pl_KeyComparator_Default
                                ((PKIX_UInt32 *)key,
                                (PKIX_UInt32 *)(element->key),
                                &compResult,
                                plContext),
                                PKIX_COULDNOTTESTWHETHERKEYSEQUAL);
                } else {
                        PKIX_CHECK_FATAL(keyComp
                                ((PKIX_PL_Object *)key,
                                (PKIX_PL_Object *)(element->key),
                                &compResult,
                                plContext),
                                PKIX_COULDNOTTESTWHETHERKEYSEQUAL);
                }

                if ((element->hashCode == hashCode) &&
                    (compResult == PKIX_TRUE)){
                        *pResult = element->value;
                        goto cleanup;
                }
        }

        /* if we've reached here, specified key doesn't exist in hashtable */
        *pResult = NULL;

cleanup:

        PKIX_RETURN(HASHTABLE);
}

/*
 * FUNCTION: pkix_pl_PrimHashTable_Destroy
 *
 *  Destroys PrimHashTable pointed to by "ht".
 *
 * PARAMETERS:
 *  "ht"
 *      Address of PrimHashtable to free. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Not Thread Safe - assumes exclusive access to "ht"
 *  (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS
 *  Returns NULL if the function succeeds.
 *  Returns a HashTable Error if the function fails in a non-fatal way.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_Destroy(
        pkix_pl_PrimHashTable *ht,
        void *plContext)
{
        pkix_pl_HT_Elem *element = NULL;
        pkix_pl_HT_Elem *temp = NULL;
        PKIX_UInt32 i;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_Destroy");
        PKIX_NULLCHECK_ONE(ht);

        /* Free each element (list) */
        for (i = 0; i < ht->size; i++) {
                for (element = ht->buckets[i];
                    element != NULL;
                    element = temp) {
                        temp = element->next;
                        element->value = NULL;
                        element->key = NULL;
                        element->hashCode = 0;
                        element->next = NULL;
                        PKIX_FREE(element);
                }
        }

        /* Free the pointer to the list array */
        PKIX_FREE(ht->buckets);
        ht->size = 0;

        /* Free the table itself */
        PKIX_FREE(ht);

        PKIX_RETURN(HASHTABLE);
}

/*
 * FUNCTION: pkix_pl_PrimHashTable_GetBucketSize
 * DESCRIPTION:
 *
 *  Retruns number of entries in the bucket the "hashCode" is designated in
 *  the hashtable "ht" in the address "pBucketSize".
 *
 * PARAMETERS:
 *  "ht"
 *      Address of PrimHashtable to get entries count. Must be non-NULL.
 *  "hashCode"
 *      Hashcode value of the key.
 *  "pBucketSize"
 *      Address that an PKIX_UInt32 is returned for number of entries in the
 *      bucket associated with the hashCode. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Not Thread Safe - assumes exclusive access to "ht"
 *  (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a HashTable Error if the function fails in a non-fatal way.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_GetBucketSize(
        pkix_pl_PrimHashTable *ht,
        PKIX_UInt32 hashCode,
        PKIX_UInt32 *pBucketSize,
        void *plContext)
{
        pkix_pl_HT_Elem **elemPtr = NULL;
        pkix_pl_HT_Elem *element = NULL;
        PKIX_UInt32 bucketSize = 0;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_GetBucketSize");
        PKIX_NULLCHECK_TWO(ht, pBucketSize);

        for (elemPtr = &((ht->buckets)[hashCode%ht->size]), element = *elemPtr;
            element != NULL; elemPtr = &(element->next), element = *elemPtr) {
                bucketSize++;
        }

        *pBucketSize = bucketSize;

        PKIX_RETURN(HASHTABLE);
}

/*
 * FUNCTION: pkix_pl_PrimHashTable_RemoveFIFO
 * DESCRIPTION:
 *
 *  Remove the first entry in the bucket the "hashCode" is designated in
 *  the hashtable "ht". Since new entry is added at end of the link list
 *  the first one is the oldest (FI) therefore removed first (FO).
 *
 * PARAMETERS:
 *  "ht"
 *      Address of PrimHashtable to get entries count. Must be non-NULL.
 *  "hashCode"
 *      Hashcode value of the key.
 *  "pKey"
 *      Address of key of the entry deleted. Must be non-NULL.
 *  "pValue"
 *      Address of Value of the entry deleted. Must be non-NULL.
 *  "plContext"
 *      Platform-specific context pointer.
 * THREAD SAFETY:
 *  Not Thread Safe - assumes exclusive access to "ht"
 *  (see Thread Safety Definitions in Programmer's Guide)
 * RETURNS:
 *  Returns NULL if the function succeeds.
 *  Returns a HashTable Error if the function fails in a non-fatal way.
 *  Returns a Fatal Error if the function fails in an unrecoverable way.
 */
PKIX_Error *
pkix_pl_PrimHashTable_RemoveFIFO(
        pkix_pl_PrimHashTable *ht,
        PKIX_UInt32 hashCode,
        void **pKey,
        void **pValue,
        void *plContext)
{
        pkix_pl_HT_Elem *element = NULL;

        PKIX_ENTER(HASHTABLE, "pkix_pl_PrimHashTable_Remove");
        PKIX_NULLCHECK_THREE(ht, pKey, pValue);

        element = (ht->buckets)[hashCode%ht->size];

        if (element != NULL) {

                *pKey = element->key;
                *pValue = element->value;
                ht->buckets[hashCode%ht->size] = element->next;
                element->key = NULL;
                element->value = NULL;
                element->next = NULL;
                PKIX_FREE(element);
        }

        PKIX_RETURN(HASHTABLE);
}