michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * CMS array functions.
michael@0:  */
michael@0: 
michael@0: #include "cmslocal.h"
michael@0: 
michael@0: #include "secerr.h"
michael@0: 
michael@0: /*
michael@0:  * ARRAY FUNCTIONS
michael@0:  *
michael@0:  * In NSS, arrays are rather primitive arrays of pointers.
michael@0:  * Makes it easy to walk the array, but hard to count elements
michael@0:  * and manage the storage.
michael@0:  *
michael@0:  * This is a feeble attempt to encapsulate the functionality
michael@0:  * and get rid of hundreds of lines of similar code
michael@0:  */
michael@0: 
michael@0: /*
michael@0:  * NSS_CMSArray_Alloc - allocate an array in an arena
michael@0:  *
michael@0:  * This allocates space for the array of pointers
michael@0:  */
michael@0: void **
michael@0: NSS_CMSArray_Alloc(PLArenaPool *poolp, int n)
michael@0: {
michael@0:     return (void **)PORT_ArenaZAlloc(poolp, n * sizeof(void *));
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * NSS_CMSArray_Add - add an element to the end of an array
michael@0:  *
michael@0:  * The array of pointers is either created (if array was empty before) or grown.
michael@0:  */
michael@0: SECStatus
michael@0: NSS_CMSArray_Add(PLArenaPool *poolp, void ***array, void *obj)
michael@0: {
michael@0:     void **p;
michael@0:     int n;
michael@0:     void **dest;
michael@0: 
michael@0:     PORT_Assert(array != NULL);
michael@0:     if (array == NULL)
michael@0: 	return SECFailure;
michael@0: 
michael@0:     if (*array == NULL) {
michael@0: 	dest = (void **)PORT_ArenaAlloc(poolp, 2 * sizeof(void *));
michael@0: 	n = 0;
michael@0:     } else {
michael@0: 	n = 0; p = *array;
michael@0: 	while (*p++)
michael@0: 	    n++;
michael@0: 	dest = (void **)PORT_ArenaGrow (poolp, 
michael@0: 			      *array,
michael@0: 			      (n + 1) * sizeof(void *),
michael@0: 			      (n + 2) * sizeof(void *));
michael@0:     }
michael@0: 
michael@0:     if (dest == NULL)
michael@0: 	return SECFailure;
michael@0: 
michael@0:     dest[n] = obj;
michael@0:     dest[n+1] = NULL;
michael@0:     *array = dest;
michael@0:     return SECSuccess;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * NSS_CMSArray_IsEmpty - check if array is empty
michael@0:  */
michael@0: PRBool
michael@0: NSS_CMSArray_IsEmpty(void **array)
michael@0: {
michael@0:     return (array == NULL || array[0] == NULL);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * NSS_CMSArray_Count - count number of elements in array
michael@0:  */
michael@0: int
michael@0: NSS_CMSArray_Count(void **array)
michael@0: {
michael@0:     int n = 0;
michael@0: 
michael@0:     if (array == NULL)
michael@0: 	return 0;
michael@0: 
michael@0:     while (*array++ != NULL)
michael@0: 	n++;
michael@0: 
michael@0:     return n;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * NSS_CMSArray_Sort - sort an array in place
michael@0:  *
michael@0:  * If "secondary" or "tertiary are not NULL, it must be arrays with the same
michael@0:  *  number of elements as "primary". The same reordering will get applied to it.
michael@0:  *
michael@0:  * "compare" is a function that returns 
michael@0:  *  < 0 when the first element is less than the second
michael@0:  *  = 0 when the first element is equal to the second
michael@0:  *  > 0 when the first element is greater than the second
michael@0:  * to acheive ascending ordering.
michael@0:  */
michael@0: void
michael@0: NSS_CMSArray_Sort(void **primary, int (*compare)(void *,void *), void **secondary, void **tertiary)
michael@0: {
michael@0:     int n, i, limit, lastxchg;
michael@0:     void *tmp;
michael@0: 
michael@0:     n = NSS_CMSArray_Count(primary);
michael@0: 
michael@0:     PORT_Assert(secondary == NULL || NSS_CMSArray_Count(secondary) == n);
michael@0:     PORT_Assert(tertiary == NULL || NSS_CMSArray_Count(tertiary) == n);
michael@0:     
michael@0:     if (n <= 1)	/* ordering is fine */
michael@0: 	return;
michael@0:     
michael@0:     /* yes, ladies and gentlemen, it's BUBBLE SORT TIME! */
michael@0:     limit = n - 1;
michael@0:     while (1) {
michael@0: 	lastxchg = 0;
michael@0: 	for (i = 0; i < limit; i++) {
michael@0: 	    if ((*compare)(primary[i], primary[i+1]) > 0) {
michael@0: 		/* exchange the neighbours */
michael@0: 		tmp = primary[i+1];
michael@0: 		primary[i+1] = primary[i];
michael@0: 		primary[i] = tmp;
michael@0: 		if (secondary) {		/* secondary array? */
michael@0: 		    tmp = secondary[i+1];	/* exchange there as well */
michael@0: 		    secondary[i+1] = secondary[i];
michael@0: 		    secondary[i] = tmp;
michael@0: 		}
michael@0: 		if (tertiary) {			/* tertiary array? */
michael@0: 		    tmp = tertiary[i+1];	/* exchange there as well */
michael@0: 		    tertiary[i+1] = tertiary[i];
michael@0: 		    tertiary[i] = tmp;
michael@0: 		}
michael@0: 		lastxchg = i+1;	/* index of the last element bubbled up */
michael@0: 	    }
michael@0: 	}
michael@0: 	if (lastxchg == 0)	/* no exchanges, so array is sorted */
michael@0: 	    break;		/* we're done */
michael@0: 	limit = lastxchg;	/* array is sorted up to [limit] */
michael@0:     }
michael@0: }
michael@0: 
michael@0: #if 0
michael@0: 
michael@0: /* array iterator stuff... not used */
michael@0: 
michael@0: typedef void **NSSCMSArrayIterator;
michael@0: 
michael@0: /* iterator */
michael@0: NSSCMSArrayIterator
michael@0: NSS_CMSArray_First(void **array)
michael@0: {
michael@0:     if (array == NULL || array[0] == NULL)
michael@0: 	return NULL;
michael@0:     return (NSSCMSArrayIterator)&(array[0]);
michael@0: }
michael@0: 
michael@0: void *
michael@0: NSS_CMSArray_Obj(NSSCMSArrayIterator iter)
michael@0: {
michael@0:     void **p = (void **)iter;
michael@0: 
michael@0:     return *iter;	/* which is NULL if we are at the end of the array */
michael@0: }
michael@0: 
michael@0: NSSCMSArrayIterator
michael@0: NSS_CMSArray_Next(NSSCMSArrayIterator iter)
michael@0: {
michael@0:     void **p = (void **)iter;
michael@0: 
michael@0:     return (NSSCMSArrayIterator)(p + 1);
michael@0: }
michael@0: 
michael@0: #endif