diff options
| -rw-r--r-- | src/common/container.c | 81 | ||||
| -rw-r--r-- | src/common/container.h | 9 | ||||
| -rw-r--r-- | src/or/test.c | 61 |
3 files changed, 151 insertions, 0 deletions
diff --git a/src/common/container.c b/src/common/container.c index 7795e514be..d8ce9d654b 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -461,6 +461,87 @@ smartlist_sort_strings(smartlist_t *sl) smartlist_sort(sl, _compare_string_ptrs); } +#define LEFT_CHILD(i) ( ((i)+1)*2 - 1) +#define RIGHT_CHILD(i) ( ((i)+1)*2 ) +#define PARENT(i) ( ((i)+1)/2 - 1) + +static INLINE void +smartlist_heapify(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx) +{ + while (1) { + int left_idx = LEFT_CHILD(idx); + int best_idx; + + if (left_idx >= sl->num_used) + return; + if (compare(sl->list[idx],sl->list[left_idx]) < 0) + best_idx = idx; + else + best_idx = left_idx; + if (left_idx+1 < sl->num_used && + compare(sl->list[left_idx+1],sl->list[best_idx]) < 0) + best_idx = left_idx + 1; + + if (best_idx == idx) { + return; + } else { + void *tmp = sl->list[idx]; + sl->list[idx] = sl->list[best_idx]; + sl->list[best_idx] = tmp; + + idx = best_idx; + } + } +} + +void +smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + void *item) +{ + int idx; + smartlist_add(sl,item); + + for (idx = sl->num_used - 1; idx; ) { + int parent = PARENT(idx); + if (compare(sl->list[idx], sl->list[parent]) < 0) { + void *tmp = sl->list[parent]; + sl->list[parent] = sl->list[idx]; + sl->list[idx] = tmp; + idx = parent; + } else { + return; + } + } +} + +void * +smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b)) +{ + void *top; + tor_assert(sl->num_used); + + top = sl->list[0]; + if (--sl->num_used) { + sl->list[0] = sl->list[sl->num_used]; + smartlist_heapify(sl, compare, 0); + } + return top; +} + +void +smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b)) +{ + int i; + for (i = sl->num_used - 1; i > 0; --i) { + tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0); + } +} + /** Helper: compare two DIGEST_LEN digests. */ static int _compare_digests(const void **_a, const void **_b) diff --git a/src/common/container.h b/src/common/container.h index 1031a6ef13..0b5d0618af 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -38,6 +38,7 @@ int smartlist_string_num_isin(const smartlist_t *sl, int num); int smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2); void smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2); void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2); + /* smartlist_choose() is defined in crypto.[ch] */ #ifdef DEBUG_SMARTLIST /** Return the number of items in sl. @@ -76,6 +77,14 @@ void smartlist_sort_digests(smartlist_t *sl); void *smartlist_bsearch(smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member)); +void smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + void *item); +void *smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b)); +void smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b)); + #define SPLIT_SKIP_SPACE 0x01 #define SPLIT_IGNORE_BLANK 0x02 int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, diff --git a/src/or/test.c b/src/or/test.c index 3e18df9d33..4a258afb71 100644 --- a/src/or/test.c +++ b/src/or/test.c @@ -921,6 +921,66 @@ test_util(void) smartlist_free(sl); } +static int +_compare_strings_for_pqueue(const void *s1, const void *s2) +{ + return strcmp((const char*)s1, (const char*)s2); +} + +static void +test_pqueue(void) +{ + smartlist_t *sl; + int (*cmp)(const void *, const void*); +#define OK() smartlist_pqueue_assert_ok(sl, cmp) + + cmp = _compare_strings_for_pqueue; + + sl = smartlist_create(); + smartlist_pqueue_add(sl, cmp, "cows"); + smartlist_pqueue_add(sl, cmp, "zebras"); + smartlist_pqueue_add(sl, cmp, "fish"); + smartlist_pqueue_add(sl, cmp, "frogs"); + smartlist_pqueue_add(sl, cmp, "apples"); + smartlist_pqueue_add(sl, cmp, "squid");// + smartlist_pqueue_add(sl, cmp, "daschunds"); + smartlist_pqueue_add(sl, cmp, "eggplants"); + smartlist_pqueue_add(sl, cmp, "weissbier");// + smartlist_pqueue_add(sl, cmp, "lobsters"); + smartlist_pqueue_add(sl, cmp, "roquefort");// + + OK(); + + test_eq(smartlist_len(sl), 11); + test_streq(smartlist_get(sl, 0), "apples"); + test_streq(smartlist_pqueue_pop(sl, cmp), "apples"); + test_eq(smartlist_len(sl), 10); + OK(); + test_streq(smartlist_pqueue_pop(sl, cmp), "cows"); + test_streq(smartlist_pqueue_pop(sl, cmp), "daschunds"); + smartlist_pqueue_add(sl, cmp, "chinchillas"); + OK(); + smartlist_pqueue_add(sl, cmp, "fireflies"); + OK(); + test_streq(smartlist_pqueue_pop(sl, cmp), "chinchillas"); + test_streq(smartlist_pqueue_pop(sl, cmp), "eggplants"); + test_streq(smartlist_pqueue_pop(sl, cmp), "fireflies"); + OK(); + test_streq(smartlist_pqueue_pop(sl, cmp), "fish"); + test_streq(smartlist_pqueue_pop(sl, cmp), "frogs"); + test_streq(smartlist_pqueue_pop(sl, cmp), "lobsters"); + test_streq(smartlist_pqueue_pop(sl, cmp), "roquefort"); + OK(); + test_eq(smartlist_len(sl), 3); + test_streq(smartlist_pqueue_pop(sl, cmp), "squid"); + test_streq(smartlist_pqueue_pop(sl, cmp), "weissbier"); + test_streq(smartlist_pqueue_pop(sl, cmp), "zebras"); + test_eq(smartlist_len(sl), 0); + OK(); +#undef OK + smartlist_free(sl); +} + static void test_gzip(void) { @@ -1675,6 +1735,7 @@ main(int c, char**v) test_util(); test_strmap(); test_control_formats(); + test_pqueue(); puts("\n========================= Onion Skins ====================="); test_onion(); test_onion_handshake(); |