Метка: bsearch

Захотелось заглянуть внутрь libc Ubuntu Linux 10.04 на реализацию функции bsearch, а там небольшая проблемка:

void *
bsearch (const void *key, const void *base, size_t nmemb, size_t size,
	 int (*compar) (const void *, const void *))
{
  size_t l, u, idx;
  const void *p;
  int comparison;

  l = 0;
  u = nmemb;
  while (l < u)
    {
      idx = (l + u) / 2;
      p = (void *) (((const char *) base) + (idx * size));
      comparison = (*compar) (key, p);
      if (comparison < 0)
	u = idx;
      else if (comparison > 0)
	l = idx + 1;
      else
	return (void *) p;
    }

  return NULL;
}

Проблема в строке

      idx = (l + u) / 2;

При достаточно больших значениях nmemb и поиске ключа из "верхнего" раздела массива, здесь может возникнуть переполнение (если компилятор не отслеживает такие ситуации), и соответственно функция будет зацикливаться.

Конечно, это касается действительно огромных массивов, с более чем 2³¹ элементов для 32-битных систем (где размер size_t равен 4 байтам).

Вариант bsearch во FreeBSD 7.1 не имеет этой проблемы:

void *
bsearch(key, base0, nmemb, size, compar)
	const void *key;
	const void *base0;
	size_t nmemb;
	size_t size;
	int (*compar)(const void *, const void *);
{
	const char *base = base0;
	size_t lim;
	int cmp;
	const void *p;

	for (lim = nmemb; lim != 0; lim >>= 1) {
		p = base + (lim >> 1) * size;
		cmp = (*compar)(key, p);
		if (cmp == 0)
			return ((void *)p);
		if (cmp > 0) {	/* key > p: move right */
			base = (char *)p + size;
			lim--;
		}		/* else move left */
	}
	return (NULL);
}