diff options
Diffstat (limited to 'src/common/container.c')
| -rw-r--r-- | src/common/container.c | 141 |
1 files changed, 99 insertions, 42 deletions
diff --git a/src/common/container.c b/src/common/container.c index ede98eca5a..d4a2f89c90 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -571,59 +571,116 @@ smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member), int *found_out) { - const int len = smartlist_len(sl); - int hi, lo, cmp, mid; + int hi, lo, cmp, mid, len, diff; + tor_assert(sl); + tor_assert(compare); + tor_assert(found_out); + + len = smartlist_len(sl); + + /* Check for the trivial case of a zero-length list */ if (len == 0) { *found_out = 0; + /* We already know smartlist_len(sl) is 0 in this case */ return 0; - } else if (len == 1) { - cmp = compare(key, (const void **) &sl->list[0]); - if (cmp == 0) { - *found_out = 1; - return 0; - } else if (cmp < 0) { - *found_out = 0; - return 0; - } else { - *found_out = 0; - return 1; - } } - hi = smartlist_len(sl) - 1; + /* Okay, we have a real search to do */ + tor_assert(len > 0); lo = 0; + hi = len - 1; + + /* + * These invariants are always true: + * + * For all i such that 0 <= i < lo, sl[i] < key + * For all i such that hi < i <= len, sl[i] > key + */ while (lo <= hi) { - mid = (lo + hi) / 2; + diff = hi - lo; + /* + * We want mid = (lo + hi) / 2, but that could lead to overflow, so + * instead diff = hi - lo (non-negative because of loop condition), and + * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2). + */ + mid = lo + (diff / 2); cmp = compare(key, (const void**) &(sl->list[mid])); - if (cmp>0) { /* key > sl[mid] */ - lo = mid+1; - } else if (cmp<0) { /* key < sl[mid] */ - hi = mid-1; - } else { /* key == sl[mid] */ + if (cmp == 0) { + /* sl[mid] == key; we found it */ *found_out = 1; return mid; - } - } - /* lo > hi. */ - { - tor_assert(lo >= 0); - if (lo < smartlist_len(sl)) { - cmp = compare(key, (const void**) &(sl->list[lo])); + } else if (cmp > 0) { + /* + * key > sl[mid] and an index i such that sl[i] == key must + * have i > mid if it exists. + */ + + /* + * Since lo <= mid <= hi, hi can only decrease on each iteration (by + * being set to mid - 1) and hi is initially len - 1, mid < len should + * always hold, and this is not symmetric with the left end of list + * mid > 0 test below. A key greater than the right end of the list + * should eventually lead to lo == hi == mid == len - 1, and then + * we set lo to len below and fall out to the same exit we hit for + * a key in the middle of the list but not matching. Thus, we just + * assert for consistency here rather than handle a mid == len case. + */ + tor_assert(mid < len); + /* Move lo to the element immediately after sl[mid] */ + lo = mid + 1; + } else { + /* This should always be true in this case */ tor_assert(cmp < 0); - } else if (smartlist_len(sl)) { - cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1])); - tor_assert(cmp > 0); + + /* + * key < sl[mid] and an index i such that sl[i] == key must + * have i < mid if it exists. + */ + + if (mid > 0) { + /* Normal case, move hi to the element immediately before sl[mid] */ + hi = mid - 1; + } else { + /* These should always be true in this case */ + tor_assert(mid == lo); + tor_assert(mid == 0); + /* + * We were at the beginning of the list and concluded that every + * element e compares e > key. + */ + *found_out = 0; + return 0; + } } } + + /* + * lo > hi; we have no element matching key but we have elements falling + * on both sides of it. The lo index points to the first element > key. + */ + tor_assert(lo == hi + 1); /* All other cases should have been handled */ + tor_assert(lo >= 0); + tor_assert(lo <= len); + tor_assert(hi >= 0); + tor_assert(hi <= len); + + if (lo < len) { + cmp = compare(key, (const void **) &(sl->list[lo])); + tor_assert(cmp < 0); + } else { + cmp = compare(key, (const void **) &(sl->list[len-1])); + tor_assert(cmp > 0); + } + *found_out = 0; return lo; } /** Helper: compare two const char **s. */ static int -_compare_string_ptrs(const void **_a, const void **_b) +compare_string_ptrs_(const void **_a, const void **_b) { return strcmp((const char*)*_a, (const char*)*_b); } @@ -633,14 +690,14 @@ _compare_string_ptrs(const void **_a, const void **_b) void smartlist_sort_strings(smartlist_t *sl) { - smartlist_sort(sl, _compare_string_ptrs); + smartlist_sort(sl, compare_string_ptrs_); } /** Return the most frequent string in the sorted list <b>sl</b> */ char * smartlist_get_most_frequent_string(smartlist_t *sl) { - return smartlist_get_most_frequent(sl, _compare_string_ptrs); + return smartlist_get_most_frequent(sl, compare_string_ptrs_); } /** Remove duplicate strings from a sorted list, and free them with tor_free(). @@ -648,7 +705,7 @@ smartlist_get_most_frequent_string(smartlist_t *sl) void smartlist_uniq_strings(smartlist_t *sl) { - smartlist_uniq(sl, _compare_string_ptrs, _tor_free); + smartlist_uniq(sl, compare_string_ptrs_, tor_free_); } /* Heap-based priority queue implementation for O(lg N) insert and remove. @@ -849,7 +906,7 @@ smartlist_pqueue_assert_ok(smartlist_t *sl, /** Helper: compare two DIGEST_LEN digests. */ static int -_compare_digests(const void **_a, const void **_b) +compare_digests_(const void **_a, const void **_b) { return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN); } @@ -858,7 +915,7 @@ _compare_digests(const void **_a, const void **_b) void smartlist_sort_digests(smartlist_t *sl) { - smartlist_sort(sl, _compare_digests); + smartlist_sort(sl, compare_digests_); } /** Remove duplicate digests from a sorted list, and free them with tor_free(). @@ -866,12 +923,12 @@ smartlist_sort_digests(smartlist_t *sl) void smartlist_uniq_digests(smartlist_t *sl) { - smartlist_uniq(sl, _compare_digests, _tor_free); + smartlist_uniq(sl, compare_digests_, tor_free_); } /** Helper: compare two DIGEST256_LEN digests. */ static int -_compare_digests256(const void **_a, const void **_b) +compare_digests256_(const void **_a, const void **_b) { return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); } @@ -880,7 +937,7 @@ _compare_digests256(const void **_a, const void **_b) void smartlist_sort_digests256(smartlist_t *sl) { - smartlist_sort(sl, _compare_digests256); + smartlist_sort(sl, compare_digests256_); } /** Return the most frequent member of the sorted list of DIGEST256_LEN @@ -888,7 +945,7 @@ smartlist_sort_digests256(smartlist_t *sl) char * smartlist_get_most_frequent_digest256(smartlist_t *sl) { - return smartlist_get_most_frequent(sl, _compare_digests256); + return smartlist_get_most_frequent(sl, compare_digests256_); } /** Remove duplicate 256-bit digests from a sorted list, and free them with @@ -897,7 +954,7 @@ smartlist_get_most_frequent_digest256(smartlist_t *sl) void smartlist_uniq_digests256(smartlist_t *sl) { - smartlist_uniq(sl, _compare_digests256, _tor_free); + smartlist_uniq(sl, compare_digests256_, tor_free_); } /** Helper: Declare an entry type and a map type to implement a mapping using |