bsearcher.c

/*
 *   Yet another generic binary search implementation
 *   bsearcher.c avp 2014
 *
 *  Very similar to the function bsearch() (see man 3 bsearch).
 *
 *    Except that:
 *    always returns the address of the first of duplicate keys
 *    and
 *    additional argument returns the position for inserting a new key
 *    (Of course, if additional argument is not NULL)
 *
 *    (thus it determines the range of duplicate keys
 *    i.e., works as equal_range() in C++).
 *
 * bsearcher - binary search an array of elements
 * Returns a pointer to the first matching element of the array,
 * or NULL if no match is found.
 *  @key: pointer to item being searched for
 *  @base: pointer to first element to search
 *  @nmemb: number of elements
 *  @size: size of each element
 *  @comp: pointer to comparison function
 *  @ipos: pointer to variable for the position to which you can insert a new key
 *         (after all items matching @key)
 *
 *  The comp routine is expected to have two arguments which point to the key
 *  object and to  an array  member,  in  that order, and should return
 *  an integer less than, equal to, or greater than zero if the  key  object
 *  is  found,  respectively, to be less than, to match, or be greater
 *  than the array member.
 *
 * bsearch_lb - is in some way analogue of lower_bound() in C++
 * Returns a pointer to the first matching element of the array,
 * or NULL if no match is found.
 *  its arguments are identical bsearcher() arguments except @ipos,
 *  which if the key is found, contains the position of the first matching item
 *
 * bsearch_ub - similar to C++ upper_bound()
 * Returns a pointer to the last matching element of the array,
 * or NULL if no match is found.
 *  its arguments are identical bsearcher() arguments.
 *
 *  These functions does a binary search on the given array.  The
 *  contents of the array should already be in ascending sorted order
 *  under the provided comparison function.
 *
 *  Compile this file gcc (or g++) -DTEST bsearcher.c for test programm.
 *  (ask any questions on the site hashcode.ru)
 */

#include <stdlib.h>

// move this function prototype in any of your .h file
void *
bsearcher (const void *key, const void *base, size_t nmemb, size_t size,
         int (*comp)(const void *key, const void *item), size_t *ipos);
void *
bsearch_lb (const void *key, const void *base, size_t nmemb, size_t size,
         int (*comp)(const void *key, const void *item), size_t *ipos);
void *
bsearch_ub (const void *key, const void *base, size_t nmemb, size_t size,
         int (*comp)(const void *key, const void *item), size_t *ipos);

void *
bsearcher (const void *key, const void *base, size_t nmemb, size_t size,
         int (*comp)(const void *key, const void *item), size_t *ipos)
{
  if (ipos)
    *ipos = 0;
  if (!nmemb || !size)
    return 0;

  size_t first = 0, last = nmemb, mid, res;

  while (first < last) {
    mid = first + (last - first) / 2; // by reason of overflow!!!
    if (comp(key, (char *)base + mid * size) > 0)
      first = mid + 1;
    else
      last = mid;
  }

  if ((res = first++) < nmemb  && comp(key, (char *)base + res * size) == 0) {
    //    puts("first key FOUND!"); // yes, it's the comment (just unusual form)
    if (first < nmemb) {
      if (comp(key, (char *)base + first * size) == 0) {
    //  puts ("Have more..., looking for last");
    last = nmemb;
    while (first < last) {
      mid = first + (last - first) / 2;
      if (comp(key, (char *)base + mid * size) < 0)
        last = mid;
      else
        first = mid + 1;
    }
      }
      if (ipos)
    *ipos = first;
    } else {
      //      puts ("last in array");
      if (ipos)
    *ipos = nmemb;
    }
  } else {
    //    puts("Not Found!");
    if (ipos)
      *ipos = res;
    return 0;
  }

  return (void *)((char *)base + res * size);
}


void *
bsearch_lb (const void *key, const void *base, size_t nmemb, size_t size,
         int (*comp)(const void *key, const void *item), size_t *ipos)
{
  if (ipos)
    *ipos = 0;
  if (!nmemb || !size)
    return 0;

  size_t first = 0, last = nmemb, mid;

  while (first < last) {
    mid = first + (last - first) / 2; // by reason of overflow!!!
    if (comp(key, (char *)base + mid * size) > 0)
      first = mid + 1;
    else
      last = mid;
  }
  if (ipos)
    *ipos = first;

  if (first < nmemb  && comp(key, (char *)base + first * size) == 0)
    return (void *)((char *)base + first * size);
  return 0;
}

void *
bsearch_ub (const void *key, const void *base, size_t nmemb, size_t size,
         int (*comp)(const void *key, const void *item), size_t *ipos)
{
  if (ipos)
    *ipos = 0;
  if (!nmemb || !size)
    return 0;

  size_t first = 0, last = nmemb, mid;

  while (first < last) {
    mid = first + (last - first) / 2;
    if (comp(key, (char *)base + mid * size) < 0)
      last = mid;
    else
      first = mid + 1;
  }
  if (ipos)
    *ipos = first;

  if (first && comp(key, (char *)base + --first * size) == 0)
    return (void *)((char *)base + first * size);
  return 0;
}


#ifdef TEST

#include <stdio.h>
#include <string.h>

int icmp (const void *a, const void *b) {
  return *((int *)a) - *((int *)b); // danger of overflow !!!
}

int fcmp (const void *a, const void *b) {
  return strcmp(*((char **)a), *((char **)b));
}

int
icheck (int key, int a[], int asz, int tno)
{
  size_t pos;
  int *res = (int *)bsearcher(&key, a, asz, sizeof(a[0]), icmp, &pos),
    tpos, *tres = 0, i;

  printf("icheck %d : ", tno);
  for (i = 0; i < asz; i++) {
    putchar(a[i]);
    if (a[i] >= key)
      break;
  }
  puts("");
  tpos = i;
  if (i < asz)
    if (key == a[i]) {
      tres = a + i;
      for (tpos = i + 1; tpos < asz && a[tpos] == key; tpos++);
    }

  if (res == tres && pos == (size_t)tpos)
    return 0;
  printf ("test %d is fail\n", tno);
  return 1;
}


int
main (int ac, char *av[])
{
  printf("Use %s ARG ...   for testing\n", av[0]);
  int i, tcap = 0, tlen = 0, *ta = 0;
  char *t, str[1000];

  // test for all characters (as int[]) from args
  for (i = 0; i < ac; i++)
    for (t = av[i]; *t; t++) {
      if (tlen == tcap)
    ta = (int *)realloc(ta, (tcap += 100) * sizeof(ta[0]));
      ta[tlen++] = *t;
    }
  qsort(ta, tlen, sizeof(ta[0]), icmp);
  puts("test argv[] characters:");

  int cnt = icheck(ta[tlen - 1] + 1, ta, tlen, -2);
  cnt += icheck(ta[0] - 1, ta, tlen, -1);
  for (i = 0; i < tlen; i++)
    cnt += icheck(ta[i], ta, tlen, i);

  printf ("%d tests. %d FAIL\n", i + 2, cnt);


  qsort(av + 1, ac - 1, sizeof(av[0]), fcmp);
  puts("array of user test strings:");
  for (i = 1; i < ac; i++)
    puts(av[i]);

  t = av[1];
  printf ("bsearch [%s] %s\n",
      t,
      bsearch(&t, av + 1, ac - 1, sizeof(av[0]), fcmp) ? "OK" : "FAIL");
  puts("user test bsearcher");
  t = str;
  while (fputs("enter: ", stdout), fflush(stdout),
     fgets(str, sizeof(str), stdin)) {
    str[strcspn(str, "\n")] = 0;

    size_t ipos;
    char **p = (char **)bsearcher(&t,
                  av + 1,
                  ac - 1,
                  sizeof(av[0]),
                  fcmp,
                  &ipos);
    printf("bsearcher: Key [%s] is %sFound. "
        "Insert point is [%s] in pos %ld\n",
        str, p ? "" : "Not ", av[ipos + 1], (long)ipos);
    if (p) {
      printf("bsearcher found array items: ");
      while (p < (av + 1 + ipos))
    printf (" %s", *p++);
      puts("");
    }

  }

  puts("\nuser test bsearch_lb");
  while (fputs("enter: ", stdout), fflush(stdout),
     fgets(str, sizeof(str), stdin)) {
    str[strcspn(str, "\n")] = 0;

    size_t ipos;
    char **p = (char **)bsearch_lb(&t,
                  av + 1,
                  ac - 1,
                  sizeof(av[0]),
                  fcmp,
                  &ipos);
    printf("bsearch_lb: Key [%s] is %sFound. "
        "Insert point is [%s] in pos %ld\n",
        str, p ? "" : "Not ", av[ipos + 1], (long)ipos);
  }


  puts("\nuser test bsearch_ub");
  while (fputs("enter: ", stdout), fflush(stdout),
     fgets(str, sizeof(str), stdin)) {
    str[strcspn(str, "\n")] = 0;

    size_t ipos;
    char **p = (char **)bsearch_ub(&t,
                  av + 1,
                  ac - 1,
                  sizeof(av[0]),
                  fcmp,
                  &ipos);
    printf("bsearch_ub: Key [%s] is %sFound. "
        "Insert point is [%s] in pos %ld\n",
        str, p ? "" : "Not ", av[ipos + 1], (long)ipos);
  }

  return puts("") == EOF;
}

#endif