aboutsummaryrefslogtreecommitdiff
path: root/src/common/container.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/common/container.c')
-rw-r--r--src/common/container.c214
1 files changed, 152 insertions, 62 deletions
diff --git a/src/common/container.c b/src/common/container.c
index ede98eca5..b937d544f 100644
--- a/src/common/container.c
+++ b/src/common/container.c
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2012, The Tor Project, Inc. */
+ * Copyright (c) 2007-2013, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
@@ -163,7 +163,7 @@ smartlist_string_remove(smartlist_t *sl, const char *element)
/** Return true iff some element E of sl has E==element.
*/
int
-smartlist_isin(const smartlist_t *sl, const void *element)
+smartlist_contains(const smartlist_t *sl, const void *element)
{
int i;
for (i=0; i < sl->num_used; i++)
@@ -176,7 +176,7 @@ smartlist_isin(const smartlist_t *sl, const void *element)
* !strcmp(E,<b>element</b>)
*/
int
-smartlist_string_isin(const smartlist_t *sl, const char *element)
+smartlist_contains_string(const smartlist_t *sl, const char *element)
{
int i;
if (!sl) return 0;
@@ -203,7 +203,7 @@ smartlist_string_pos(const smartlist_t *sl, const char *element)
* !strcasecmp(E,<b>element</b>)
*/
int
-smartlist_string_isin_case(const smartlist_t *sl, const char *element)
+smartlist_contains_string_case(const smartlist_t *sl, const char *element)
{
int i;
if (!sl) return 0;
@@ -217,11 +217,11 @@ smartlist_string_isin_case(const smartlist_t *sl, const char *element)
* to the decimal encoding of <b>num</b>.
*/
int
-smartlist_string_num_isin(const smartlist_t *sl, int num)
+smartlist_contains_int_as_string(const smartlist_t *sl, int num)
{
char buf[32]; /* long enough for 64-bit int, and then some. */
tor_snprintf(buf,sizeof(buf),"%d", num);
- return smartlist_string_isin(sl, buf);
+ return smartlist_contains_string(sl, buf);
}
/** Return true iff the two lists contain the same strings in the same
@@ -243,11 +243,30 @@ smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2)
return 1;
}
+/** Return true iff the two lists contain the same int pointer values in
+ * the same order, or if they are both NULL. */
+int
+smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2)
+{
+ if (sl1 == NULL)
+ return sl2 == NULL;
+ if (sl2 == NULL)
+ return 0;
+ if (smartlist_len(sl1) != smartlist_len(sl2))
+ return 0;
+ SMARTLIST_FOREACH(sl1, int *, cp1, {
+ int *cp2 = smartlist_get(sl2, cp1_sl_idx);
+ if (*cp1 != *cp2)
+ return 0;
+ });
+ return 1;
+}
+
/** Return true iff <b>sl</b> has some element E such that
* tor_memeq(E,<b>element</b>,DIGEST_LEN)
*/
int
-smartlist_digest_isin(const smartlist_t *sl, const char *element)
+smartlist_contains_digest(const smartlist_t *sl, const char *element)
{
int i;
if (!sl) return 0;
@@ -257,19 +276,19 @@ smartlist_digest_isin(const smartlist_t *sl, const char *element)
return 0;
}
-/** Return true iff some element E of sl2 has smartlist_isin(sl1,E).
+/** Return true iff some element E of sl2 has smartlist_contains(sl1,E).
*/
int
smartlist_overlap(const smartlist_t *sl1, const smartlist_t *sl2)
{
int i;
for (i=0; i < sl2->num_used; i++)
- if (smartlist_isin(sl1, sl2->list[i]))
+ if (smartlist_contains(sl1, sl2->list[i]))
return 1;
return 0;
}
-/** Remove every element E of sl1 such that !smartlist_isin(sl2,E).
+/** Remove every element E of sl1 such that !smartlist_contains(sl2,E).
* Does not preserve the order of sl1.
*/
void
@@ -277,13 +296,13 @@ smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2)
{
int i;
for (i=0; i < sl1->num_used; i++)
- if (!smartlist_isin(sl2, sl1->list[i])) {
+ if (!smartlist_contains(sl2, sl1->list[i])) {
sl1->list[i] = sl1->list[--sl1->num_used]; /* swap with the end */
i--; /* so we process the new i'th element */
}
}
-/** Remove every element E of sl1 such that smartlist_isin(sl2,E).
+/** Remove every element E of sl1 such that smartlist_contains(sl2,E).
* Does not preserve the order of sl1.
*/
void
@@ -571,59 +590,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 +709,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 +724,27 @@ 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_);
+}
+
+/** Helper: compare two pointers. */
+static int
+compare_ptrs_(const void **_a, const void **_b)
+{
+ const void *a = *_a, *b = *_b;
+ if (a<b)
+ return -1;
+ else if (a==b)
+ return 0;
+ else
+ return 1;
+}
+
+/** Sort <b>sl</b> in ascending order of the pointers it contains. */
+void
+smartlist_sort_pointers(smartlist_t *sl)
+{
+ smartlist_sort(sl, compare_ptrs_);
}
/* Heap-based priority queue implementation for O(lg N) insert and remove.
@@ -849,7 +945,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 +954,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 +962,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 +976,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 +984,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 +993,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
@@ -928,7 +1024,7 @@ strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b)
static INLINE unsigned int
strmap_entry_hash(const strmap_entry_t *a)
{
- return ht_string_hash(a->key);
+ return (unsigned) siphash24g(a->key, strlen(a->key));
}
/** Helper: compare digestmap_entry_t objects by key value. */
@@ -942,13 +1038,7 @@ digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b)
static INLINE unsigned int
digestmap_entry_hash(const digestmap_entry_t *a)
{
-#if SIZEOF_INT != 8
- const uint32_t *p = (const uint32_t*)a->key;
- return p[0] ^ p[1] ^ p[2] ^ p[3] ^ p[4];
-#else
- const uint64_t *p = (const uint64_t*)a->key;
- return p[0] ^ p[1];
-#endif
+ return (unsigned) siphash24g(a->key, DIGEST_LEN);
}
HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
generated by cgit v1.2.3 (git 2.25.4) at 2024-05-18 08:54:22 +0000