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