OSX/libsecurity_smime/lib/cmsarray.c

   1 /*
   2  * The contents of this file are subject to the Mozilla Public
   3  * License Version 1.1 (the "License"); you may not use this file
   4  * except in compliance with the License. You may obtain a copy of
   5  * the License at http://www.mozilla.org/MPL/
   6  *
   7  * Software distributed under the License is distributed on an "AS
   8  * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
   9  * implied. See the License for the specific language governing
  10  * rights and limitations under the License.
  11  *
  12  * The Original Code is the Netscape security libraries.
  13  *
  14  * The Initial Developer of the Original Code is Netscape
  15  * Communications Corporation.  Portions created by Netscape are
  16  * Copyright (C) 1994-2000 Netscape Communications Corporation.  All
  17  * Rights Reserved.
  18  *
  19  * Contributor(s):
  20  *
  21  * Alternatively, the contents of this file may be used under the
  22  * terms of the GNU General Public License Version 2 or later (the
  23  * "GPL"), in which case the provisions of the GPL are applicable
  24  * instead of those above.  If you wish to allow use of your
  25  * version of this file only under the terms of the GPL and not to
  26  * allow others to use your version of this file under the MPL,
  27  * indicate your decision by deleting the provisions above and
  28  * replace them with the notice and other provisions required by
  29  * the GPL.  If you do not delete the provisions above, a recipient
  30  * may use your version of this file under either the MPL or the
  31  * GPL.
  32  */
  33
  34 /*
  35  * CMS array functions.
  36  */
  37
  38 #include "cmslocal.h"
  39
  40 #include <security_asn1/secerr.h>
  41
  42 /*
  43  * ARRAY FUNCTIONS
  44  *
  45  * In NSS, arrays are rather primitive arrays of pointers.
  46  * Makes it easy to walk the array, but hard to count elements
  47  * and manage the storage.
  48  *
  49  * This is a feeble attempt to encapsulate the functionality
  50  * and get rid of hundreds of lines of similar code
  51  */
  52
  53 /*
  54  * SecCmsArrayAlloc - allocate an array in an arena
  55  *
  56  * This allocates space for the array of pointers
  57  */
  58 void **
  59 SecCmsArrayAlloc(PRArenaPool *poolp, int n)
  60 {
  61     if (n>=(int)(INT_MAX/sizeof(void *))) {return (void **)NULL;} // Prevent under-allocation due to integer overflow
  62     return (void **)PORT_ArenaZAlloc(poolp, n * sizeof(void *));
  63 }
  64
  65 /*
  66  * SecCmsArrayAdd - add an element to the end of an array
  67  *
  68  * The array of pointers is either created (if array was empty before) or grown.
  69  */
  70 OSStatus
  71 SecCmsArrayAdd(PRArenaPool *poolp, void ***array, void *obj)
  72 {
  73     void **p;
  74     int n;
  75     void **dest;
  76
  77     PORT_Assert(array != NULL);
  78     if (array == NULL)
  79         return SECFailure;
  80
  81     if (*array == NULL) {
  82         dest = (void **)PORT_ArenaAlloc(poolp, 2 * sizeof(void *));
  83         n = 0;
  84     } else {
  85         n = 0; p = *array;
  86         while (*p++)
  87             n++;
  88         if (n>=(int)((INT_MAX/sizeof(void *))-2)) {
  89                 // Prevent under-allocation due to integer overflow
  90                 return SECFailure;
  91         }
  92         dest = (void **)PORT_ArenaGrow (poolp,
  93                               *array,
  94                               (n + 1) * sizeof(void *),
  95                               (n + 2) * sizeof(void *));
  96     }
  97
  98     if (dest == NULL)
  99         return SECFailure;
 100
 101     dest[n] = obj;
 102     dest[n+1] = NULL;
 103     *array = dest;
 104     return SECSuccess;
 105 }
 106
 107 /*
 108  * SecCmsArrayIsEmpty - check if array is empty
 109  */
 110 Boolean
 111 SecCmsArrayIsEmpty(void **array)
 112 {
 113     return (array == NULL || array[0] == NULL);
 114 }
 115
 116 /*
 117  * SecCmsArrayCount - count number of elements in array
 118  */
 119 int
 120 SecCmsArrayCount(void **array)
 121 {
 122     int n = 0;
 123
 124     if (array == NULL)
 125         return 0;
 126
 127     while (*array++ != NULL)
 128         n++;
 129
 130     return n;
 131 }
 132
 133 /*
 134  * SecCmsArraySort - sort an array in place
 135  *
 136  * If "secondary" or "tertiary are not NULL, it must be arrays with the same
 137  *  number of elements as "primary". The same reordering will get applied to it.
 138  *
 139  * "compare" is a function that returns
 140  *  < 0 when the first element is less than the second
 141  *  = 0 when the first element is equal to the second
 142  *  > 0 when the first element is greater than the second
 143  * to acheive ascending ordering.
 144  */
 145 void
 146 SecCmsArraySort(void **primary, int (*compare)(void *,void *), void **secondary, void **tertiary)
 147 {
 148     int n, i, limit, lastxchg;
 149     void *tmp;
 150     int n_2nd=0,n_3rd=0;
 151
 152     n = SecCmsArrayCount(primary);
 153
 154     PORT_Assert(secondary == NULL || SecCmsArrayCount(secondary) == n);
 155     PORT_Assert(tertiary == NULL || SecCmsArrayCount(tertiary) == n);
 156
 157     if (secondary) {
 158         n_2nd = SecCmsArrayCount(secondary);
 159     }
 160     if (tertiary) {
 161         n_3rd = SecCmsArrayCount(tertiary);
 162     }
 163
 164     if (n <= 1) /* ordering is fine */
 165         return;
 166
 167     /* yes, ladies and gentlemen, it's BUBBLE SORT TIME! */
 168     limit = n - 1;
 169     while (1) {
 170         lastxchg = 0;
 171         for (i = 0; i < limit; i++) {
 172             if ((*compare)(primary[i], primary[i+1]) > 0) {
 173                 /* exchange the neighbours */
 174                 tmp = primary[i+1];
 175                 primary[i+1] = primary[i];
 176                 primary[i] = tmp;
 177                 if (secondary && ((i+1)<n_2nd)) {/* secondary array? */
 178                     tmp = secondary[i+1];        /* exchange there as well */
 179                     secondary[i+1] = secondary[i];
 180                     secondary[i] = tmp;
 181                 }
 182                 if (tertiary && ((i+1)<n_3rd)) {/* tertiary array? */
 183                     tmp = tertiary[i+1];        /* exchange there as well */
 184                     tertiary[i+1] = tertiary[i];
 185                     tertiary[i] = tmp;
 186                 }
 187                 lastxchg = i+1; /* index of the last element bubbled up */
 188             }
 189         }
 190         if (lastxchg == 0)      /* no exchanges, so array is sorted */
 191             break;              /* we're done */
 192         limit = lastxchg;       /* array is sorted up to [limit] */
 193     }
 194 }
 195
 196 #if 0
 197
 198 /* array iterator stuff... not used */
 199
 200 typedef void **SecCmsArrayIterator;
 201
 202 /* iterator */
 203 SecCmsArrayIterator
 204 SecCmsArrayFirst(void **array)
 205 {
 206     if (array == NULL || array[0] == NULL)
 207         return NULL;
 208     return (SecCmsArrayIterator)&(array[0]);
 209 }
 210
 211 void *
 212 SecCmsArrayObj(SecCmsArrayIterator iter)
 213 {
 214     void **p = (void **)iter;
 215
 216     return *iter;       /* which is NULL if we are at the end of the array */
 217 }
 218
 219 SecCmsArrayIterator
 220 SecCmsArrayNext(SecCmsArrayIterator iter)
 221 {
 222     void **p = (void **)iter;
 223
 224     return (SecCmsArrayIterator)(p + 1);
 225 }
 226
 227 #endif