From 657ff55408d82f49fc9599cb662702cdc0995f08 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Thu, 21 Jun 2018 16:25:31 -0400 Subject: Split container.c based on container types, and minimize includes Minimizing includes revealed other places includes were necessary. --- src/lib/container/bitarray.h | 80 +++ src/lib/container/bloomfilt.c | 49 ++ src/lib/container/bloomfilt.h | 58 ++ src/lib/container/container.c | 1549 ----------------------------------------- src/lib/container/container.h | 745 +------------------- src/lib/container/include.am | 12 +- src/lib/container/map.c | 413 +++++++++++ src/lib/container/map.h | 255 +++++++ src/lib/container/order.c | 51 ++ src/lib/container/order.h | 54 ++ src/lib/container/smartlist.c | 1094 +++++++++++++++++++++++++++++ src/lib/container/smartlist.h | 351 ++++++++++ src/lib/malloc/util_malloc.c | 1 - src/lib/malloc/util_malloc.h | 2 + 14 files changed, 2422 insertions(+), 2292 deletions(-) create mode 100644 src/lib/container/bitarray.h create mode 100644 src/lib/container/bloomfilt.c create mode 100644 src/lib/container/bloomfilt.h delete mode 100644 src/lib/container/container.c create mode 100644 src/lib/container/map.c create mode 100644 src/lib/container/map.h create mode 100644 src/lib/container/order.c create mode 100644 src/lib/container/order.h create mode 100644 src/lib/container/smartlist.c create mode 100644 src/lib/container/smartlist.h (limited to 'src/lib') diff --git a/src/lib/container/bitarray.h b/src/lib/container/bitarray.h new file mode 100644 index 0000000000..2cea433fb0 --- /dev/null +++ b/src/lib/container/bitarray.h @@ -0,0 +1,80 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_BITARRAY_H +#define TOR_BITARRAY_H + +#include "orconfig.h" +#include +#include "lib/cc/torint.h" +#include "lib/malloc/util_malloc.h" + +#if SIZEOF_INT == 4 +#define BITARRAY_SHIFT 5 +#elif SIZEOF_INT == 8 +#define BITARRAY_SHIFT 6 +#else +#error "int is neither 4 nor 8 bytes. I can't deal with that." +#endif /* SIZEOF_INT == 4 || ... */ +#define BITARRAY_MASK ((1u<n_bits bits. */ +static inline bitarray_t * +bitarray_init_zero(unsigned int n_bits) +{ + /* round up to the next int. */ + size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; + return tor_calloc(sz, sizeof(unsigned int)); +} +/** Expand ba from holding n_bits_old to n_bits_new, + * clearing all new bits. Returns a possibly changed pointer to the + * bitarray. */ +static inline bitarray_t * +bitarray_expand(bitarray_t *ba, + unsigned int n_bits_old, unsigned int n_bits_new) +{ + size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT; + size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT; + char *ptr; + if (sz_new <= sz_old) + return ba; + ptr = tor_reallocarray(ba, sz_new, sizeof(unsigned int)); + /* This memset does nothing to the older excess bytes. But they were + * already set to 0 by bitarry_init_zero. */ + memset(ptr+sz_old*sizeof(unsigned int), 0, + (sz_new-sz_old)*sizeof(unsigned int)); + return (bitarray_t*) ptr; +} +/** Free the bit array ba. */ +static inline void +bitarray_free_(bitarray_t *ba) +{ + tor_free(ba); +} +#define bitarray_free(ba) FREE_AND_NULL(bitarray_t, bitarray_free_, (ba)) + +/** Set the bitth bit in b to 1. */ +static inline void +bitarray_set(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); +} +/** Set the bitth bit in b to 0. */ +static inline void +bitarray_clear(bitarray_t *b, int bit) +{ + b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); +} +/** Return true iff bitth bit in b is nonzero. NOTE: does + * not necessarily return 1 on true. */ +static inline unsigned int +bitarray_is_set(bitarray_t *b, int bit) +{ + return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); +} + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/bloomfilt.c b/src/lib/container/bloomfilt.c new file mode 100644 index 0000000000..4847408ee7 --- /dev/null +++ b/src/lib/container/bloomfilt.c @@ -0,0 +1,49 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file container.c + * \brief Implements a smartlist (a resizable array) along + * with helper functions to use smartlists. Also includes + * hash table implementations of a string-to-void* map, and of + * a digest-to-void* map. + **/ + +#include +#include "lib/malloc/util_malloc.h" +#include "lib/container/bloomfilt.h" +#include "common/util.h" // For tor_log2 + +/** Return a newly allocated digestset_t, optimized to hold a total of + * max_elements digests with a reasonably low false positive weight. */ +digestset_t * +digestset_new(int max_elements) +{ + /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k + * is the number of hash functions per entry, m is the bits in the array, + * and n is the number of elements inserted. For us, k==4, n<=max_elements, + * and m==n_bits= approximately max_elements*32. This gives + * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019 + * + * It would be more optimal in space vs false positives to get this false + * positive rate by going for k==13, and m==18.5n, but we also want to + * conserve CPU, and k==13 is pretty big. + */ + int n_bits = 1u << (tor_log2(max_elements)+5); + digestset_t *r = tor_malloc(sizeof(digestset_t)); + r->mask = n_bits - 1; + r->ba = bitarray_init_zero(n_bits); + return r; +} + +/** Free all storage held in set. */ +void +digestset_free_(digestset_t *set) +{ + if (!set) + return; + bitarray_free(set->ba); + tor_free(set); +} diff --git a/src/lib/container/bloomfilt.h b/src/lib/container/bloomfilt.h new file mode 100644 index 0000000000..adcdb10fc3 --- /dev/null +++ b/src/lib/container/bloomfilt.h @@ -0,0 +1,58 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_BLOOMFILT_H +#define TOR_BLOOMFILT_H + +#include "orconfig.h" +#include "lib/cc/torint.h" +#include "lib/container/bitarray.h" +#include "siphash.h" + +/** A set of digests, implemented as a Bloom filter. */ +typedef struct { + int mask; /**< One less than the number of bits in ba; always one less + * than a power of two. */ + bitarray_t *ba; /**< A bit array to implement the Bloom filter. */ +} digestset_t; + +#define BIT(n) ((n) & set->mask) +/** Add the digest digest to set. */ +static inline void +digestset_add(digestset_t *set, const char *digest) +{ + const uint64_t x = siphash24g(digest, 20); + const uint32_t d1 = (uint32_t) x; + const uint32_t d2 = (uint32_t)( (x>>16) + x); + const uint32_t d3 = (uint32_t)( (x>>32) + x); + const uint32_t d4 = (uint32_t)( (x>>48) + x); + bitarray_set(set->ba, BIT(d1)); + bitarray_set(set->ba, BIT(d2)); + bitarray_set(set->ba, BIT(d3)); + bitarray_set(set->ba, BIT(d4)); +} + +/** If digest is in set, return nonzero. Otherwise, + * probably return zero. */ +static inline int +digestset_contains(const digestset_t *set, const char *digest) +{ + const uint64_t x = siphash24g(digest, 20); + const uint32_t d1 = (uint32_t) x; + const uint32_t d2 = (uint32_t)( (x>>16) + x); + const uint32_t d3 = (uint32_t)( (x>>32) + x); + const uint32_t d4 = (uint32_t)( (x>>48) + x); + return bitarray_is_set(set->ba, BIT(d1)) && + bitarray_is_set(set->ba, BIT(d2)) && + bitarray_is_set(set->ba, BIT(d3)) && + bitarray_is_set(set->ba, BIT(d4)); +} +#undef BIT + +digestset_t *digestset_new(int max_elements); +void digestset_free_(digestset_t* set); +#define digestset_free(set) FREE_AND_NULL(digestset_t, digestset_free_, (set)) + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/container.c b/src/lib/container/container.c deleted file mode 100644 index d31044fe27..0000000000 --- a/src/lib/container/container.c +++ /dev/null @@ -1,1549 +0,0 @@ -/* Copyright (c) 2003-2004, Roger Dingledine - * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2018, The Tor Project, Inc. */ -/* See LICENSE for licensing information */ - -/** - * \file container.c - * \brief Implements a smartlist (a resizable array) along - * with helper functions to use smartlists. Also includes - * hash table implementations of a string-to-void* map, and of - * a digest-to-void* map. - **/ - -#include "common/util.h" -#include "lib/container/container.h" -#include "lib/crypt_ops/crypto_digest.h" - -#include -#include - -#include "ht.h" - -/** All newly allocated smartlists have this capacity. */ -#define SMARTLIST_DEFAULT_CAPACITY 16 - -/** Allocate and return an empty smartlist. - */ -MOCK_IMPL(smartlist_t *, -smartlist_new,(void)) -{ - smartlist_t *sl = tor_malloc(sizeof(smartlist_t)); - sl->num_used = 0; - sl->capacity = SMARTLIST_DEFAULT_CAPACITY; - sl->list = tor_calloc(sizeof(void *), sl->capacity); - return sl; -} - -/** Deallocate a smartlist. Does not release storage associated with the - * list's elements. - */ -MOCK_IMPL(void, -smartlist_free_,(smartlist_t *sl)) -{ - if (!sl) - return; - tor_free(sl->list); - tor_free(sl); -} - -/** Remove all elements from the list. - */ -void -smartlist_clear(smartlist_t *sl) -{ - memset(sl->list, 0, sizeof(void *) * sl->num_used); - sl->num_used = 0; -} - -#if SIZE_MAX < INT_MAX -#error "We don't support systems where size_t is smaller than int." -#endif - -/** Make sure that sl can hold at least size entries. */ -static inline void -smartlist_ensure_capacity(smartlist_t *sl, size_t size) -{ - /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */ -#if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX -#define MAX_CAPACITY (INT_MAX) -#else -#define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*)))) -#endif - - raw_assert(size <= MAX_CAPACITY); - - if (size > (size_t) sl->capacity) { - size_t higher = (size_t) sl->capacity; - if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { - higher = MAX_CAPACITY; - } else { - while (size > higher) - higher *= 2; - } - sl->list = tor_reallocarray(sl->list, sizeof(void *), - ((size_t)higher)); - memset(sl->list + sl->capacity, 0, - sizeof(void *) * (higher - sl->capacity)); - sl->capacity = (int) higher; - } -#undef ASSERT_CAPACITY -#undef MAX_CAPACITY -} - -/** Append element to the end of the list. */ -void -smartlist_add(smartlist_t *sl, void *element) -{ - smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); - sl->list[sl->num_used++] = element; -} - -/** Append each element from S2 to the end of S1. */ -void -smartlist_add_all(smartlist_t *s1, const smartlist_t *s2) -{ - size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used; - tor_assert(new_size >= (size_t) s1->num_used); /* check for overflow. */ - smartlist_ensure_capacity(s1, new_size); - memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*)); - tor_assert(new_size <= INT_MAX); /* redundant. */ - s1->num_used = (int) new_size; -} - -/** Append a copy of string to sl */ -void -smartlist_add_strdup(struct smartlist_t *sl, const char *string) -{ - char *copy; - - copy = tor_strdup(string); - - smartlist_add(sl, copy); -} - -/** Remove all elements E from sl such that E==element. Preserve - * the order of any elements before E, but elements after E can be - * rearranged. - */ -void -smartlist_remove(smartlist_t *sl, const void *element) -{ - int i; - if (element == NULL) - return; - for (i=0; i < sl->num_used; i++) - if (sl->list[i] == element) { - sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ - i--; /* so we process the new i'th element */ - sl->list[sl->num_used] = NULL; - } -} - -/** As smartlist_remove, but do not change the order of - * any elements not removed */ -void -smartlist_remove_keeporder(smartlist_t *sl, const void *element) -{ - int i, j, num_used_orig = sl->num_used; - if (element == NULL) - return; - - for (i=j=0; j < num_used_orig; ++j) { - if (sl->list[j] == element) { - --sl->num_used; - } else { - sl->list[i++] = sl->list[j]; - } - } -} - -/** If sl is nonempty, remove and return the final element. Otherwise, - * return NULL. */ -void * -smartlist_pop_last(smartlist_t *sl) -{ - tor_assert(sl); - if (sl->num_used) { - void *tmp = sl->list[--sl->num_used]; - sl->list[sl->num_used] = NULL; - return tmp; - } else - return NULL; -} - -/** Reverse the order of the items in sl. */ -void -smartlist_reverse(smartlist_t *sl) -{ - int i, j; - void *tmp; - tor_assert(sl); - for (i = 0, j = sl->num_used-1; i < j; ++i, --j) { - tmp = sl->list[i]; - sl->list[i] = sl->list[j]; - sl->list[j] = tmp; - } -} - -/** If there are any strings in sl equal to element, remove and free them. - * Does not preserve order. */ -void -smartlist_string_remove(smartlist_t *sl, const char *element) -{ - int i; - tor_assert(sl); - tor_assert(element); - for (i = 0; i < sl->num_used; ++i) { - if (!strcmp(element, sl->list[i])) { - tor_free(sl->list[i]); - sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ - i--; /* so we process the new i'th element */ - sl->list[sl->num_used] = NULL; - } - } -} - -/** Return true iff some element E of sl has E==element. - */ -int -smartlist_contains(const smartlist_t *sl, const void *element) -{ - int i; - for (i=0; i < sl->num_used; i++) - if (sl->list[i] == element) - return 1; - return 0; -} - -/** Return true iff sl has some element E such that - * !strcmp(E,element) - */ -int -smartlist_contains_string(const smartlist_t *sl, const char *element) -{ - int i; - if (!sl) return 0; - for (i=0; i < sl->num_used; i++) - if (strcmp((const char*)sl->list[i],element)==0) - return 1; - return 0; -} - -/** If element is equal to an element of sl, return that - * element's index. Otherwise, return -1. */ -int -smartlist_string_pos(const smartlist_t *sl, const char *element) -{ - int i; - if (!sl) return -1; - for (i=0; i < sl->num_used; i++) - if (strcmp((const char*)sl->list[i],element)==0) - return i; - return -1; -} - -/** If element is the same pointer as an element of sl, return - * that element's index. Otherwise, return -1. */ -int -smartlist_pos(const smartlist_t *sl, const void *element) -{ - int i; - if (!sl) return -1; - for (i=0; i < sl->num_used; i++) - if (element == sl->list[i]) - return i; - return -1; -} - -/** Return true iff sl has some element E such that - * !strcasecmp(E,element) - */ -int -smartlist_contains_string_case(const smartlist_t *sl, const char *element) -{ - int i; - if (!sl) return 0; - for (i=0; i < sl->num_used; i++) - if (strcasecmp((const char*)sl->list[i],element)==0) - return 1; - return 0; -} - -/** Return true iff sl has some element E such that E is equal - * to the decimal encoding of num. - */ -int -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_contains_string(sl, buf); -} - -/** Return true iff the two lists contain the same strings in the same - * order, or if they are both NULL. */ -int -smartlist_strings_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, const char *, cp1, { - const char *cp2 = smartlist_get(sl2, cp1_sl_idx); - if (strcmp(cp1, cp2)) - return 0; - }); - 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 sl has some element E such that - * tor_memeq(E,element,DIGEST_LEN) - */ -int -smartlist_contains_digest(const smartlist_t *sl, const char *element) -{ - int i; - if (!sl) return 0; - for (i=0; i < sl->num_used; i++) - if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN)) - return 1; - return 0; -} - -/** 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_contains(sl1, sl2->list[i])) - return 1; - return 0; -} - -/** Remove every element E of sl1 such that !smartlist_contains(sl2,E). - * Does not preserve the order of sl1. - */ -void -smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) -{ - int i; - for (i=0; i < sl1->num_used; 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 */ - sl1->list[sl1->num_used] = NULL; - } -} - -/** Remove every element E of sl1 such that smartlist_contains(sl2,E). - * Does not preserve the order of sl1. - */ -void -smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) -{ - int i; - for (i=0; i < sl2->num_used; i++) - smartlist_remove(sl1, sl2->list[i]); -} - -/** Remove the idxth element of sl; if idx is not the last - * element, swap the last element of sl into the idxth space. - */ -void -smartlist_del(smartlist_t *sl, int idx) -{ - tor_assert(sl); - tor_assert(idx>=0); - tor_assert(idx < sl->num_used); - sl->list[idx] = sl->list[--sl->num_used]; - sl->list[sl->num_used] = NULL; -} - -/** Remove the idxth element of sl; if idx is not the last element, - * moving all subsequent elements back one space. Return the old value - * of the idxth element. - */ -void -smartlist_del_keeporder(smartlist_t *sl, int idx) -{ - tor_assert(sl); - tor_assert(idx>=0); - tor_assert(idx < sl->num_used); - --sl->num_used; - if (idx < sl->num_used) - memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx)); - sl->list[sl->num_used] = NULL; -} - -/** Insert the value val as the new idxth element of - * sl, moving all items previously at idx or later - * forward one space. - */ -void -smartlist_insert(smartlist_t *sl, int idx, void *val) -{ - tor_assert(sl); - tor_assert(idx>=0); - tor_assert(idx <= sl->num_used); - if (idx == sl->num_used) { - smartlist_add(sl, val); - } else { - smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); - /* Move other elements away */ - if (idx < sl->num_used) - memmove(sl->list + idx + 1, sl->list + idx, - sizeof(void*)*(sl->num_used-idx)); - sl->num_used++; - sl->list[idx] = val; - } -} - -/** - * Split a string str along all occurrences of sep, - * appending the (newly allocated) split strings, in order, to - * sl. Return the number of strings added to sl. - * - * If flags&SPLIT_SKIP_SPACE is true, remove initial and - * trailing space from each entry. - * If flags&SPLIT_IGNORE_BLANK is true, remove any entries - * of length 0. - * If flags&SPLIT_STRIP_SPACE is true, strip spaces from each - * split string. - * - * If max\>0, divide the string into no more than max pieces. If - * sep is NULL, split on any sequence of horizontal space. - */ -int -smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, - int flags, int max) -{ - const char *cp, *end, *next; - int n = 0; - - tor_assert(sl); - tor_assert(str); - - cp = str; - while (1) { - if (flags&SPLIT_SKIP_SPACE) { - while (TOR_ISSPACE(*cp)) ++cp; - } - - if (max>0 && n == max-1) { - end = strchr(cp,'\0'); - } else if (sep) { - end = strstr(cp,sep); - if (!end) - end = strchr(cp,'\0'); - } else { - for (end = cp; *end && *end != '\t' && *end != ' '; ++end) - ; - } - - tor_assert(end); - - if (!*end) { - next = NULL; - } else if (sep) { - next = end+strlen(sep); - } else { - next = end+1; - while (*next == '\t' || *next == ' ') - ++next; - } - - if (flags&SPLIT_SKIP_SPACE) { - while (end > cp && TOR_ISSPACE(*(end-1))) - --end; - } - if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) { - char *string = tor_strndup(cp, end-cp); - if (flags&SPLIT_STRIP_SPACE) - tor_strstrip(string, " "); - smartlist_add(sl, string); - ++n; - } - if (!next) - break; - cp = next; - } - - return n; -} - -/** Allocate and return a new string containing the concatenation of - * the elements of sl, in order, separated by join. If - * terminate is true, also terminate the string with join. - * If len_out is not NULL, set len_out to the length of - * the returned string. Requires that every element of sl is - * NUL-terminated string. - */ -char * -smartlist_join_strings(smartlist_t *sl, const char *join, - int terminate, size_t *len_out) -{ - return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out); -} - -/** As smartlist_join_strings, but instead of separating/terminated with a - * NUL-terminated string join, uses the join_len-byte sequence - * at join. (Useful for generating a sequence of NUL-terminated - * strings.) - */ -char * -smartlist_join_strings2(smartlist_t *sl, const char *join, - size_t join_len, int terminate, size_t *len_out) -{ - int i; - size_t n = 0; - char *r = NULL, *dst, *src; - - tor_assert(sl); - tor_assert(join); - - if (terminate) - n = join_len; - - for (i = 0; i < sl->num_used; ++i) { - n += strlen(sl->list[i]); - if (i+1 < sl->num_used) /* avoid double-counting the last one */ - n += join_len; - } - dst = r = tor_malloc(n+1); - for (i = 0; i < sl->num_used; ) { - for (src = sl->list[i]; *src; ) - *dst++ = *src++; - if (++i < sl->num_used) { - memcpy(dst, join, join_len); - dst += join_len; - } - } - if (terminate) { - memcpy(dst, join, join_len); - dst += join_len; - } - *dst = '\0'; - - if (len_out) - *len_out = dst-r; - return r; -} - -/** Sort the members of sl into an order defined by - * the ordering function compare, which returns less then 0 if a - * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b. - */ -void -smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) -{ - if (!sl->num_used) - return; - qsort(sl->list, sl->num_used, sizeof(void*), - (int (*)(const void *,const void*))compare); -} - -/** Given a smartlist sl sorted with the function compare, - * return the most frequent member in the list. Break ties in favor of - * later elements. If the list is empty, return NULL. If count_out is - * non-null, set it to the count of the most frequent member. - */ -void * -smartlist_get_most_frequent_(const smartlist_t *sl, - int (*compare)(const void **a, const void **b), - int *count_out) -{ - const void *most_frequent = NULL; - int most_frequent_count = 0; - - const void *cur = NULL; - int i, count=0; - - if (!sl->num_used) { - if (count_out) - *count_out = 0; - return NULL; - } - for (i = 0; i < sl->num_used; ++i) { - const void *item = sl->list[i]; - if (cur && 0 == compare(&cur, &item)) { - ++count; - } else { - if (cur && count >= most_frequent_count) { - most_frequent = cur; - most_frequent_count = count; - } - cur = item; - count = 1; - } - } - if (cur && count >= most_frequent_count) { - most_frequent = cur; - most_frequent_count = count; - } - if (count_out) - *count_out = most_frequent_count; - return (void*)most_frequent; -} - -/** Given a sorted smartlist sl and the comparison function used to - * sort it, remove all duplicate members. If free_fn is provided, calls - * free_fn on each duplicate. Otherwise, just removes them. Preserves order. - */ -void -smartlist_uniq(smartlist_t *sl, - int (*compare)(const void **a, const void **b), - void (*free_fn)(void *a)) -{ - int i; - for (i=1; i < sl->num_used; ++i) { - if (compare((const void **)&(sl->list[i-1]), - (const void **)&(sl->list[i])) == 0) { - if (free_fn) - free_fn(sl->list[i]); - smartlist_del_keeporder(sl, i--); - } - } -} - -/** Assuming the members of sl are in order, return a pointer to the - * member that matches key. Ordering and matching are defined by a - * compare function that returns 0 on a match; less than 0 if key is - * less than member, and greater than 0 if key is greater then member. - */ -void * -smartlist_bsearch(smartlist_t *sl, const void *key, - int (*compare)(const void *key, const void **member)) -{ - int found, idx; - idx = smartlist_bsearch_idx(sl, key, compare, &found); - return found ? smartlist_get(sl, idx) : NULL; -} - -/** Assuming the members of sl are in order, return the index of the - * member that matches key. If no member matches, return the index of - * the first member greater than key, or smartlist_len(sl) if no member - * is greater than key. Set found_out to true on a match, to - * false otherwise. Ordering and matching are defined by a compare - * function that returns 0 on a match; less than 0 if key is less than member, - * and greater than 0 if key is greater then member. - */ -int -smartlist_bsearch_idx(const smartlist_t *sl, const void *key, - int (*compare)(const void *key, const void **member), - int *found_out) -{ - 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; - } - - /* 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) { - 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) { - /* sl[mid] == key; we found it */ - *found_out = 1; - return mid; - } 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); - - /* - * 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) -{ - return strcmp((const char*)*_a, (const char*)*_b); -} - -/** Sort a smartlist sl containing strings into lexically ascending - * order. */ -void -smartlist_sort_strings(smartlist_t *sl) -{ - smartlist_sort(sl, compare_string_ptrs_); -} - -/** Return the most frequent string in the sorted list sl */ -const char * -smartlist_get_most_frequent_string(smartlist_t *sl) -{ - return smartlist_get_most_frequent(sl, compare_string_ptrs_); -} - -/** Return the most frequent string in the sorted list sl. - * If count_out is provided, set count_out to the - * number of times that string appears. - */ -const char * -smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out) -{ - return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out); -} - -/** Remove duplicate strings from a sorted list, and free them with tor_free(). - */ -void -smartlist_uniq_strings(smartlist_t *sl) -{ - 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 (asl 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. - * Recall that the heap property is that, for every index I, h[I] < - * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]]. - * - * For us to remove items other than the topmost item, each item must store - * its own index within the heap. When calling the pqueue functions, tell - * them about the offset of the field that stores the index within the item. - * - * Example: - * - * typedef struct timer_t { - * struct timeval tv; - * int heap_index; - * } timer_t; - * - * static int compare(const void *p1, const void *p2) { - * const timer_t *t1 = p1, *t2 = p2; - * if (t1->tv.tv_sec < t2->tv.tv_sec) { - * return -1; - * } else if (t1->tv.tv_sec > t2->tv.tv_sec) { - * return 1; - * } else { - * return t1->tv.tv_usec - t2->tv_usec; - * } - * } - * - * void timer_heap_insert(smartlist_t *heap, timer_t *timer) { - * smartlist_pqueue_add(heap, compare, offsetof(timer_t, heap_index), - * timer); - * } - * - * void timer_heap_pop(smartlist_t *heap) { - * return smartlist_pqueue_pop(heap, compare, - * offsetof(timer_t, heap_index)); - * } - */ - -/** @{ */ -/** Functions to manipulate heap indices to find a node's parent and children. - * - * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] - * = 2*x + 1. But this is C, so we have to adjust a little. */ - -/* MAX_PARENT_IDX is the largest IDX in the smartlist which might have - * children whose indices fit inside an int. - * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2; - * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1; - * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size. - */ -#define MAX_PARENT_IDX ((INT_MAX - 2) / 2) -/* If this is true, then i is small enough to potentially have children - * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */ -#define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX) -#define LEFT_CHILD(i) ( 2*(i) + 1 ) -#define RIGHT_CHILD(i) ( 2*(i) + 2 ) -#define PARENT(i) ( ((i)-1) / 2 ) -/** }@ */ - -/** @{ */ -/** Helper macros for heaps: Given a local variable idx_field_offset - * set to the offset of an integer index within the heap element structure, - * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to - * where p's index is stored. Given additionally a local smartlist sl, - * UPDATE_IDX(i) sets the index of the element at i to the correct - * value (that is, to i). - */ -#define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset)) - -#define UPDATE_IDX(i) do { \ - void *updated = sl->list[i]; \ - *IDXP(updated) = i; \ - } while (0) - -#define IDX_OF_ITEM(p) (*IDXP(p)) -/** @} */ - -/** Helper. sl may have at most one violation of the heap property: - * the item at idx may be greater than one or both of its children. - * Restore the heap property. */ -static inline void -smartlist_heapify(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset, - int idx) -{ - while (1) { - if (! IDX_MAY_HAVE_CHILDREN(idx)) { - /* idx is so large that it cannot have any children, since doing so - * would mean the smartlist was over-capacity. Therefore it cannot - * violate the heap property by being greater than a child (since it - * doesn't have any). */ - return; - } - - 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; - UPDATE_IDX(idx); - UPDATE_IDX(best_idx); - - idx = best_idx; - } - } -} - -/** Insert item into the heap stored in sl, where order is - * determined by compare and the offset of the item in the heap is - * stored in an int-typed field at position idx_field_offset within - * item. - */ -void -smartlist_pqueue_add(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset, - void *item) -{ - int idx; - smartlist_add(sl,item); - UPDATE_IDX(sl->num_used-1); - - 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; - UPDATE_IDX(parent); - UPDATE_IDX(idx); - idx = parent; - } else { - return; - } - } -} - -/** Remove and return the top-priority item from the heap stored in sl, - * where order is determined by compare and the item's position is - * stored at position idx_field_offset within the item. sl must - * not be empty. */ -void * -smartlist_pqueue_pop(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset) -{ - void *top; - tor_assert(sl->num_used); - - top = sl->list[0]; - *IDXP(top)=-1; - if (--sl->num_used) { - sl->list[0] = sl->list[sl->num_used]; - sl->list[sl->num_used] = NULL; - UPDATE_IDX(0); - smartlist_heapify(sl, compare, idx_field_offset, 0); - } - sl->list[sl->num_used] = NULL; - return top; -} - -/** Remove the item item from the heap stored in sl, - * where order is determined by compare and the item's position is - * stored at position idx_field_offset within the item. sl must - * not be empty. */ -void -smartlist_pqueue_remove(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset, - void *item) -{ - int idx = IDX_OF_ITEM(item); - tor_assert(idx >= 0); - tor_assert(sl->list[idx] == item); - --sl->num_used; - *IDXP(item) = -1; - if (idx == sl->num_used) { - sl->list[sl->num_used] = NULL; - return; - } else { - sl->list[idx] = sl->list[sl->num_used]; - sl->list[sl->num_used] = NULL; - UPDATE_IDX(idx); - smartlist_heapify(sl, compare, idx_field_offset, idx); - } -} - -/** Assert that the heap property is correctly maintained by the heap stored - * in sl, where order is determined by compare. */ -void -smartlist_pqueue_assert_ok(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset) -{ - int i; - for (i = sl->num_used - 1; i >= 0; --i) { - if (i>0) - tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0); - tor_assert(IDX_OF_ITEM(sl->list[i]) == i); - } -} - -/** Helper: compare two DIGEST_LEN digests. */ -static int -compare_digests_(const void **_a, const void **_b) -{ - return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN); -} - -/** Sort the list of DIGEST_LEN-byte digests into ascending order. */ -void -smartlist_sort_digests(smartlist_t *sl) -{ - smartlist_sort(sl, compare_digests_); -} - -/** Remove duplicate digests from a sorted list, and free them with tor_free(). - */ -void -smartlist_uniq_digests(smartlist_t *sl) -{ - smartlist_uniq(sl, compare_digests_, tor_free_); -} - -/** Helper: compare two DIGEST256_LEN digests. */ -static int -compare_digests256_(const void **_a, const void **_b) -{ - return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); -} - -/** Sort the list of DIGEST256_LEN-byte digests into ascending order. */ -void -smartlist_sort_digests256(smartlist_t *sl) -{ - smartlist_sort(sl, compare_digests256_); -} - -/** Return the most frequent member of the sorted list of DIGEST256_LEN - * digests in sl */ -const uint8_t * -smartlist_get_most_frequent_digest256(smartlist_t *sl) -{ - return smartlist_get_most_frequent(sl, compare_digests256_); -} - -/** Remove duplicate 256-bit digests from a sorted list, and free them with - * tor_free(). - */ -void -smartlist_uniq_digests256(smartlist_t *sl) -{ - smartlist_uniq(sl, compare_digests256_, tor_free_); -} - -/** Helper: Declare an entry type and a map type to implement a mapping using - * ht.h. The map type will be called maptype. The key part of each - * entry is declared using the C declaration keydecl. All functions - * and types associated with the map get prefixed with prefix */ -#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \ - typedef struct prefix ## entry_t { \ - HT_ENTRY(prefix ## entry_t) node; \ - void *val; \ - keydecl; \ - } prefix ## entry_t; \ - struct maptype { \ - HT_HEAD(prefix ## impl, prefix ## entry_t) head; \ - } - -DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_); -DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_); -DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_); - -/** Helper: compare strmap_entry_t objects by key value. */ -static inline int -strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b) -{ - return !strcmp(a->key, b->key); -} - -/** Helper: return a hash value for a strmap_entry_t. */ -static inline unsigned int -strmap_entry_hash(const strmap_entry_t *a) -{ - return (unsigned) siphash24g(a->key, strlen(a->key)); -} - -/** Helper: compare digestmap_entry_t objects by key value. */ -static inline int -digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b) -{ - return tor_memeq(a->key, b->key, DIGEST_LEN); -} - -/** Helper: return a hash value for a digest_map_t. */ -static inline unsigned int -digestmap_entry_hash(const digestmap_entry_t *a) -{ - return (unsigned) siphash24g(a->key, DIGEST_LEN); -} - -/** Helper: compare digestmap_entry_t objects by key value. */ -static inline int -digest256map_entries_eq(const digest256map_entry_t *a, - const digest256map_entry_t *b) -{ - return tor_memeq(a->key, b->key, DIGEST256_LEN); -} - -/** Helper: return a hash value for a digest_map_t. */ -static inline unsigned int -digest256map_entry_hash(const digest256map_entry_t *a) -{ - return (unsigned) siphash24g(a->key, DIGEST256_LEN); -} - -HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, - strmap_entries_eq) -HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash, - strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) - -HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, - digestmap_entries_eq) -HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, - digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) - -HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node, - digest256map_entry_hash, - digest256map_entries_eq) -HT_GENERATE2(digest256map_impl, digest256map_entry_t, node, - digest256map_entry_hash, - digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_) - -#define strmap_entry_free(ent) \ - FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent)) -#define digestmap_entry_free(ent) \ - FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent)) -#define digest256map_entry_free(ent) \ - FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent)) - -static inline void -strmap_entry_free_(strmap_entry_t *ent) -{ - tor_free(ent->key); - tor_free(ent); -} -static inline void -digestmap_entry_free_(digestmap_entry_t *ent) -{ - tor_free(ent); -} -static inline void -digest256map_entry_free_(digest256map_entry_t *ent) -{ - tor_free(ent); -} - -static inline void -strmap_assign_tmp_key(strmap_entry_t *ent, const char *key) -{ - ent->key = (char*)key; -} -static inline void -digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key) -{ - memcpy(ent->key, key, DIGEST_LEN); -} -static inline void -digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key) -{ - memcpy(ent->key, key, DIGEST256_LEN); -} -static inline void -strmap_assign_key(strmap_entry_t *ent, const char *key) -{ - ent->key = tor_strdup(key); -} -static inline void -digestmap_assign_key(digestmap_entry_t *ent, const char *key) -{ - memcpy(ent->key, key, DIGEST_LEN); -} -static inline void -digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key) -{ - memcpy(ent->key, key, DIGEST256_LEN); -} - -/** - * Macro: implement all the functions for a map that are declared in - * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a - * prefix_entry_free_() function to free entries (and their keys), a - * prefix_assign_tmp_key() function to temporarily set a stack-allocated - * entry to hold a key, and a prefix_assign_key() function to set a - * heap-allocated entry to hold a key. - */ -#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \ - /** Create and return a new empty map. */ \ - MOCK_IMPL(maptype *, \ - prefix##_new,(void)) \ - { \ - maptype *result; \ - result = tor_malloc(sizeof(maptype)); \ - HT_INIT(prefix##_impl, &result->head); \ - return result; \ - } \ - \ - /** Return the item from map whose key matches key, or \ - * NULL if no such value exists. */ \ - void * \ - prefix##_get(const maptype *map, const keytype key) \ - { \ - prefix ##_entry_t *resolve; \ - prefix ##_entry_t search; \ - tor_assert(map); \ - tor_assert(key); \ - prefix ##_assign_tmp_key(&search, key); \ - resolve = HT_FIND(prefix ##_impl, &map->head, &search); \ - if (resolve) { \ - return resolve->val; \ - } else { \ - return NULL; \ - } \ - } \ - \ - /** Add an entry to map mapping key to val; \ - * return the previous value, or NULL if no such value existed. */ \ - void * \ - prefix##_set(maptype *map, const keytype key, void *val) \ - { \ - prefix##_entry_t search; \ - void *oldval; \ - tor_assert(map); \ - tor_assert(key); \ - tor_assert(val); \ - prefix##_assign_tmp_key(&search, key); \ - /* We a lot of our time in this function, so the code below is */ \ - /* meant to optimize the check/alloc/set cycle by avoiding the two */\ - /* trips to the hash table that we would do in the unoptimized */ \ - /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \ - /* HT_SET_HASH and HT_FIND_P.) */ \ - HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \ - &(map->head), \ - prefix##_entry_t, &search, ptr, \ - { \ - /* we found an entry. */ \ - oldval = (*ptr)->val; \ - (*ptr)->val = val; \ - return oldval; \ - }, \ - { \ - /* We didn't find the entry. */ \ - prefix##_entry_t *newent = \ - tor_malloc_zero(sizeof(prefix##_entry_t)); \ - prefix##_assign_key(newent, key); \ - newent->val = val; \ - HT_FOI_INSERT_(node, &(map->head), \ - &search, newent, ptr); \ - return NULL; \ - }); \ - } \ - \ - /** Remove the value currently associated with key from the map. \ - * Return the value if one was set, or NULL if there was no entry for \ - * key. \ - * \ - * Note: you must free any storage associated with the returned value. \ - */ \ - void * \ - prefix##_remove(maptype *map, const keytype key) \ - { \ - prefix##_entry_t *resolve; \ - prefix##_entry_t search; \ - void *oldval; \ - tor_assert(map); \ - tor_assert(key); \ - prefix##_assign_tmp_key(&search, key); \ - resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \ - if (resolve) { \ - oldval = resolve->val; \ - prefix##_entry_free(resolve); \ - return oldval; \ - } else { \ - return NULL; \ - } \ - } \ - \ - /** Return the number of elements in map. */ \ - int \ - prefix##_size(const maptype *map) \ - { \ - return HT_SIZE(&map->head); \ - } \ - \ - /** Return true iff map has no entries. */ \ - int \ - prefix##_isempty(const maptype *map) \ - { \ - return HT_EMPTY(&map->head); \ - } \ - \ - /** Assert that map is not corrupt. */ \ - void \ - prefix##_assert_ok(const maptype *map) \ - { \ - tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \ - } \ - \ - /** Remove all entries from map, and deallocate storage for \ - * those entries. If free_val is provided, invoked it every value in \ - * map. */ \ - MOCK_IMPL(void, \ - prefix##_free_, (maptype *map, void (*free_val)(void*))) \ - { \ - prefix##_entry_t **ent, **next, *this; \ - if (!map) \ - return; \ - for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \ - ent = next) { \ - this = *ent; \ - next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \ - if (free_val) \ - free_val(this->val); \ - prefix##_entry_free(this); \ - } \ - tor_assert(HT_EMPTY(&map->head)); \ - HT_CLEAR(prefix##_impl, &map->head); \ - tor_free(map); \ - } \ - \ - /** return an iterator pointer to the front of a map. \ - * \ - * Iterator example: \ - * \ - * \code \ - * // uppercase values in "map", removing empty values. \ - * \ - * strmap_iter_t *iter; \ - * const char *key; \ - * void *val; \ - * char *cp; \ - * \ - * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \ - * strmap_iter_get(iter, &key, &val); \ - * cp = (char*)val; \ - * if (!*cp) { \ - * iter = strmap_iter_next_rmv(map,iter); \ - * free(val); \ - * } else { \ - * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \ - */ \ - prefix##_iter_t * \ - prefix##_iter_init(maptype *map) \ - { \ - tor_assert(map); \ - return HT_START(prefix##_impl, &map->head); \ - } \ - \ - /** Advance iter a single step to the next entry, and return \ - * its new value. */ \ - prefix##_iter_t * \ - prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \ - { \ - tor_assert(map); \ - tor_assert(iter); \ - return HT_NEXT(prefix##_impl, &map->head, iter); \ - } \ - /** Advance iter a single step to the next entry, removing the \ - * current entry, and return its new value. */ \ - prefix##_iter_t * \ - prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \ - { \ - prefix##_entry_t *rmv; \ - tor_assert(map); \ - tor_assert(iter); \ - tor_assert(*iter); \ - rmv = *iter; \ - iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \ - prefix##_entry_free(rmv); \ - return iter; \ - } \ - /** Set *keyp and *valp to the current entry pointed \ - * to by iter. */ \ - void \ - prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \ - void **valp) \ - { \ - tor_assert(iter); \ - tor_assert(*iter); \ - tor_assert(keyp); \ - tor_assert(valp); \ - *keyp = (*iter)->key; \ - *valp = (*iter)->val; \ - } \ - /** Return true iff iter has advanced past the last entry of \ - * map. */ \ - int \ - prefix##_iter_done(prefix##_iter_t *iter) \ - { \ - return iter == NULL; \ - } - -IMPLEMENT_MAP_FNS(strmap_t, char *, strmap) -IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap) -IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map) - -/** Same as strmap_set, but first converts key to lowercase. */ -void * -strmap_set_lc(strmap_t *map, const char *key, void *val) -{ - /* We could be a little faster by using strcasecmp instead, and a separate - * type, but I don't think it matters. */ - void *v; - char *lc_key = tor_strdup(key); - tor_strlower(lc_key); - v = strmap_set(map,lc_key,val); - tor_free(lc_key); - return v; -} - -/** Same as strmap_get, but first converts key to lowercase. */ -void * -strmap_get_lc(const strmap_t *map, const char *key) -{ - void *v; - char *lc_key = tor_strdup(key); - tor_strlower(lc_key); - v = strmap_get(map,lc_key); - tor_free(lc_key); - return v; -} - -/** Same as strmap_remove, but first converts key to lowercase */ -void * -strmap_remove_lc(strmap_t *map, const char *key) -{ - void *v; - char *lc_key = tor_strdup(key); - tor_strlower(lc_key); - v = strmap_remove(map,lc_key); - tor_free(lc_key); - return v; -} - -/** Declare a function called funcname that acts as a find_nth_FOO - * function for an array of type elt_t*. - * - * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding - * the kth element of an n-element list can be done in O(n). Then again, this - * implementation is not in critical path, and it is obviously correct. */ -#define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ - static int \ - _cmp_ ## elt_t(const void *_a, const void *_b) \ - { \ - const elt_t *a = _a, *b = _b; \ - if (*a<*b) \ - return -1; \ - else if (*a>*b) \ - return 1; \ - else \ - return 0; \ - } \ - elt_t \ - funcname(elt_t *array, int n_elements, int nth) \ - { \ - tor_assert(nth >= 0); \ - tor_assert(nth < n_elements); \ - qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ - return array[nth]; \ - } - -IMPLEMENT_ORDER_FUNC(find_nth_int, int) -IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) -IMPLEMENT_ORDER_FUNC(find_nth_double, double) -IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) -IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t) -IMPLEMENT_ORDER_FUNC(find_nth_long, long) - -/** Return a newly allocated digestset_t, optimized to hold a total of - * max_elements digests with a reasonably low false positive weight. */ -digestset_t * -digestset_new(int max_elements) -{ - /* The probability of false positives is about P=(1 - exp(-kn/m))^k, where k - * is the number of hash functions per entry, m is the bits in the array, - * and n is the number of elements inserted. For us, k==4, n<=max_elements, - * and m==n_bits= approximately max_elements*32. This gives - * P<(1-exp(-4*n/(32*n)))^4 == (1-exp(1/-8))^4 == .00019 - * - * It would be more optimal in space vs false positives to get this false - * positive rate by going for k==13, and m==18.5n, but we also want to - * conserve CPU, and k==13 is pretty big. - */ - int n_bits = 1u << (tor_log2(max_elements)+5); - digestset_t *r = tor_malloc(sizeof(digestset_t)); - r->mask = n_bits - 1; - r->ba = bitarray_init_zero(n_bits); - return r; -} - -/** Free all storage held in set. */ -void -digestset_free_(digestset_t *set) -{ - if (!set) - return; - bitarray_free(set->ba); - tor_free(set); -} diff --git a/src/lib/container/container.h b/src/lib/container/container.h index c45bfc359b..ba89838468 100644 --- a/src/lib/container/container.h +++ b/src/lib/container/container.h @@ -6,745 +6,10 @@ #ifndef TOR_CONTAINER_H #define TOR_CONTAINER_H -#include -#include -#include - -#include "lib/cc/compat_compiler.h" -#include "lib/cc/torint.h" -#include "lib/testsupport/testsupport.h" -#include "lib/malloc/util_malloc.h" -#include "common/util_bug.h" -#include "siphash.h" - -/** A resizeable list of pointers, with associated helpful functionality. - * - * The members of this struct are exposed only so that macros and inlines can - * use them; all access to smartlist internals should go through the functions - * and macros defined here. - **/ -typedef struct smartlist_t { - /** @{ */ - /** list has enough capacity to store exactly capacity elements - * before it needs to be resized. Only the first num_used (\<= - * capacity) elements point to valid data. - */ - void **list; - int num_used; - int capacity; - /** @} */ -} smartlist_t; - -MOCK_DECL(smartlist_t *, smartlist_new, (void)); -MOCK_DECL(void, smartlist_free_, (smartlist_t *sl)); -#define smartlist_free(sl) FREE_AND_NULL(smartlist_t, smartlist_free_, (sl)) - -void smartlist_clear(smartlist_t *sl); -void smartlist_add(smartlist_t *sl, void *element); -void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2); -void smartlist_add_strdup(struct smartlist_t *sl, const char *string); -void smartlist_remove(smartlist_t *sl, const void *element); -void smartlist_remove_keeporder(smartlist_t *sl, const void *element); -void *smartlist_pop_last(smartlist_t *sl); -void smartlist_reverse(smartlist_t *sl); -void smartlist_string_remove(smartlist_t *sl, const char *element); -int smartlist_contains(const smartlist_t *sl, const void *element); -int smartlist_contains_string(const smartlist_t *sl, const char *element); -int smartlist_pos(const smartlist_t *sl, const void *element); -int smartlist_string_pos(const smartlist_t *, const char *elt); -int smartlist_contains_string_case(const smartlist_t *sl, const char *element); -int smartlist_contains_int_as_string(const smartlist_t *sl, int num); -int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2); -int smartlist_contains_digest(const smartlist_t *sl, const char *element); -int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2); -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. - */ -static inline int smartlist_len(const smartlist_t *sl); -static inline int smartlist_len(const smartlist_t *sl) { - tor_assert(sl); - return (sl)->num_used; -} -/** Return the idxth element of sl. - */ -static inline void *smartlist_get(const smartlist_t *sl, int idx); -static inline void *smartlist_get(const smartlist_t *sl, int idx) { - tor_assert(sl); - tor_assert(idx>=0); - tor_assert(sl->num_used > idx); - return sl->list[idx]; -} -static inline void smartlist_set(smartlist_t *sl, int idx, void *val) { - tor_assert(sl); - tor_assert(idx>=0); - tor_assert(sl->num_used > idx); - sl->list[idx] = val; -} -#else /* !(defined(DEBUG_SMARTLIST)) */ -#define smartlist_len(sl) ((sl)->num_used) -#define smartlist_get(sl, idx) ((sl)->list[idx]) -#define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val)) -#endif /* defined(DEBUG_SMARTLIST) */ - -/** Exchange the elements at indices idx1 and idx2 of the - * smartlist sl. */ -static inline void smartlist_swap(smartlist_t *sl, int idx1, int idx2) -{ - if (idx1 != idx2) { - void *elt = smartlist_get(sl, idx1); - smartlist_set(sl, idx1, smartlist_get(sl, idx2)); - smartlist_set(sl, idx2, elt); - } -} - -void smartlist_del(smartlist_t *sl, int idx); -void smartlist_del_keeporder(smartlist_t *sl, int idx); -void smartlist_insert(smartlist_t *sl, int idx, void *val); -void smartlist_sort(smartlist_t *sl, - int (*compare)(const void **a, const void **b)); -void *smartlist_get_most_frequent_(const smartlist_t *sl, - int (*compare)(const void **a, const void **b), - int *count_out); -#define smartlist_get_most_frequent(sl, compare) \ - smartlist_get_most_frequent_((sl), (compare), NULL) -void smartlist_uniq(smartlist_t *sl, - int (*compare)(const void **a, const void **b), - void (*free_fn)(void *elt)); - -void smartlist_sort_strings(smartlist_t *sl); -void smartlist_sort_digests(smartlist_t *sl); -void smartlist_sort_digests256(smartlist_t *sl); -void smartlist_sort_pointers(smartlist_t *sl); - -const char *smartlist_get_most_frequent_string(smartlist_t *sl); -const char *smartlist_get_most_frequent_string_(smartlist_t *sl, - int *count_out); -const uint8_t *smartlist_get_most_frequent_digest256(smartlist_t *sl); - -void smartlist_uniq_strings(smartlist_t *sl); -void smartlist_uniq_digests(smartlist_t *sl); -void smartlist_uniq_digests256(smartlist_t *sl); -void *smartlist_bsearch(smartlist_t *sl, const void *key, - int (*compare)(const void *key, const void **member)); -int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, - int (*compare)(const void *key, const void **member), - int *found_out); - -void smartlist_pqueue_add(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset, - void *item); -void *smartlist_pqueue_pop(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset); -void smartlist_pqueue_remove(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset, - void *item); -void smartlist_pqueue_assert_ok(smartlist_t *sl, - int (*compare)(const void *a, const void *b), - int idx_field_offset); - -#define SPLIT_SKIP_SPACE 0x01 -#define SPLIT_IGNORE_BLANK 0x02 -#define SPLIT_STRIP_SPACE 0x04 -int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, - int flags, int max); -char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, - size_t *len_out) ATTR_MALLOC; -char *smartlist_join_strings2(smartlist_t *sl, const char *join, - size_t join_len, int terminate, size_t *len_out) - ATTR_MALLOC; - -/** Iterate over the items in a smartlist sl, in order. For each item, - * assign it to a new local variable of type type named var, and - * execute the statements inside the loop body. Inside the loop, the loop - * index can be accessed as var_sl_idx and the length of the list can - * be accessed as var_sl_len. - * - * NOTE: Do not change the length of the list while the loop is in progress, - * unless you adjust the _sl_len variable correspondingly. See second example - * below. - * - * Example use: - * 
- *   smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
- *   SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
- *     printf("%d: %s\n", cp_sl_idx, cp);
- *     tor_free(cp);
- *   } SMARTLIST_FOREACH_END(cp);
- *   smartlist_free(list);
- *
- * - * Example use (advanced): - * 
- *   SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
- *     if (!strcmp(cp, "junk")) {
- *       tor_free(cp);
- *       SMARTLIST_DEL_CURRENT(list, cp);
- *     }
- *   } SMARTLIST_FOREACH_END(cp);
- *
- */ -/* Note: these macros use token pasting, and reach into smartlist internals. - * This can make them a little daunting. Here's the approximate unpacking of - * the above examples, for entertainment value: - * - * 
- * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
- * {
- *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
- *   char *cp;
- *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
- *     cp = smartlist_get(list, cp_sl_idx);
- *     printf("%d: %s\n", cp_sl_idx, cp);
- *     tor_free(cp);
- *   }
- * }
- * smartlist_free(list);
- *
- * - * 
- * {
- *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
- *   char *cp;
- *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
- *     cp = smartlist_get(list, cp_sl_idx);
- *     if (!strcmp(cp, "junk")) {
- *       tor_free(cp);
- *       smartlist_del(list, cp_sl_idx);
- *       --cp_sl_idx;
- *       --cp_sl_len;
- *     }
- *   }
- * }
- *
- */ -#define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ - STMT_BEGIN \ - int var ## _sl_idx, var ## _sl_len=(sl)->num_used; \ - type var; \ - for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len; \ - ++var ## _sl_idx) { \ - var = (sl)->list[var ## _sl_idx]; - -#define SMARTLIST_FOREACH_END(var) \ - var = NULL; \ - (void) var ## _sl_idx; \ - } STMT_END - -/** - * An alias for SMARTLIST_FOREACH_BEGIN and SMARTLIST_FOREACH_END, using - * cmd as the loop body. This wrapper is here for convenience with - * very short loops. - * - * By convention, we do not use this for loops which nest, or for loops over - * 10 lines or so. Use SMARTLIST_FOREACH_{BEGIN,END} for those. - */ -#define SMARTLIST_FOREACH(sl, type, var, cmd) \ - SMARTLIST_FOREACH_BEGIN(sl,type,var) { \ - cmd; \ - } SMARTLIST_FOREACH_END(var) - -/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed - * with the variable var, remove the current element in a way that - * won't confuse the loop. */ -#define SMARTLIST_DEL_CURRENT(sl, var) \ - STMT_BEGIN \ - smartlist_del(sl, var ## _sl_idx); \ - --var ## _sl_idx; \ - --var ## _sl_len; \ - STMT_END - -/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed - * with the variable var, remove the current element in a way that - * won't confuse the loop. */ -#define SMARTLIST_DEL_CURRENT_KEEPORDER(sl, var) \ - STMT_BEGIN \ - smartlist_del_keeporder(sl, var ## _sl_idx); \ - --var ## _sl_idx; \ - --var ## _sl_len; \ - STMT_END - -/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed - * with the variable var, replace the current element with val. - * Does not deallocate the current value of var. - */ -#define SMARTLIST_REPLACE_CURRENT(sl, var, val) \ - STMT_BEGIN \ - smartlist_set(sl, var ## _sl_idx, val); \ - STMT_END - -/* Helper: Given two lists of items, possibly of different types, such that - * both lists are sorted on some common field (as determined by a comparison - * expression cmpexpr), and such that one list (sl1) has no - * duplicates on the common field, loop through the lists in lockstep, and - * execute unmatched_var2 on items in var2 that do not appear in - * var1. - * - * WARNING: It isn't safe to add remove elements from either list while the - * loop is in progress. - * - * Example use: - * SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs, - * routerinfo_list, routerinfo_t *, ri, - * tor_memcmp(rs->identity_digest, ri->identity_digest, 20), - * log_info(LD_GENERAL,"No match for %s", ri->nickname)) { - * log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs); - * } SMARTLIST_FOREACH_JOIN_END(rs, ri); - **/ -/* The example above unpacks (approximately) to: - * int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list); - * int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list); - * int rs_ri_cmp; - * routerstatus_t *rs; - * routerinfo_t *ri; - * for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) { - * ri = smartlist_get(routerinfo_list, ri_sl_idx); - * while (rs_sl_idx < rs_sl_len) { - * rs = smartlist_get(routerstatus_list, rs_sl_idx); - * rs_ri_cmp = tor_memcmp(rs->identity_digest, ri->identity_digest, 20); - * if (rs_ri_cmp > 0) { - * break; - * } else if (rs_ri_cmp == 0) { - * goto matched_ri; - * } else { - * ++rs_sl_idx; - * } - * } - * log_info(LD_GENERAL,"No match for %s", ri->nickname); - * continue; - * matched_ri: { - * log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs); - * } - * } - */ -#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \ - cmpexpr, unmatched_var2) \ - STMT_BEGIN \ - int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \ - int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \ - int var1 ## _ ## var2 ## _cmp; \ - type1 var1; \ - type2 var2; \ - for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \ - var2 = (sl2)->list[var2##_sl_idx]; \ - while (var1##_sl_idx < var1##_sl_len) { \ - var1 = (sl1)->list[var1##_sl_idx]; \ - var1##_##var2##_cmp = (cmpexpr); \ - if (var1##_##var2##_cmp > 0) { \ - break; \ - } else if (var1##_##var2##_cmp == 0) { \ - goto matched_##var2; \ - } else { \ - ++var1##_sl_idx; \ - } \ - } \ - /* Ran out of v1, or no match for var2. */ \ - unmatched_var2; \ - continue; \ - matched_##var2: ; \ - -#define SMARTLIST_FOREACH_JOIN_END(var1, var2) \ - } \ - STMT_END - -#define DECLARE_MAP_FNS(maptype, keytype, prefix) \ - typedef struct maptype maptype; \ - typedef struct prefix##entry_t *prefix##iter_t; \ - MOCK_DECL(maptype*, prefix##new, (void)); \ - void* prefix##set(maptype *map, keytype key, void *val); \ - void* prefix##get(const maptype *map, keytype key); \ - void* prefix##remove(maptype *map, keytype key); \ - MOCK_DECL(void, prefix##free_, (maptype *map, void (*free_val)(void*))); \ - int prefix##isempty(const maptype *map); \ - int prefix##size(const maptype *map); \ - prefix##iter_t *prefix##iter_init(maptype *map); \ - prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \ - prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \ - void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \ - int prefix##iter_done(prefix##iter_t *iter); \ - void prefix##assert_ok(const maptype *map) - -/* Map from const char * to void *. Implemented with a hash table. */ -DECLARE_MAP_FNS(strmap_t, const char *, strmap_); -/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */ -DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_); -/* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash - * table. */ -DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_); - -#define MAP_FREE_AND_NULL(maptype, map, fn) \ - do { \ - maptype ## _free_((map), (fn)); \ - (map) = NULL; \ - } while (0) - -#define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn)) -#define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn)) -#define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn)) - -#undef DECLARE_MAP_FNS - -/** Iterates over the key-value pairs in a map map in order. - * prefix is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_). - * The map's keys and values are of type keytype and valtype respectively; - * each iteration assigns them to keyvar and valvar. - * - * Example use: - * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { - * // use k and r - * } MAP_FOREACH_END. - */ -/* Unpacks to, approximately: - * { - * digestmap_iter_t *k_iter; - * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); - * k_iter = digestmap_iter_next(m, k_iter)) { - * const char *k; - * void *r_voidp; - * routerinfo_t *r; - * digestmap_iter_get(k_iter, &k, &r_voidp); - * r = r_voidp; - * // use k and r - * } - * } - */ -#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \ - STMT_BEGIN \ - prefix##iter_t *keyvar##_iter; \ - for (keyvar##_iter = prefix##iter_init(map); \ - !prefix##iter_done(keyvar##_iter); \ - keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \ - keytype keyvar; \ - void *valvar##_voidp; \ - valtype valvar; \ - prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ - valvar = valvar##_voidp; - -/** As MAP_FOREACH, except allows members to be removed from the map - * during the iteration via MAP_DEL_CURRENT. Example use: - * - * Example use: - * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { - * if (is_very_old(r)) - * MAP_DEL_CURRENT(k); - * } MAP_FOREACH_END. - **/ -/* Unpacks to, approximately: - * { - * digestmap_iter_t *k_iter; - * int k_del=0; - * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); - * k_iter = k_del ? digestmap_iter_next(m, k_iter) - * : digestmap_iter_next_rmv(m, k_iter)) { - * const char *k; - * void *r_voidp; - * routerinfo_t *r; - * k_del=0; - * digestmap_iter_get(k_iter, &k, &r_voidp); - * r = r_voidp; - * if (is_very_old(r)) { - * k_del = 1; - * } - * } - * } - */ -#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \ - STMT_BEGIN \ - prefix##iter_t *keyvar##_iter; \ - int keyvar##_del=0; \ - for (keyvar##_iter = prefix##iter_init(map); \ - !prefix##iter_done(keyvar##_iter); \ - keyvar##_iter = keyvar##_del ? \ - prefix##iter_next_rmv(map, keyvar##_iter) : \ - prefix##iter_next(map, keyvar##_iter)) { \ - keytype keyvar; \ - void *valvar##_voidp; \ - valtype valvar; \ - keyvar##_del=0; \ - prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ - valvar = valvar##_voidp; - -/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon - * member of the map. */ -#define MAP_DEL_CURRENT(keyvar) \ - STMT_BEGIN \ - keyvar##_del = 1; \ - STMT_END - -/** Used to end a MAP_FOREACH() block. */ -#define MAP_FOREACH_END } STMT_END ; - -/** As MAP_FOREACH, but does not require declaration of prefix or keytype. - * Example use: - * DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) { - * // use k and r - * } DIGESTMAP_FOREACH_END. - */ -#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \ - MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar) - -/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or - * keytype. - * Example use: - * DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) { - * if (is_very_old(r)) - * MAP_DEL_CURRENT(k); - * } DIGESTMAP_FOREACH_END. - */ -#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ - MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar) -/** Used to end a DIGESTMAP_FOREACH() block. */ -#define DIGESTMAP_FOREACH_END MAP_FOREACH_END - -#define DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \ - MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar) -#define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ - MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \ - keyvar, valtype, valvar) -#define DIGEST256MAP_FOREACH_END MAP_FOREACH_END - -#define STRMAP_FOREACH(map, keyvar, valtype, valvar) \ - MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar) -#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ - MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar) -#define STRMAP_FOREACH_END MAP_FOREACH_END - -void* strmap_set_lc(strmap_t *map, const char *key, void *val); -void* strmap_get_lc(const strmap_t *map, const char *key); -void* strmap_remove_lc(strmap_t *map, const char *key); - -#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \ - typedef struct maptype maptype; \ - typedef struct prefix##iter_t *prefix##iter_t; \ - ATTR_UNUSED static inline maptype* \ - prefix##new(void) \ - { \ - return (maptype*)digestmap_new(); \ - } \ - ATTR_UNUSED static inline digestmap_t* \ - prefix##to_digestmap(maptype *map) \ - { \ - return (digestmap_t*)map; \ - } \ - ATTR_UNUSED static inline valtype* \ - prefix##get(maptype *map, const char *key) \ - { \ - return (valtype*)digestmap_get((digestmap_t*)map, key); \ - } \ - ATTR_UNUSED static inline valtype* \ - prefix##set(maptype *map, const char *key, valtype *val) \ - { \ - return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ - } \ - ATTR_UNUSED static inline valtype* \ - prefix##remove(maptype *map, const char *key) \ - { \ - return (valtype*)digestmap_remove((digestmap_t*)map, key); \ - } \ - ATTR_UNUSED static inline void \ - prefix##f##ree_(maptype *map, void (*free_val)(void*)) \ - { \ - digestmap_free_((digestmap_t*)map, free_val); \ - } \ - ATTR_UNUSED static inline int \ - prefix##isempty(maptype *map) \ - { \ - return digestmap_isempty((digestmap_t*)map); \ - } \ - ATTR_UNUSED static inline int \ - prefix##size(maptype *map) \ - { \ - return digestmap_size((digestmap_t*)map); \ - } \ - ATTR_UNUSED static inline \ - prefix##iter_t *prefix##iter_init(maptype *map) \ - { \ - return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ - } \ - ATTR_UNUSED static inline \ - prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter) \ - { \ - return (prefix##iter_t*) digestmap_iter_next( \ - (digestmap_t*)map, (digestmap_iter_t*)iter); \ - } \ - ATTR_UNUSED static inline prefix##iter_t* \ - prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter) \ - { \ - return (prefix##iter_t*) digestmap_iter_next_rmv( \ - (digestmap_t*)map, (digestmap_iter_t*)iter); \ - } \ - ATTR_UNUSED static inline void \ - prefix##iter_get(prefix##iter_t *iter, \ - const char **keyp, \ - valtype **valp) \ - { \ - void *v; \ - digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \ - *valp = v; \ - } \ - ATTR_UNUSED static inline int \ - prefix##iter_done(prefix##iter_t *iter) \ - { \ - return digestmap_iter_done((digestmap_iter_t*)iter); \ - } - -#if SIZEOF_INT == 4 -#define BITARRAY_SHIFT 5 -#elif SIZEOF_INT == 8 -#define BITARRAY_SHIFT 6 -#else -#error "int is neither 4 nor 8 bytes. I can't deal with that." -#endif /* SIZEOF_INT == 4 || ... */ -#define BITARRAY_MASK ((1u<n_bits bits. */ -static inline bitarray_t * -bitarray_init_zero(unsigned int n_bits) -{ - /* round up to the next int. */ - size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; - return tor_calloc(sz, sizeof(unsigned int)); -} -/** Expand ba from holding n_bits_old to n_bits_new, - * clearing all new bits. Returns a possibly changed pointer to the - * bitarray. */ -static inline bitarray_t * -bitarray_expand(bitarray_t *ba, - unsigned int n_bits_old, unsigned int n_bits_new) -{ - size_t sz_old = (n_bits_old+BITARRAY_MASK) >> BITARRAY_SHIFT; - size_t sz_new = (n_bits_new+BITARRAY_MASK) >> BITARRAY_SHIFT; - char *ptr; - if (sz_new <= sz_old) - return ba; - ptr = tor_reallocarray(ba, sz_new, sizeof(unsigned int)); - /* This memset does nothing to the older excess bytes. But they were - * already set to 0 by bitarry_init_zero. */ - memset(ptr+sz_old*sizeof(unsigned int), 0, - (sz_new-sz_old)*sizeof(unsigned int)); - return (bitarray_t*) ptr; -} -/** Free the bit array ba. */ -static inline void -bitarray_free_(bitarray_t *ba) -{ - tor_free(ba); -} -#define bitarray_free(ba) FREE_AND_NULL(bitarray_t, bitarray_free_, (ba)) - -/** Set the bitth bit in b to 1. */ -static inline void -bitarray_set(bitarray_t *b, int bit) -{ - b[bit >> BITARRAY_SHIFT] |= (1u << (bit & BITARRAY_MASK)); -} -/** Set the bitth bit in b to 0. */ -static inline void -bitarray_clear(bitarray_t *b, int bit) -{ - b[bit >> BITARRAY_SHIFT] &= ~ (1u << (bit & BITARRAY_MASK)); -} -/** Return true iff bitth bit in b is nonzero. NOTE: does - * not necessarily return 1 on true. */ -static inline unsigned int -bitarray_is_set(bitarray_t *b, int bit) -{ - return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK)); -} - -/** A set of digests, implemented as a Bloom filter. */ -typedef struct { - int mask; /**< One less than the number of bits in ba; always one less - * than a power of two. */ - bitarray_t *ba; /**< A bit array to implement the Bloom filter. */ -} digestset_t; - -#define BIT(n) ((n) & set->mask) -/** Add the digest digest to set. */ -static inline void -digestset_add(digestset_t *set, const char *digest) -{ - const uint64_t x = siphash24g(digest, 20); - const uint32_t d1 = (uint32_t) x; - const uint32_t d2 = (uint32_t)( (x>>16) + x); - const uint32_t d3 = (uint32_t)( (x>>32) + x); - const uint32_t d4 = (uint32_t)( (x>>48) + x); - bitarray_set(set->ba, BIT(d1)); - bitarray_set(set->ba, BIT(d2)); - bitarray_set(set->ba, BIT(d3)); - bitarray_set(set->ba, BIT(d4)); -} - -/** If digest is in set, return nonzero. Otherwise, - * probably return zero. */ -static inline int -digestset_contains(const digestset_t *set, const char *digest) -{ - const uint64_t x = siphash24g(digest, 20); - const uint32_t d1 = (uint32_t) x; - const uint32_t d2 = (uint32_t)( (x>>16) + x); - const uint32_t d3 = (uint32_t)( (x>>32) + x); - const uint32_t d4 = (uint32_t)( (x>>48) + x); - return bitarray_is_set(set->ba, BIT(d1)) && - bitarray_is_set(set->ba, BIT(d2)) && - bitarray_is_set(set->ba, BIT(d3)) && - bitarray_is_set(set->ba, BIT(d4)); -} -#undef BIT - -digestset_t *digestset_new(int max_elements); -void digestset_free_(digestset_t* set); -#define digestset_free(set) FREE_AND_NULL(digestset_t, digestset_free_, (set)) - -/* These functions, given an array of n_elements, return the - * nth lowest element. nth=0 gives the lowest element; - * n_elements-1 gives the highest; and (n_elements-1) / 2 gives - * the median. As a side effect, the elements of array are sorted. */ -int find_nth_int(int *array, int n_elements, int nth); -time_t find_nth_time(time_t *array, int n_elements, int nth); -double find_nth_double(double *array, int n_elements, int nth); -int32_t find_nth_int32(int32_t *array, int n_elements, int nth); -uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth); -long find_nth_long(long *array, int n_elements, int nth); -static inline int -median_int(int *array, int n_elements) -{ - return find_nth_int(array, n_elements, (n_elements-1)/2); -} -static inline time_t -median_time(time_t *array, int n_elements) -{ - return find_nth_time(array, n_elements, (n_elements-1)/2); -} -static inline double -median_double(double *array, int n_elements) -{ - return find_nth_double(array, n_elements, (n_elements-1)/2); -} -static inline uint32_t -median_uint32(uint32_t *array, int n_elements) -{ - return find_nth_uint32(array, n_elements, (n_elements-1)/2); -} -static inline int32_t -median_int32(int32_t *array, int n_elements) -{ - return find_nth_int32(array, n_elements, (n_elements-1)/2); -} - -static inline uint32_t -third_quartile_uint32(uint32_t *array, int n_elements) -{ - return find_nth_uint32(array, n_elements, (n_elements*3)/4); -} +#include "lib/container/smartlist.h" +#include "lib/container/map.h" +#include "lib/container/bitarray.h" +#include "lib/container/bloomfilt.h" +#include "lib/container/order.h" #endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/include.am b/src/lib/container/include.am index d7648c80c0..e2994674ad 100644 --- a/src/lib/container/include.am +++ b/src/lib/container/include.am @@ -6,7 +6,10 @@ noinst_LIBRARIES += src/lib/libtor-container-testing.a endif src_lib_libtor_container_a_SOURCES = \ - src/lib/container/container.c + src/lib/container/bloomfilt.c \ + src/lib/container/map.c \ + src/lib/container/order.c \ + src/lib/container/smartlist.c src_lib_libtor_container_testing_a_SOURCES = \ $(src_lib_libtor_container_a_SOURCES) @@ -14,4 +17,9 @@ src_lib_libtor_container_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS) src_lib_libtor_container_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS) noinst_HEADERS += \ - src/lib/container/container.h + src/lib/container/bitarray.h \ + src/lib/container/bloomfilt.h \ + src/lib/container/container.h \ + src/lib/container/map.h \ + src/lib/container/order.h \ + src/lib/container/smartlist.h diff --git a/src/lib/container/map.c b/src/lib/container/map.c new file mode 100644 index 0000000000..227fb8f5e3 --- /dev/null +++ b/src/lib/container/map.c @@ -0,0 +1,413 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file container.c + * \brief Implements a smartlist (a resizable array) along + * with helper functions to use smartlists. Also includes + * hash table implementations of a string-to-void* map, and of + * a digest-to-void* map. + **/ + +#include "lib/container/map.h" +#include "lib/ctime/di_ops.h" +#include "lib/crypt_ops/crypto_digest.h" + +#include "common/util_bug.h" +#include "common/util.h" // For strlower + +#include +#include + +#include "ht.h" + +/** Helper: Declare an entry type and a map type to implement a mapping using + * ht.h. The map type will be called maptype. The key part of each + * entry is declared using the C declaration keydecl. All functions + * and types associated with the map get prefixed with prefix */ +#define DEFINE_MAP_STRUCTS(maptype, keydecl, prefix) \ + typedef struct prefix ## entry_t { \ + HT_ENTRY(prefix ## entry_t) node; \ + void *val; \ + keydecl; \ + } prefix ## entry_t; \ + struct maptype { \ + HT_HEAD(prefix ## impl, prefix ## entry_t) head; \ + } + +DEFINE_MAP_STRUCTS(strmap_t, char *key, strmap_); +DEFINE_MAP_STRUCTS(digestmap_t, char key[DIGEST_LEN], digestmap_); +DEFINE_MAP_STRUCTS(digest256map_t, uint8_t key[DIGEST256_LEN], digest256map_); + +/** Helper: compare strmap_entry_t objects by key value. */ +static inline int +strmap_entries_eq(const strmap_entry_t *a, const strmap_entry_t *b) +{ + return !strcmp(a->key, b->key); +} + +/** Helper: return a hash value for a strmap_entry_t. */ +static inline unsigned int +strmap_entry_hash(const strmap_entry_t *a) +{ + return (unsigned) siphash24g(a->key, strlen(a->key)); +} + +/** Helper: compare digestmap_entry_t objects by key value. */ +static inline int +digestmap_entries_eq(const digestmap_entry_t *a, const digestmap_entry_t *b) +{ + return tor_memeq(a->key, b->key, DIGEST_LEN); +} + +/** Helper: return a hash value for a digest_map_t. */ +static inline unsigned int +digestmap_entry_hash(const digestmap_entry_t *a) +{ + return (unsigned) siphash24g(a->key, DIGEST_LEN); +} + +/** Helper: compare digestmap_entry_t objects by key value. */ +static inline int +digest256map_entries_eq(const digest256map_entry_t *a, + const digest256map_entry_t *b) +{ + return tor_memeq(a->key, b->key, DIGEST256_LEN); +} + +/** Helper: return a hash value for a digest_map_t. */ +static inline unsigned int +digest256map_entry_hash(const digest256map_entry_t *a) +{ + return (unsigned) siphash24g(a->key, DIGEST256_LEN); +} + +HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq) +HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash, + strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) + +HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq) +HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash, + digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_) + +HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node, + digest256map_entry_hash, + digest256map_entries_eq) +HT_GENERATE2(digest256map_impl, digest256map_entry_t, node, + digest256map_entry_hash, + digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_) + +#define strmap_entry_free(ent) \ + FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent)) +#define digestmap_entry_free(ent) \ + FREE_AND_NULL(digestmap_entry_t, digestmap_entry_free_, (ent)) +#define digest256map_entry_free(ent) \ + FREE_AND_NULL(digest256map_entry_t, digest256map_entry_free_, (ent)) + +static inline void +strmap_entry_free_(strmap_entry_t *ent) +{ + tor_free(ent->key); + tor_free(ent); +} +static inline void +digestmap_entry_free_(digestmap_entry_t *ent) +{ + tor_free(ent); +} +static inline void +digest256map_entry_free_(digest256map_entry_t *ent) +{ + tor_free(ent); +} + +static inline void +strmap_assign_tmp_key(strmap_entry_t *ent, const char *key) +{ + ent->key = (char*)key; +} +static inline void +digestmap_assign_tmp_key(digestmap_entry_t *ent, const char *key) +{ + memcpy(ent->key, key, DIGEST_LEN); +} +static inline void +digest256map_assign_tmp_key(digest256map_entry_t *ent, const uint8_t *key) +{ + memcpy(ent->key, key, DIGEST256_LEN); +} +static inline void +strmap_assign_key(strmap_entry_t *ent, const char *key) +{ + ent->key = tor_strdup(key); +} +static inline void +digestmap_assign_key(digestmap_entry_t *ent, const char *key) +{ + memcpy(ent->key, key, DIGEST_LEN); +} +static inline void +digest256map_assign_key(digest256map_entry_t *ent, const uint8_t *key) +{ + memcpy(ent->key, key, DIGEST256_LEN); +} + +/** + * Macro: implement all the functions for a map that are declared in + * container.h by the DECLARE_MAP_FNS() macro. You must additionally define a + * prefix_entry_free_() function to free entries (and their keys), a + * prefix_assign_tmp_key() function to temporarily set a stack-allocated + * entry to hold a key, and a prefix_assign_key() function to set a + * heap-allocated entry to hold a key. + */ +#define IMPLEMENT_MAP_FNS(maptype, keytype, prefix) \ + /** Create and return a new empty map. */ \ + MOCK_IMPL(maptype *, \ + prefix##_new,(void)) \ + { \ + maptype *result; \ + result = tor_malloc(sizeof(maptype)); \ + HT_INIT(prefix##_impl, &result->head); \ + return result; \ + } \ + \ + /** Return the item from map whose key matches key, or \ + * NULL if no such value exists. */ \ + void * \ + prefix##_get(const maptype *map, const keytype key) \ + { \ + prefix ##_entry_t *resolve; \ + prefix ##_entry_t search; \ + tor_assert(map); \ + tor_assert(key); \ + prefix ##_assign_tmp_key(&search, key); \ + resolve = HT_FIND(prefix ##_impl, &map->head, &search); \ + if (resolve) { \ + return resolve->val; \ + } else { \ + return NULL; \ + } \ + } \ + \ + /** Add an entry to map mapping key to val; \ + * return the previous value, or NULL if no such value existed. */ \ + void * \ + prefix##_set(maptype *map, const keytype key, void *val) \ + { \ + prefix##_entry_t search; \ + void *oldval; \ + tor_assert(map); \ + tor_assert(key); \ + tor_assert(val); \ + prefix##_assign_tmp_key(&search, key); \ + /* We a lot of our time in this function, so the code below is */ \ + /* meant to optimize the check/alloc/set cycle by avoiding the two */\ + /* trips to the hash table that we would do in the unoptimized */ \ + /* version of this code. (Each of HT_INSERT and HT_FIND calls */ \ + /* HT_SET_HASH and HT_FIND_P.) */ \ + HT_FIND_OR_INSERT_(prefix##_impl, node, prefix##_entry_hash, \ + &(map->head), \ + prefix##_entry_t, &search, ptr, \ + { \ + /* we found an entry. */ \ + oldval = (*ptr)->val; \ + (*ptr)->val = val; \ + return oldval; \ + }, \ + { \ + /* We didn't find the entry. */ \ + prefix##_entry_t *newent = \ + tor_malloc_zero(sizeof(prefix##_entry_t)); \ + prefix##_assign_key(newent, key); \ + newent->val = val; \ + HT_FOI_INSERT_(node, &(map->head), \ + &search, newent, ptr); \ + return NULL; \ + }); \ + } \ + \ + /** Remove the value currently associated with key from the map. \ + * Return the value if one was set, or NULL if there was no entry for \ + * key. \ + * \ + * Note: you must free any storage associated with the returned value. \ + */ \ + void * \ + prefix##_remove(maptype *map, const keytype key) \ + { \ + prefix##_entry_t *resolve; \ + prefix##_entry_t search; \ + void *oldval; \ + tor_assert(map); \ + tor_assert(key); \ + prefix##_assign_tmp_key(&search, key); \ + resolve = HT_REMOVE(prefix##_impl, &map->head, &search); \ + if (resolve) { \ + oldval = resolve->val; \ + prefix##_entry_free(resolve); \ + return oldval; \ + } else { \ + return NULL; \ + } \ + } \ + \ + /** Return the number of elements in map. */ \ + int \ + prefix##_size(const maptype *map) \ + { \ + return HT_SIZE(&map->head); \ + } \ + \ + /** Return true iff map has no entries. */ \ + int \ + prefix##_isempty(const maptype *map) \ + { \ + return HT_EMPTY(&map->head); \ + } \ + \ + /** Assert that map is not corrupt. */ \ + void \ + prefix##_assert_ok(const maptype *map) \ + { \ + tor_assert(!prefix##_impl_HT_REP_IS_BAD_(&map->head)); \ + } \ + \ + /** Remove all entries from map, and deallocate storage for \ + * those entries. If free_val is provided, invoked it every value in \ + * map. */ \ + MOCK_IMPL(void, \ + prefix##_free_, (maptype *map, void (*free_val)(void*))) \ + { \ + prefix##_entry_t **ent, **next, *this; \ + if (!map) \ + return; \ + for (ent = HT_START(prefix##_impl, &map->head); ent != NULL; \ + ent = next) { \ + this = *ent; \ + next = HT_NEXT_RMV(prefix##_impl, &map->head, ent); \ + if (free_val) \ + free_val(this->val); \ + prefix##_entry_free(this); \ + } \ + tor_assert(HT_EMPTY(&map->head)); \ + HT_CLEAR(prefix##_impl, &map->head); \ + tor_free(map); \ + } \ + \ + /** return an iterator pointer to the front of a map. \ + * \ + * Iterator example: \ + * \ + * \code \ + * // uppercase values in "map", removing empty values. \ + * \ + * strmap_iter_t *iter; \ + * const char *key; \ + * void *val; \ + * char *cp; \ + * \ + * for (iter = strmap_iter_init(map); !strmap_iter_done(iter); ) { \ + * strmap_iter_get(iter, &key, &val); \ + * cp = (char*)val; \ + * if (!*cp) { \ + * iter = strmap_iter_next_rmv(map,iter); \ + * free(val); \ + * } else { \ + * for (;*cp;cp++) *cp = TOR_TOUPPER(*cp); \ + */ \ + prefix##_iter_t * \ + prefix##_iter_init(maptype *map) \ + { \ + tor_assert(map); \ + return HT_START(prefix##_impl, &map->head); \ + } \ + \ + /** Advance iter a single step to the next entry, and return \ + * its new value. */ \ + prefix##_iter_t * \ + prefix##_iter_next(maptype *map, prefix##_iter_t *iter) \ + { \ + tor_assert(map); \ + tor_assert(iter); \ + return HT_NEXT(prefix##_impl, &map->head, iter); \ + } \ + /** Advance iter a single step to the next entry, removing the \ + * current entry, and return its new value. */ \ + prefix##_iter_t * \ + prefix##_iter_next_rmv(maptype *map, prefix##_iter_t *iter) \ + { \ + prefix##_entry_t *rmv; \ + tor_assert(map); \ + tor_assert(iter); \ + tor_assert(*iter); \ + rmv = *iter; \ + iter = HT_NEXT_RMV(prefix##_impl, &map->head, iter); \ + prefix##_entry_free(rmv); \ + return iter; \ + } \ + /** Set *keyp and *valp to the current entry pointed \ + * to by iter. */ \ + void \ + prefix##_iter_get(prefix##_iter_t *iter, const keytype *keyp, \ + void **valp) \ + { \ + tor_assert(iter); \ + tor_assert(*iter); \ + tor_assert(keyp); \ + tor_assert(valp); \ + *keyp = (*iter)->key; \ + *valp = (*iter)->val; \ + } \ + /** Return true iff iter has advanced past the last entry of \ + * map. */ \ + int \ + prefix##_iter_done(prefix##_iter_t *iter) \ + { \ + return iter == NULL; \ + } + +IMPLEMENT_MAP_FNS(strmap_t, char *, strmap) +IMPLEMENT_MAP_FNS(digestmap_t, char *, digestmap) +IMPLEMENT_MAP_FNS(digest256map_t, uint8_t *, digest256map) + +/** Same as strmap_set, but first converts key to lowercase. */ +void * +strmap_set_lc(strmap_t *map, const char *key, void *val) +{ + /* We could be a little faster by using strcasecmp instead, and a separate + * type, but I don't think it matters. */ + void *v; + char *lc_key = tor_strdup(key); + tor_strlower(lc_key); + v = strmap_set(map,lc_key,val); + tor_free(lc_key); + return v; +} + +/** Same as strmap_get, but first converts key to lowercase. */ +void * +strmap_get_lc(const strmap_t *map, const char *key) +{ + void *v; + char *lc_key = tor_strdup(key); + tor_strlower(lc_key); + v = strmap_get(map,lc_key); + tor_free(lc_key); + return v; +} + +/** Same as strmap_remove, but first converts key to lowercase */ +void * +strmap_remove_lc(strmap_t *map, const char *key) +{ + void *v; + char *lc_key = tor_strdup(key); + tor_strlower(lc_key); + v = strmap_remove(map,lc_key); + tor_free(lc_key); + return v; +} diff --git a/src/lib/container/map.h b/src/lib/container/map.h new file mode 100644 index 0000000000..ac21c28718 --- /dev/null +++ b/src/lib/container/map.h @@ -0,0 +1,255 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_MAP_H +#define TOR_MAP_H + +#include "lib/testsupport/testsupport.h" +#include "lib/cc/torint.h" + +#include "siphash.h" + +#define DECLARE_MAP_FNS(maptype, keytype, prefix) \ + typedef struct maptype maptype; \ + typedef struct prefix##entry_t *prefix##iter_t; \ + MOCK_DECL(maptype*, prefix##new, (void)); \ + void* prefix##set(maptype *map, keytype key, void *val); \ + void* prefix##get(const maptype *map, keytype key); \ + void* prefix##remove(maptype *map, keytype key); \ + MOCK_DECL(void, prefix##free_, (maptype *map, void (*free_val)(void*))); \ + int prefix##isempty(const maptype *map); \ + int prefix##size(const maptype *map); \ + prefix##iter_t *prefix##iter_init(maptype *map); \ + prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \ + prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \ + void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \ + int prefix##iter_done(prefix##iter_t *iter); \ + void prefix##assert_ok(const maptype *map) + +/* Map from const char * to void *. Implemented with a hash table. */ +DECLARE_MAP_FNS(strmap_t, const char *, strmap_); +/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */ +DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_); +/* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash + * table. */ +DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_); + +#define MAP_FREE_AND_NULL(maptype, map, fn) \ + do { \ + maptype ## _free_((map), (fn)); \ + (map) = NULL; \ + } while (0) + +#define strmap_free(map, fn) MAP_FREE_AND_NULL(strmap, (map), (fn)) +#define digestmap_free(map, fn) MAP_FREE_AND_NULL(digestmap, (map), (fn)) +#define digest256map_free(map, fn) MAP_FREE_AND_NULL(digest256map, (map), (fn)) + +#undef DECLARE_MAP_FNS + +/** Iterates over the key-value pairs in a map map in order. + * prefix is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_). + * The map's keys and values are of type keytype and valtype respectively; + * each iteration assigns them to keyvar and valvar. + * + * Example use: + * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { + * // use k and r + * } MAP_FOREACH_END. + */ +/* Unpacks to, approximately: + * { + * digestmap_iter_t *k_iter; + * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); + * k_iter = digestmap_iter_next(m, k_iter)) { + * const char *k; + * void *r_voidp; + * routerinfo_t *r; + * digestmap_iter_get(k_iter, &k, &r_voidp); + * r = r_voidp; + * // use k and r + * } + * } + */ +#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \ + STMT_BEGIN \ + prefix##iter_t *keyvar##_iter; \ + for (keyvar##_iter = prefix##iter_init(map); \ + !prefix##iter_done(keyvar##_iter); \ + keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \ + keytype keyvar; \ + void *valvar##_voidp; \ + valtype valvar; \ + prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ + valvar = valvar##_voidp; + +/** As MAP_FOREACH, except allows members to be removed from the map + * during the iteration via MAP_DEL_CURRENT. Example use: + * + * Example use: + * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) { + * if (is_very_old(r)) + * MAP_DEL_CURRENT(k); + * } MAP_FOREACH_END. + **/ +/* Unpacks to, approximately: + * { + * digestmap_iter_t *k_iter; + * int k_del=0; + * for (k_iter = digestmap_iter_init(m); !digestmap_iter_done(k_iter); + * k_iter = k_del ? digestmap_iter_next(m, k_iter) + * : digestmap_iter_next_rmv(m, k_iter)) { + * const char *k; + * void *r_voidp; + * routerinfo_t *r; + * k_del=0; + * digestmap_iter_get(k_iter, &k, &r_voidp); + * r = r_voidp; + * if (is_very_old(r)) { + * k_del = 1; + * } + * } + * } + */ +#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \ + STMT_BEGIN \ + prefix##iter_t *keyvar##_iter; \ + int keyvar##_del=0; \ + for (keyvar##_iter = prefix##iter_init(map); \ + !prefix##iter_done(keyvar##_iter); \ + keyvar##_iter = keyvar##_del ? \ + prefix##iter_next_rmv(map, keyvar##_iter) : \ + prefix##iter_next(map, keyvar##_iter)) { \ + keytype keyvar; \ + void *valvar##_voidp; \ + valtype valvar; \ + keyvar##_del=0; \ + prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \ + valvar = valvar##_voidp; + +/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon + * member of the map. */ +#define MAP_DEL_CURRENT(keyvar) \ + STMT_BEGIN \ + keyvar##_del = 1; \ + STMT_END + +/** Used to end a MAP_FOREACH() block. */ +#define MAP_FOREACH_END } STMT_END ; + +/** As MAP_FOREACH, but does not require declaration of prefix or keytype. + * Example use: + * DIGESTMAP_FOREACH(m, k, routerinfo_t *, r) { + * // use k and r + * } DIGESTMAP_FOREACH_END. + */ +#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar) + +/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or + * keytype. + * Example use: + * DIGESTMAP_FOREACH_MODIFY(m, k, routerinfo_t *, r) { + * if (is_very_old(r)) + * MAP_DEL_CURRENT(k); + * } DIGESTMAP_FOREACH_END. + */ +#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar) +/** Used to end a DIGESTMAP_FOREACH() block. */ +#define DIGESTMAP_FOREACH_END MAP_FOREACH_END + +#define DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar) +#define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \ + keyvar, valtype, valvar) +#define DIGEST256MAP_FOREACH_END MAP_FOREACH_END + +#define STRMAP_FOREACH(map, keyvar, valtype, valvar) \ + MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar) +#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \ + MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar) +#define STRMAP_FOREACH_END MAP_FOREACH_END + +void* strmap_set_lc(strmap_t *map, const char *key, void *val); +void* strmap_get_lc(const strmap_t *map, const char *key); +void* strmap_remove_lc(strmap_t *map, const char *key); + +#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \ + typedef struct maptype maptype; \ + typedef struct prefix##iter_t *prefix##iter_t; \ + ATTR_UNUSED static inline maptype* \ + prefix##new(void) \ + { \ + return (maptype*)digestmap_new(); \ + } \ + ATTR_UNUSED static inline digestmap_t* \ + prefix##to_digestmap(maptype *map) \ + { \ + return (digestmap_t*)map; \ + } \ + ATTR_UNUSED static inline valtype* \ + prefix##get(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_get((digestmap_t*)map, key); \ + } \ + ATTR_UNUSED static inline valtype* \ + prefix##set(maptype *map, const char *key, valtype *val) \ + { \ + return (valtype*)digestmap_set((digestmap_t*)map, key, val); \ + } \ + ATTR_UNUSED static inline valtype* \ + prefix##remove(maptype *map, const char *key) \ + { \ + return (valtype*)digestmap_remove((digestmap_t*)map, key); \ + } \ + ATTR_UNUSED static inline void \ + prefix##f##ree_(maptype *map, void (*free_val)(void*)) \ + { \ + digestmap_free_((digestmap_t*)map, free_val); \ + } \ + ATTR_UNUSED static inline int \ + prefix##isempty(maptype *map) \ + { \ + return digestmap_isempty((digestmap_t*)map); \ + } \ + ATTR_UNUSED static inline int \ + prefix##size(maptype *map) \ + { \ + return digestmap_size((digestmap_t*)map); \ + } \ + ATTR_UNUSED static inline \ + prefix##iter_t *prefix##iter_init(maptype *map) \ + { \ + return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \ + } \ + ATTR_UNUSED static inline \ + prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter) \ + { \ + return (prefix##iter_t*) digestmap_iter_next( \ + (digestmap_t*)map, (digestmap_iter_t*)iter); \ + } \ + ATTR_UNUSED static inline prefix##iter_t* \ + prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter) \ + { \ + return (prefix##iter_t*) digestmap_iter_next_rmv( \ + (digestmap_t*)map, (digestmap_iter_t*)iter); \ + } \ + ATTR_UNUSED static inline void \ + prefix##iter_get(prefix##iter_t *iter, \ + const char **keyp, \ + valtype **valp) \ + { \ + void *v; \ + digestmap_iter_get((digestmap_iter_t*) iter, keyp, &v); \ + *valp = v; \ + } \ + ATTR_UNUSED static inline int \ + prefix##iter_done(prefix##iter_t *iter) \ + { \ + return digestmap_iter_done((digestmap_iter_t*)iter); \ + } + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/order.c b/src/lib/container/order.c new file mode 100644 index 0000000000..599f833007 --- /dev/null +++ b/src/lib/container/order.c @@ -0,0 +1,51 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file container.c + * \brief Implements a smartlist (a resizable array) along + * with helper functions to use smartlists. Also includes + * hash table implementations of a string-to-void* map, and of + * a digest-to-void* map. + **/ + +#include + +#include "lib/container/order.h" +#include "common/util_bug.h" + +/** Declare a function called funcname that acts as a find_nth_FOO + * function for an array of type elt_t*. + * + * NOTE: The implementation kind of sucks: It's O(n log n), whereas finding + * the kth element of an n-element list can be done in O(n). Then again, this + * implementation is not in critical path, and it is obviously correct. */ +#define IMPLEMENT_ORDER_FUNC(funcname, elt_t) \ + static int \ + _cmp_ ## elt_t(const void *_a, const void *_b) \ + { \ + const elt_t *a = _a, *b = _b; \ + if (*a<*b) \ + return -1; \ + else if (*a>*b) \ + return 1; \ + else \ + return 0; \ + } \ + elt_t \ + funcname(elt_t *array, int n_elements, int nth) \ + { \ + tor_assert(nth >= 0); \ + tor_assert(nth < n_elements); \ + qsort(array, n_elements, sizeof(elt_t), _cmp_ ##elt_t); \ + return array[nth]; \ + } + +IMPLEMENT_ORDER_FUNC(find_nth_int, int) +IMPLEMENT_ORDER_FUNC(find_nth_time, time_t) +IMPLEMENT_ORDER_FUNC(find_nth_double, double) +IMPLEMENT_ORDER_FUNC(find_nth_uint32, uint32_t) +IMPLEMENT_ORDER_FUNC(find_nth_int32, int32_t) +IMPLEMENT_ORDER_FUNC(find_nth_long, long) diff --git a/src/lib/container/order.h b/src/lib/container/order.h new file mode 100644 index 0000000000..bd23750d54 --- /dev/null +++ b/src/lib/container/order.h @@ -0,0 +1,54 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_ORDER_H +#define TOR_ORDER_H + +#include "lib/cc/compat_compiler.h" +#include "lib/cc/torint.h" + +/* These functions, given an array of n_elements, return the + * nth lowest element. nth=0 gives the lowest element; + * n_elements-1 gives the highest; and (n_elements-1) / 2 gives + * the median. As a side effect, the elements of array are sorted. */ +int find_nth_int(int *array, int n_elements, int nth); +time_t find_nth_time(time_t *array, int n_elements, int nth); +double find_nth_double(double *array, int n_elements, int nth); +int32_t find_nth_int32(int32_t *array, int n_elements, int nth); +uint32_t find_nth_uint32(uint32_t *array, int n_elements, int nth); +long find_nth_long(long *array, int n_elements, int nth); +static inline int +median_int(int *array, int n_elements) +{ + return find_nth_int(array, n_elements, (n_elements-1)/2); +} +static inline time_t +median_time(time_t *array, int n_elements) +{ + return find_nth_time(array, n_elements, (n_elements-1)/2); +} +static inline double +median_double(double *array, int n_elements) +{ + return find_nth_double(array, n_elements, (n_elements-1)/2); +} +static inline uint32_t +median_uint32(uint32_t *array, int n_elements) +{ + return find_nth_uint32(array, n_elements, (n_elements-1)/2); +} +static inline int32_t +median_int32(int32_t *array, int n_elements) +{ + return find_nth_int32(array, n_elements, (n_elements-1)/2); +} + +static inline uint32_t +third_quartile_uint32(uint32_t *array, int n_elements) +{ + return find_nth_uint32(array, n_elements, (n_elements*3)/4); +} + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/container/smartlist.c b/src/lib/container/smartlist.c new file mode 100644 index 0000000000..6aef728547 --- /dev/null +++ b/src/lib/container/smartlist.c @@ -0,0 +1,1094 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file container.c + * \brief Implements a smartlist (a resizable array) along + * with helper functions to use smartlists. Also includes + * hash table implementations of a string-to-void* map, and of + * a digest-to-void* map. + **/ + +#include "lib/malloc/util_malloc.h" +#include "lib/container/smartlist.h" +#include "common/util.h" +#include "lib/crypt_ops/crypto_digest.h" +#include "lib/ctime/di_ops.h" + +#include +#include + +/** All newly allocated smartlists have this capacity. */ +#define SMARTLIST_DEFAULT_CAPACITY 16 + +/** Allocate and return an empty smartlist. + */ +MOCK_IMPL(smartlist_t *, +smartlist_new,(void)) +{ + smartlist_t *sl = tor_malloc(sizeof(smartlist_t)); + sl->num_used = 0; + sl->capacity = SMARTLIST_DEFAULT_CAPACITY; + sl->list = tor_calloc(sizeof(void *), sl->capacity); + return sl; +} + +/** Deallocate a smartlist. Does not release storage associated with the + * list's elements. + */ +MOCK_IMPL(void, +smartlist_free_,(smartlist_t *sl)) +{ + if (!sl) + return; + tor_free(sl->list); + tor_free(sl); +} + +/** Remove all elements from the list. + */ +void +smartlist_clear(smartlist_t *sl) +{ + memset(sl->list, 0, sizeof(void *) * sl->num_used); + sl->num_used = 0; +} + +#if SIZE_MAX < INT_MAX +#error "We don't support systems where size_t is smaller than int." +#endif + +/** Make sure that sl can hold at least size entries. */ +static inline void +smartlist_ensure_capacity(smartlist_t *sl, size_t size) +{ + /* Set MAX_CAPACITY to MIN(INT_MAX, SIZE_MAX / sizeof(void*)) */ +#if (SIZE_MAX/SIZEOF_VOID_P) > INT_MAX +#define MAX_CAPACITY (INT_MAX) +#else +#define MAX_CAPACITY (int)((SIZE_MAX / (sizeof(void*)))) +#endif + + raw_assert(size <= MAX_CAPACITY); + + if (size > (size_t) sl->capacity) { + size_t higher = (size_t) sl->capacity; + if (PREDICT_UNLIKELY(size > MAX_CAPACITY/2)) { + higher = MAX_CAPACITY; + } else { + while (size > higher) + higher *= 2; + } + sl->list = tor_reallocarray(sl->list, sizeof(void *), + ((size_t)higher)); + memset(sl->list + sl->capacity, 0, + sizeof(void *) * (higher - sl->capacity)); + sl->capacity = (int) higher; + } +#undef ASSERT_CAPACITY +#undef MAX_CAPACITY +} + +/** Append element to the end of the list. */ +void +smartlist_add(smartlist_t *sl, void *element) +{ + smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); + sl->list[sl->num_used++] = element; +} + +/** Append each element from S2 to the end of S1. */ +void +smartlist_add_all(smartlist_t *s1, const smartlist_t *s2) +{ + size_t new_size = (size_t)s1->num_used + (size_t)s2->num_used; + tor_assert(new_size >= (size_t) s1->num_used); /* check for overflow. */ + smartlist_ensure_capacity(s1, new_size); + memcpy(s1->list + s1->num_used, s2->list, s2->num_used*sizeof(void*)); + tor_assert(new_size <= INT_MAX); /* redundant. */ + s1->num_used = (int) new_size; +} + +/** Append a copy of string to sl */ +void +smartlist_add_strdup(struct smartlist_t *sl, const char *string) +{ + char *copy; + + copy = tor_strdup(string); + + smartlist_add(sl, copy); +} + +/** Remove all elements E from sl such that E==element. Preserve + * the order of any elements before E, but elements after E can be + * rearranged. + */ +void +smartlist_remove(smartlist_t *sl, const void *element) +{ + int i; + if (element == NULL) + return; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) { + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + sl->list[sl->num_used] = NULL; + } +} + +/** As smartlist_remove, but do not change the order of + * any elements not removed */ +void +smartlist_remove_keeporder(smartlist_t *sl, const void *element) +{ + int i, j, num_used_orig = sl->num_used; + if (element == NULL) + return; + + for (i=j=0; j < num_used_orig; ++j) { + if (sl->list[j] == element) { + --sl->num_used; + } else { + sl->list[i++] = sl->list[j]; + } + } +} + +/** If sl is nonempty, remove and return the final element. Otherwise, + * return NULL. */ +void * +smartlist_pop_last(smartlist_t *sl) +{ + tor_assert(sl); + if (sl->num_used) { + void *tmp = sl->list[--sl->num_used]; + sl->list[sl->num_used] = NULL; + return tmp; + } else + return NULL; +} + +/** Reverse the order of the items in sl. */ +void +smartlist_reverse(smartlist_t *sl) +{ + int i, j; + void *tmp; + tor_assert(sl); + for (i = 0, j = sl->num_used-1; i < j; ++i, --j) { + tmp = sl->list[i]; + sl->list[i] = sl->list[j]; + sl->list[j] = tmp; + } +} + +/** If there are any strings in sl equal to element, remove and free them. + * Does not preserve order. */ +void +smartlist_string_remove(smartlist_t *sl, const char *element) +{ + int i; + tor_assert(sl); + tor_assert(element); + for (i = 0; i < sl->num_used; ++i) { + if (!strcmp(element, sl->list[i])) { + tor_free(sl->list[i]); + sl->list[i] = sl->list[--sl->num_used]; /* swap with the end */ + i--; /* so we process the new i'th element */ + sl->list[sl->num_used] = NULL; + } + } +} + +/** Return true iff some element E of sl has E==element. + */ +int +smartlist_contains(const smartlist_t *sl, const void *element) +{ + int i; + for (i=0; i < sl->num_used; i++) + if (sl->list[i] == element) + return 1; + return 0; +} + +/** Return true iff sl has some element E such that + * !strcmp(E,element) + */ +int +smartlist_contains_string(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** If element is equal to an element of sl, return that + * element's index. Otherwise, return -1. */ +int +smartlist_string_pos(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return -1; + for (i=0; i < sl->num_used; i++) + if (strcmp((const char*)sl->list[i],element)==0) + return i; + return -1; +} + +/** If element is the same pointer as an element of sl, return + * that element's index. Otherwise, return -1. */ +int +smartlist_pos(const smartlist_t *sl, const void *element) +{ + int i; + if (!sl) return -1; + for (i=0; i < sl->num_used; i++) + if (element == sl->list[i]) + return i; + return -1; +} + +/** Return true iff sl has some element E such that + * !strcasecmp(E,element) + */ +int +smartlist_contains_string_case(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (strcasecmp((const char*)sl->list[i],element)==0) + return 1; + return 0; +} + +/** Return true iff sl has some element E such that E is equal + * to the decimal encoding of num. + */ +int +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_contains_string(sl, buf); +} + +/** Return true iff the two lists contain the same strings in the same + * order, or if they are both NULL. */ +int +smartlist_strings_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, const char *, cp1, { + const char *cp2 = smartlist_get(sl2, cp1_sl_idx); + if (strcmp(cp1, cp2)) + return 0; + }); + 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 sl has some element E such that + * tor_memeq(E,element,DIGEST_LEN) + */ +int +smartlist_contains_digest(const smartlist_t *sl, const char *element) +{ + int i; + if (!sl) return 0; + for (i=0; i < sl->num_used; i++) + if (tor_memeq((const char*)sl->list[i],element,DIGEST_LEN)) + return 1; + return 0; +} + +/** 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_contains(sl1, sl2->list[i])) + return 1; + return 0; +} + +/** Remove every element E of sl1 such that !smartlist_contains(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_intersect(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl1->num_used; 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 */ + sl1->list[sl1->num_used] = NULL; + } +} + +/** Remove every element E of sl1 such that smartlist_contains(sl2,E). + * Does not preserve the order of sl1. + */ +void +smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2) +{ + int i; + for (i=0; i < sl2->num_used; i++) + smartlist_remove(sl1, sl2->list[i]); +} + +/** Remove the idxth element of sl; if idx is not the last + * element, swap the last element of sl into the idxth space. + */ +void +smartlist_del(smartlist_t *sl, int idx) +{ + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(idx < sl->num_used); + sl->list[idx] = sl->list[--sl->num_used]; + sl->list[sl->num_used] = NULL; +} + +/** Remove the idxth element of sl; if idx is not the last element, + * moving all subsequent elements back one space. Return the old value + * of the idxth element. + */ +void +smartlist_del_keeporder(smartlist_t *sl, int idx) +{ + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(idx < sl->num_used); + --sl->num_used; + if (idx < sl->num_used) + memmove(sl->list+idx, sl->list+idx+1, sizeof(void*)*(sl->num_used-idx)); + sl->list[sl->num_used] = NULL; +} + +/** Insert the value val as the new idxth element of + * sl, moving all items previously at idx or later + * forward one space. + */ +void +smartlist_insert(smartlist_t *sl, int idx, void *val) +{ + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(idx <= sl->num_used); + if (idx == sl->num_used) { + smartlist_add(sl, val); + } else { + smartlist_ensure_capacity(sl, ((size_t) sl->num_used)+1); + /* Move other elements away */ + if (idx < sl->num_used) + memmove(sl->list + idx + 1, sl->list + idx, + sizeof(void*)*(sl->num_used-idx)); + sl->num_used++; + sl->list[idx] = val; + } +} + +/** + * Split a string str along all occurrences of sep, + * appending the (newly allocated) split strings, in order, to + * sl. Return the number of strings added to sl. + * + * If flags&SPLIT_SKIP_SPACE is true, remove initial and + * trailing space from each entry. + * If flags&SPLIT_IGNORE_BLANK is true, remove any entries + * of length 0. + * If flags&SPLIT_STRIP_SPACE is true, strip spaces from each + * split string. + * + * If max\>0, divide the string into no more than max pieces. If + * sep is NULL, split on any sequence of horizontal space. + */ +int +smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max) +{ + const char *cp, *end, *next; + int n = 0; + + tor_assert(sl); + tor_assert(str); + + cp = str; + while (1) { + if (flags&SPLIT_SKIP_SPACE) { + while (TOR_ISSPACE(*cp)) ++cp; + } + + if (max>0 && n == max-1) { + end = strchr(cp,'\0'); + } else if (sep) { + end = strstr(cp,sep); + if (!end) + end = strchr(cp,'\0'); + } else { + for (end = cp; *end && *end != '\t' && *end != ' '; ++end) + ; + } + + tor_assert(end); + + if (!*end) { + next = NULL; + } else if (sep) { + next = end+strlen(sep); + } else { + next = end+1; + while (*next == '\t' || *next == ' ') + ++next; + } + + if (flags&SPLIT_SKIP_SPACE) { + while (end > cp && TOR_ISSPACE(*(end-1))) + --end; + } + if (end != cp || !(flags&SPLIT_IGNORE_BLANK)) { + char *string = tor_strndup(cp, end-cp); + if (flags&SPLIT_STRIP_SPACE) + tor_strstrip(string, " "); + smartlist_add(sl, string); + ++n; + } + if (!next) + break; + cp = next; + } + + return n; +} + +/** Allocate and return a new string containing the concatenation of + * the elements of sl, in order, separated by join. If + * terminate is true, also terminate the string with join. + * If len_out is not NULL, set len_out to the length of + * the returned string. Requires that every element of sl is + * NUL-terminated string. + */ +char * +smartlist_join_strings(smartlist_t *sl, const char *join, + int terminate, size_t *len_out) +{ + return smartlist_join_strings2(sl,join,strlen(join),terminate,len_out); +} + +/** As smartlist_join_strings, but instead of separating/terminated with a + * NUL-terminated string join, uses the join_len-byte sequence + * at join. (Useful for generating a sequence of NUL-terminated + * strings.) + */ +char * +smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) +{ + int i; + size_t n = 0; + char *r = NULL, *dst, *src; + + tor_assert(sl); + tor_assert(join); + + if (terminate) + n = join_len; + + for (i = 0; i < sl->num_used; ++i) { + n += strlen(sl->list[i]); + if (i+1 < sl->num_used) /* avoid double-counting the last one */ + n += join_len; + } + dst = r = tor_malloc(n+1); + for (i = 0; i < sl->num_used; ) { + for (src = sl->list[i]; *src; ) + *dst++ = *src++; + if (++i < sl->num_used) { + memcpy(dst, join, join_len); + dst += join_len; + } + } + if (terminate) { + memcpy(dst, join, join_len); + dst += join_len; + } + *dst = '\0'; + + if (len_out) + *len_out = dst-r; + return r; +} + +/** Sort the members of sl into an order defined by + * the ordering function compare, which returns less then 0 if a + * precedes b, greater than 0 if b precedes a, and 0 if a 'equals' b. + */ +void +smartlist_sort(smartlist_t *sl, int (*compare)(const void **a, const void **b)) +{ + if (!sl->num_used) + return; + qsort(sl->list, sl->num_used, sizeof(void*), + (int (*)(const void *,const void*))compare); +} + +/** Given a smartlist sl sorted with the function compare, + * return the most frequent member in the list. Break ties in favor of + * later elements. If the list is empty, return NULL. If count_out is + * non-null, set it to the count of the most frequent member. + */ +void * +smartlist_get_most_frequent_(const smartlist_t *sl, + int (*compare)(const void **a, const void **b), + int *count_out) +{ + const void *most_frequent = NULL; + int most_frequent_count = 0; + + const void *cur = NULL; + int i, count=0; + + if (!sl->num_used) { + if (count_out) + *count_out = 0; + return NULL; + } + for (i = 0; i < sl->num_used; ++i) { + const void *item = sl->list[i]; + if (cur && 0 == compare(&cur, &item)) { + ++count; + } else { + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + cur = item; + count = 1; + } + } + if (cur && count >= most_frequent_count) { + most_frequent = cur; + most_frequent_count = count; + } + if (count_out) + *count_out = most_frequent_count; + return (void*)most_frequent; +} + +/** Given a sorted smartlist sl and the comparison function used to + * sort it, remove all duplicate members. If free_fn is provided, calls + * free_fn on each duplicate. Otherwise, just removes them. Preserves order. + */ +void +smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *a)) +{ + int i; + for (i=1; i < sl->num_used; ++i) { + if (compare((const void **)&(sl->list[i-1]), + (const void **)&(sl->list[i])) == 0) { + if (free_fn) + free_fn(sl->list[i]); + smartlist_del_keeporder(sl, i--); + } + } +} + +/** Assuming the members of sl are in order, return a pointer to the + * member that matches key. Ordering and matching are defined by a + * compare function that returns 0 on a match; less than 0 if key is + * less than member, and greater than 0 if key is greater then member. + */ +void * +smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)) +{ + int found, idx; + idx = smartlist_bsearch_idx(sl, key, compare, &found); + return found ? smartlist_get(sl, idx) : NULL; +} + +/** Assuming the members of sl are in order, return the index of the + * member that matches key. If no member matches, return the index of + * the first member greater than key, or smartlist_len(sl) if no member + * is greater than key. Set found_out to true on a match, to + * false otherwise. Ordering and matching are defined by a compare + * function that returns 0 on a match; less than 0 if key is less than member, + * and greater than 0 if key is greater then member. + */ +int +smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out) +{ + 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; + } + + /* 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) { + 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) { + /* sl[mid] == key; we found it */ + *found_out = 1; + return mid; + } 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); + + /* + * 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) +{ + return strcmp((const char*)*_a, (const char*)*_b); +} + +/** Sort a smartlist sl containing strings into lexically ascending + * order. */ +void +smartlist_sort_strings(smartlist_t *sl) +{ + smartlist_sort(sl, compare_string_ptrs_); +} + +/** Return the most frequent string in the sorted list sl */ +const char * +smartlist_get_most_frequent_string(smartlist_t *sl) +{ + return smartlist_get_most_frequent(sl, compare_string_ptrs_); +} + +/** Return the most frequent string in the sorted list sl. + * If count_out is provided, set count_out to the + * number of times that string appears. + */ +const char * +smartlist_get_most_frequent_string_(smartlist_t *sl, int *count_out) +{ + return smartlist_get_most_frequent_(sl, compare_string_ptrs_, count_out); +} + +/** Remove duplicate strings from a sorted list, and free them with tor_free(). + */ +void +smartlist_uniq_strings(smartlist_t *sl) +{ + 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 (asl 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. + * Recall that the heap property is that, for every index I, h[I] < + * H[LEFT_CHILD[I]] and h[I] < H[RIGHT_CHILD[I]]. + * + * For us to remove items other than the topmost item, each item must store + * its own index within the heap. When calling the pqueue functions, tell + * them about the offset of the field that stores the index within the item. + * + * Example: + * + * typedef struct timer_t { + * struct timeval tv; + * int heap_index; + * } timer_t; + * + * static int compare(const void *p1, const void *p2) { + * const timer_t *t1 = p1, *t2 = p2; + * if (t1->tv.tv_sec < t2->tv.tv_sec) { + * return -1; + * } else if (t1->tv.tv_sec > t2->tv.tv_sec) { + * return 1; + * } else { + * return t1->tv.tv_usec - t2->tv_usec; + * } + * } + * + * void timer_heap_insert(smartlist_t *heap, timer_t *timer) { + * smartlist_pqueue_add(heap, compare, offsetof(timer_t, heap_index), + * timer); + * } + * + * void timer_heap_pop(smartlist_t *heap) { + * return smartlist_pqueue_pop(heap, compare, + * offsetof(timer_t, heap_index)); + * } + */ + +/** @{ */ +/** Functions to manipulate heap indices to find a node's parent and children. + * + * For a 1-indexed array, we would use LEFT_CHILD[x] = 2*x and RIGHT_CHILD[x] + * = 2*x + 1. But this is C, so we have to adjust a little. */ + +/* MAX_PARENT_IDX is the largest IDX in the smartlist which might have + * children whose indices fit inside an int. + * LEFT_CHILD(MAX_PARENT_IDX) == INT_MAX-2; + * RIGHT_CHILD(MAX_PARENT_IDX) == INT_MAX-1; + * LEFT_CHILD(MAX_PARENT_IDX + 1) == INT_MAX // impossible, see max list size. + */ +#define MAX_PARENT_IDX ((INT_MAX - 2) / 2) +/* If this is true, then i is small enough to potentially have children + * in the smartlist, and it is save to use LEFT_CHILD/RIGHT_CHILD on it. */ +#define IDX_MAY_HAVE_CHILDREN(i) ((i) <= MAX_PARENT_IDX) +#define LEFT_CHILD(i) ( 2*(i) + 1 ) +#define RIGHT_CHILD(i) ( 2*(i) + 2 ) +#define PARENT(i) ( ((i)-1) / 2 ) +/** }@ */ + +/** @{ */ +/** Helper macros for heaps: Given a local variable idx_field_offset + * set to the offset of an integer index within the heap element structure, + * IDX_OF_ITEM(p) gives you the index of p, and IDXP(p) gives you a pointer to + * where p's index is stored. Given additionally a local smartlist sl, + * UPDATE_IDX(i) sets the index of the element at i to the correct + * value (that is, to i). + */ +#define IDXP(p) ((int*)STRUCT_VAR_P(p, idx_field_offset)) + +#define UPDATE_IDX(i) do { \ + void *updated = sl->list[i]; \ + *IDXP(updated) = i; \ + } while (0) + +#define IDX_OF_ITEM(p) (*IDXP(p)) +/** @} */ + +/** Helper. sl may have at most one violation of the heap property: + * the item at idx may be greater than one or both of its children. + * Restore the heap property. */ +static inline void +smartlist_heapify(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + int idx) +{ + while (1) { + if (! IDX_MAY_HAVE_CHILDREN(idx)) { + /* idx is so large that it cannot have any children, since doing so + * would mean the smartlist was over-capacity. Therefore it cannot + * violate the heap property by being greater than a child (since it + * doesn't have any). */ + return; + } + + 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; + UPDATE_IDX(idx); + UPDATE_IDX(best_idx); + + idx = best_idx; + } + } +} + +/** Insert item into the heap stored in sl, where order is + * determined by compare and the offset of the item in the heap is + * stored in an int-typed field at position idx_field_offset within + * item. + */ +void +smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx; + smartlist_add(sl,item); + UPDATE_IDX(sl->num_used-1); + + 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; + UPDATE_IDX(parent); + UPDATE_IDX(idx); + idx = parent; + } else { + return; + } + } +} + +/** Remove and return the top-priority item from the heap stored in sl, + * where order is determined by compare and the item's position is + * stored at position idx_field_offset within the item. sl must + * not be empty. */ +void * +smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + void *top; + tor_assert(sl->num_used); + + top = sl->list[0]; + *IDXP(top)=-1; + if (--sl->num_used) { + sl->list[0] = sl->list[sl->num_used]; + sl->list[sl->num_used] = NULL; + UPDATE_IDX(0); + smartlist_heapify(sl, compare, idx_field_offset, 0); + } + sl->list[sl->num_used] = NULL; + return top; +} + +/** Remove the item item from the heap stored in sl, + * where order is determined by compare and the item's position is + * stored at position idx_field_offset within the item. sl must + * not be empty. */ +void +smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item) +{ + int idx = IDX_OF_ITEM(item); + tor_assert(idx >= 0); + tor_assert(sl->list[idx] == item); + --sl->num_used; + *IDXP(item) = -1; + if (idx == sl->num_used) { + sl->list[sl->num_used] = NULL; + return; + } else { + sl->list[idx] = sl->list[sl->num_used]; + sl->list[sl->num_used] = NULL; + UPDATE_IDX(idx); + smartlist_heapify(sl, compare, idx_field_offset, idx); + } +} + +/** Assert that the heap property is correctly maintained by the heap stored + * in sl, where order is determined by compare. */ +void +smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset) +{ + int i; + for (i = sl->num_used - 1; i >= 0; --i) { + if (i>0) + tor_assert(compare(sl->list[PARENT(i)], sl->list[i]) <= 0); + tor_assert(IDX_OF_ITEM(sl->list[i]) == i); + } +} + +/** Helper: compare two DIGEST_LEN digests. */ +static int +compare_digests_(const void **_a, const void **_b) +{ + return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST_LEN); +} + +/** Sort the list of DIGEST_LEN-byte digests into ascending order. */ +void +smartlist_sort_digests(smartlist_t *sl) +{ + smartlist_sort(sl, compare_digests_); +} + +/** Remove duplicate digests from a sorted list, and free them with tor_free(). + */ +void +smartlist_uniq_digests(smartlist_t *sl) +{ + smartlist_uniq(sl, compare_digests_, tor_free_); +} + +/** Helper: compare two DIGEST256_LEN digests. */ +static int +compare_digests256_(const void **_a, const void **_b) +{ + return tor_memcmp((const char*)*_a, (const char*)*_b, DIGEST256_LEN); +} + +/** Sort the list of DIGEST256_LEN-byte digests into ascending order. */ +void +smartlist_sort_digests256(smartlist_t *sl) +{ + smartlist_sort(sl, compare_digests256_); +} + +/** Return the most frequent member of the sorted list of DIGEST256_LEN + * digests in sl */ +const uint8_t * +smartlist_get_most_frequent_digest256(smartlist_t *sl) +{ + return smartlist_get_most_frequent(sl, compare_digests256_); +} + +/** Remove duplicate 256-bit digests from a sorted list, and free them with + * tor_free(). + */ +void +smartlist_uniq_digests256(smartlist_t *sl) +{ + smartlist_uniq(sl, compare_digests256_, tor_free_); +} diff --git a/src/lib/container/smartlist.h b/src/lib/container/smartlist.h new file mode 100644 index 0000000000..7b80a9fed3 --- /dev/null +++ b/src/lib/container/smartlist.h @@ -0,0 +1,351 @@ +/* Copyright (c) 2003-2004, Roger Dingledine + * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. + * Copyright (c) 2007-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#ifndef TOR_SMARTLIST_H +#define TOR_SMARTLIST_H + +#include +#include "lib/cc/compat_compiler.h" +#include "common/util_bug.h" +#include "lib/testsupport/testsupport.h" + +/** A resizeable list of pointers, with associated helpful functionality. + * + * The members of this struct are exposed only so that macros and inlines can + * use them; all access to smartlist internals should go through the functions + * and macros defined here. + **/ +typedef struct smartlist_t { + /** @{ */ + /** list has enough capacity to store exactly capacity elements + * before it needs to be resized. Only the first num_used (\<= + * capacity) elements point to valid data. + */ + void **list; + int num_used; + int capacity; + /** @} */ +} smartlist_t; + +MOCK_DECL(smartlist_t *, smartlist_new, (void)); +MOCK_DECL(void, smartlist_free_, (smartlist_t *sl)); +#define smartlist_free(sl) FREE_AND_NULL(smartlist_t, smartlist_free_, (sl)) + +void smartlist_clear(smartlist_t *sl); +void smartlist_add(smartlist_t *sl, void *element); +void smartlist_add_all(smartlist_t *sl, const smartlist_t *s2); +void smartlist_add_strdup(struct smartlist_t *sl, const char *string); +void smartlist_remove(smartlist_t *sl, const void *element); +void smartlist_remove_keeporder(smartlist_t *sl, const void *element); +void *smartlist_pop_last(smartlist_t *sl); +void smartlist_reverse(smartlist_t *sl); +void smartlist_string_remove(smartlist_t *sl, const char *element); +int smartlist_contains(const smartlist_t *sl, const void *element); +int smartlist_contains_string(const smartlist_t *sl, const char *element); +int smartlist_pos(const smartlist_t *sl, const void *element); +int smartlist_string_pos(const smartlist_t *, const char *elt); +int smartlist_contains_string_case(const smartlist_t *sl, const char *element); +int smartlist_contains_int_as_string(const smartlist_t *sl, int num); +int smartlist_strings_eq(const smartlist_t *sl1, const smartlist_t *sl2); +int smartlist_contains_digest(const smartlist_t *sl, const char *element); +int smartlist_ints_eq(const smartlist_t *sl1, const smartlist_t *sl2); +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. + */ +static inline int smartlist_len(const smartlist_t *sl); +static inline int smartlist_len(const smartlist_t *sl) { + tor_assert(sl); + return (sl)->num_used; +} +/** Return the idxth element of sl. + */ +static inline void *smartlist_get(const smartlist_t *sl, int idx); +static inline void *smartlist_get(const smartlist_t *sl, int idx) { + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(sl->num_used > idx); + return sl->list[idx]; +} +static inline void smartlist_set(smartlist_t *sl, int idx, void *val) { + tor_assert(sl); + tor_assert(idx>=0); + tor_assert(sl->num_used > idx); + sl->list[idx] = val; +} +#else /* !(defined(DEBUG_SMARTLIST)) */ +#define smartlist_len(sl) ((sl)->num_used) +#define smartlist_get(sl, idx) ((sl)->list[idx]) +#define smartlist_set(sl, idx, val) ((sl)->list[idx] = (val)) +#endif /* defined(DEBUG_SMARTLIST) */ + +/** Exchange the elements at indices idx1 and idx2 of the + * smartlist sl. */ +static inline void smartlist_swap(smartlist_t *sl, int idx1, int idx2) +{ + if (idx1 != idx2) { + void *elt = smartlist_get(sl, idx1); + smartlist_set(sl, idx1, smartlist_get(sl, idx2)); + smartlist_set(sl, idx2, elt); + } +} + +void smartlist_del(smartlist_t *sl, int idx); +void smartlist_del_keeporder(smartlist_t *sl, int idx); +void smartlist_insert(smartlist_t *sl, int idx, void *val); +void smartlist_sort(smartlist_t *sl, + int (*compare)(const void **a, const void **b)); +void *smartlist_get_most_frequent_(const smartlist_t *sl, + int (*compare)(const void **a, const void **b), + int *count_out); +#define smartlist_get_most_frequent(sl, compare) \ + smartlist_get_most_frequent_((sl), (compare), NULL) +void smartlist_uniq(smartlist_t *sl, + int (*compare)(const void **a, const void **b), + void (*free_fn)(void *elt)); + +void smartlist_sort_strings(smartlist_t *sl); +void smartlist_sort_digests(smartlist_t *sl); +void smartlist_sort_digests256(smartlist_t *sl); +void smartlist_sort_pointers(smartlist_t *sl); + +const char *smartlist_get_most_frequent_string(smartlist_t *sl); +const char *smartlist_get_most_frequent_string_(smartlist_t *sl, + int *count_out); +const uint8_t *smartlist_get_most_frequent_digest256(smartlist_t *sl); + +void smartlist_uniq_strings(smartlist_t *sl); +void smartlist_uniq_digests(smartlist_t *sl); +void smartlist_uniq_digests256(smartlist_t *sl); +void *smartlist_bsearch(smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member)); +int smartlist_bsearch_idx(const smartlist_t *sl, const void *key, + int (*compare)(const void *key, const void **member), + int *found_out); + +void smartlist_pqueue_add(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item); +void *smartlist_pqueue_pop(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset); +void smartlist_pqueue_remove(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset, + void *item); +void smartlist_pqueue_assert_ok(smartlist_t *sl, + int (*compare)(const void *a, const void *b), + int idx_field_offset); + +#define SPLIT_SKIP_SPACE 0x01 +#define SPLIT_IGNORE_BLANK 0x02 +#define SPLIT_STRIP_SPACE 0x04 +int smartlist_split_string(smartlist_t *sl, const char *str, const char *sep, + int flags, int max); +char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, + size_t *len_out) ATTR_MALLOC; +char *smartlist_join_strings2(smartlist_t *sl, const char *join, + size_t join_len, int terminate, size_t *len_out) + ATTR_MALLOC; + +/** Iterate over the items in a smartlist sl, in order. For each item, + * assign it to a new local variable of type type named var, and + * execute the statements inside the loop body. Inside the loop, the loop + * index can be accessed as var_sl_idx and the length of the list can + * be accessed as var_sl_len. + * + * NOTE: Do not change the length of the list while the loop is in progress, + * unless you adjust the _sl_len variable correspondingly. See second example + * below. + * + * Example use: + * 
+ *   smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
+ *   SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
+ *     printf("%d: %s\n", cp_sl_idx, cp);
+ *     tor_free(cp);
+ *   } SMARTLIST_FOREACH_END(cp);
+ *   smartlist_free(list);
+ *
+ * + * Example use (advanced): + * 
+ *   SMARTLIST_FOREACH_BEGIN(list, char *, cp) {
+ *     if (!strcmp(cp, "junk")) {
+ *       tor_free(cp);
+ *       SMARTLIST_DEL_CURRENT(list, cp);
+ *     }
+ *   } SMARTLIST_FOREACH_END(cp);
+ *
+ */ +/* Note: these macros use token pasting, and reach into smartlist internals. + * This can make them a little daunting. Here's the approximate unpacking of + * the above examples, for entertainment value: + * + * 
+ * smartlist_t *list = smartlist_split("A:B:C", ":", 0, 0);
+ * {
+ *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
+ *   char *cp;
+ *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
+ *     cp = smartlist_get(list, cp_sl_idx);
+ *     printf("%d: %s\n", cp_sl_idx, cp);
+ *     tor_free(cp);
+ *   }
+ * }
+ * smartlist_free(list);
+ *
+ * + * 
+ * {
+ *   int cp_sl_idx, cp_sl_len = smartlist_len(list);
+ *   char *cp;
+ *   for (cp_sl_idx = 0; cp_sl_idx < cp_sl_len; ++cp_sl_idx) {
+ *     cp = smartlist_get(list, cp_sl_idx);
+ *     if (!strcmp(cp, "junk")) {
+ *       tor_free(cp);
+ *       smartlist_del(list, cp_sl_idx);
+ *       --cp_sl_idx;
+ *       --cp_sl_len;
+ *     }
+ *   }
+ * }
+ *
+ */ +#define SMARTLIST_FOREACH_BEGIN(sl, type, var) \ + STMT_BEGIN \ + int var ## _sl_idx, var ## _sl_len=(sl)->num_used; \ + type var; \ + for (var ## _sl_idx = 0; var ## _sl_idx < var ## _sl_len; \ + ++var ## _sl_idx) { \ + var = (sl)->list[var ## _sl_idx]; + +#define SMARTLIST_FOREACH_END(var) \ + var = NULL; \ + (void) var ## _sl_idx; \ + } STMT_END + +/** + * An alias for SMARTLIST_FOREACH_BEGIN and SMARTLIST_FOREACH_END, using + * cmd as the loop body. This wrapper is here for convenience with + * very short loops. + * + * By convention, we do not use this for loops which nest, or for loops over + * 10 lines or so. Use SMARTLIST_FOREACH_{BEGIN,END} for those. + */ +#define SMARTLIST_FOREACH(sl, type, var, cmd) \ + SMARTLIST_FOREACH_BEGIN(sl,type,var) { \ + cmd; \ + } SMARTLIST_FOREACH_END(var) + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, remove the current element in a way that + * won't confuse the loop. */ +#define SMARTLIST_DEL_CURRENT(sl, var) \ + STMT_BEGIN \ + smartlist_del(sl, var ## _sl_idx); \ + --var ## _sl_idx; \ + --var ## _sl_len; \ + STMT_END + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, remove the current element in a way that + * won't confuse the loop. */ +#define SMARTLIST_DEL_CURRENT_KEEPORDER(sl, var) \ + STMT_BEGIN \ + smartlist_del_keeporder(sl, var ## _sl_idx); \ + --var ## _sl_idx; \ + --var ## _sl_len; \ + STMT_END + +/** Helper: While in a SMARTLIST_FOREACH loop over the list sl indexed + * with the variable var, replace the current element with val. + * Does not deallocate the current value of var. + */ +#define SMARTLIST_REPLACE_CURRENT(sl, var, val) \ + STMT_BEGIN \ + smartlist_set(sl, var ## _sl_idx, val); \ + STMT_END + +/* Helper: Given two lists of items, possibly of different types, such that + * both lists are sorted on some common field (as determined by a comparison + * expression cmpexpr), and such that one list (sl1) has no + * duplicates on the common field, loop through the lists in lockstep, and + * execute unmatched_var2 on items in var2 that do not appear in + * var1. + * + * WARNING: It isn't safe to add remove elements from either list while the + * loop is in progress. + * + * Example use: + * SMARTLIST_FOREACH_JOIN(routerstatus_list, routerstatus_t *, rs, + * routerinfo_list, routerinfo_t *, ri, + * tor_memcmp(rs->identity_digest, ri->identity_digest, 20), + * log_info(LD_GENERAL,"No match for %s", ri->nickname)) { + * log_info(LD_GENERAL, "%s matches routerstatus %p", ri->nickname, rs); + * } SMARTLIST_FOREACH_JOIN_END(rs, ri); + **/ +/* The example above unpacks (approximately) to: + * int rs_sl_idx = 0, rs_sl_len = smartlist_len(routerstatus_list); + * int ri_sl_idx, ri_sl_len = smartlist_len(routerinfo_list); + * int rs_ri_cmp; + * routerstatus_t *rs; + * routerinfo_t *ri; + * for (; ri_sl_idx < ri_sl_len; ++ri_sl_idx) { + * ri = smartlist_get(routerinfo_list, ri_sl_idx); + * while (rs_sl_idx < rs_sl_len) { + * rs = smartlist_get(routerstatus_list, rs_sl_idx); + * rs_ri_cmp = tor_memcmp(rs->identity_digest, ri->identity_digest, 20); + * if (rs_ri_cmp > 0) { + * break; + * } else if (rs_ri_cmp == 0) { + * goto matched_ri; + * } else { + * ++rs_sl_idx; + * } + * } + * log_info(LD_GENERAL,"No match for %s", ri->nickname); + * continue; + * matched_ri: { + * log_info(LD_GENERAL,"%s matches with routerstatus %p",ri->nickname,rs); + * } + * } + */ +#define SMARTLIST_FOREACH_JOIN(sl1, type1, var1, sl2, type2, var2, \ + cmpexpr, unmatched_var2) \ + STMT_BEGIN \ + int var1 ## _sl_idx = 0, var1 ## _sl_len=(sl1)->num_used; \ + int var2 ## _sl_idx = 0, var2 ## _sl_len=(sl2)->num_used; \ + int var1 ## _ ## var2 ## _cmp; \ + type1 var1; \ + type2 var2; \ + for (; var2##_sl_idx < var2##_sl_len; ++var2##_sl_idx) { \ + var2 = (sl2)->list[var2##_sl_idx]; \ + while (var1##_sl_idx < var1##_sl_len) { \ + var1 = (sl1)->list[var1##_sl_idx]; \ + var1##_##var2##_cmp = (cmpexpr); \ + if (var1##_##var2##_cmp > 0) { \ + break; \ + } else if (var1##_##var2##_cmp == 0) { \ + goto matched_##var2; \ + } else { \ + ++var1##_sl_idx; \ + } \ + } \ + /* Ran out of v1, or no match for var2. */ \ + unmatched_var2; \ + continue; \ + matched_##var2: ; \ + +#define SMARTLIST_FOREACH_JOIN_END(var1, var2) \ + } \ + STMT_END + +#endif /* !defined(TOR_CONTAINER_H) */ diff --git a/src/lib/malloc/util_malloc.c b/src/lib/malloc/util_malloc.c index 4a0b3a9336..f3b0e50c70 100644 --- a/src/lib/malloc/util_malloc.c +++ b/src/lib/malloc/util_malloc.c @@ -12,7 +12,6 @@ #include "orconfig.h" #include -#include #include #include "lib/testsupport/testsupport.h" diff --git a/src/lib/malloc/util_malloc.h b/src/lib/malloc/util_malloc.h index 3da40351c6..88ecc04530 100644 --- a/src/lib/malloc/util_malloc.h +++ b/src/lib/malloc/util_malloc.h @@ -11,6 +11,8 @@ #ifndef TOR_UTIL_MALLOC_H #define TOR_UTIL_MALLOC_H +#include +#include #include "lib/cc/compat_compiler.h" /* Memory management */ -- cgit v1.2.3-54-g00ecf