1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay@cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay@cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] */ 56 57#include <openssl/stack.h> 58 59#include <openssl/mem.h> 60 61/* kMinSize is the number of pointers that will be initially allocated in a new 62 * stack. */ 63static const size_t kMinSize = 4; 64 65_STACK *sk_new(stack_cmp_func comp) { 66 _STACK *ret; 67 68 ret = OPENSSL_malloc(sizeof(_STACK)); 69 if (ret == NULL) { 70 goto err; 71 } 72 memset(ret, 0, sizeof(_STACK)); 73 74 ret->data = OPENSSL_malloc(sizeof(void *) * kMinSize); 75 if (ret->data == NULL) { 76 goto err; 77 } 78 79 memset(ret->data, 0, sizeof(void *) * kMinSize); 80 81 ret->comp = comp; 82 ret->num_alloc = kMinSize; 83 84 return ret; 85 86err: 87 if (ret) { 88 OPENSSL_free(ret); 89 } 90 return NULL; 91} 92 93_STACK *sk_new_null(void) { return sk_new(NULL); } 94 95size_t sk_num(const _STACK *sk) { 96 if (sk == NULL) { 97 return 0; 98 } 99 return sk->num; 100} 101 102void sk_zero(_STACK *sk) { 103 if (sk == NULL || sk->num == 0) { 104 return; 105 } 106 memset(sk->data, 0, sizeof(void*) * sk->num); 107 sk->num = 0; 108 sk->sorted = 0; 109} 110 111void *sk_value(const _STACK *sk, size_t i) { 112 if (!sk || i >= sk->num) { 113 return NULL; 114 } 115 return sk->data[i]; 116} 117 118void *sk_set(_STACK *sk, size_t i, void *value) { 119 if (!sk || i >= sk->num) { 120 return NULL; 121 } 122 return sk->data[i] = value; 123} 124 125void sk_free(_STACK *sk) { 126 if (sk == NULL) { 127 return; 128 } 129 OPENSSL_free(sk->data); 130 OPENSSL_free(sk); 131} 132 133void sk_pop_free(_STACK *sk, void (*func)(void *)) { 134 size_t i; 135 136 if (sk == NULL) { 137 return; 138 } 139 140 for (i = 0; i < sk->num; i++) { 141 if (sk->data[i] != NULL) { 142 func(sk->data[i]); 143 } 144 } 145 sk_free(sk); 146} 147 148size_t sk_insert(_STACK *sk, void *p, size_t where) { 149 if (sk == NULL) { 150 return 0; 151 } 152 153 if (sk->num_alloc <= sk->num + 1) { 154 /* Attempt to double the size of the array. */ 155 size_t new_alloc = sk->num_alloc << 1; 156 size_t alloc_size = new_alloc * sizeof(void *); 157 void **data; 158 159 /* If the doubling overflowed, try to increment. */ 160 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) { 161 new_alloc = sk->num_alloc + 1; 162 alloc_size = new_alloc * sizeof(void *); 163 } 164 165 /* If the increment also overflowed, fail. */ 166 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) { 167 return 0; 168 } 169 170 data = OPENSSL_realloc(sk->data, alloc_size); 171 if (data == NULL) { 172 return 0; 173 } 174 175 sk->data = data; 176 sk->num_alloc = new_alloc; 177 } 178 179 if (where >= sk->num) { 180 sk->data[sk->num] = p; 181 } else { 182 memmove(&sk->data[where + 1], &sk->data[where], 183 sizeof(void *) * (sk->num - where)); 184 sk->data[where] = p; 185 } 186 187 sk->num++; 188 sk->sorted = 0; 189 190 return sk->num; 191} 192 193void *sk_delete(_STACK *sk, size_t where) { 194 void *ret; 195 196 if (!sk || where >= sk->num) { 197 return NULL; 198 } 199 200 ret = sk->data[where]; 201 202 if (where != sk->num - 1) { 203 memmove(&sk->data[where], &sk->data[where + 1], 204 sizeof(void *) * (sk->num - where - 1)); 205 } 206 207 sk->num--; 208 return ret; 209} 210 211void *sk_delete_ptr(_STACK *sk, void *p) { 212 size_t i; 213 214 if (sk == NULL) { 215 return NULL; 216 } 217 218 for (i = 0; i < sk->num; i++) { 219 if (sk->data[i] == p) { 220 return sk_delete(sk, i); 221 } 222 } 223 224 return NULL; 225} 226 227int sk_find(_STACK *sk, size_t *out_index, void *p) { 228 const void *const *r; 229 size_t i; 230 int (*comp_func)(const void *,const void *); 231 232 if (sk == NULL) { 233 return -1; 234 } 235 236 if (sk->comp == NULL) { 237 /* Use pointer equality when no comparison function has been set. */ 238 for (i = 0; i < sk->num; i++) { 239 if (sk->data[i] == p) { 240 if (out_index) { 241 *out_index = i; 242 } 243 return 1; 244 } 245 } 246 return 0; 247 } 248 249 if (p == NULL) { 250 return 0; 251 } 252 253 sk_sort(sk); 254 255 /* sk->comp is a function that takes pointers to pointers to elements, but 256 * qsort and bsearch take a comparison function that just takes pointers to 257 * elements. However, since we're passing an array of pointers to 258 * qsort/bsearch, we can just cast the comparison function and everything 259 * works. */ 260 comp_func=(int (*)(const void *,const void *))(sk->comp); 261 r = bsearch(&p, sk->data, sk->num, sizeof(void *), comp_func); 262 if (r == NULL) { 263 return 0; 264 } 265 i = ((void **)r) - sk->data; 266 /* This function always returns the first result. */ 267 while (i > 0 && sk->comp((const void**) &p, (const void**) &sk->data[i-1]) == 0) { 268 i--; 269 } 270 if (out_index) { 271 *out_index = i; 272 } 273 return 1; 274} 275 276void *sk_shift(_STACK *sk) { 277 if (sk == NULL) { 278 return NULL; 279 } 280 if (sk->num == 0) { 281 return NULL; 282 } 283 return sk_delete(sk, 0); 284} 285 286size_t sk_push(_STACK *sk, void *p) { return (sk_insert(sk, p, sk->num)); } 287 288void *sk_pop(_STACK *sk) { 289 if (sk == NULL) { 290 return NULL; 291 } 292 if (sk->num == 0) { 293 return NULL; 294 } 295 return sk_delete(sk, sk->num - 1); 296} 297 298_STACK *sk_dup(const _STACK *sk) { 299 _STACK *ret; 300 void **s; 301 302 if (sk == NULL) { 303 return NULL; 304 } 305 306 ret = sk_new(sk->comp); 307 if (ret == NULL) { 308 goto err; 309 } 310 311 s = (void **)OPENSSL_realloc(ret->data, sizeof(void *) * sk->num_alloc); 312 if (s == NULL) { 313 goto err; 314 } 315 ret->data = s; 316 317 ret->num = sk->num; 318 memcpy(ret->data, sk->data, sizeof(void *) * sk->num); 319 ret->sorted = sk->sorted; 320 ret->num_alloc = sk->num_alloc; 321 ret->comp = sk->comp; 322 return ret; 323 324err: 325 if (ret) { 326 sk_free(ret); 327 } 328 return NULL; 329} 330 331void sk_sort(_STACK *sk) { 332 int (*comp_func)(const void *,const void *); 333 334 if (sk == NULL || sk->sorted) { 335 return; 336 } 337 338 /* See the comment in sk_find about this cast. */ 339 comp_func = (int (*)(const void *, const void *))(sk->comp); 340 qsort(sk->data, sk->num, sizeof(void *), comp_func); 341 sk->sorted = 1; 342} 343 344int sk_is_sorted(const _STACK *sk) { 345 if (!sk) { 346 return 1; 347 } 348 return sk->sorted; 349} 350 351stack_cmp_func sk_set_cmp_func(_STACK *sk, stack_cmp_func comp) { 352 stack_cmp_func old = sk->comp; 353 354 if (sk->comp != comp) { 355 sk->sorted = 0; 356 } 357 sk->comp = comp; 358 359 return old; 360} 361