Changeset 2b37be2

Timestamp:

Jul 29, 2009, 2:52:36 AM (15 years ago)

Author:

Anders Kaseorg <andersk@mit.edu>

Branches:

master, release-1.10, 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:

• dict.c (modified) (1 diff)

dict.c

@@ -32 +32 @@
  * Returns 1 if found, else 0. */
 int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
-  int lo, hi, mid, cmp;
-  lo = 0;
-  hi = d->size;
+  int lo = 0, hi = d->size;
   while (lo < hi) {
-    mid = (lo+hi)/2; // lo goes up and we can't hit hi, so no +1
-    cmp = strcmp(k, d->els[mid].k);
-    if (cmp == 0) {
-      lo = hi = mid;
-    } else if (cmp < 0) {
+    int mid = (lo + hi)/2; /* lo goes up and we can't hit hi, so no +1 */
+    int cmp = strcmp(k, d->els[mid].k);
+    if (cmp < 0) {
       hi = mid;
-    } else { // cmp > 0
+    } else if (cmp > 0) {
       lo = mid+1;
+    } else {
+      *pos = mid;
+      return 1;
     }
   }
   *pos = lo;
-  return !!(lo < d->size && !strcmp(k, d->els[lo].k));
+  return 0;
 }