Changes in / [c4efb46:19cc7b00]
 Files:

 1 added
 1 edited
Legend:
 Unmodified
 Added
 Removed

dict.c
r4d86e06 r7cd5878 3 3 * Stores as a sorted list of key/value pairs. 4 4 * 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 6 6 */ 7 7 … … 30 30 /* Finds the position of an element with key k, or of the element where 31 31 * this element would logically go, and stores the index in pos. 32 * TODO: optimize to do a binary search.33 32 * Returns 1 if found, else 0. */ 34 33 int _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 } 42 47 } 48 *pos = lo; 49 return !!(lo < d>size && !strcmp(k, d>els[lo].k)); 43 50 } 44 51
Note: See TracChangeset
for help on using the changeset viewer.