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 #include <security_asn1/secport.h>
  42
  43 /*
  44  * ARRAY FUNCTIONS
  45  *
  46  * In NSS, arrays are rather primitive arrays of pointers.
  47  * Makes it easy to walk the array, but hard to count elements
  48  * and manage the storage.
  49  *
  50  * This is a feeble attempt to encapsulate the functionality
  51  * and get rid of hundreds of lines of similar code
  52  */
  53
  54 /*
  55  * SecCmsArrayAlloc - allocate an array in an arena
  56  *
  57  * This allocates space for the array of pointers
  58  */
  59 void **
  60 SecCmsArrayAlloc(PRArenaPool *poolp, int n)
  61 {
  62     if (n>=(int)(INT_MAX/sizeof(void *))) {return (void **)NULL;} // Prevent under-allocation due to integer overflow
  63     return (void **)PORT_ArenaZAlloc(poolp, n * sizeof(void *));
  64 }
  65
  66 /*
  67  * SecCmsArrayAdd - add an element to the end of an array
  68  *
  69  * The array of pointers is either created (if array was empty before) or grown.
  70  */
  71 OSStatus
  72 SecCmsArrayAdd(PRArenaPool *poolp, void ***array, void *obj)
  73 {
  74     void **p;
  75     int n;
  76     void **dest;
  77
  78     PORT_Assert(array != NULL);
  79     if (array == NULL)
  80         return SECFailure;
  81
  82     if (*array == NULL) {
  83         dest = (void **)PORT_ArenaAlloc(poolp, 2 * sizeof(void *));
  84         n = 0;
  85     } else {
  86         n = 0; p = *array;
  87         while (*p++)
  88             n++;
  89         if (n>=(int)((INT_MAX/sizeof(void *))-2)) {
  90                 // Prevent under-allocation due to integer overflow
  91                 return SECFailure;
  92         }
  93         dest = (void **)PORT_ArenaGrow (poolp,
  94                               *array,
  95                               (n + 1) * sizeof(void *),
  96                               (n + 2) * sizeof(void *));
  97     }
  98
  99     if (dest == NULL)
 100         return SECFailure;
 101
 102     dest[n] = obj;
 103     dest[n+1] = NULL;
 104     *array = dest;
 105     return SECSuccess;
 106 }
 107
 108 /*
 109  * SecCmsArrayIsEmpty - check if array is empty
 110  */
 111 Boolean
 112 SecCmsArrayIsEmpty(void **array)
 113 {
 114     return (array == NULL || array[0] == NULL);
 115 }
 116
 117 /*
 118  * SecCmsArrayCount - count number of elements in array
 119  */
 120 int
 121 SecCmsArrayCount(void **array)
 122 {
 123     int n = 0;
 124
 125     if (array == NULL)
 126         return 0;
 127
 128     while (*array++ != NULL)
 129         n++;
 130
 131     return n;
 132 }
 133
 134 /*
 135  * SecCmsArraySort - sort an array in place
 136  *
 137  * If "secondary" or "tertiary are not NULL, it must be arrays with the same
 138  *  number of elements as "primary". The same reordering will get applied to it.
 139  *
 140  * "compare" is a function that returns
 141  *  < 0 when the first element is less than the second
 142  *  = 0 when the first element is equal to the second
 143  *  > 0 when the first element is greater than the second
 144  * to acheive ascending ordering.
 145  */
 146 void
 147 SecCmsArraySort(void **primary, int (*compare)(void *,void *), void **secondary, void **tertiary)
 148 {
 149     int n, i, limit, lastxchg;
 150     void *tmp;
 151     int n_2nd=0,n_3rd=0;
 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