1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/libpkix/pkix/util/pkix_list.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1701 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +/*
1.8 + * pkix_list.c
1.9 + *
1.10 + * List Object Functions
1.11 + *
1.12 + */
1.13 +
1.14 +#include "pkix_list.h"
1.15 +
1.16 +/* --Private-Functions-------------------------------------------- */
1.17 +
1.18 +/*
1.19 + * FUNCTION: pkix_List_Create_Internal
1.20 + * DESCRIPTION:
1.21 + *
1.22 + * Creates a new List, using the Boolean value of "isHeader" to determine
1.23 + * whether the new List should be a header, and stores it at "pList". The
1.24 + * List is initially empty and holds no items. To initially add items to
1.25 + * the List, use PKIX_List_AppendItem.
1.26 + *
1.27 + * PARAMETERS:
1.28 + * "isHeader"
1.29 + * Boolean value indicating whether new List should be a header.
1.30 + * "pList"
1.31 + * Address where object pointer will be stored. Must be non-NULL.
1.32 + * "plContext"
1.33 + * Platform-specific context pointer.
1.34 + * THREAD SAFETY:
1.35 + * Thread Safe (see Thread Safety Definitions in Programmer's Guide)
1.36 + * RETURNS:
1.37 + * Returns NULL if the function succeeds.
1.38 + * Returns a Fatal Error if the function fails in an unrecoverable way.
1.39 + */
1.40 +static PKIX_Error *
1.41 +pkix_List_Create_Internal(
1.42 + PKIX_Boolean isHeader,
1.43 + PKIX_List **pList,
1.44 + void *plContext)
1.45 +{
1.46 + PKIX_List *list = NULL;
1.47 +
1.48 + PKIX_ENTER(LIST, "pkix_List_Create_Internal");
1.49 + PKIX_NULLCHECK_ONE(pList);
1.50 +
1.51 + PKIX_CHECK(PKIX_PL_Object_Alloc
1.52 + (PKIX_LIST_TYPE,
1.53 + ((PKIX_UInt32)(sizeof (PKIX_List))),
1.54 + (PKIX_PL_Object **)&list, plContext),
1.55 + PKIX_ERRORCREATINGLISTITEM);
1.56 +
1.57 + list->item = NULL;
1.58 + list->next = NULL;
1.59 + list->immutable = PKIX_FALSE;
1.60 + list->length = 0;
1.61 + list->isHeader = isHeader;
1.62 +
1.63 + *pList = list;
1.64 +
1.65 +cleanup:
1.66 +
1.67 + PKIX_RETURN(LIST);
1.68 +}
1.69 +
1.70 +/*
1.71 + * FUNCTION: pkix_List_Destroy
1.72 + * (see comments for PKIX_PL_DestructorCallback in pkix_pl_system.h)
1.73 + */
1.74 +static PKIX_Error *
1.75 +pkix_List_Destroy(
1.76 + PKIX_PL_Object *object,
1.77 + void *plContext)
1.78 +{
1.79 + PKIX_List *list = NULL;
1.80 + PKIX_List *nextItem = NULL;
1.81 +
1.82 + PKIX_ENTER(LIST, "pkix_List_Destroy");
1.83 + PKIX_NULLCHECK_ONE(object);
1.84 +
1.85 + /* Check that this object is a list */
1.86 + PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext),
1.87 + PKIX_OBJECTNOTLIST);
1.88 +
1.89 + list = (PKIX_List *)object;
1.90 +
1.91 + /* We have a valid list. DecRef its item and recurse on next */
1.92 + PKIX_DECREF(list->item);
1.93 + while ((nextItem = list->next) != NULL) {
1.94 + list->next = nextItem->next;
1.95 + nextItem->next = NULL;
1.96 + PKIX_DECREF(nextItem);
1.97 + }
1.98 + list->immutable = PKIX_FALSE;
1.99 + list->length = 0;
1.100 + list->isHeader = PKIX_FALSE;
1.101 +
1.102 +cleanup:
1.103 +
1.104 + PKIX_RETURN(LIST);
1.105 +}
1.106 +
1.107 +/*
1.108 + * FUNCTION: pkix_List_ToString_Helper
1.109 + * DESCRIPTION:
1.110 + *
1.111 + * Helper function that creates a string representation of the List pointed
1.112 + * to by "list" and stores its address in the object pointed to by "pString".
1.113 + *
1.114 + * PARAMETERS
1.115 + * "list"
1.116 + * Address of List whose string representation is desired.
1.117 + * Must be non-NULL.
1.118 + * "pString"
1.119 + * Address of object pointer's destination. Must be non-NULL.
1.120 + * "plContext"
1.121 + * Platform-specific context pointer.
1.122 + * THREAD SAFETY:
1.123 + * Conditionally Thread Safe
1.124 + * (see Thread Safety Definitions in Programmer's Guide)
1.125 + * RETURNS:
1.126 + * Returns NULL if the function succeeds.
1.127 + * Returns a List Error if the function fails in a non-fatal way.
1.128 + * Returns a Fatal Error if the function fails in an unrecoverable way.
1.129 + */
1.130 +static PKIX_Error *
1.131 +pkix_List_ToString_Helper(
1.132 + PKIX_List *list,
1.133 + PKIX_PL_String **pString,
1.134 + void *plContext)
1.135 +{
1.136 + PKIX_PL_String *itemString = NULL;
1.137 + PKIX_PL_String *nextString = NULL;
1.138 + PKIX_PL_String *format = NULL;
1.139 + PKIX_Boolean empty;
1.140 +
1.141 + PKIX_ENTER(LIST, "pkix_List_ToString_Helper");
1.142 + PKIX_NULLCHECK_TWO(list, pString);
1.143 +
1.144 + /* special case when list is the header */
1.145 + if (list->isHeader){
1.146 +
1.147 + PKIX_CHECK(PKIX_List_IsEmpty(list, &empty, plContext),
1.148 + PKIX_LISTISEMPTYFAILED);
1.149 +
1.150 + if (empty){
1.151 + PKIX_CHECK(PKIX_PL_String_Create
1.152 + (PKIX_ESCASCII,
1.153 + "EMPTY",
1.154 + 0,
1.155 + &itemString,
1.156 + plContext),
1.157 + PKIX_ERRORCREATINGITEMSTRING);
1.158 + (*pString) = itemString;
1.159 + PKIX_DEBUG_EXIT(LIST);
1.160 + return (NULL);
1.161 + } else {
1.162 + PKIX_CHECK(pkix_List_ToString_Helper
1.163 + (list->next, &itemString, plContext),
1.164 + PKIX_LISTTOSTRINGHELPERFAILED);
1.165 + }
1.166 +
1.167 + /* Create a string object from the format */
1.168 + PKIX_CHECK(PKIX_PL_String_Create
1.169 + (PKIX_ESCASCII, "%s", 0, &format, plContext),
1.170 + PKIX_STRINGCREATEFAILED);
1.171 +
1.172 + PKIX_CHECK(PKIX_PL_Sprintf
1.173 + (pString, plContext, format, itemString),
1.174 + PKIX_SPRINTFFAILED);
1.175 + } else {
1.176 + /* Get a string for this list's item */
1.177 + if (list->item == NULL) {
1.178 + PKIX_CHECK(PKIX_PL_String_Create
1.179 + (PKIX_ESCASCII,
1.180 + "(null)",
1.181 + 0,
1.182 + &itemString,
1.183 + plContext),
1.184 + PKIX_STRINGCREATEFAILED);
1.185 + } else {
1.186 + PKIX_CHECK(PKIX_PL_Object_ToString
1.187 + ((PKIX_PL_Object*)list->item,
1.188 + &itemString,
1.189 + plContext),
1.190 + PKIX_OBJECTTOSTRINGFAILED);
1.191 + }
1.192 + if (list->next == NULL) {
1.193 + /* Just return the itemstring */
1.194 + (*pString) = itemString;
1.195 + PKIX_DEBUG_EXIT(LIST);
1.196 + return (NULL);
1.197 + }
1.198 +
1.199 + /* Recursive call to get string for this list's next pointer */
1.200 + PKIX_CHECK(pkix_List_ToString_Helper
1.201 + (list->next, &nextString, plContext),
1.202 + PKIX_LISTTOSTRINGHELPERFAILED);
1.203 +
1.204 + /* Create a string object from the format */
1.205 + PKIX_CHECK(PKIX_PL_String_Create
1.206 + (PKIX_ESCASCII,
1.207 + "%s, %s",
1.208 + 0,
1.209 + &format,
1.210 + plContext),
1.211 + PKIX_STRINGCREATEFAILED);
1.212 +
1.213 + PKIX_CHECK(PKIX_PL_Sprintf
1.214 + (pString,
1.215 + plContext,
1.216 + format,
1.217 + itemString,
1.218 + nextString),
1.219 + PKIX_SPRINTFFAILED);
1.220 + }
1.221 +
1.222 +cleanup:
1.223 +
1.224 + PKIX_DECREF(itemString);
1.225 + PKIX_DECREF(nextString);
1.226 + PKIX_DECREF(format);
1.227 +
1.228 + PKIX_RETURN(LIST);
1.229 +}
1.230 +
1.231 +/*
1.232 + * FUNCTION: pkix_List_ToString
1.233 + * (see comments for PKIX_PL_ToStringCallback in pkix_pl_system.h)
1.234 + */
1.235 +static PKIX_Error *
1.236 +pkix_List_ToString(
1.237 + PKIX_PL_Object *object,
1.238 + PKIX_PL_String **pString,
1.239 + void *plContext)
1.240 +{
1.241 + PKIX_List *list = NULL;
1.242 + PKIX_PL_String *listString = NULL;
1.243 + PKIX_PL_String *format = NULL;
1.244 +
1.245 + PKIX_ENTER(LIST, "pkix_List_ToString");
1.246 + PKIX_NULLCHECK_TWO(object, pString);
1.247 +
1.248 + PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext),
1.249 + PKIX_OBJECTNOTLIST);
1.250 +
1.251 + list = (PKIX_List *)object;
1.252 +
1.253 + if (!list->isHeader){
1.254 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.255 + }
1.256 +
1.257 + PKIX_CHECK(pkix_List_ToString_Helper(list, &listString, plContext),
1.258 + PKIX_LISTTOSTRINGHELPERFAILED);
1.259 +
1.260 + PKIX_CHECK(PKIX_PL_String_Create
1.261 + (PKIX_ESCASCII, "(%s)", 0, &format, plContext),
1.262 + PKIX_STRINGCREATEFAILED);
1.263 +
1.264 + PKIX_CHECK(PKIX_PL_Sprintf(pString, plContext, format, listString),
1.265 + PKIX_SPRINTFFAILED);
1.266 +
1.267 +cleanup:
1.268 +
1.269 + PKIX_DECREF(listString);
1.270 + PKIX_DECREF(format);
1.271 +
1.272 + PKIX_RETURN(LIST);
1.273 +}
1.274 +
1.275 +/*
1.276 + * FUNCTION: pkix_List_Equals
1.277 + * (see comments for PKIX_PL_EqualsCallback in pkix_pl_system.h)
1.278 + */
1.279 +static PKIX_Error *
1.280 +pkix_List_Equals(
1.281 + PKIX_PL_Object *first,
1.282 + PKIX_PL_Object *second,
1.283 + PKIX_Boolean *pResult,
1.284 + void *plContext)
1.285 +{
1.286 + PKIX_UInt32 secondType;
1.287 + PKIX_Boolean cmpResult;
1.288 + PKIX_List *firstList = NULL;
1.289 + PKIX_List *secondList = NULL;
1.290 + PKIX_UInt32 firstLength = 0;
1.291 + PKIX_UInt32 secondLength = 0;
1.292 + PKIX_PL_Object *firstItem = NULL;
1.293 + PKIX_PL_Object *secondItem = NULL;
1.294 + PKIX_UInt32 i = 0;
1.295 +
1.296 + PKIX_ENTER(LIST, "pkix_List_Equals");
1.297 + PKIX_NULLCHECK_THREE(first, second, pResult);
1.298 +
1.299 + /* test that first is a List */
1.300 + PKIX_CHECK(pkix_CheckType(first, PKIX_LIST_TYPE, plContext),
1.301 + PKIX_FIRSTOBJECTNOTLIST);
1.302 +
1.303 + /*
1.304 + * Since we know first is a List, if both references are
1.305 + * identical, they must be equal
1.306 + */
1.307 + if (first == second){
1.308 + *pResult = PKIX_TRUE;
1.309 + goto cleanup;
1.310 + }
1.311 +
1.312 + /*
1.313 + * If second isn't a List, we don't throw an error.
1.314 + * We simply return a Boolean result of FALSE
1.315 + */
1.316 + *pResult = PKIX_FALSE;
1.317 + PKIX_CHECK(PKIX_PL_Object_GetType(second, &secondType, plContext),
1.318 + PKIX_COULDNOTGETTYPEOFSECONDARGUMENT);
1.319 + if (secondType != PKIX_LIST_TYPE) goto cleanup;
1.320 +
1.321 + firstList = (PKIX_List *)first;
1.322 + secondList = (PKIX_List *)second;
1.323 +
1.324 + if ((!firstList->isHeader) && (!secondList->isHeader)){
1.325 + PKIX_ERROR(PKIX_INPUTLISTSMUSTBELISTHEADERS);
1.326 + }
1.327 +
1.328 + firstLength = firstList->length;
1.329 + secondLength = secondList->length;
1.330 +
1.331 + cmpResult = PKIX_FALSE;
1.332 + if (firstLength == secondLength){
1.333 + for (i = 0, cmpResult = PKIX_TRUE;
1.334 + ((i < firstLength) && cmpResult);
1.335 + i++){
1.336 + PKIX_CHECK(PKIX_List_GetItem
1.337 + (firstList, i, &firstItem, plContext),
1.338 + PKIX_LISTGETITEMFAILED);
1.339 +
1.340 + PKIX_CHECK(PKIX_List_GetItem
1.341 + (secondList, i, &secondItem, plContext),
1.342 + PKIX_LISTGETITEMFAILED);
1.343 +
1.344 + if ((!firstItem && secondItem) ||
1.345 + (firstItem && !secondItem)){
1.346 + cmpResult = PKIX_FALSE;
1.347 + } else if (!firstItem && !secondItem){
1.348 + continue;
1.349 + } else {
1.350 + PKIX_CHECK(PKIX_PL_Object_Equals
1.351 + (firstItem,
1.352 + secondItem,
1.353 + &cmpResult,
1.354 + plContext),
1.355 + PKIX_OBJECTEQUALSFAILED);
1.356 +
1.357 + PKIX_DECREF(firstItem);
1.358 + PKIX_DECREF(secondItem);
1.359 + }
1.360 + }
1.361 + }
1.362 +
1.363 + *pResult = cmpResult;
1.364 +
1.365 +cleanup:
1.366 +
1.367 + PKIX_DECREF(firstItem);
1.368 + PKIX_DECREF(secondItem);
1.369 +
1.370 + PKIX_RETURN(LIST);
1.371 +}
1.372 +
1.373 +/*
1.374 + * FUNCTION: pkix_List_Hashcode
1.375 + * (see comments for PKIX_PL_HashcodeCallback in pkix_pl_system.h)
1.376 + */
1.377 +static PKIX_Error *
1.378 +pkix_List_Hashcode(
1.379 + PKIX_PL_Object *object,
1.380 + PKIX_UInt32 *pHashcode,
1.381 + void *plContext)
1.382 +{
1.383 + PKIX_List *list = NULL;
1.384 + PKIX_PL_Object *element = NULL;
1.385 + PKIX_UInt32 hash = 0;
1.386 + PKIX_UInt32 tempHash = 0;
1.387 + PKIX_UInt32 length, i;
1.388 +
1.389 + PKIX_ENTER(LIST, "pkix_List_Hashcode");
1.390 + PKIX_NULLCHECK_TWO(object, pHashcode);
1.391 +
1.392 + PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext),
1.393 + PKIX_OBJECTNOTLIST);
1.394 +
1.395 + list = (PKIX_List *)object;
1.396 +
1.397 + if (!list->isHeader){
1.398 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.399 + }
1.400 +
1.401 + length = list->length;
1.402 +
1.403 + for (i = 0; i < length; i++){
1.404 + PKIX_CHECK(PKIX_List_GetItem(list, i, &element, plContext),
1.405 + PKIX_LISTGETITEMFAILED);
1.406 +
1.407 + if (!element){
1.408 + tempHash = 100;
1.409 + } else {
1.410 + PKIX_CHECK(PKIX_PL_Object_Hashcode
1.411 + (element, &tempHash, plContext),
1.412 + PKIX_LISTHASHCODEFAILED);
1.413 + }
1.414 +
1.415 + hash = 31 * hash + tempHash;
1.416 +
1.417 + PKIX_DECREF(element);
1.418 + }
1.419 +
1.420 + *pHashcode = hash;
1.421 +
1.422 +cleanup:
1.423 +
1.424 + PKIX_DECREF(element);
1.425 + PKIX_RETURN(LIST);
1.426 +}
1.427 +
1.428 +/*
1.429 + * FUNCTION: pkix_List_Duplicate
1.430 + * (see comments for PKIX_PL_DuplicateCallback in pkix_pl_system.h)
1.431 + */
1.432 +static PKIX_Error *
1.433 +pkix_List_Duplicate(
1.434 + PKIX_PL_Object *object,
1.435 + PKIX_PL_Object **pNewObject,
1.436 + void *plContext)
1.437 +{
1.438 + PKIX_List *list = NULL;
1.439 + PKIX_List *listDuplicate = NULL;
1.440 +
1.441 + PKIX_ENTER(LIST, "pkix_List_Duplicate");
1.442 + PKIX_NULLCHECK_TWO(object, pNewObject);
1.443 +
1.444 + PKIX_CHECK(pkix_CheckType(object, PKIX_LIST_TYPE, plContext),
1.445 + PKIX_OBJECTNOTLIST);
1.446 +
1.447 + list = (PKIX_List *)object;
1.448 +
1.449 + if (list->immutable){
1.450 + PKIX_CHECK(pkix_duplicateImmutable
1.451 + (object, pNewObject, plContext),
1.452 + PKIX_DUPLICATEIMMUTABLEFAILED);
1.453 + } else {
1.454 +
1.455 + PKIX_CHECK(pkix_List_Create_Internal
1.456 + (list->isHeader, &listDuplicate, plContext),
1.457 + PKIX_LISTCREATEINTERNALFAILED);
1.458 +
1.459 + listDuplicate->length = list->length;
1.460 +
1.461 + PKIX_INCREF(list->item);
1.462 + listDuplicate->item = list->item;
1.463 +
1.464 + if (list->next == NULL){
1.465 + listDuplicate->next = NULL;
1.466 + } else {
1.467 + /* Recursively Duplicate list */
1.468 + PKIX_CHECK(pkix_List_Duplicate
1.469 + ((PKIX_PL_Object *)list->next,
1.470 + (PKIX_PL_Object **)&listDuplicate->next,
1.471 + plContext),
1.472 + PKIX_LISTDUPLICATEFAILED);
1.473 + }
1.474 +
1.475 + *pNewObject = (PKIX_PL_Object *)listDuplicate;
1.476 + }
1.477 +
1.478 +cleanup:
1.479 +
1.480 + if (PKIX_ERROR_RECEIVED){
1.481 + PKIX_DECREF(listDuplicate);
1.482 + }
1.483 +
1.484 + PKIX_RETURN(LIST);
1.485 +}
1.486 +
1.487 +
1.488 +/*
1.489 + * FUNCTION: pkix_List_GetElement
1.490 + * DESCRIPTION:
1.491 + *
1.492 + * Copies the "list"'s element at "index" into "element". The input List must
1.493 + * be the header of the List (as opposed to being an element of the List). The
1.494 + * index counts from zero and must be less than the List's length. This
1.495 + * function does NOT increment the reference count of the List element since
1.496 + * the returned element's reference will not be stored by the calling
1.497 + * function.
1.498 + *
1.499 + * PARAMETERS:
1.500 + * "list"
1.501 + * Address of List (must be header) to get element from. Must be non-NULL.
1.502 + * "index"
1.503 + * Index of list to get element from. Must be less than List's length.
1.504 + * "pElement"
1.505 + * Address where object pointer will be stored. Must be non-NULL.
1.506 + * "plContext"
1.507 + * Platform-specific context pointer.
1.508 + * THREAD SAFETY:
1.509 + * Conditionally Thread Safe
1.510 + * (see Thread Safety Definitions in Programmer's Guide)
1.511 + * RETURNS:
1.512 + * Returns NULL if the function succeeds.
1.513 + * Returns a Fatal Error if the function fails in an unrecoverable way.
1.514 + */
1.515 +static PKIX_Error *
1.516 +pkix_List_GetElement(
1.517 + PKIX_List *list,
1.518 + PKIX_UInt32 index,
1.519 + PKIX_List **pElement,
1.520 + void *plContext)
1.521 +{
1.522 + PKIX_List *iterator = NULL;
1.523 + PKIX_UInt32 length;
1.524 + PKIX_UInt32 position = 0;
1.525 +
1.526 + PKIX_ENTER(LIST, "pkix_List_GetElement");
1.527 + PKIX_NULLCHECK_TWO(list, pElement);
1.528 +
1.529 + if (!list->isHeader){
1.530 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.531 + }
1.532 +
1.533 + length = list->length;
1.534 +
1.535 + if (index >= length) {
1.536 + PKIX_ERROR(PKIX_INDEXOUTOFBOUNDS);
1.537 + }
1.538 +
1.539 + for (iterator = list; position++ <= index; iterator = iterator->next)
1.540 + ;
1.541 +
1.542 + (*pElement) = iterator;
1.543 +
1.544 +cleanup:
1.545 +
1.546 + PKIX_RETURN(LIST);
1.547 +}
1.548 +
1.549 +
1.550 +/*
1.551 + * FUNCTION: pkix_List_RegisterSelf
1.552 + * DESCRIPTION:
1.553 + * Registers PKIX_LIST_TYPE and its related functions with systemClasses[]
1.554 + * THREAD SAFETY:
1.555 + * Not Thread Safe - for performance and complexity reasons
1.556 + *
1.557 + * Since this function is only called by PKIX_PL_Initialize, which should
1.558 + * only be called once, it is acceptable that this function is not
1.559 + * thread-safe.
1.560 + */
1.561 +PKIX_Error *
1.562 +pkix_List_RegisterSelf(void *plContext)
1.563 +{
1.564 + extern pkix_ClassTable_Entry systemClasses[PKIX_NUMTYPES];
1.565 + pkix_ClassTable_Entry entry;
1.566 +
1.567 + PKIX_ENTER(LIST, "pkix_List_RegisterSelf");
1.568 +
1.569 + entry.description = "List";
1.570 + entry.objCounter = 0;
1.571 + entry.typeObjectSize = sizeof(PKIX_List);
1.572 + entry.destructor = pkix_List_Destroy;
1.573 + entry.equalsFunction = pkix_List_Equals;
1.574 + entry.hashcodeFunction = pkix_List_Hashcode;
1.575 + entry.toStringFunction = pkix_List_ToString;
1.576 + entry.comparator = NULL;
1.577 + entry.duplicateFunction = pkix_List_Duplicate;
1.578 +
1.579 + systemClasses[PKIX_LIST_TYPE] = entry;
1.580 +
1.581 + PKIX_RETURN(LIST);
1.582 +}
1.583 +
1.584 +/*
1.585 + * FUNCTION: pkix_List_Contains
1.586 + * DESCRIPTION:
1.587 + *
1.588 + * Checks a List pointed to by "list", to determine whether it includes
1.589 + * an entry that is equal to the Object pointed to by "object", and stores
1.590 + * the result in "pFound".
1.591 + *
1.592 + * PARAMETERS:
1.593 + * "list"
1.594 + * List to be searched; may be empty; must be non-NULL
1.595 + * "object"
1.596 + * Object to be checked for; must be non-NULL
1.597 + * "pFound"
1.598 + * Address where the result of the search will be stored. Must
1.599 + * be non-NULL
1.600 + * "plContext"
1.601 + * platform-specific context pointer
1.602 + * THREAD SAFETY:
1.603 + * Thread Safe (see Thread Safety Definitions in Programmer's Guide)
1.604 + * RETURNS:
1.605 + * Returns NULL if the function succeeds
1.606 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.607 + */
1.608 +PKIX_Error *
1.609 +pkix_List_Contains(
1.610 + PKIX_List *list,
1.611 + PKIX_PL_Object *object,
1.612 + PKIX_Boolean *pFound,
1.613 + void *plContext)
1.614 +{
1.615 + PKIX_PL_Object *current = NULL;
1.616 + PKIX_UInt32 numEntries = 0;
1.617 + PKIX_UInt32 index = 0;
1.618 + PKIX_Boolean match = PKIX_FALSE;
1.619 +
1.620 + PKIX_ENTER(LIST, "pkix_List_Contains");
1.621 + PKIX_NULLCHECK_THREE(list, object, pFound);
1.622 +
1.623 + PKIX_CHECK(PKIX_List_GetLength(list, &numEntries, plContext),
1.624 + PKIX_LISTGETLENGTHFAILED);
1.625 +
1.626 + for (index = 0; index < numEntries; index++) {
1.627 + PKIX_CHECK(PKIX_List_GetItem
1.628 + (list, index, ¤t, plContext),
1.629 + PKIX_LISTGETITEMFAILED);
1.630 +
1.631 + if (current) {
1.632 + PKIX_CHECK(PKIX_PL_Object_Equals
1.633 + (object, current, &match, plContext),
1.634 + PKIX_OBJECTEQUALSFAILED);
1.635 +
1.636 + PKIX_DECREF(current);
1.637 + }
1.638 +
1.639 + if (match) {
1.640 + break;
1.641 + }
1.642 + }
1.643 +
1.644 + *pFound = match;
1.645 +
1.646 +cleanup:
1.647 +
1.648 + PKIX_DECREF(current);
1.649 + PKIX_RETURN(LIST);
1.650 +}
1.651 +
1.652 +/*
1.653 + * FUNCTION: pkix_List_Remove
1.654 + * DESCRIPTION:
1.655 + *
1.656 + * Traverses the List pointed to by "list", to find and delete an entry
1.657 + * that is equal to the Object pointed to by "object". If no such entry
1.658 + * is found the function does not return an error.
1.659 + *
1.660 + * PARAMETERS:
1.661 + * "list"
1.662 + * List to be searched; may be empty; must be non-NULL
1.663 + * "object"
1.664 + * Object to be checked for and deleted, if found; must be non-NULL
1.665 + * "plContext"
1.666 + * platform-specific context pointer
1.667 + * THREAD SAFETY:
1.668 + * Thread Safe (see Thread Safety Definitions in Programmer's Guide)
1.669 + * RETURNS:
1.670 + * Returns NULL if the function succeeds
1.671 + * Returns a Validate Error if the functions fails in a non-fatal way
1.672 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.673 + */
1.674 +PKIX_Error *
1.675 +pkix_List_Remove(
1.676 + PKIX_List *list,
1.677 + PKIX_PL_Object *object,
1.678 + void *plContext)
1.679 +{
1.680 + PKIX_PL_Object *current = NULL;
1.681 + PKIX_UInt32 numEntries = 0;
1.682 + PKIX_UInt32 index = 0;
1.683 + PKIX_Boolean match = PKIX_FALSE;
1.684 +
1.685 + PKIX_ENTER(LIST, "pkix_List_Remove");
1.686 + PKIX_NULLCHECK_TWO(list, object);
1.687 +
1.688 + PKIX_CHECK(PKIX_List_GetLength(list, &numEntries, plContext),
1.689 + PKIX_LISTGETLENGTHFAILED);
1.690 +
1.691 + for (index = 0; index < numEntries; index++) {
1.692 + PKIX_CHECK(PKIX_List_GetItem
1.693 + (list, index, ¤t, plContext),
1.694 + PKIX_LISTGETITEMFAILED);
1.695 +
1.696 + if (current) {
1.697 + PKIX_CHECK(PKIX_PL_Object_Equals
1.698 + (object, current, &match, plContext),
1.699 + PKIX_OBJECTEQUALSFAILED);
1.700 +
1.701 + PKIX_DECREF(current);
1.702 + }
1.703 +
1.704 + if (match) {
1.705 + PKIX_CHECK(PKIX_List_DeleteItem
1.706 + (list, index, plContext),
1.707 + PKIX_LISTDELETEITEMFAILED);
1.708 + break;
1.709 + }
1.710 + }
1.711 +
1.712 +cleanup:
1.713 +
1.714 + PKIX_DECREF(current);
1.715 + PKIX_RETURN(LIST);
1.716 +}
1.717 +
1.718 +/*
1.719 + * FUNCTION: pkix_List_RemoveItems
1.720 + * DESCRIPTION:
1.721 + *
1.722 + * Traverses the List pointed to by "list", to find and delete an entry
1.723 + * that is equal to the Object in the "deleteList". If no such entry
1.724 + * is found the function does not return an error.
1.725 + *
1.726 + * PARAMETERS:
1.727 + * "list"
1.728 + * Object in "list" is checked for object in "deleteList" and deleted if
1.729 + * found; may be empty; must be non-NULL
1.730 + * "deleteList"
1.731 + * List of objects to be searched ; may be empty; must be non-NULL
1.732 + * "plContext"
1.733 + * platform-specific context pointer
1.734 + * THREAD SAFETY:
1.735 + * Thread Safe (see Thread Safety Definitions in Programmer's Guide)
1.736 + * RETURNS:
1.737 + * Returns NULL if the function succeeds
1.738 + * Returns a Validate Error if the functions fails in a non-fatal way
1.739 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.740 + */
1.741 +PKIX_Error *
1.742 +pkix_List_RemoveItems(
1.743 + PKIX_List *list,
1.744 + PKIX_List *deleteList,
1.745 + void *plContext)
1.746 +{
1.747 + PKIX_PL_Object *current = NULL;
1.748 + PKIX_UInt32 numEntries = 0;
1.749 + PKIX_UInt32 index = 0;
1.750 +
1.751 + PKIX_ENTER(LIST, "pkix_List_RemoveItems");
1.752 + PKIX_NULLCHECK_TWO(list, deleteList);
1.753 +
1.754 + PKIX_CHECK(PKIX_List_GetLength(deleteList, &numEntries, plContext),
1.755 + PKIX_LISTGETLENGTHFAILED);
1.756 +
1.757 + for (index = 0; index < numEntries; index++) {
1.758 + PKIX_CHECK(PKIX_List_GetItem
1.759 + (deleteList, index, ¤t, plContext),
1.760 + PKIX_LISTGETITEMFAILED);
1.761 +
1.762 + if (current) {
1.763 + PKIX_CHECK(pkix_List_Remove
1.764 + (list, current, plContext),
1.765 + PKIX_OBJECTEQUALSFAILED);
1.766 +
1.767 + PKIX_DECREF(current);
1.768 + }
1.769 + }
1.770 +
1.771 +cleanup:
1.772 +
1.773 + PKIX_DECREF(current);
1.774 + PKIX_RETURN(LIST);
1.775 +}
1.776 +
1.777 +/*
1.778 + * FUNCTION: pkix_List_MergeLists
1.779 + * DESCRIPTION:
1.780 + *
1.781 + * Creates a new list consisting of the items from "firstList", followed by
1.782 + * the items on "secondList", returns the new list at "pMergedList". If
1.783 + * both input lists are NULL or empty, the result is an empty list. If an error
1.784 + * occurs, the result is NULL.
1.785 + *
1.786 + * PARAMETERS:
1.787 + * "firstList"
1.788 + * Address of list to be merged from. May be NULL or empty.
1.789 + * "secondList"
1.790 + * Address of list to be merged from. May be NULL or empty.
1.791 + * "pMergedList"
1.792 + * Address where returned object is stored.
1.793 + * "plContext"
1.794 + * platform-specific context pointer * THREAD SAFETY:
1.795 + * Thread Safe (see Thread Safety Definitions in Programmer's Guide)
1.796 + * RETURNS:
1.797 + * Returns NULL if the function succeeds
1.798 + * Returns a List Error if the functions fails in a non-fatal way
1.799 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.800 + */
1.801 +PKIX_Error *
1.802 +pkix_List_MergeLists(
1.803 + PKIX_List *firstList,
1.804 + PKIX_List *secondList,
1.805 + PKIX_List **pMergedList,
1.806 + void *plContext)
1.807 +{
1.808 + PKIX_List *list = NULL;
1.809 + PKIX_PL_Object *item = NULL;
1.810 + PKIX_UInt32 numItems = 0;
1.811 + PKIX_UInt32 i;
1.812 +
1.813 + PKIX_ENTER(LIST, "pkix_List_MergeLists");
1.814 + PKIX_NULLCHECK_ONE(pMergedList);
1.815 +
1.816 + *pMergedList = NULL;
1.817 +
1.818 + PKIX_CHECK(PKIX_List_Create(&list, plContext),
1.819 + PKIX_LISTCREATEFAILED);
1.820 +
1.821 + if (firstList != NULL) {
1.822 +
1.823 + PKIX_CHECK(PKIX_List_GetLength(firstList, &numItems, plContext),
1.824 + PKIX_LISTGETLENGTHFAILED);
1.825 + }
1.826 +
1.827 + for (i = 0; i < numItems; i++) {
1.828 +
1.829 + PKIX_CHECK(PKIX_List_GetItem(firstList, i, &item, plContext),
1.830 + PKIX_LISTGETITEMFAILED);
1.831 +
1.832 + PKIX_CHECK(PKIX_List_AppendItem(list, item, plContext),
1.833 + PKIX_LISTAPPENDITEMFAILED);
1.834 +
1.835 + PKIX_DECREF(item);
1.836 + }
1.837 +
1.838 + numItems = 0;
1.839 + if (secondList != NULL) {
1.840 +
1.841 + PKIX_CHECK(PKIX_List_GetLength
1.842 + (secondList,
1.843 + &numItems,
1.844 + plContext),
1.845 + PKIX_LISTGETLENGTHFAILED);
1.846 +
1.847 + }
1.848 +
1.849 + for (i = 0; i < numItems; i++) {
1.850 +
1.851 + PKIX_CHECK(PKIX_List_GetItem
1.852 + (secondList, i, &item, plContext),
1.853 + PKIX_LISTGETITEMFAILED);
1.854 +
1.855 + PKIX_CHECK(PKIX_List_AppendItem
1.856 + (list, item, plContext), PKIX_LISTAPPENDITEMFAILED);
1.857 +
1.858 + PKIX_DECREF(item);
1.859 + }
1.860 +
1.861 + *pMergedList = list;
1.862 + list = NULL;
1.863 +
1.864 +cleanup:
1.865 + PKIX_DECREF(list);
1.866 + PKIX_DECREF(item);
1.867 +
1.868 + PKIX_RETURN(LIST);
1.869 +}
1.870 +
1.871 +/*
1.872 + * FUNCTION: pkix_List_AppendList
1.873 + * DESCRIPTION:
1.874 + *
1.875 + * Append items on "fromList" to the "toList". Item reference count on
1.876 + * "toList" is not incremented, but items appended from "fromList" are
1.877 + * incremented.
1.878 + *
1.879 + * PARAMETERS:
1.880 + * "toList"
1.881 + * Address of list to be appended to. Must be non-NULL.
1.882 + * "fromList"
1.883 + * Address of list to be appended from. May be NULL or empty.
1.884 + * "plContext"
1.885 + * platform-specific context pointer
1.886 + * THREAD SAFETY:
1.887 + * Thread Safe (see Thread Safety Definitions in Programmer's Guide)
1.888 + * RETURNS:
1.889 + * Returns NULL if the function succeeds
1.890 + * Returns a List Error if the functions fails in a non-fatal way
1.891 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.892 + */
1.893 +PKIX_Error *
1.894 +pkix_List_AppendList(
1.895 + PKIX_List *toList,
1.896 + PKIX_List *fromList,
1.897 + void *plContext)
1.898 +{
1.899 + PKIX_PL_Object *item = NULL;
1.900 + PKIX_UInt32 numItems = 0;
1.901 + PKIX_UInt32 i;
1.902 +
1.903 + PKIX_ENTER(LIST, "pkix_List_AppendList");
1.904 + PKIX_NULLCHECK_ONE(toList);
1.905 +
1.906 + /* if fromList is NULL or is an empty list, no action */
1.907 +
1.908 + if (fromList == NULL) {
1.909 + goto cleanup;
1.910 + }
1.911 +
1.912 + PKIX_CHECK(PKIX_List_GetLength(fromList, &numItems, plContext),
1.913 + PKIX_LISTGETLENGTHFAILED);
1.914 +
1.915 + if (numItems == 0) {
1.916 + goto cleanup;
1.917 + }
1.918 +
1.919 + for (i = 0; i < numItems; i++) {
1.920 +
1.921 + PKIX_CHECK(PKIX_List_GetItem
1.922 + (fromList, i, &item, plContext),
1.923 + PKIX_LISTGETITEMFAILED);
1.924 +
1.925 + PKIX_CHECK(PKIX_List_AppendItem(toList, item, plContext),
1.926 + PKIX_LISTAPPENDITEMFAILED);
1.927 +
1.928 + PKIX_DECREF(item);
1.929 + }
1.930 +
1.931 +cleanup:
1.932 +
1.933 + PKIX_DECREF(item);
1.934 +
1.935 + PKIX_RETURN(LIST);
1.936 +}
1.937 +
1.938 +/*
1.939 + * FUNCTION: pkix_List_AppendUnique
1.940 + * DESCRIPTION:
1.941 + *
1.942 + * Adds each Object in the List pointed to by "fromList" to the List pointed
1.943 + * to by "toList", if it is not already a member of that List. In other words,
1.944 + * "toList" becomes the union of the two sets.
1.945 + *
1.946 + * PARAMETERS:
1.947 + * "toList"
1.948 + * Address of a List of Objects to be augmented by "fromList". Must be
1.949 + * non-NULL, but may be empty.
1.950 + * "fromList"
1.951 + * Address of a List of Objects to be added, if not already present, to
1.952 + * "toList". Must be non-NULL, but may be empty.
1.953 + * "plContext"
1.954 + * Platform-specific context pointer.
1.955 + * THREAD SAFETY:
1.956 + * Not Thread Safe - assumes exclusive access to "toList"
1.957 + * (see Thread Safety Definitions in Programmer's Guide)
1.958 + * RETURNS:
1.959 + * Returns NULL if the function succeeds
1.960 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.961 + */
1.962 +PKIX_Error *
1.963 +pkix_List_AppendUnique(
1.964 + PKIX_List *toList,
1.965 + PKIX_List *fromList,
1.966 + void *plContext)
1.967 +{
1.968 + PKIX_Boolean isContained = PKIX_FALSE;
1.969 + PKIX_UInt32 listLen = 0;
1.970 + PKIX_UInt32 listIx = 0;
1.971 + PKIX_PL_Object *object = NULL;
1.972 +
1.973 + PKIX_ENTER(BUILD, "pkix_List_AppendUnique");
1.974 + PKIX_NULLCHECK_TWO(fromList, toList);
1.975 +
1.976 + PKIX_CHECK(PKIX_List_GetLength(fromList, &listLen, plContext),
1.977 + PKIX_LISTGETLENGTHFAILED);
1.978 +
1.979 + for (listIx = 0; listIx < listLen; listIx++) {
1.980 +
1.981 + PKIX_CHECK(PKIX_List_GetItem
1.982 + (fromList, listIx, &object, plContext),
1.983 + PKIX_LISTGETITEMFAILED);
1.984 +
1.985 + PKIX_CHECK(pkix_List_Contains
1.986 + (toList, object, &isContained, plContext),
1.987 + PKIX_LISTCONTAINSFAILED);
1.988 +
1.989 + if (isContained == PKIX_FALSE) {
1.990 + PKIX_CHECK(PKIX_List_AppendItem
1.991 + (toList, object, plContext),
1.992 + PKIX_LISTAPPENDITEMFAILED);
1.993 + }
1.994 +
1.995 + PKIX_DECREF(object);
1.996 + }
1.997 +
1.998 +cleanup:
1.999 +
1.1000 + PKIX_DECREF(object);
1.1001 +
1.1002 + PKIX_RETURN(LIST);
1.1003 +}
1.1004 +
1.1005 +/*
1.1006 + * FUNCTION: pkix_List_QuickSort
1.1007 + * DESCRIPTION:
1.1008 + *
1.1009 + * Sorts List of Objects "fromList" using "comparatorCallback"'s result as
1.1010 + * comasrison key and returns the sorted List at "pSortedList". The sorting
1.1011 + * algorithm used is quick sort (n*logn).
1.1012 + *
1.1013 + * PARAMETERS:
1.1014 + * "fromList"
1.1015 + * Address of a List of Objects to be sorted. Must be non-NULL, but may be
1.1016 + * empty.
1.1017 + * "comparatorCallback"
1.1018 + * Address of callback function that will compare two Objects on the List.
1.1019 + * It should return -1 for less, 0 for equal and 1 for greater. The
1.1020 + * callback implementation chooses what in Objects to be compared. Must be
1.1021 + * non-NULL.
1.1022 + * "pSortedList"
1.1023 + * Address of a List of Objects that shall be sorted and returned. Must be
1.1024 + * non-NULL, but may be empty.
1.1025 + * "plContext"
1.1026 + * Platform-specific context pointer.
1.1027 + * THREAD SAFETY:
1.1028 + * Not Thread Safe - assumes exclusive access to "toList"
1.1029 + * (see Thread Safety Definitions in Programmer's Guide)
1.1030 + * RETURNS:
1.1031 + * Returns NULL if the function succeeds
1.1032 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.1033 + */
1.1034 +PKIX_Error *
1.1035 +pkix_List_QuickSort(
1.1036 + PKIX_List *fromList,
1.1037 + PKIX_List_SortComparatorCallback comparator,
1.1038 + PKIX_List **pSortedList,
1.1039 + void *plContext)
1.1040 +{
1.1041 + PKIX_List *sortedList = NULL;
1.1042 + PKIX_List *lessList = NULL;
1.1043 + PKIX_List *greaterList = NULL;
1.1044 + PKIX_List *sortedLessList = NULL;
1.1045 + PKIX_List *sortedGreaterList = NULL;
1.1046 + PKIX_PL_Object *object = NULL;
1.1047 + PKIX_PL_Object *cmpObj = NULL;
1.1048 + PKIX_Int32 cmpResult = 0;
1.1049 + PKIX_UInt32 size = 0;
1.1050 + PKIX_UInt32 i;
1.1051 +
1.1052 + PKIX_ENTER(BUILD, "pkix_List_QuickSort");
1.1053 + PKIX_NULLCHECK_THREE(fromList, comparator, pSortedList);
1.1054 +
1.1055 + PKIX_CHECK(PKIX_List_GetLength(fromList, &size, plContext),
1.1056 + PKIX_LISTGETLENGTHFAILED);
1.1057 +
1.1058 + PKIX_CHECK(PKIX_List_Create(&lessList, plContext),
1.1059 + PKIX_LISTCREATEFAILED);
1.1060 +
1.1061 + PKIX_CHECK(PKIX_List_Create(&greaterList, plContext),
1.1062 + PKIX_LISTCREATEFAILED);
1.1063 +
1.1064 + PKIX_CHECK(PKIX_List_GetItem
1.1065 + (fromList, 0, &object, plContext),
1.1066 + PKIX_LISTGETITEMFAILED);
1.1067 +
1.1068 + /*
1.1069 + * Pick the first item on the list as the one to be compared.
1.1070 + * Separate rest of the itmes into two lists: less-than or greater-
1.1071 + * than lists. Sort those two lists recursively. Insert sorted
1.1072 + * less-than list before the picked item and append the greater-
1.1073 + * than list after the picked item.
1.1074 + */
1.1075 + for (i = 1; i < size; i++) {
1.1076 +
1.1077 + PKIX_CHECK(PKIX_List_GetItem
1.1078 + (fromList, i, &cmpObj, plContext),
1.1079 + PKIX_LISTGETITEMFAILED);
1.1080 +
1.1081 + PKIX_CHECK(comparator(object, cmpObj, &cmpResult, plContext),
1.1082 + PKIX_COMPARATORCALLBACKFAILED);
1.1083 +
1.1084 + if (cmpResult >= 0) {
1.1085 + PKIX_CHECK(PKIX_List_AppendItem
1.1086 + (lessList, cmpObj, plContext),
1.1087 + PKIX_LISTAPPENDITEMFAILED);
1.1088 + } else {
1.1089 + PKIX_CHECK(PKIX_List_AppendItem
1.1090 + (greaterList, cmpObj, plContext),
1.1091 + PKIX_LISTAPPENDITEMFAILED);
1.1092 + }
1.1093 + PKIX_DECREF(cmpObj);
1.1094 + }
1.1095 +
1.1096 + PKIX_CHECK(PKIX_List_Create(&sortedList, plContext),
1.1097 + PKIX_LISTCREATEFAILED);
1.1098 +
1.1099 + PKIX_CHECK(PKIX_List_GetLength(lessList, &size, plContext),
1.1100 + PKIX_LISTGETLENGTHFAILED);
1.1101 +
1.1102 + if (size > 1) {
1.1103 +
1.1104 + PKIX_CHECK(pkix_List_QuickSort
1.1105 + (lessList, comparator, &sortedLessList, plContext),
1.1106 + PKIX_LISTQUICKSORTFAILED);
1.1107 +
1.1108 + PKIX_CHECK(pkix_List_AppendList
1.1109 + (sortedList, sortedLessList, plContext),
1.1110 + PKIX_LISTAPPENDLISTFAILED);
1.1111 + } else {
1.1112 + PKIX_CHECK(pkix_List_AppendList
1.1113 + (sortedList, lessList, plContext),
1.1114 + PKIX_LISTAPPENDLISTFAILED);
1.1115 + }
1.1116 +
1.1117 + PKIX_CHECK(PKIX_List_AppendItem(sortedList, object, plContext),
1.1118 + PKIX_LISTAPPENDFAILED);
1.1119 +
1.1120 + PKIX_CHECK(PKIX_List_GetLength(greaterList, &size, plContext),
1.1121 + PKIX_LISTGETLENGTHFAILED);
1.1122 +
1.1123 + if (size > 1) {
1.1124 +
1.1125 + PKIX_CHECK(pkix_List_QuickSort
1.1126 + (greaterList, comparator, &sortedGreaterList, plContext),
1.1127 + PKIX_LISTQUICKSORTFAILED);
1.1128 +
1.1129 + PKIX_CHECK(pkix_List_AppendList
1.1130 + (sortedList, sortedGreaterList, plContext),
1.1131 + PKIX_LISTAPPENDLISTFAILED);
1.1132 + } else {
1.1133 + PKIX_CHECK(pkix_List_AppendList
1.1134 + (sortedList, greaterList, plContext),
1.1135 + PKIX_LISTAPPENDLISTFAILED);
1.1136 + }
1.1137 +
1.1138 + *pSortedList = sortedList;
1.1139 +
1.1140 +cleanup:
1.1141 +
1.1142 + PKIX_DECREF(cmpObj);
1.1143 + PKIX_DECREF(object);
1.1144 + PKIX_DECREF(sortedGreaterList);
1.1145 + PKIX_DECREF(sortedLessList);
1.1146 + PKIX_DECREF(greaterList);
1.1147 + PKIX_DECREF(lessList);
1.1148 +
1.1149 + PKIX_RETURN(LIST);
1.1150 +}
1.1151 +
1.1152 +/*
1.1153 + * FUNCTION: pkix_List_BubbleSort
1.1154 + * DESCRIPTION:
1.1155 + *
1.1156 + * Sorts List of Objects "fromList" using "comparatorCallback"'s result as
1.1157 + * comasrison key and returns the sorted List at "pSortedList". The sorting
1.1158 + * algorithm used is bubble sort (n*n).
1.1159 + *
1.1160 + * PARAMETERS:
1.1161 + * "fromList"
1.1162 + * Address of a List of Objects to be sorted. Must be non-NULL, but may be
1.1163 + * empty.
1.1164 + * "comparatorCallback"
1.1165 + * Address of callback function that will compare two Objects on the List.
1.1166 + * It should return -1 for less, 0 for equal and 1 for greater. The
1.1167 + * callback implementation chooses what in Objects to be compared. Must be
1.1168 + * non-NULL.
1.1169 + * "pSortedList"
1.1170 + * Address of a List of Objects that shall be sorted and returned. Must be
1.1171 + * non-NULL, but may be empty.
1.1172 + * "plContext"
1.1173 + * Platform-specific context pointer.
1.1174 + * THREAD SAFETY:
1.1175 + * Not Thread Safe - assumes exclusive access to "toList"
1.1176 + * (see Thread Safety Definitions in Programmer's Guide)
1.1177 + * RETURNS:
1.1178 + * Returns NULL if the function succeeds
1.1179 + * Returns a Fatal Error if the function fails in an unrecoverable way
1.1180 + */
1.1181 +PKIX_Error *
1.1182 +pkix_List_BubbleSort(
1.1183 + PKIX_List *fromList,
1.1184 + PKIX_List_SortComparatorCallback comparator,
1.1185 + PKIX_List **pSortedList,
1.1186 + void *plContext)
1.1187 +{
1.1188 + PKIX_List *sortedList = NULL;
1.1189 + PKIX_PL_Object *cmpObj = NULL;
1.1190 + PKIX_PL_Object *leastObj = NULL;
1.1191 + PKIX_Int32 cmpResult = 0;
1.1192 + PKIX_UInt32 size = 0;
1.1193 + PKIX_UInt32 i, j;
1.1194 +
1.1195 + PKIX_ENTER(BUILD, "pkix_List_BubbleSort");
1.1196 + PKIX_NULLCHECK_THREE(fromList, comparator, pSortedList);
1.1197 +
1.1198 + if (fromList->immutable) {
1.1199 + PKIX_ERROR(PKIX_CANNOTSORTIMMUTABLELIST);
1.1200 + }
1.1201 + PKIX_CHECK(pkix_List_Duplicate
1.1202 + ((PKIX_PL_Object *) fromList,
1.1203 + (PKIX_PL_Object **) &sortedList,
1.1204 + plContext),
1.1205 + PKIX_LISTDUPLICATEFAILED);
1.1206 +
1.1207 + PKIX_CHECK(PKIX_List_GetLength(sortedList, &size, plContext),
1.1208 + PKIX_LISTGETLENGTHFAILED);
1.1209 +
1.1210 + if (size > 1) {
1.1211 +
1.1212 + /*
1.1213 + * Move from the first of the item on the list, For each iteration,
1.1214 + * compare and swap the least value to the head of the comparisoning
1.1215 + * sub-list.
1.1216 + */
1.1217 + for (i = 0; i < size - 1; i++) {
1.1218 +
1.1219 + PKIX_CHECK(PKIX_List_GetItem
1.1220 + (sortedList, i, &leastObj, plContext),
1.1221 + PKIX_LISTGETITEMFAILED);
1.1222 +
1.1223 + for (j = i + 1; j < size; j++) {
1.1224 + PKIX_CHECK(PKIX_List_GetItem
1.1225 + (sortedList, j, &cmpObj, plContext),
1.1226 + PKIX_LISTGETITEMFAILED);
1.1227 + PKIX_CHECK(comparator
1.1228 + (leastObj, cmpObj, &cmpResult, plContext),
1.1229 + PKIX_COMPARATORCALLBACKFAILED);
1.1230 + if (cmpResult > 0) {
1.1231 + PKIX_CHECK(PKIX_List_SetItem
1.1232 + (sortedList, j, leastObj, plContext),
1.1233 + PKIX_LISTSETITEMFAILED);
1.1234 +
1.1235 + PKIX_DECREF(leastObj);
1.1236 + leastObj = cmpObj;
1.1237 + cmpObj = NULL;
1.1238 + } else {
1.1239 + PKIX_DECREF(cmpObj);
1.1240 + }
1.1241 + }
1.1242 + PKIX_CHECK(PKIX_List_SetItem
1.1243 + (sortedList, i, leastObj, plContext),
1.1244 + PKIX_LISTSETITEMFAILED);
1.1245 +
1.1246 + PKIX_DECREF(leastObj);
1.1247 + }
1.1248 +
1.1249 + }
1.1250 +
1.1251 + *pSortedList = sortedList;
1.1252 + sortedList = NULL;
1.1253 +cleanup:
1.1254 +
1.1255 + PKIX_DECREF(sortedList);
1.1256 + PKIX_DECREF(leastObj);
1.1257 + PKIX_DECREF(cmpObj);
1.1258 +
1.1259 + PKIX_RETURN(LIST);
1.1260 +}
1.1261 +
1.1262 +/* --Public-List-Functions--------------------------------------------- */
1.1263 +
1.1264 +/*
1.1265 + * FUNCTION: PKIX_List_Create (see comments in pkix_util.h)
1.1266 + */
1.1267 +PKIX_Error *
1.1268 +PKIX_List_Create(
1.1269 + PKIX_List **pList,
1.1270 + void *plContext)
1.1271 +{
1.1272 + PKIX_List *list = NULL;
1.1273 +
1.1274 + PKIX_ENTER(LIST, "PKIX_List_Create");
1.1275 + PKIX_NULLCHECK_ONE(pList);
1.1276 +
1.1277 + PKIX_CHECK(pkix_List_Create_Internal(PKIX_TRUE, &list, plContext),
1.1278 + PKIX_LISTCREATEINTERNALFAILED);
1.1279 +
1.1280 + *pList = list;
1.1281 +
1.1282 +cleanup:
1.1283 +
1.1284 + PKIX_RETURN(LIST);
1.1285 +}
1.1286 +
1.1287 +/*
1.1288 + * FUNCTION: PKIX_List_SetImmutable (see comments in pkix_util.h)
1.1289 + */
1.1290 +PKIX_Error *
1.1291 +PKIX_List_SetImmutable(
1.1292 + PKIX_List *list,
1.1293 + void *plContext)
1.1294 +{
1.1295 + PKIX_ENTER(LIST, "PKIX_List_SetImmutable");
1.1296 + PKIX_NULLCHECK_ONE(list);
1.1297 +
1.1298 + if (!list->isHeader){
1.1299 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1300 + }
1.1301 +
1.1302 + list->immutable = PKIX_TRUE;
1.1303 +
1.1304 +cleanup:
1.1305 +
1.1306 + PKIX_RETURN(LIST);
1.1307 +}
1.1308 +
1.1309 +/*
1.1310 + * FUNCTION: PKIX_List_IsImmutable (see comments in pkix_util.h)
1.1311 + */
1.1312 +PKIX_Error *
1.1313 +PKIX_List_IsImmutable(
1.1314 + PKIX_List *list,
1.1315 + PKIX_Boolean *pImmutable,
1.1316 + void *plContext)
1.1317 +{
1.1318 + PKIX_ENTER(LIST, "PKIX_List_IsImmutable");
1.1319 + PKIX_NULLCHECK_TWO(list, pImmutable);
1.1320 +
1.1321 + if (!list->isHeader){
1.1322 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1323 + }
1.1324 +
1.1325 + *pImmutable = list->immutable;
1.1326 +
1.1327 +cleanup:
1.1328 +
1.1329 + PKIX_RETURN(LIST);
1.1330 +}
1.1331 +
1.1332 +/*
1.1333 + * FUNCTION: PKIX_List_GetLength (see comments in pkix_util.h)
1.1334 + */
1.1335 +PKIX_Error *
1.1336 +PKIX_List_GetLength(
1.1337 + PKIX_List *list,
1.1338 + PKIX_UInt32 *pLength,
1.1339 + void *plContext)
1.1340 +{
1.1341 + PKIX_ENTER(LIST, "PKIX_List_GetLength");
1.1342 + PKIX_NULLCHECK_TWO(list, pLength);
1.1343 +
1.1344 + if (!list->isHeader){
1.1345 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1346 + }
1.1347 +
1.1348 + *pLength = list->length;
1.1349 +
1.1350 +cleanup:
1.1351 +
1.1352 + PKIX_RETURN(LIST);
1.1353 +}
1.1354 +
1.1355 +/*
1.1356 + * FUNCTION: PKIX_List_IsEmpty (see comments in pkix_util.h)
1.1357 + */
1.1358 +PKIX_Error *
1.1359 +PKIX_List_IsEmpty(
1.1360 + PKIX_List *list,
1.1361 + PKIX_Boolean *pEmpty,
1.1362 + void *plContext)
1.1363 +{
1.1364 + PKIX_UInt32 length;
1.1365 +
1.1366 + PKIX_ENTER(LIST, "PKIX_List_IsEmpty");
1.1367 + PKIX_NULLCHECK_TWO(list, pEmpty);
1.1368 +
1.1369 + if (!list->isHeader){
1.1370 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1371 + }
1.1372 +
1.1373 + length = list->length;
1.1374 +
1.1375 + if (length == 0){
1.1376 + *pEmpty = PKIX_TRUE;
1.1377 + } else {
1.1378 + *pEmpty = PKIX_FALSE;
1.1379 + }
1.1380 +
1.1381 +cleanup:
1.1382 +
1.1383 + PKIX_RETURN(LIST);
1.1384 +}
1.1385 +
1.1386 +/*
1.1387 + * FUNCTION: PKIX_List_AppendItem (see comments in pkix_util.h)
1.1388 + */
1.1389 +PKIX_Error *
1.1390 +PKIX_List_AppendItem(
1.1391 + PKIX_List *list,
1.1392 + PKIX_PL_Object *item,
1.1393 + void *plContext)
1.1394 +{
1.1395 + PKIX_List *lastElement = NULL;
1.1396 + PKIX_List *newElement = NULL;
1.1397 + PKIX_UInt32 length, i;
1.1398 +
1.1399 + PKIX_ENTER(LIST, "PKIX_List_AppendItem");
1.1400 + PKIX_NULLCHECK_ONE(list);
1.1401 +
1.1402 + if (list->immutable){
1.1403 + PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST);
1.1404 + }
1.1405 +
1.1406 + if (!list->isHeader){
1.1407 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1408 + }
1.1409 +
1.1410 + length = list->length;
1.1411 +
1.1412 + /* find last element of list and create new element there */
1.1413 +
1.1414 + lastElement = list;
1.1415 + for (i = 0; i < length; i++){
1.1416 + lastElement = lastElement->next;
1.1417 + }
1.1418 +
1.1419 + PKIX_CHECK(pkix_List_Create_Internal
1.1420 + (PKIX_FALSE, &newElement, plContext),
1.1421 + PKIX_LISTCREATEINTERNALFAILED);
1.1422 +
1.1423 + PKIX_INCREF(item);
1.1424 + newElement->item = item;
1.1425 +
1.1426 + PKIX_CHECK(PKIX_PL_Object_InvalidateCache
1.1427 + ((PKIX_PL_Object *)list, plContext),
1.1428 + PKIX_OBJECTINVALIDATECACHEFAILED);
1.1429 +
1.1430 + lastElement->next = newElement;
1.1431 + newElement = NULL;
1.1432 + list->length += 1;
1.1433 +
1.1434 +cleanup:
1.1435 +
1.1436 + PKIX_DECREF(newElement);
1.1437 +
1.1438 + PKIX_RETURN(LIST);
1.1439 +}
1.1440 +
1.1441 +/*
1.1442 + * FUNCTION: PKIX_List_InsertItem (see comments in pkix_util.h)
1.1443 + */
1.1444 +PKIX_Error *
1.1445 +PKIX_List_InsertItem(
1.1446 + PKIX_List *list,
1.1447 + PKIX_UInt32 index,
1.1448 + PKIX_PL_Object *item,
1.1449 + void *plContext)
1.1450 +{
1.1451 + PKIX_List *element = NULL;
1.1452 + PKIX_List *newElem = NULL;
1.1453 +
1.1454 + PKIX_ENTER(LIST, "PKIX_List_InsertItem");
1.1455 + PKIX_NULLCHECK_ONE(list);
1.1456 +
1.1457 +
1.1458 + if (list->immutable){
1.1459 + PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST);
1.1460 + }
1.1461 +
1.1462 + if (!list->isHeader){
1.1463 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1464 + }
1.1465 +
1.1466 + /* Create a new list object */
1.1467 + PKIX_CHECK(pkix_List_Create_Internal(PKIX_FALSE, &newElem, plContext),
1.1468 + PKIX_LISTCREATEINTERNALFAILED);
1.1469 +
1.1470 + if (list->length) {
1.1471 + PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext),
1.1472 + PKIX_LISTGETELEMENTFAILED);
1.1473 + /* Copy the old element's contents into the new element */
1.1474 + newElem->item = element->item;
1.1475 + /* Add new item to the list */
1.1476 + PKIX_INCREF(item);
1.1477 + element->item = item;
1.1478 + /* Set the new element's next pointer to the old element's next */
1.1479 + newElem->next = element->next;
1.1480 + /* Set the old element's next pointer to the new element */
1.1481 + element->next = newElem;
1.1482 + newElem = NULL;
1.1483 + } else {
1.1484 + PKIX_INCREF(item);
1.1485 + newElem->item = item;
1.1486 + newElem->next = NULL;
1.1487 + list->next = newElem;
1.1488 + newElem = NULL;
1.1489 + }
1.1490 + list->length++;
1.1491 +
1.1492 + PKIX_CHECK(PKIX_PL_Object_InvalidateCache
1.1493 + ((PKIX_PL_Object *)list, plContext),
1.1494 + PKIX_OBJECTINVALIDATECACHEFAILED);
1.1495 +cleanup:
1.1496 + PKIX_DECREF(newElem);
1.1497 +
1.1498 + PKIX_RETURN(LIST);
1.1499 +}
1.1500 +
1.1501 +/*
1.1502 + * FUNCTION: PKIX_List_GetItem (see comments in pkix_util.h)
1.1503 + */
1.1504 +PKIX_Error *
1.1505 +PKIX_List_GetItem(
1.1506 + PKIX_List *list,
1.1507 + PKIX_UInt32 index,
1.1508 + PKIX_PL_Object **pItem,
1.1509 + void *plContext)
1.1510 +{
1.1511 + PKIX_List *element = NULL;
1.1512 +
1.1513 + PKIX_ENTER(LIST, "PKIX_List_GetItem");
1.1514 + PKIX_NULLCHECK_TWO(list, pItem);
1.1515 +
1.1516 + if (!list->isHeader){
1.1517 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1518 + }
1.1519 +
1.1520 + PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext),
1.1521 + PKIX_LISTGETELEMENTFAILED);
1.1522 +
1.1523 + PKIX_INCREF(element->item);
1.1524 + *pItem = element->item;
1.1525 +
1.1526 +cleanup:
1.1527 +
1.1528 + PKIX_RETURN(LIST);
1.1529 +}
1.1530 +
1.1531 +/*
1.1532 + * FUNCTION: PKIX_List_SetItem (see comments in pkix_util.h)
1.1533 + */
1.1534 +PKIX_Error *
1.1535 +PKIX_List_SetItem(
1.1536 + PKIX_List *list,
1.1537 + PKIX_UInt32 index,
1.1538 + PKIX_PL_Object *item,
1.1539 + void *plContext)
1.1540 +{
1.1541 + PKIX_List *element;
1.1542 +
1.1543 + PKIX_ENTER(LIST, "PKIX_List_SetItem");
1.1544 + PKIX_NULLCHECK_ONE(list);
1.1545 +
1.1546 + if (list->immutable){
1.1547 + PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST);
1.1548 + }
1.1549 +
1.1550 + if (!list->isHeader){
1.1551 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1552 + }
1.1553 +
1.1554 + PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext),
1.1555 + PKIX_LISTGETELEMENTFAILED);
1.1556 +
1.1557 + /* DecRef old contents */
1.1558 + PKIX_DECREF(element->item);
1.1559 +
1.1560 + /* Set New Contents */
1.1561 + PKIX_INCREF(item);
1.1562 + element->item = item;
1.1563 +
1.1564 + PKIX_CHECK(PKIX_PL_Object_InvalidateCache
1.1565 + ((PKIX_PL_Object *)list, plContext),
1.1566 + PKIX_OBJECTINVALIDATECACHEFAILED);
1.1567 +
1.1568 +cleanup:
1.1569 +
1.1570 + PKIX_RETURN(LIST);
1.1571 +}
1.1572 +
1.1573 +/*
1.1574 + * FUNCTION: PKIX_List_DeleteItem (see comments in pkix_util.h)
1.1575 + */
1.1576 +PKIX_Error *
1.1577 +PKIX_List_DeleteItem(
1.1578 + PKIX_List *list,
1.1579 + PKIX_UInt32 index,
1.1580 + void *plContext)
1.1581 +{
1.1582 + PKIX_List *element = NULL;
1.1583 + PKIX_List *prevElement = NULL;
1.1584 + PKIX_List *nextElement = NULL;
1.1585 +
1.1586 + PKIX_ENTER(LIST, "PKIX_List_DeleteItem");
1.1587 + PKIX_NULLCHECK_ONE(list);
1.1588 +
1.1589 + if (list->immutable){
1.1590 + PKIX_ERROR(PKIX_OPERATIONNOTPERMITTEDONIMMUTABLELIST);
1.1591 + }
1.1592 +
1.1593 + if (!list->isHeader){
1.1594 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1595 + }
1.1596 +
1.1597 + PKIX_CHECK(pkix_List_GetElement(list, index, &element, plContext),
1.1598 + PKIX_LISTGETELEMENTFAILED);
1.1599 +
1.1600 + /* DecRef old contents */
1.1601 + PKIX_DECREF(element->item);
1.1602 +
1.1603 + nextElement = element->next;
1.1604 +
1.1605 + if (nextElement != NULL) {
1.1606 + /* If the next element exists, splice it out. */
1.1607 +
1.1608 + /* Don't need to change ref counts for targets of next */
1.1609 + element->item = nextElement->item;
1.1610 + nextElement->item = NULL;
1.1611 +
1.1612 + /* Don't need to change ref counts for targets of next */
1.1613 + element->next = nextElement->next;
1.1614 + nextElement->next = NULL;
1.1615 +
1.1616 + PKIX_DECREF(nextElement);
1.1617 +
1.1618 + } else { /* The element is at the tail of the list */
1.1619 + if (index != 0) {
1.1620 + PKIX_CHECK(pkix_List_GetElement
1.1621 + (list, index-1, &prevElement, plContext),
1.1622 + PKIX_LISTGETELEMENTFAILED);
1.1623 + } else if (index == 0){ /* prevElement must be header */
1.1624 + prevElement = list;
1.1625 + }
1.1626 + prevElement->next = NULL;
1.1627 +
1.1628 + /* Delete the element */
1.1629 + PKIX_DECREF(element);
1.1630 + }
1.1631 +
1.1632 + PKIX_CHECK(PKIX_PL_Object_InvalidateCache
1.1633 + ((PKIX_PL_Object *)list, plContext),
1.1634 + PKIX_OBJECTINVALIDATECACHEFAILED);
1.1635 +
1.1636 + list->length = list->length - 1;
1.1637 +
1.1638 +cleanup:
1.1639 +
1.1640 + PKIX_RETURN(LIST);
1.1641 +}
1.1642 +
1.1643 +/*
1.1644 + * FUNCTION: PKIX_List_ReverseList (see comments in pkix_util.h)
1.1645 + */
1.1646 +PKIX_Error *
1.1647 +PKIX_List_ReverseList(
1.1648 + PKIX_List *list,
1.1649 + PKIX_List **pReversedList,
1.1650 + void *plContext)
1.1651 +{
1.1652 + PKIX_List *reversedList = NULL;
1.1653 + PKIX_PL_Object *item = NULL;
1.1654 + PKIX_PL_Object *duplicateItem = NULL;
1.1655 + PKIX_UInt32 length, i;
1.1656 +
1.1657 + PKIX_ENTER(LIST, "pkix_List_ReverseList");
1.1658 + PKIX_NULLCHECK_TWO(list, pReversedList);
1.1659 +
1.1660 + if (!list->isHeader){
1.1661 + PKIX_ERROR(PKIX_INPUTLISTMUSTBEHEADER);
1.1662 + }
1.1663 +
1.1664 + length = list->length;
1.1665 +
1.1666 + /* Create a new list object */
1.1667 + PKIX_CHECK(PKIX_List_Create(&reversedList, plContext),
1.1668 + PKIX_LISTCREATEINTERNALFAILED);
1.1669 +
1.1670 + /*
1.1671 + * Starting with the last item and traversing backwards (from
1.1672 + * the original list), append each item to the reversed list
1.1673 + */
1.1674 +
1.1675 + for (i = 1; i <= length; i++){
1.1676 + PKIX_CHECK(PKIX_List_GetItem
1.1677 + (list, (length - i), &item, plContext),
1.1678 + PKIX_LISTGETITEMFAILED);
1.1679 +
1.1680 + PKIX_CHECK(PKIX_PL_Object_Duplicate
1.1681 + (item, &duplicateItem, plContext),
1.1682 + PKIX_LISTDUPLICATEFAILED);
1.1683 +
1.1684 + PKIX_CHECK(PKIX_List_AppendItem
1.1685 + (reversedList, duplicateItem, plContext),
1.1686 + PKIX_LISTAPPENDITEMFAILED);
1.1687 +
1.1688 + PKIX_DECREF(item);
1.1689 + PKIX_DECREF(duplicateItem);
1.1690 + }
1.1691 +
1.1692 + *pReversedList = reversedList;
1.1693 +
1.1694 +cleanup:
1.1695 +
1.1696 + PKIX_DECREF(item);
1.1697 + PKIX_DECREF(duplicateItem);
1.1698 +
1.1699 + if (PKIX_ERROR_RECEIVED){
1.1700 + PKIX_DECREF(reversedList);
1.1701 + }
1.1702 +
1.1703 + PKIX_RETURN(LIST);
1.1704 +}
