/**
 * slibc — Yet another C library
 * Copyright © 2015, 2016  Mattias Andrée (m@maandree.se)
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
#include <stdlib.h>


# pragma GCC diagnostic ignored "-Wdiscarded-qualifiers"



/**
 * Search for an item in a sorted list of comparable
 * elements. The list must be sorted in ascending order.
 * The function usually implements binary search,
 * as is done in this implementation.
 * 
 * @etymology  (B)inary (search).
 * 
 * @param   sought  The sought item.
 * @param   list    The beginning of the list to search.
 * @param   n       The number of elements in the list.
 * @param   width   The width, in bytes, of each element in the list.
 * @param   compar  A function that shall compare two items, and return
 *                  a value less than, equal to, or greater than zero
 *                  if the first argument is less than, equal to, or
 *                  greater than the second argument, respectively.
 * @return          The address of an arbritrart element in `list` that
 *                  is equal to `sought`, or `NULL` if no such element
 *                  can be found (does not exist, or because `list`
 *                  is not properly sorted.)
 * 
 * @since  Always.
 */
void* (bsearch)(const void* sought, const void* list, size_t n, size_t width,
		int (*compar)(const void*, const void*))
{
  int cmp;
  size_t i;
  char* test;
  if (n == 0)
    return NULL;
  for (;;)
    {
      i = n >> 1;
      test = (char*)list + i * width;
      cmp = compar(sought, test);
      if (!i)
	return cmp ? NULL : test;
      else if (cmp < 0)
	n = i;
      else if (cmp > 0)
	n -= i, list = test;
      else
	return test;
    }
}