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