/* 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_list.c * * List Object Functions * */ #include "pkix_list.h" /* --Private-Functions-------------------------------------------- */ /* * FUNCTION: pkix_List_Create_Internal * DESCRIPTION: * * Creates a new List, using the Boolean value of "isHeader" to determine * whether the new List should be a header, and stores it at "pList". The * List is initially empty and holds no items. To initially add items to * the List, use PKIX_List_AppendItem. * * PARAMETERS: * "isHeader" * Boolean value indicating whether new List should be a header. * "pList" * Address where object 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. */ static PKIX_Error * pkix_List_Create_Internal( PKIX_Boolean isHeader, PKIX_List **pList, void *plContext) { PKIX_List *list = NULL; PKIX_ENTER(LIST, "pkix_List_Create_Internal"); PKIX_NULLCHECK_ONE(pList); PKIX_CHECK(PKIX_PL_Object_Alloc (PKIX_LIST_TYPE, ((PKIX_UInt32)(sizeof (PKIX_List))), (PKIX_PL_Object **)&list, plContext), PKIX_ERRORCREATINGLISTITEM); list->item = NULL; list->next = NULL; list->immutable = PKIX_FALSE; list->length = 0; list->isHeader = isHeader; *pList = list; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_Destroy * (see comments for PKIX_PL_DestructorCallback in pkix_pl_system.h) */ static PKIX_Error * pkix_List_Destroy( PKIX_PL_Object *object, void *plContext) { PKIX_List *list = NULL; PKIX_List *nextItem = NULL; PKIX_ENTER(LIST, "pkix_List_Destroy"); PKIX_NULLCHECK_ONE(object); /* Check that this object is a list */ PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext), PKIX_OBJECTNOTLIST); list = (PKIX_List *)object; /* We have a valid list. DecRef its item and recurse on next */ PKIX_DECREF(list->item); while ((nextItem = list->next) != NULL) { list->next = nextItem->next; nextItem->next = NULL; PKIX_DECREF(nextItem); } list->immutable = PKIX_FALSE; list->length = 0; list->isHeader = PKIX_FALSE; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_ToString_Helper * DESCRIPTION: * * Helper function that creates a string representation of the List pointed * to by "list" and stores its address in the object pointed to by "pString". * * PARAMETERS * "list" * Address of List whose string representation is desired. * Must be non-NULL. * "pString" * Address of object pointer's destination. 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 List Error if the function fails in a non-fatal way. * Returns a Fatal Error if the function fails in an unrecoverable way. */ static PKIX_Error * pkix_List_ToString_Helper( PKIX_List *list, PKIX_PL_String **pString, void *plContext) { PKIX_PL_String *itemString = NULL; PKIX_PL_String *nextString = NULL; PKIX_PL_String *format = NULL; PKIX_Boolean empty; PKIX_ENTER(LIST, "pkix_List_ToString_Helper"); PKIX_NULLCHECK_TWO(list, pString); /* special case when list is the header */ if (list->isHeader){ PKIX_CHECK(PKIX_List_IsEmpty(list, &empty, plContext), PKIX_LISTISEMPTYFAILED); if (empty){ PKIX_CHECK(PKIX_PL_String_Create (PKIX_ESCASCII, "EMPTY", 0, &itemString, plContext), PKIX_ERRORCREATINGITEMSTRING); (*pString) = itemString; PKIX_DEBUG_EXIT(LIST); return (NULL); } else { PKIX_CHECK(pkix_List_ToString_Helper (list->next, &itemString, plContext), PKIX_LISTTOSTRINGHELPERFAILED); } /* Create a string object from the format */ PKIX_CHECK(PKIX_PL_String_Create (PKIX_ESCASCII, "%s", 0, &format, plContext), PKIX_STRINGCREATEFAILED); PKIX_CHECK(PKIX_PL_Sprintf (pString, plContext, format, itemString), PKIX_SPRINTFFAILED); } else { /* Get a string for this list's item */ if (list->item == NULL) { PKIX_CHECK(PKIX_PL_String_Create (PKIX_ESCASCII, "(null)", 0, &itemString, plContext), PKIX_STRINGCREATEFAILED); } else { PKIX_CHECK(PKIX_PL_Object_ToString ((PKIX_PL_Object*)list->item, &itemString, plContext), PKIX_OBJECTTOSTRINGFAILED); } if (list->next == NULL) { /* Just return the itemstring */ (*pString) = itemString; PKIX_DEBUG_EXIT(LIST); return (NULL); } /* Recursive call to get string for this list's next pointer */ PKIX_CHECK(pkix_List_ToString_Helper (list->next, &nextString, plContext), PKIX_LISTTOSTRINGHELPERFAILED); /* Create a string object from the format */ PKIX_CHECK(PKIX_PL_String_Create (PKIX_ESCASCII, "%s, %s", 0, &format, plContext), PKIX_STRINGCREATEFAILED); PKIX_CHECK(PKIX_PL_Sprintf (pString, plContext, format, itemString, nextString), PKIX_SPRINTFFAILED); } cleanup: PKIX_DECREF(itemString); PKIX_DECREF(nextString); PKIX_DECREF(format); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_ToString * (see comments for PKIX_PL_ToStringCallback in pkix_pl_system.h) */ static PKIX_Error * pkix_List_ToString( PKIX_PL_Object *object, PKIX_PL_String **pString, void *plContext) { PKIX_List *list = NULL; PKIX_PL_String *listString = NULL; PKIX_PL_String *format = NULL; PKIX_ENTER(LIST, "pkix_List_ToString"); PKIX_NULLCHECK_TWO(object, pString); PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext), PKIX_OBJECTNOTLIST); list = (PKIX_List *)object; if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } PKIX_CHECK(pkix_List_ToString_Helper(list, &listString, plContext), PKIX_LISTTOSTRINGHELPERFAILED); PKIX_CHECK(PKIX_PL_String_Create (PKIX_ESCASCII, "(%s)", 0, &format, plContext), PKIX_STRINGCREATEFAILED); PKIX_CHECK(PKIX_PL_Sprintf(pString, plContext, format, listString), PKIX_SPRINTFFAILED); cleanup: PKIX_DECREF(listString); PKIX_DECREF(format); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_Equals * (see comments for PKIX_PL_EqualsCallback in pkix_pl_system.h) */ static PKIX_Error * pkix_List_Equals( PKIX_PL_Object *first, PKIX_PL_Object *second, PKIX_Boolean *pResult, void *plContext) { PKIX_UInt32 secondType; PKIX_Boolean cmpResult; PKIX_List *firstList = NULL; PKIX_List *secondList = NULL; PKIX_UInt32 firstLength = 0; PKIX_UInt32 secondLength = 0; PKIX_PL_Object *firstItem = NULL; PKIX_PL_Object *secondItem = NULL; PKIX_UInt32 i = 0; PKIX_ENTER(LIST, "pkix_List_Equals"); PKIX_NULLCHECK_THREE(first, second, pResult); /* test that first is a List */ PKIX_CHECK(pkix_CheckType(first, PKIX_LIST_TYPE, plContext), PKIX_FIRSTOBJECTNOTLIST); /* * Since we know first is a List, if both references are * identical, they must be equal */ if (first == second){ *pResult = PKIX_TRUE; goto cleanup; } /* * If second isn't a List, we don't throw an error. * We simply return a Boolean result of FALSE */ *pResult = PKIX_FALSE; PKIX_CHECK(PKIX_PL_Object_GetType(second, &secondType, plContext), PKIX_COULDNOTGETTYPEOFSECONDARGUMENT); if (secondType != PKIX_LIST_TYPE) goto cleanup; firstList = (PKIX_List *)first; secondList = (PKIX_List *)second; if ((!firstList->isHeader) && (!secondList->isHeader)){ PKIX_ERROR(PKIX_INPUTLISTSMUSTBELISTHEADERS); } firstLength = firstList->length; secondLength = secondList->length; cmpResult = PKIX_FALSE; if (firstLength == secondLength){ for (i = 0, cmpResult = PKIX_TRUE; ((i < firstLength) && cmpResult); i++){ PKIX_CHECK(PKIX_List_GetItem (firstList, i, &firstItem, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(PKIX_List_GetItem (secondList, i, &secondItem, plContext), PKIX_LISTGETITEMFAILED); if ((!firstItem && secondItem) || (firstItem && !secondItem)){ cmpResult = PKIX_FALSE; } else if (!firstItem && !secondItem){ continue; } else { PKIX_CHECK(PKIX_PL_Object_Equals (firstItem, secondItem, &cmpResult, plContext), PKIX_OBJECTEQUALSFAILED); PKIX_DECREF(firstItem); PKIX_DECREF(secondItem); } } } *pResult = cmpResult; cleanup: PKIX_DECREF(firstItem); PKIX_DECREF(secondItem); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_Hashcode * (see comments for PKIX_PL_HashcodeCallback in pkix_pl_system.h) */ static PKIX_Error * pkix_List_Hashcode( PKIX_PL_Object *object, PKIX_UInt32 *pHashcode, void *plContext) { PKIX_List *list = NULL; PKIX_PL_Object *element = NULL; PKIX_UInt32 hash = 0; PKIX_UInt32 tempHash = 0; PKIX_UInt32 length, i; PKIX_ENTER(LIST, "pkix_List_Hashcode"); PKIX_NULLCHECK_TWO(object, pHashcode); PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext), PKIX_OBJECTNOTLIST); list = (PKIX_List *)object; if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } length = list->length; for (i = 0; i < length; i++){ PKIX_CHECK(PKIX_List_GetItem(list, i, &element, plContext), PKIX_LISTGETITEMFAILED); if (!element){ tempHash = 100; } else { PKIX_CHECK(PKIX_PL_Object_Hashcode (element, &tempHash, plContext), PKIX_LISTHASHCODEFAILED); } hash = 31 * hash + tempHash; PKIX_DECREF(element); } *pHashcode = hash; cleanup: PKIX_DECREF(element); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_Duplicate * (see comments for PKIX_PL_DuplicateCallback in pkix_pl_system.h) */ static PKIX_Error * pkix_List_Duplicate( PKIX_PL_Object *object, PKIX_PL_Object **pNewObject, void *plContext) { PKIX_List *list = NULL; PKIX_List *listDuplicate = NULL; PKIX_ENTER(LIST, "pkix_List_Duplicate"); PKIX_NULLCHECK_TWO(object, pNewObject); PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext), PKIX_OBJECTNOTLIST); list = (PKIX_List *)object; if (list->immutable){ PKIX_CHECK(pkix_duplicateImmutable (object, pNewObject, plContext), PKIX_DUPLICATEIMMUTABLEFAILED); } else { PKIX_CHECK(pkix_List_Create_Internal (list->isHeader, &listDuplicate, plContext), PKIX_LISTCREATEINTERNALFAILED); listDuplicate->length = list->length; PKIX_INCREF(list->item); listDuplicate->item = list->item; if (list->next == NULL){ listDuplicate->next = NULL; } else { /* Recursively Duplicate list */ PKIX_CHECK(pkix_List_Duplicate ((PKIX_PL_Object *)list->next, (PKIX_PL_Object **)&listDuplicate->next, plContext), PKIX_LISTDUPLICATEFAILED); } *pNewObject = (PKIX_PL_Object *)listDuplicate; } cleanup: if (PKIX_ERROR_RECEIVED){ PKIX_DECREF(listDuplicate); } PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_GetElement * DESCRIPTION: * * Copies the "list"'s element at "index" into "element". The input List must * be the header of the List (as opposed to being an element of the List). The * index counts from zero and must be less than the List's length. This * function does NOT increment the reference count of the List element since * the returned element's reference will not be stored by the calling * function. * * PARAMETERS: * "list" * Address of List (must be header) to get element from. Must be non-NULL. * "index" * Index of list to get element from. Must be less than List's length. * "pElement" * Address where object pointer 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. */ static PKIX_Error * pkix_List_GetElement( PKIX_List *list, PKIX_UInt32 index, PKIX_List **pElement, void *plContext) { PKIX_List *iterator = NULL; PKIX_UInt32 length; PKIX_UInt32 position = 0; PKIX_ENTER(LIST, "pkix_List_GetElement"); PKIX_NULLCHECK_TWO(list, pElement); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } length = list->length; if (index >= length) { PKIX_ERROR(PKIX_INDEXOUTOFBOUNDS); } for (iterator = list; position++ <= index; iterator = iterator->next) ; (*pElement) = iterator; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_RegisterSelf * DESCRIPTION: * Registers PKIX_LIST_TYPE and its related functions with systemClasses[] * THREAD SAFETY: * Not Thread Safe - for performance and complexity reasons * * Since this function is only called by PKIX_PL_Initialize, which should * only be called once, it is acceptable that this function is not * thread-safe. */ PKIX_Error * pkix_List_RegisterSelf(void *plContext) { extern pkix_ClassTable_Entry systemClasses[PKIX_NUMTYPES]; pkix_ClassTable_Entry entry; PKIX_ENTER(LIST, "pkix_List_RegisterSelf"); entry.description = "List"; entry.objCounter = 0; entry.typeObjectSize = sizeof(PKIX_List); entry.destructor = pkix_List_Destroy; entry.equalsFunction = pkix_List_Equals; entry.hashcodeFunction = pkix_List_Hashcode; entry.toStringFunction = pkix_List_ToString; entry.comparator = NULL; entry.duplicateFunction = pkix_List_Duplicate; systemClasses[PKIX_LIST_TYPE] = entry; PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_Contains * DESCRIPTION: * * Checks a List pointed to by "list", to determine whether it includes * an entry that is equal to the Object pointed to by "object", and stores * the result in "pFound". * * PARAMETERS: * "list" * List to be searched; may be empty; must be non-NULL * "object" * Object to be checked for; must be non-NULL * "pFound" * Address where the result of the search 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_List_Contains( PKIX_List *list, PKIX_PL_Object *object, PKIX_Boolean *pFound, void *plContext) { PKIX_PL_Object *current = NULL; PKIX_UInt32 numEntries = 0; PKIX_UInt32 index = 0; PKIX_Boolean match = PKIX_FALSE; PKIX_ENTER(LIST, "pkix_List_Contains"); PKIX_NULLCHECK_THREE(list, object, pFound); PKIX_CHECK(PKIX_List_GetLength(list, &numEntries, plContext), PKIX_LISTGETLENGTHFAILED); for (index = 0; index < numEntries; index++) { PKIX_CHECK(PKIX_List_GetItem (list, index, ¤t, plContext), PKIX_LISTGETITEMFAILED); if (current) { PKIX_CHECK(PKIX_PL_Object_Equals (object, current, &match, plContext), PKIX_OBJECTEQUALSFAILED); PKIX_DECREF(current); } if (match) { break; } } *pFound = match; cleanup: PKIX_DECREF(current); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_Remove * DESCRIPTION: * * Traverses the List pointed to by "list", to find and delete an entry * that is equal to the Object pointed to by "object". If no such entry * is found the function does not return an error. * * PARAMETERS: * "list" * List to be searched; may be empty; must be non-NULL * "object" * Object to be checked for and deleted, if found; 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 Validate Error if the functions fails in a non-fatal way * Returns a Fatal Error if the function fails in an unrecoverable way */ PKIX_Error * pkix_List_Remove( PKIX_List *list, PKIX_PL_Object *object, void *plContext) { PKIX_PL_Object *current = NULL; PKIX_UInt32 numEntries = 0; PKIX_UInt32 index = 0; PKIX_Boolean match = PKIX_FALSE; PKIX_ENTER(LIST, "pkix_List_Remove"); PKIX_NULLCHECK_TWO(list, object); PKIX_CHECK(PKIX_List_GetLength(list, &numEntries, plContext), PKIX_LISTGETLENGTHFAILED); for (index = 0; index < numEntries; index++) { PKIX_CHECK(PKIX_List_GetItem (list, index, ¤t, plContext), PKIX_LISTGETITEMFAILED); if (current) { PKIX_CHECK(PKIX_PL_Object_Equals (object, current, &match, plContext), PKIX_OBJECTEQUALSFAILED); PKIX_DECREF(current); } if (match) { PKIX_CHECK(PKIX_List_DeleteItem (list, index, plContext), PKIX_LISTDELETEITEMFAILED); break; } } cleanup: PKIX_DECREF(current); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_RemoveItems * DESCRIPTION: * * Traverses the List pointed to by "list", to find and delete an entry * that is equal to the Object in the "deleteList". If no such entry * is found the function does not return an error. * * PARAMETERS: * "list" * Object in "list" is checked for object in "deleteList" and deleted if * found; may be empty; must be non-NULL * "deleteList" * List of objects to be searched ; may be empty; 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 Validate Error if the functions fails in a non-fatal way * Returns a Fatal Error if the function fails in an unrecoverable way */ PKIX_Error * pkix_List_RemoveItems( PKIX_List *list, PKIX_List *deleteList, void *plContext) { PKIX_PL_Object *current = NULL; PKIX_UInt32 numEntries = 0; PKIX_UInt32 index = 0; PKIX_ENTER(LIST, "pkix_List_RemoveItems"); PKIX_NULLCHECK_TWO(list, deleteList); PKIX_CHECK(PKIX_List_GetLength(deleteList, &numEntries, plContext), PKIX_LISTGETLENGTHFAILED); for (index = 0; index < numEntries; index++) { PKIX_CHECK(PKIX_List_GetItem (deleteList, index, ¤t, plContext), PKIX_LISTGETITEMFAILED); if (current) { PKIX_CHECK(pkix_List_Remove (list, current, plContext), PKIX_OBJECTEQUALSFAILED); PKIX_DECREF(current); } } cleanup: PKIX_DECREF(current); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_MergeLists * DESCRIPTION: * * Creates a new list consisting of the items from "firstList", followed by * the items on "secondList", returns the new list at "pMergedList". If * both input lists are NULL or empty, the result is an empty list. If an error * occurs, the result is NULL. * * PARAMETERS: * "firstList" * Address of list to be merged from. May be NULL or empty. * "secondList" * Address of list to be merged from. May be NULL or empty. * "pMergedList" * Address where returned object is stored. * "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 List Error if the functions fails in a non-fatal way * Returns a Fatal Error if the function fails in an unrecoverable way */ PKIX_Error * pkix_List_MergeLists( PKIX_List *firstList, PKIX_List *secondList, PKIX_List **pMergedList, void *plContext) { PKIX_List *list = NULL; PKIX_PL_Object *item = NULL; PKIX_UInt32 numItems = 0; PKIX_UInt32 i; PKIX_ENTER(LIST, "pkix_List_MergeLists"); PKIX_NULLCHECK_ONE(pMergedList); *pMergedList = NULL; PKIX_CHECK(PKIX_List_Create(&list, plContext), PKIX_LISTCREATEFAILED); if (firstList != NULL) { PKIX_CHECK(PKIX_List_GetLength(firstList, &numItems, plContext), PKIX_LISTGETLENGTHFAILED); } for (i = 0; i < numItems; i++) { PKIX_CHECK(PKIX_List_GetItem(firstList, i, &item, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(PKIX_List_AppendItem(list, item, plContext), PKIX_LISTAPPENDITEMFAILED); PKIX_DECREF(item); } numItems = 0; if (secondList != NULL) { PKIX_CHECK(PKIX_List_GetLength (secondList, &numItems, plContext), PKIX_LISTGETLENGTHFAILED); } for (i = 0; i < numItems; i++) { PKIX_CHECK(PKIX_List_GetItem (secondList, i, &item, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(PKIX_List_AppendItem (list, item, plContext), PKIX_LISTAPPENDITEMFAILED); PKIX_DECREF(item); } *pMergedList = list; list = NULL; cleanup: PKIX_DECREF(list); PKIX_DECREF(item); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_AppendList * DESCRIPTION: * * Append items on "fromList" to the "toList". Item reference count on * "toList" is not incremented, but items appended from "fromList" are * incremented. * * PARAMETERS: * "toList" * Address of list to be appended to. Must be non-NULL. * "fromList" * Address of list to be appended from. May be NULL or empty. * "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 List Error if the functions fails in a non-fatal way * Returns a Fatal Error if the function fails in an unrecoverable way */ PKIX_Error * pkix_List_AppendList( PKIX_List *toList, PKIX_List *fromList, void *plContext) { PKIX_PL_Object *item = NULL; PKIX_UInt32 numItems = 0; PKIX_UInt32 i; PKIX_ENTER(LIST, "pkix_List_AppendList"); PKIX_NULLCHECK_ONE(toList); /* if fromList is NULL or is an empty list, no action */ if (fromList == NULL) { goto cleanup; } PKIX_CHECK(PKIX_List_GetLength(fromList, &numItems, plContext), PKIX_LISTGETLENGTHFAILED); if (numItems == 0) { goto cleanup; } for (i = 0; i < numItems; i++) { PKIX_CHECK(PKIX_List_GetItem (fromList, i, &item, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(PKIX_List_AppendItem(toList, item, plContext), PKIX_LISTAPPENDITEMFAILED); PKIX_DECREF(item); } cleanup: PKIX_DECREF(item); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_AppendUnique * DESCRIPTION: * * Adds each Object in the List pointed to by "fromList" to the List pointed * to by "toList", if it is not already a member of that List. In other words, * "toList" becomes the union of the two sets. * * PARAMETERS: * "toList" * Address of a List of Objects to be augmented by "fromList". Must be * non-NULL, but may be empty. * "fromList" * Address of a List of Objects to be added, if not already present, to * "toList". Must be non-NULL, but may be empty. * "plContext" * Platform-specific context pointer. * THREAD SAFETY: * Not Thread Safe - assumes exclusive access to "toList" * (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_List_AppendUnique( PKIX_List *toList, PKIX_List *fromList, void *plContext) { PKIX_Boolean isContained = PKIX_FALSE; PKIX_UInt32 listLen = 0; PKIX_UInt32 listIx = 0; PKIX_PL_Object *object = NULL; PKIX_ENTER(BUILD, "pkix_List_AppendUnique"); PKIX_NULLCHECK_TWO(fromList, toList); PKIX_CHECK(PKIX_List_GetLength(fromList, &listLen, plContext), PKIX_LISTGETLENGTHFAILED); for (listIx = 0; listIx < listLen; listIx++) { PKIX_CHECK(PKIX_List_GetItem (fromList, listIx, &object, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(pkix_List_Contains (toList, object, &isContained, plContext), PKIX_LISTCONTAINSFAILED); if (isContained == PKIX_FALSE) { PKIX_CHECK(PKIX_List_AppendItem (toList, object, plContext), PKIX_LISTAPPENDITEMFAILED); } PKIX_DECREF(object); } cleanup: PKIX_DECREF(object); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_QuickSort * DESCRIPTION: * * Sorts List of Objects "fromList" using "comparatorCallback"'s result as * comasrison key and returns the sorted List at "pSortedList". The sorting * algorithm used is quick sort (n*logn). * * PARAMETERS: * "fromList" * Address of a List of Objects to be sorted. Must be non-NULL, but may be * empty. * "comparatorCallback" * Address of callback function that will compare two Objects on the List. * It should return -1 for less, 0 for equal and 1 for greater. The * callback implementation chooses what in Objects to be compared. Must be * non-NULL. * "pSortedList" * Address of a List of Objects that shall be sorted and returned. Must be * non-NULL, but may be empty. * "plContext" * Platform-specific context pointer. * THREAD SAFETY: * Not Thread Safe - assumes exclusive access to "toList" * (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_List_QuickSort( PKIX_List *fromList, PKIX_List_SortComparatorCallback comparator, PKIX_List **pSortedList, void *plContext) { PKIX_List *sortedList = NULL; PKIX_List *lessList = NULL; PKIX_List *greaterList = NULL; PKIX_List *sortedLessList = NULL; PKIX_List *sortedGreaterList = NULL; PKIX_PL_Object *object = NULL; PKIX_PL_Object *cmpObj = NULL; PKIX_Int32 cmpResult = 0; PKIX_UInt32 size = 0; PKIX_UInt32 i; PKIX_ENTER(BUILD, "pkix_List_QuickSort"); PKIX_NULLCHECK_THREE(fromList, comparator, pSortedList); PKIX_CHECK(PKIX_List_GetLength(fromList, &size, plContext), PKIX_LISTGETLENGTHFAILED); PKIX_CHECK(PKIX_List_Create(&lessList, plContext), PKIX_LISTCREATEFAILED); PKIX_CHECK(PKIX_List_Create(&greaterList, plContext), PKIX_LISTCREATEFAILED); PKIX_CHECK(PKIX_List_GetItem (fromList, 0, &object, plContext), PKIX_LISTGETITEMFAILED); /* * Pick the first item on the list as the one to be compared. * Separate rest of the itmes into two lists: less-than or greater- * than lists. Sort those two lists recursively. Insert sorted * less-than list before the picked item and append the greater- * than list after the picked item. */ for (i = 1; i < size; i++) { PKIX_CHECK(PKIX_List_GetItem (fromList, i, &cmpObj, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(comparator(object, cmpObj, &cmpResult, plContext), PKIX_COMPARATORCALLBACKFAILED); if (cmpResult >= 0) { PKIX_CHECK(PKIX_List_AppendItem (lessList, cmpObj, plContext), PKIX_LISTAPPENDITEMFAILED); } else { PKIX_CHECK(PKIX_List_AppendItem (greaterList, cmpObj, plContext), PKIX_LISTAPPENDITEMFAILED); } PKIX_DECREF(cmpObj); } PKIX_CHECK(PKIX_List_Create(&sortedList, plContext), PKIX_LISTCREATEFAILED); PKIX_CHECK(PKIX_List_GetLength(lessList, &size, plContext), PKIX_LISTGETLENGTHFAILED); if (size > 1) { PKIX_CHECK(pkix_List_QuickSort (lessList, comparator, &sortedLessList, plContext), PKIX_LISTQUICKSORTFAILED); PKIX_CHECK(pkix_List_AppendList (sortedList, sortedLessList, plContext), PKIX_LISTAPPENDLISTFAILED); } else { PKIX_CHECK(pkix_List_AppendList (sortedList, lessList, plContext), PKIX_LISTAPPENDLISTFAILED); } PKIX_CHECK(PKIX_List_AppendItem(sortedList, object, plContext), PKIX_LISTAPPENDFAILED); PKIX_CHECK(PKIX_List_GetLength(greaterList, &size, plContext), PKIX_LISTGETLENGTHFAILED); if (size > 1) { PKIX_CHECK(pkix_List_QuickSort (greaterList, comparator, &sortedGreaterList, plContext), PKIX_LISTQUICKSORTFAILED); PKIX_CHECK(pkix_List_AppendList (sortedList, sortedGreaterList, plContext), PKIX_LISTAPPENDLISTFAILED); } else { PKIX_CHECK(pkix_List_AppendList (sortedList, greaterList, plContext), PKIX_LISTAPPENDLISTFAILED); } *pSortedList = sortedList; cleanup: PKIX_DECREF(cmpObj); PKIX_DECREF(object); PKIX_DECREF(sortedGreaterList); PKIX_DECREF(sortedLessList); PKIX_DECREF(greaterList); PKIX_DECREF(lessList); PKIX_RETURN(LIST); } /* * FUNCTION: pkix_List_BubbleSort * DESCRIPTION: * * Sorts List of Objects "fromList" using "comparatorCallback"'s result as * comasrison key and returns the sorted List at "pSortedList". The sorting * algorithm used is bubble sort (n*n). * * PARAMETERS: * "fromList" * Address of a List of Objects to be sorted. Must be non-NULL, but may be * empty. * "comparatorCallback" * Address of callback function that will compare two Objects on the List. * It should return -1 for less, 0 for equal and 1 for greater. The * callback implementation chooses what in Objects to be compared. Must be * non-NULL. * "pSortedList" * Address of a List of Objects that shall be sorted and returned. Must be * non-NULL, but may be empty. * "plContext" * Platform-specific context pointer. * THREAD SAFETY: * Not Thread Safe - assumes exclusive access to "toList" * (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_List_BubbleSort( PKIX_List *fromList, PKIX_List_SortComparatorCallback comparator, PKIX_List **pSortedList, void *plContext) { PKIX_List *sortedList = NULL; PKIX_PL_Object *cmpObj = NULL; PKIX_PL_Object *leastObj = NULL; PKIX_Int32 cmpResult = 0; PKIX_UInt32 size = 0; PKIX_UInt32 i, j; PKIX_ENTER(BUILD, "pkix_List_BubbleSort"); PKIX_NULLCHECK_THREE(fromList, comparator, pSortedList); if (fromList->immutable) { PKIX_ERROR(PKIX_CANNOTSORTIMMUTABLELIST); } PKIX_CHECK(pkix_List_Duplicate ((PKIX_PL_Object *) fromList, (PKIX_PL_Object **) &sortedList, plContext), PKIX_LISTDUPLICATEFAILED); PKIX_CHECK(PKIX_List_GetLength(sortedList, &size, plContext), PKIX_LISTGETLENGTHFAILED); if (size > 1) { /* * Move from the first of the item on the list, For each iteration, * compare and swap the least value to the head of the comparisoning * sub-list. */ for (i = 0; i < size - 1; i++) { PKIX_CHECK(PKIX_List_GetItem (sortedList, i, &leastObj, plContext), PKIX_LISTGETITEMFAILED); for (j = i + 1; j < size; j++) { PKIX_CHECK(PKIX_List_GetItem (sortedList, j, &cmpObj, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(comparator (leastObj, cmpObj, &cmpResult, plContext), PKIX_COMPARATORCALLBACKFAILED); if (cmpResult > 0) { PKIX_CHECK(PKIX_List_SetItem (sortedList, j, leastObj, plContext), PKIX_LISTSETITEMFAILED); PKIX_DECREF(leastObj); leastObj = cmpObj; cmpObj = NULL; } else { PKIX_DECREF(cmpObj); } } PKIX_CHECK(PKIX_List_SetItem (sortedList, i, leastObj, plContext), PKIX_LISTSETITEMFAILED); PKIX_DECREF(leastObj); } } *pSortedList = sortedList; sortedList = NULL; cleanup: PKIX_DECREF(sortedList); PKIX_DECREF(leastObj); PKIX_DECREF(cmpObj); PKIX_RETURN(LIST); } /* --Public-List-Functions--------------------------------------------- */ /* * FUNCTION: PKIX_List_Create (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_Create( PKIX_List **pList, void *plContext) { PKIX_List *list = NULL; PKIX_ENTER(LIST, "PKIX_List_Create"); PKIX_NULLCHECK_ONE(pList); PKIX_CHECK(pkix_List_Create_Internal(PKIX_TRUE, &list, plContext), PKIX_LISTCREATEINTERNALFAILED); *pList = list; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_SetImmutable (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_SetImmutable( PKIX_List *list, void *plContext) { PKIX_ENTER(LIST, "PKIX_List_SetImmutable"); PKIX_NULLCHECK_ONE(list); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } list->immutable = PKIX_TRUE; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_IsImmutable (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_IsImmutable( PKIX_List *list, PKIX_Boolean *pImmutable, void *plContext) { PKIX_ENTER(LIST, "PKIX_List_IsImmutable"); PKIX_NULLCHECK_TWO(list, pImmutable); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } *pImmutable = list->immutable; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_GetLength (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_GetLength( PKIX_List *list, PKIX_UInt32 *pLength, void *plContext) { PKIX_ENTER(LIST, "PKIX_List_GetLength"); PKIX_NULLCHECK_TWO(list, pLength); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } *pLength = list->length; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_IsEmpty (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_IsEmpty( PKIX_List *list, PKIX_Boolean *pEmpty, void *plContext) { PKIX_UInt32 length; PKIX_ENTER(LIST, "PKIX_List_IsEmpty"); PKIX_NULLCHECK_TWO(list, pEmpty); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } length = list->length; if (length == 0){ *pEmpty = PKIX_TRUE; } else { *pEmpty = PKIX_FALSE; } cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_AppendItem (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_AppendItem( PKIX_List *list, PKIX_PL_Object *item, void *plContext) { PKIX_List *lastElement = NULL; PKIX_List *newElement = NULL; PKIX_UInt32 length, i; PKIX_ENTER(LIST, "PKIX_List_AppendItem"); PKIX_NULLCHECK_ONE(list); if (list->immutable){ PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST); } if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } length = list->length; /* find last element of list and create new element there */ lastElement = list; for (i = 0; i < length; i++){ lastElement = lastElement->next; } PKIX_CHECK(pkix_List_Create_Internal (PKIX_FALSE, &newElement, plContext), PKIX_LISTCREATEINTERNALFAILED); PKIX_INCREF(item); newElement->item = item; PKIX_CHECK(PKIX_PL_Object_InvalidateCache ((PKIX_PL_Object *)list, plContext), PKIX_OBJECTINVALIDATECACHEFAILED); lastElement->next = newElement; newElement = NULL; list->length += 1; cleanup: PKIX_DECREF(newElement); PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_InsertItem (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_InsertItem( PKIX_List *list, PKIX_UInt32 index, PKIX_PL_Object *item, void *plContext) { PKIX_List *element = NULL; PKIX_List *newElem = NULL; PKIX_ENTER(LIST, "PKIX_List_InsertItem"); PKIX_NULLCHECK_ONE(list); if (list->immutable){ PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST); } if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } /* Create a new list object */ PKIX_CHECK(pkix_List_Create_Internal(PKIX_FALSE, &newElem, plContext), PKIX_LISTCREATEINTERNALFAILED); if (list->length) { PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext), PKIX_LISTGETELEMENTFAILED); /* Copy the old element's contents into the new element */ newElem->item = element->item; /* Add new item to the list */ PKIX_INCREF(item); element->item = item; /* Set the new element's next pointer to the old element's next */ newElem->next = element->next; /* Set the old element's next pointer to the new element */ element->next = newElem; newElem = NULL; } else { PKIX_INCREF(item); newElem->item = item; newElem->next = NULL; list->next = newElem; newElem = NULL; } list->length++; PKIX_CHECK(PKIX_PL_Object_InvalidateCache ((PKIX_PL_Object *)list, plContext), PKIX_OBJECTINVALIDATECACHEFAILED); cleanup: PKIX_DECREF(newElem); PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_GetItem (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_GetItem( PKIX_List *list, PKIX_UInt32 index, PKIX_PL_Object **pItem, void *plContext) { PKIX_List *element = NULL; PKIX_ENTER(LIST, "PKIX_List_GetItem"); PKIX_NULLCHECK_TWO(list, pItem); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext), PKIX_LISTGETELEMENTFAILED); PKIX_INCREF(element->item); *pItem = element->item; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_SetItem (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_SetItem( PKIX_List *list, PKIX_UInt32 index, PKIX_PL_Object *item, void *plContext) { PKIX_List *element; PKIX_ENTER(LIST, "PKIX_List_SetItem"); PKIX_NULLCHECK_ONE(list); if (list->immutable){ PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST); } if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext), PKIX_LISTGETELEMENTFAILED); /* DecRef old contents */ PKIX_DECREF(element->item); /* Set New Contents */ PKIX_INCREF(item); element->item = item; PKIX_CHECK(PKIX_PL_Object_InvalidateCache ((PKIX_PL_Object *)list, plContext), PKIX_OBJECTINVALIDATECACHEFAILED); cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_DeleteItem (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_DeleteItem( PKIX_List *list, PKIX_UInt32 index, void *plContext) { PKIX_List *element = NULL; PKIX_List *prevElement = NULL; PKIX_List *nextElement = NULL; PKIX_ENTER(LIST, "PKIX_List_DeleteItem"); PKIX_NULLCHECK_ONE(list); if (list->immutable){ PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST); } if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext), PKIX_LISTGETELEMENTFAILED); /* DecRef old contents */ PKIX_DECREF(element->item); nextElement = element->next; if (nextElement != NULL) { /* If the next element exists, splice it out. */ /* Don't need to change ref counts for targets of next */ element->item = nextElement->item; nextElement->item = NULL; /* Don't need to change ref counts for targets of next */ element->next = nextElement->next; nextElement->next = NULL; PKIX_DECREF(nextElement); } else { /* The element is at the tail of the list */ if (index != 0) { PKIX_CHECK(pkix_List_GetElement (list, index-1, &prevElement, plContext), PKIX_LISTGETELEMENTFAILED); } else if (index == 0){ /* prevElement must be header */ prevElement = list; } prevElement->next = NULL; /* Delete the element */ PKIX_DECREF(element); } PKIX_CHECK(PKIX_PL_Object_InvalidateCache ((PKIX_PL_Object *)list, plContext), PKIX_OBJECTINVALIDATECACHEFAILED); list->length = list->length - 1; cleanup: PKIX_RETURN(LIST); } /* * FUNCTION: PKIX_List_ReverseList (see comments in pkix_util.h) */ PKIX_Error * PKIX_List_ReverseList( PKIX_List *list, PKIX_List **pReversedList, void *plContext) { PKIX_List *reversedList = NULL; PKIX_PL_Object *item = NULL; PKIX_PL_Object *duplicateItem = NULL; PKIX_UInt32 length, i; PKIX_ENTER(LIST, "pkix_List_ReverseList"); PKIX_NULLCHECK_TWO(list, pReversedList); if (!list->isHeader){ PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER); } length = list->length; /* Create a new list object */ PKIX_CHECK(PKIX_List_Create(&reversedList, plContext), PKIX_LISTCREATEINTERNALFAILED); /* * Starting with the last item and traversing backwards (from * the original list), append each item to the reversed list */ for (i = 1; i <= length; i++){ PKIX_CHECK(PKIX_List_GetItem (list, (length - i), &item, plContext), PKIX_LISTGETITEMFAILED); PKIX_CHECK(PKIX_PL_Object_Duplicate (item, &duplicateItem, plContext), PKIX_LISTDUPLICATEFAILED); PKIX_CHECK(PKIX_List_AppendItem (reversedList, duplicateItem, plContext), PKIX_LISTAPPENDITEMFAILED); PKIX_DECREF(item); PKIX_DECREF(duplicateItem); } *pReversedList = reversedList; cleanup: PKIX_DECREF(item); PKIX_DECREF(duplicateItem); if (PKIX_ERROR_RECEIVED){ PKIX_DECREF(reversedList); } PKIX_RETURN(LIST); }