Changeset 2b37be2


Ignore:
Timestamp:
Jul 29, 2009, 2:52:36 AM (8 years ago)
Author:
Anders Kaseorg <andersk@mit.edu>
Branches:
master, release-1.4, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9
Children:
e711ca7
Parents:
19cc7b00
git-author:
Anders Kaseorg <andersk@mit.edu> (07/29/09 02:32:07)
git-committer:
Anders Kaseorg <andersk@mit.edu> (07/29/09 02:52:36)
Message:
_owl_dict_find_pos: Clean up binary search.

The incomprehensible boolean return expression is better expressed
using control flow; as a happy side effect, this optimizes out an
expected 2 strcmps.  Correctly scope variables.  Also, don’t use C++
comments in C.

Signed-off-by: Anders Kaseorg <andersk@mit.edu>
File:
1 edited

Legend:

Unmodified
Added
Removed
  • dict.c

    r7cd5878 r2b37be2  
    3232 * Returns 1 if found, else 0. */
    3333int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
    34   int lo, hi, mid, cmp;
    35   lo = 0;
    36   hi = d->size;
     34  int lo = 0, hi = d->size;
    3735  while (lo < hi) {
    38     mid = (lo+hi)/2; // lo goes up and we can't hit hi, so no +1
    39     cmp = strcmp(k, d->els[mid].k);
    40     if (cmp == 0) {
    41       lo = hi = mid;
    42     } else if (cmp < 0) {
     36    int mid = (lo + hi)/2; /* lo goes up and we can't hit hi, so no +1 */
     37    int cmp = strcmp(k, d->els[mid].k);
     38    if (cmp < 0) {
    4339      hi = mid;
    44     } else { // cmp > 0
     40    } else if (cmp > 0) {
    4541      lo = mid+1;
     42    } else {
     43      *pos = mid;
     44      return 1;
    4645    }
    4746  }
    4847  *pos = lo;
    49   return !!(lo < d->size && !strcmp(k, d->els[lo].k));
     48  return 0;
    5049}
    5150
Note: See TracChangeset for help on using the changeset viewer.