bsearch.c

Go to the documentation of this file.

typedef unsigned int size_t;
#define NULL 0
void *bsearch(const void *key, const void *base, size_t /* nmemb */ high,
                          size_t size, int (*compar)(const void *, const void *))
{
        register char *p;
        size_t low;
        size_t mid;
        int r;

        if (size > 0) {                         /* TODO: change this to an assert?? */
                low = 0;
                while (low < high) {
                        mid = low + ((high - low) >> 1); /* Avoid possible overflow here. */
                        p = ((char *)base) + mid * size; /* Could overflow here... */
                        r = (*compar)(key, p); /* but that's an application problem! */
                        if (r > 0) {
                                low = mid + 1;
                        } else if (r < 0) {
                                high = mid;
                        } else {
                                return p;
                        }
                }
        }
        return NULL;
}