Back to index

lightning-sunbird  0.9+nobinonly
cmsarray.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is the Netscape security libraries.
00015  *
00016  * The Initial Developer of the Original Code is
00017  * Netscape Communications Corporation.
00018  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00019  * the Initial Developer. All Rights Reserved.
00020  *
00021  * Contributor(s):
00022  *
00023  * Alternatively, the contents of this file may be used under the terms of
00024  * either the GNU General Public License Version 2 or later (the "GPL"), or
00025  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00026  * in which case the provisions of the GPL or the LGPL are applicable instead
00027  * of those above. If you wish to allow use of your version of this file only
00028  * under the terms of either the GPL or the LGPL, and not to allow others to
00029  * use your version of this file under the terms of the MPL, indicate your
00030  * decision by deleting the provisions above and replace them with the notice
00031  * and other provisions required by the GPL or the LGPL. If you do not delete
00032  * the provisions above, a recipient may use your version of this file under
00033  * the terms of any one of the MPL, the GPL or the LGPL.
00034  *
00035  * ***** END LICENSE BLOCK ***** */
00036 
00037 /*
00038  * CMS array functions.
00039  *
00040  * $Id: cmsarray.c,v 1.5 2004/04/25 15:03:15 gerv%gerv.net Exp $
00041  */
00042 
00043 #include "cmslocal.h"
00044 
00045 #include "secerr.h"
00046 
00047 /*
00048  * ARRAY FUNCTIONS
00049  *
00050  * In NSS, arrays are rather primitive arrays of pointers.
00051  * Makes it easy to walk the array, but hard to count elements
00052  * and manage the storage.
00053  *
00054  * This is a feeble attempt to encapsulate the functionality
00055  * and get rid of hundreds of lines of similar code
00056  */
00057 
00058 /*
00059  * NSS_CMSArray_Alloc - allocate an array in an arena
00060  *
00061  * This allocates space for the array of pointers
00062  */
00063 void **
00064 NSS_CMSArray_Alloc(PRArenaPool *poolp, int n)
00065 {
00066     return (void **)PORT_ArenaZAlloc(poolp, n * sizeof(void *));
00067 }
00068 
00069 /*
00070  * NSS_CMSArray_Add - add an element to the end of an array
00071  *
00072  * The array of pointers is either created (if array was empty before) or grown.
00073  */
00074 SECStatus
00075 NSS_CMSArray_Add(PRArenaPool *poolp, void ***array, void *obj)
00076 {
00077     void **p;
00078     int n;
00079     void **dest;
00080 
00081     PORT_Assert(array != NULL);
00082     if (array == NULL)
00083        return SECFailure;
00084 
00085     if (*array == NULL) {
00086        dest = (void **)PORT_ArenaAlloc(poolp, 2 * sizeof(void *));
00087        n = 0;
00088     } else {
00089        n = 0; p = *array;
00090        while (*p++)
00091            n++;
00092        dest = (void **)PORT_ArenaGrow (poolp, 
00093                            *array,
00094                            (n + 1) * sizeof(void *),
00095                            (n + 2) * sizeof(void *));
00096     }
00097 
00098     if (dest == NULL)
00099        return SECFailure;
00100 
00101     dest[n] = obj;
00102     dest[n+1] = NULL;
00103     *array = dest;
00104     return SECSuccess;
00105 }
00106 
00107 /*
00108  * NSS_CMSArray_IsEmpty - check if array is empty
00109  */
00110 PRBool
00111 NSS_CMSArray_IsEmpty(void **array)
00112 {
00113     return (array == NULL || array[0] == NULL);
00114 }
00115 
00116 /*
00117  * NSS_CMSArray_Count - count number of elements in array
00118  */
00119 int
00120 NSS_CMSArray_Count(void **array)
00121 {
00122     int n = 0;
00123 
00124     if (array == NULL)
00125        return 0;
00126 
00127     while (*array++ != NULL)
00128        n++;
00129 
00130     return n;
00131 }
00132 
00133 /*
00134  * NSS_CMSArray_Sort - sort an array in place
00135  *
00136  * If "secondary" or "tertiary are not NULL, it must be arrays with the same
00137  *  number of elements as "primary". The same reordering will get applied to it.
00138  *
00139  * "compare" is a function that returns 
00140  *  < 0 when the first element is less than the second
00141  *  = 0 when the first element is equal to the second
00142  *  > 0 when the first element is greater than the second
00143  * to acheive ascending ordering.
00144  */
00145 void
00146 NSS_CMSArray_Sort(void **primary, int (*compare)(void *,void *), void **secondary, void **tertiary)
00147 {
00148     int n, i, limit, lastxchg;
00149     void *tmp;
00150 
00151     n = NSS_CMSArray_Count(primary);
00152 
00153     PORT_Assert(secondary == NULL || NSS_CMSArray_Count(secondary) == n);
00154     PORT_Assert(tertiary == NULL || NSS_CMSArray_Count(tertiary) == n);
00155     
00156     if (n <= 1)      /* ordering is fine */
00157        return;
00158     
00159     /* yes, ladies and gentlemen, it's BUBBLE SORT TIME! */
00160     limit = n - 1;
00161     while (1) {
00162        lastxchg = 0;
00163        for (i = 0; i < limit; i++) {
00164            if ((*compare)(primary[i], primary[i+1]) > 0) {
00165               /* exchange the neighbours */
00166               tmp = primary[i+1];
00167               primary[i+1] = primary[i];
00168               primary[i] = tmp;
00169               if (secondary) {            /* secondary array? */
00170                   tmp = secondary[i+1];   /* exchange there as well */
00171                   secondary[i+1] = secondary[i];
00172                   secondary[i] = tmp;
00173               }
00174               if (tertiary) {                    /* tertiary array? */
00175                   tmp = tertiary[i+1];    /* exchange there as well */
00176                   tertiary[i+1] = tertiary[i];
00177                   tertiary[i] = tmp;
00178               }
00179               lastxchg = i+1;      /* index of the last element bubbled up */
00180            }
00181        }
00182        if (lastxchg == 0)   /* no exchanges, so array is sorted */
00183            break;           /* we're done */
00184        limit = lastxchg;    /* array is sorted up to [limit] */
00185     }
00186 }
00187 
00188 #if 0
00189 
00190 /* array iterator stuff... not used */
00191 
00192 typedef void **NSSCMSArrayIterator;
00193 
00194 /* iterator */
00195 NSSCMSArrayIterator
00196 NSS_CMSArray_First(void **array)
00197 {
00198     if (array == NULL || array[0] == NULL)
00199        return NULL;
00200     return (NSSCMSArrayIterator)&(array[0]);
00201 }
00202 
00203 void *
00204 NSS_CMSArray_Obj(NSSCMSArrayIterator iter)
00205 {
00206     void **p = (void **)iter;
00207 
00208     return *iter;    /* which is NULL if we are at the end of the array */
00209 }
00210 
00211 NSSCMSArrayIterator
00212 NSS_CMSArray_Next(NSSCMSArrayIterator iter)
00213 {
00214     void **p = (void **)iter;
00215 
00216     return (NSSCMSArrayIterator)(p + 1);
00217 }
00218 
00219 #endif