avp210159

bsearcher.c

May 20th, 2014
261
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  *   Yet another generic binary search implementation
  3.  *   bsearcher.c avp 2014
  4.  *
  5.  *  Very similar to the function bsearch() (see man 3 bsearch).
  6.  *
  7.  *    Except that:
  8.  *    always returns the address of the first of duplicate keys
  9.  *    and
  10.  *    additional argument returns the position for inserting a new key
  11.  *    (Of course, if additional argument is not NULL)
  12.  *
  13.  *    (thus it determines the range of duplicate keys
  14.  *    i.e., works as equal_range() in C++).
  15.  *
  16.  * bsearcher - binary search an array of elements
  17.  * Returns a pointer to the first matching element of the array,
  18.  * or NULL if no match is found.
  19.  *  @key: pointer to item being searched for
  20.  *  @base: pointer to first element to search
  21.  *  @nmemb: number of elements
  22.  *  @size: size of each element
  23.  *  @comp: pointer to comparison function
  24.  *  @ipos: pointer to variable for the position to which you can insert a new key
  25.  *         (after all items matching @key)
  26.  *
  27.  *  The comp routine is expected to have two arguments which point to the key
  28.  *  object and to  an array  member,  in  that order, and should return
  29.  *  an integer less than, equal to, or greater than zero if the  key  object  
  30.  *  is  found,  respectively, to be less than, to match, or be greater
  31.  *  than the array member.
  32.  *
  33.  * bsearch_lb - is in some way analogue of lower_bound() in C++
  34.  * Returns a pointer to the first matching element of the array,
  35.  * or NULL if no match is found.
  36.  *  its arguments are identical bsearcher() arguments except @ipos,
  37.  *  which if the key is found, contains the position of the first matching item
  38.  *
  39.  * bsearch_ub - similar to C++ upper_bound()
  40.  * Returns a pointer to the last matching element of the array,
  41.  * or NULL if no match is found.
  42.  *  its arguments are identical bsearcher() arguments.
  43.  *
  44.  *  These functions does a binary search on the given array.  The
  45.  *  contents of the array should already be in ascending sorted order
  46.  *  under the provided comparison function.
  47.  *
  48.  *  Compile this file gcc (or g++) -DTEST bsearcher.c for test programm.
  49.  *  (ask any questions on the site hashcode.ru)
  50.  */
  51.  
  52. #include <stdlib.h>
  53.  
  54. // move this function prototype in any of your .h file
  55. void *
  56. bsearcher (const void *key, const void *base, size_t nmemb, size_t size,
  57.          int (*comp)(const void *key, const void *item), size_t *ipos);
  58. void *
  59. bsearch_lb (const void *key, const void *base, size_t nmemb, size_t size,
  60.          int (*comp)(const void *key, const void *item), size_t *ipos);
  61. void *
  62. bsearch_ub (const void *key, const void *base, size_t nmemb, size_t size,
  63.          int (*comp)(const void *key, const void *item), size_t *ipos);
  64.  
  65. void *
  66. bsearcher (const void *key, const void *base, size_t nmemb, size_t size,
  67.          int (*comp)(const void *key, const void *item), size_t *ipos)
  68. {
  69.   if (ipos)
  70.     *ipos = 0;
  71.   if (!nmemb || !size)
  72.     return 0;
  73.  
  74.   size_t first = 0, last = nmemb, mid, res;
  75.  
  76.   while (first < last) {
  77.     mid = first + (last - first) / 2; // by reason of overflow!!!
  78.     if (comp(key, (char *)base + mid * size) > 0)
  79.       first = mid + 1;
  80.     else
  81.       last = mid;
  82.   }
  83.  
  84.   if ((res = first++) < nmemb  && comp(key, (char *)base + res * size) == 0) {
  85.     //    puts("first key FOUND!"); // yes, it's the comment (just unusual form)
  86.     if (first < nmemb) {
  87.       if (comp(key, (char *)base + first * size) == 0) {
  88.     //  puts ("Have more..., looking for last");
  89.     last = nmemb;
  90.     while (first < last) {
  91.       mid = first + (last - first) / 2;
  92.       if (comp(key, (char *)base + mid * size) < 0)
  93.         last = mid;
  94.       else
  95.         first = mid + 1;
  96.     }
  97.       }
  98.       if (ipos)
  99.     *ipos = first;
  100.     } else {
  101.       //      puts ("last in array");
  102.       if (ipos)
  103.     *ipos = nmemb;
  104.     }
  105.   } else {
  106.     //    puts("Not Found!");
  107.     if (ipos)
  108.       *ipos = res;
  109.     return 0;
  110.   }
  111.  
  112.   return (void *)((char *)base + res * size);
  113. }
  114.  
  115.  
  116. void *
  117. bsearch_lb (const void *key, const void *base, size_t nmemb, size_t size,
  118.          int (*comp)(const void *key, const void *item), size_t *ipos)
  119. {
  120.   if (ipos)
  121.     *ipos = 0;
  122.   if (!nmemb || !size)
  123.     return 0;
  124.  
  125.   size_t first = 0, last = nmemb, mid;
  126.  
  127.   while (first < last) {
  128.     mid = first + (last - first) / 2; // by reason of overflow!!!
  129.     if (comp(key, (char *)base + mid * size) > 0)
  130.       first = mid + 1;
  131.     else
  132.       last = mid;
  133.   }
  134.   if (ipos)
  135.     *ipos = first;
  136.  
  137.   if (first < nmemb  && comp(key, (char *)base + first * size) == 0)
  138.     return (void *)((char *)base + first * size);
  139.   return 0;
  140. }
  141.  
  142. void *
  143. bsearch_ub (const void *key, const void *base, size_t nmemb, size_t size,
  144.          int (*comp)(const void *key, const void *item), size_t *ipos)
  145. {
  146.   if (ipos)
  147.     *ipos = 0;
  148.   if (!nmemb || !size)
  149.     return 0;
  150.  
  151.   size_t first = 0, last = nmemb, mid;
  152.  
  153.   while (first < last) {
  154.     mid = first + (last - first) / 2;
  155.     if (comp(key, (char *)base + mid * size) < 0)
  156.       last = mid;
  157.     else
  158.       first = mid + 1;
  159.   }
  160.   if (ipos)
  161.     *ipos = first;
  162.  
  163.   if (first && comp(key, (char *)base + --first * size) == 0)
  164.     return (void *)((char *)base + first * size);
  165.   return 0;
  166. }
  167.  
  168.  
  169. #ifdef TEST
  170.  
  171. #include <stdio.h>
  172. #include <string.h>
  173.  
  174. int icmp (const void *a, const void *b) {
  175.   return *((int *)a) - *((int *)b); // danger of overflow !!!
  176. }
  177.  
  178. int fcmp (const void *a, const void *b) {
  179.   return strcmp(*((char **)a), *((char **)b));
  180. }
  181.  
  182. int
  183. icheck (int key, int a[], int asz, int tno)
  184. {
  185.   size_t pos;
  186.   int *res = (int *)bsearcher(&key, a, asz, sizeof(a[0]), icmp, &pos),
  187.     tpos, *tres = 0, i;
  188.  
  189.   printf("icheck %d : ", tno);
  190.   for (i = 0; i < asz; i++) {
  191.     putchar(a[i]);
  192.     if (a[i] >= key)
  193.       break;
  194.   }
  195.   puts("");
  196.   tpos = i;
  197.   if (i < asz)
  198.     if (key == a[i]) {
  199.       tres = a + i;
  200.       for (tpos = i + 1; tpos < asz && a[tpos] == key; tpos++);
  201.     }
  202.  
  203.   if (res == tres && pos == (size_t)tpos)
  204.     return 0;
  205.   printf ("test %d is fail\n", tno);
  206.   return 1;
  207. }
  208.  
  209.  
  210. int
  211. main (int ac, char *av[])
  212. {
  213.   printf("Use %s ARG ...   for testing\n", av[0]);
  214.   int i, tcap = 0, tlen = 0, *ta = 0;
  215.   char *t, str[1000];
  216.  
  217.   // test for all characters (as int[]) from args
  218.   for (i = 0; i < ac; i++)
  219.     for (t = av[i]; *t; t++) {
  220.       if (tlen == tcap)
  221.     ta = (int *)realloc(ta, (tcap += 100) * sizeof(ta[0]));
  222.       ta[tlen++] = *t;
  223.     }
  224.   qsort(ta, tlen, sizeof(ta[0]), icmp);
  225.   puts("test argv[] characters:");
  226.  
  227.   int cnt = icheck(ta[tlen - 1] + 1, ta, tlen, -2);
  228.   cnt += icheck(ta[0] - 1, ta, tlen, -1);
  229.   for (i = 0; i < tlen; i++)
  230.     cnt += icheck(ta[i], ta, tlen, i);
  231.  
  232.   printf ("%d tests. %d FAIL\n", i + 2, cnt);
  233.    
  234.  
  235.   qsort(av + 1, ac - 1, sizeof(av[0]), fcmp);
  236.   puts("array of user test strings:");
  237.   for (i = 1; i < ac; i++)
  238.     puts(av[i]);
  239.  
  240.   t = av[1];
  241.   printf ("bsearch [%s] %s\n",
  242.       t,
  243.       bsearch(&t, av + 1, ac - 1, sizeof(av[0]), fcmp) ? "OK" : "FAIL");
  244.   puts("user test bsearcher");
  245.   t = str;
  246.   while (fputs("enter: ", stdout), fflush(stdout),
  247.      fgets(str, sizeof(str), stdin)) {
  248.     str[strcspn(str, "\n")] = 0;
  249.  
  250.     size_t ipos;
  251.     char **p = (char **)bsearcher(&t,
  252.                   av + 1,
  253.                   ac - 1,
  254.                   sizeof(av[0]),
  255.                   fcmp,
  256.                   &ipos);
  257.     printf("bsearcher: Key [%s] is %sFound. "
  258.         "Insert point is [%s] in pos %ld\n",
  259.         str, p ? "" : "Not ", av[ipos + 1], (long)ipos);
  260.     if (p) {
  261.       printf("bsearcher found array items: ");
  262.       while (p < (av + 1 + ipos))
  263.     printf (" %s", *p++);
  264.       puts("");
  265.     }
  266.  
  267.   }
  268.  
  269.   puts("\nuser test bsearch_lb");
  270.   while (fputs("enter: ", stdout), fflush(stdout),
  271.      fgets(str, sizeof(str), stdin)) {
  272.     str[strcspn(str, "\n")] = 0;
  273.  
  274.     size_t ipos;
  275.     char **p = (char **)bsearch_lb(&t,
  276.                   av + 1,
  277.                   ac - 1,
  278.                   sizeof(av[0]),
  279.                   fcmp,
  280.                   &ipos);
  281.     printf("bsearch_lb: Key [%s] is %sFound. "
  282.         "Insert point is [%s] in pos %ld\n",
  283.         str, p ? "" : "Not ", av[ipos + 1], (long)ipos);
  284.   }
  285.  
  286.  
  287.   puts("\nuser test bsearch_ub");
  288.   while (fputs("enter: ", stdout), fflush(stdout),
  289.      fgets(str, sizeof(str), stdin)) {
  290.     str[strcspn(str, "\n")] = 0;
  291.  
  292.     size_t ipos;
  293.     char **p = (char **)bsearch_ub(&t,
  294.                   av + 1,
  295.                   ac - 1,
  296.                   sizeof(av[0]),
  297.                   fcmp,
  298.                   &ipos);
  299.     printf("bsearch_ub: Key [%s] is %sFound. "
  300.         "Insert point is [%s] in pos %ld\n",
  301.         str, p ? "" : "Not ", av[ipos + 1], (long)ipos);
  302.   }
  303.  
  304.   return puts("") == EOF;
  305. }
  306.  
  307. #endif
RAW Paste Data