crypto/bsearch.c

   1 /*
   2  * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <stddef.h>
  11 #include "internal/cryptlib.h"
  12
  13 const void *ossl_bsearch(const void *key, const void *base, int num,
  14                          int size, int (*cmp) (const void *, const void *),
  15                          int flags)
  16 {
  17     const char *base_ = base;
  18     int l, h, i = 0, c = 0;
  19     const char *p = NULL;
  20
  21     if (num == 0)
  22         return NULL;
  23     l = 0;
  24     h = num;
  25     while (l < h) {
  26         i = (l + h) / 2;
  27         p = &(base_[i * size]);
  28         c = (*cmp) (key, p);
  29         if (c < 0)
  30             h = i;
  31         else if (c > 0)
  32             l = i + 1;
  33         else
  34             break;
  35     }
  36     if (c != 0 && !(flags & OSSL_BSEARCH_VALUE_ON_NOMATCH))
  37         p = NULL;
  38     else if (c == 0 && (flags & OSSL_BSEARCH_FIRST_VALUE_ON_MATCH)) {
  39         while (i > 0 && (*cmp) (key, &(base_[(i - 1) * size])) == 0)
  40             i--;
  41         p = &(base_[i * size]);
  42     }
  43     return p;
  44 }