0

我对下面 VS2010 上的代码有一个非常烦人的问题：

template <class N>
size_t NumericIndex<N>::GetPageIndex(const PageRef& page, Id id) const
{
  size_t size=page->entries.size();

  if (size>0) {
    size_t left=0;
    size_t right=size-1;
    size_t mid;

    while (left<=right) {
      mid=(left+right)/2;
      if (page->entries[mid].startId<=id &&
          (mid+1>=size || page->entries[mid+1].startId>id)) {
        return mid;
      }
      else if (page->entries[mid].startId<id) {
        left=mid+1;
      }
      else {
        right=mid-1;
      }
    }
  }

  return size;
}

它通过以下方法调用：

template <class N>
bool NumericIndex<N>::GetOffset(const N& id,
                                FileOffset& offset) const
{
  size_t r=GetPageIndex(root,id);
  ...
}

问题是，在第一次调用该方法时，一切都很好，size并且left初始化right良好，但在第二次调用时，它直接跳转到该行while (left<=right) {，跳过该行之前的每个指令，并right用垃圾初始化。

你知道问题可能出在哪里吗？

提前致谢。

该代码是项目libosmscout的一部分。

[编辑]

Arne Mertz 解决了这个问题。实际上这是循环的第二遍。由于 size_t 是无符号类型，所以当 mid == 0 和 right=mid-1 时我们会溢出。

修复代码应该是：

template <class N>
size_t NumericIndex<N>::GetPageIndex(const PageRef& page, Id id) const
{
  size_t size=page->entries.size();

  if (size>0) {
    size_t left=0;
    size_t right=size-1;
    size_t mid;

    while (left<=right) {
      mid=(left+right)/2;
      if (page->entries[mid].startId<=id &&
          (mid+1>=size || page->entries[mid+1].startId>id)) {
        return mid;
      }
      else if (page->entries[mid].startId<id) {
        left=mid+1;
      }
      else {
        if (mid == 0) {
          return size;
        }
        right=mid-1;
      }
    }
  }

  return size;
}
4

0 回答 0