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