source/lib/ldb/common/util.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Andrew Tridgell  2004
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 2 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23 */
  24
  25 /*
  26  *  Name: ldb
  27  *
  28  *  Component: ldb utility functions
  29  *
  30  *  Description: miscellanous utility functions for ldb
  31  *
  32  *  Author: Andrew Tridgell
  33  */
  34
  35 #include "includes.h"
  36
  37
  38 #define MAX_MALLOC_SIZE 0x7fffffff
  39
  40 /*
  41   realloc an array, checking for integer overflow in the array size
  42 */
  43 void *realloc_array(void *ptr, size_t el_size, unsigned count)
  44 {
  45         if (count == 0 ||
  46             count >= MAX_MALLOC_SIZE/el_size) {
  47                 return NULL;
  48         }
  49         if (!ptr) {
  50                 return malloc(el_size * count);
  51         }
  52         return realloc(ptr, el_size * count);
  53 }
  54
  55
  56 /*
  57   find an element in a list, using the given comparison function and
  58   assuming that the list is already sorted using comp_fn
  59
  60   return -1 if not found, or the index of the first occurance of needle if found
  61 */
  62 int list_find(const void *needle,
  63               const void *base, size_t nmemb, size_t size, comparison_fn_t comp_fn)
  64 {
  65         const char *base_p = base;
  66         size_t min_i, max_i, test_i;
  67
  68         if (nmemb == 0) {
  69                 return -1;
  70         }
  71
  72         min_i = 0;
  73         max_i = nmemb-1;
  74
  75         while (min_i < max_i) {
  76                 size_t test_t;
  77                 int r;
  78
  79                 test_i = (min_i + max_i) / 2;
  80                 r = comp_fn(needle, *(void * const *)(base_p + (size * test_i)));
  81                 if (r == 0) {
  82                         /* scan back for first element */
  83                         while (test_t > 0 &&
  84                                comp_fn(needle, *(void * const *)(base_p + (size * (test_i-1)))) == 0) {
  85                                 test_i--;
  86                         }
  87                         return test_i;
  88                 }
  89                 if (r == -1) {
  90                         max_i = test_i - 1;
  91                 }
  92                 if (r == 1) {
  93                         min_i = test_i + 1;
  94                 }
  95         }
  96
  97         if (comp_fn(needle, *(void * const *)(base_p + (size * min_i))) == 0) {
  98                 return min_i;
  99         }
 100
 101         return -1;
 102 }