Changeset 7cd5878 for dict.c


Ignore:
Timestamp:
Jul 28, 2009, 10:12:06 PM (12 years ago)
Author:
David Benjamin <davidben@mit.edu>
Branches:
master, release-1.4, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9
Children:
d4ecc78
Parents:
f80ada8
git-author:
David Benjamin <davidben@mit.edu> (07/28/09 20:13:03)
git-committer:
David Benjamin <davidben@mit.edu> (07/28/09 22:12:06)
Message:
Implement binary search in dict.c

Just because there's a TODO and it was asking for it.

Signed-off-by: David Benjamin <davidben@mit.edu>
File:
1 edited

Legend:

Unmodified
Added
Removed
  • dict.c

    r4d86e06 r7cd5878  
    33 * Stores as a sorted list of key/value pairs.
    44 * O(n) on inserts and deletes.
    5  * O(n) on searches, although it should switch to a binary search for O(log n)
     5 * O(log n) on searches
    66 */
    77
     
    3030/* Finds the position of an element with key k, or of the element where
    3131 * this element would logically go, and stores the index in pos.
    32  * TODO: optimize to do a binary search.
    3332 * Returns 1 if found, else 0. */
    3433int _owl_dict_find_pos(owl_dict *d, char *k, int *pos) {
    35   int i;
    36   for (i=0; (i<d->size) && strcmp(k,d->els[i].k)>0; i++);
    37   *pos = i;
    38   if (i>=d->size || strcmp(k,d->els[i].k)) {
    39     return(0);
    40   } else {
    41     return(1);
     34  int lo, hi, mid, cmp;
     35  lo = 0;
     36  hi = d->size;
     37  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) {
     43      hi = mid;
     44    } else { // cmp > 0
     45      lo = mid+1;
     46    }
    4247  }
     48  *pos = lo;
     49  return !!(lo < d->size && !strcmp(k, d->els[lo].k));
    4350}
    4451
Note: See TracChangeset for help on using the changeset viewer.