tor-browser

pkix_pl_primhash.c (19319B)

---

/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/*
* 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 **pKey,
       void **pValue,
       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_FOUR(ht, key, pKey, pValue);

       *pKey = NULL;
       *pValue = NULL;

       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;
                       }
                       *pKey = element->key;
                       *pValue = element->value;
                       element->key = NULL;
                       element->value = NULL;
                       element->next = NULL;
                       PKIX_FREE(element);
                       goto cleanup;
               }
       }

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 {
                      pkixErrorResult =
                          keyComp((PKIX_PL_Object *)key,
                                  (PKIX_PL_Object *)(element->key),
                                  &compResult,
                                  plContext);
                      if (pkixErrorResult) {
                          pkixErrorClass = PKIX_FATAL_ERROR;
                          pkixErrorCode = PKIX_COULDNOTTESTWHETHERKEYSEQUAL;
                          goto cleanup;
                      }
               }

               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);
}