1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) 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 (at) 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 (at) 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 (at) 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 <string.h> 60 61 #include <openssl/mem.h> 62 63 #include "../internal.h" 64 65 66 // kMinSize is the number of pointers that will be initially allocated in a new 67 // stack. 68 static const size_t kMinSize = 4; 69 70 _STACK *sk_new(stack_cmp_func comp) { 71 _STACK *ret; 72 73 ret = OPENSSL_malloc(sizeof(_STACK)); 74 if (ret == NULL) { 75 goto err; 76 } 77 OPENSSL_memset(ret, 0, sizeof(_STACK)); 78 79 ret->data = OPENSSL_malloc(sizeof(void *) * kMinSize); 80 if (ret->data == NULL) { 81 goto err; 82 } 83 84 OPENSSL_memset(ret->data, 0, sizeof(void *) * kMinSize); 85 86 ret->comp = comp; 87 ret->num_alloc = kMinSize; 88 89 return ret; 90 91 err: 92 OPENSSL_free(ret); 93 return NULL; 94 } 95 96 _STACK *sk_new_null(void) { return sk_new(NULL); } 97 98 size_t sk_num(const _STACK *sk) { 99 if (sk == NULL) { 100 return 0; 101 } 102 return sk->num; 103 } 104 105 void sk_zero(_STACK *sk) { 106 if (sk == NULL || sk->num == 0) { 107 return; 108 } 109 OPENSSL_memset(sk->data, 0, sizeof(void*) * sk->num); 110 sk->num = 0; 111 sk->sorted = 0; 112 } 113 114 void *sk_value(const _STACK *sk, size_t i) { 115 if (!sk || i >= sk->num) { 116 return NULL; 117 } 118 return sk->data[i]; 119 } 120 121 void *sk_set(_STACK *sk, size_t i, void *value) { 122 if (!sk || i >= sk->num) { 123 return NULL; 124 } 125 return sk->data[i] = value; 126 } 127 128 void sk_free(_STACK *sk) { 129 if (sk == NULL) { 130 return; 131 } 132 OPENSSL_free(sk->data); 133 OPENSSL_free(sk); 134 } 135 136 void sk_pop_free(_STACK *sk, void (*func)(void *)) { 137 if (sk == NULL) { 138 return; 139 } 140 141 for (size_t i = 0; i < sk->num; i++) { 142 if (sk->data[i] != NULL) { 143 func(sk->data[i]); 144 } 145 } 146 sk_free(sk); 147 } 148 149 size_t sk_insert(_STACK *sk, void *p, size_t where) { 150 if (sk == NULL) { 151 return 0; 152 } 153 154 if (sk->num_alloc <= sk->num + 1) { 155 // Attempt to double the size of the array. 156 size_t new_alloc = sk->num_alloc << 1; 157 size_t alloc_size = new_alloc * sizeof(void *); 158 void **data; 159 160 // If the doubling overflowed, try to increment. 161 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) { 162 new_alloc = sk->num_alloc + 1; 163 alloc_size = new_alloc * sizeof(void *); 164 } 165 166 // If the increment also overflowed, fail. 167 if (new_alloc < sk->num_alloc || alloc_size / sizeof(void *) != new_alloc) { 168 return 0; 169 } 170 171 data = OPENSSL_realloc(sk->data, alloc_size); 172 if (data == NULL) { 173 return 0; 174 } 175 176 sk->data = data; 177 sk->num_alloc = new_alloc; 178 } 179 180 if (where >= sk->num) { 181 sk->data[sk->num] = p; 182 } else { 183 OPENSSL_memmove(&sk->data[where + 1], &sk->data[where], 184 sizeof(void *) * (sk->num - where)); 185 sk->data[where] = p; 186 } 187 188 sk->num++; 189 sk->sorted = 0; 190 191 return sk->num; 192 } 193 194 void *sk_delete(_STACK *sk, size_t where) { 195 void *ret; 196 197 if (!sk || where >= sk->num) { 198 return NULL; 199 } 200 201 ret = sk->data[where]; 202 203 if (where != sk->num - 1) { 204 OPENSSL_memmove(&sk->data[where], &sk->data[where + 1], 205 sizeof(void *) * (sk->num - where - 1)); 206 } 207 208 sk->num--; 209 return ret; 210 } 211 212 void *sk_delete_ptr(_STACK *sk, void *p) { 213 if (sk == NULL) { 214 return NULL; 215 } 216 217 for (size_t i = 0; i < sk->num; i++) { 218 if (sk->data[i] == p) { 219 return sk_delete(sk, i); 220 } 221 } 222 223 return NULL; 224 } 225 226 int sk_find(_STACK *sk, size_t *out_index, void *p) { 227 if (sk == NULL) { 228 return 0; 229 } 230 231 if (sk->comp == NULL) { 232 // Use pointer equality when no comparison function has been set. 233 for (size_t i = 0; i < sk->num; i++) { 234 if (sk->data[i] == p) { 235 if (out_index) { 236 *out_index = i; 237 } 238 return 1; 239 } 240 } 241 return 0; 242 } 243 244 if (p == NULL) { 245 return 0; 246 } 247 248 sk_sort(sk); 249 250 // sk->comp is a function that takes pointers to pointers to elements, but 251 // qsort and bsearch take a comparison function that just takes pointers to 252 // elements. However, since we're passing an array of pointers to 253 // qsort/bsearch, we can just cast the comparison function and everything 254 // works. 255 const void *const *r = bsearch(&p, sk->data, sk->num, sizeof(void *), 256 (int (*)(const void *, const void *))sk->comp); 257 if (r == NULL) { 258 return 0; 259 } 260 size_t idx = ((void **)r) - sk->data; 261 // This function always returns the first result. 262 while (idx > 0 && 263 sk->comp((const void **)&p, (const void **)&sk->data[idx - 1]) == 0) { 264 idx--; 265 } 266 if (out_index) { 267 *out_index = idx; 268 } 269 return 1; 270 } 271 272 void *sk_shift(_STACK *sk) { 273 if (sk == NULL) { 274 return NULL; 275 } 276 if (sk->num == 0) { 277 return NULL; 278 } 279 return sk_delete(sk, 0); 280 } 281 282 size_t sk_push(_STACK *sk, void *p) { return (sk_insert(sk, p, sk->num)); } 283 284 void *sk_pop(_STACK *sk) { 285 if (sk == NULL) { 286 return NULL; 287 } 288 if (sk->num == 0) { 289 return NULL; 290 } 291 return sk_delete(sk, sk->num - 1); 292 } 293 294 _STACK *sk_dup(const _STACK *sk) { 295 _STACK *ret; 296 void **s; 297 298 if (sk == NULL) { 299 return NULL; 300 } 301 302 ret = sk_new(sk->comp); 303 if (ret == NULL) { 304 goto err; 305 } 306 307 s = (void **)OPENSSL_realloc(ret->data, sizeof(void *) * sk->num_alloc); 308 if (s == NULL) { 309 goto err; 310 } 311 ret->data = s; 312 313 ret->num = sk->num; 314 OPENSSL_memcpy(ret->data, sk->data, sizeof(void *) * sk->num); 315 ret->sorted = sk->sorted; 316 ret->num_alloc = sk->num_alloc; 317 ret->comp = sk->comp; 318 return ret; 319 320 err: 321 sk_free(ret); 322 return NULL; 323 } 324 325 void sk_sort(_STACK *sk) { 326 int (*comp_func)(const void *,const void *); 327 328 if (sk == NULL || sk->comp == NULL || sk->sorted) { 329 return; 330 } 331 332 // See the comment in sk_find about this cast. 333 comp_func = (int (*)(const void *, const void *))(sk->comp); 334 qsort(sk->data, sk->num, sizeof(void *), comp_func); 335 sk->sorted = 1; 336 } 337 338 int sk_is_sorted(const _STACK *sk) { 339 if (!sk) { 340 return 1; 341 } 342 return sk->sorted; 343 } 344 345 stack_cmp_func sk_set_cmp_func(_STACK *sk, stack_cmp_func comp) { 346 stack_cmp_func old = sk->comp; 347 348 if (sk->comp != comp) { 349 sk->sorted = 0; 350 } 351 sk->comp = comp; 352 353 return old; 354 } 355 356 _STACK *sk_deep_copy(const _STACK *sk, void *(*copy_func)(void *), 357 void (*free_func)(void *)) { 358 _STACK *ret = sk_dup(sk); 359 if (ret == NULL) { 360 return NULL; 361 } 362 363 for (size_t i = 0; i < ret->num; i++) { 364 if (ret->data[i] == NULL) { 365 continue; 366 } 367 ret->data[i] = copy_func(ret->data[i]); 368 if (ret->data[i] == NULL) { 369 for (size_t j = 0; j < i; j++) { 370 if (ret->data[j] != NULL) { 371 free_func(ret->data[j]); 372 } 373 } 374 sk_free(ret); 375 return NULL; 376 } 377 } 378 379 return ret; 380 } 381