diff options
Diffstat (limited to 'src/common/container.h')
| -rw-r--r-- | src/common/container.h | 79 |
1 files changed, 57 insertions, 22 deletions
diff --git a/src/common/container.h b/src/common/container.h index fb93747945..bf4f04762c 100644 --- a/src/common/container.h +++ b/src/common/container.h @@ -1,12 +1,13 @@ /* Copyright (c) 2003-2004, Roger Dingledine * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. - * Copyright (c) 2007-2013, The Tor Project, Inc. */ + * Copyright (c) 2007-2015, The Tor Project, Inc. */ /* See LICENSE for licensing information */ #ifndef TOR_CONTAINER_H #define TOR_CONTAINER_H #include "util.h" +#include "siphash.h" /** A resizeable list of pointers, with associated helpful functionality. * @@ -26,8 +27,8 @@ typedef struct smartlist_t { /** @} */ } smartlist_t; -smartlist_t *smartlist_new(void); -void smartlist_free(smartlist_t *sl); +MOCK_DECL(smartlist_t *, smartlist_new, (void)); +MOCK_DECL(void, smartlist_free, (smartlist_t *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); @@ -37,11 +38,13 @@ 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); @@ -92,8 +95,11 @@ 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)); +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)); @@ -101,9 +107,12 @@ void smartlist_uniq(smartlist_t *sl, 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); -char *smartlist_get_most_frequent_string(smartlist_t *sl); -char *smartlist_get_most_frequent_digest256(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); @@ -240,6 +249,16 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join, STMT_END /** Helper: While in a SMARTLIST_FOREACH loop over the list <b>sl</b> indexed + * with the variable <b>var</b>, 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 <b>sl</b> indexed * with the variable <b>var</b>, replace the current element with <b>val</b>. * Does not deallocate the current value of <b>var</b>. */ @@ -325,11 +344,11 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join, #define DECLARE_MAP_FNS(maptype, keytype, prefix) \ typedef struct maptype maptype; \ typedef struct prefix##entry_t *prefix##iter_t; \ - maptype* prefix##new(void); \ + 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); \ - void prefix##free(maptype *map, void (*free_val)(void*)); \ + 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); \ @@ -343,6 +362,9 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join, 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_); #undef DECLARE_MAP_FNS @@ -458,6 +480,13 @@ DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_); /** 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) \ @@ -470,7 +499,7 @@ 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; \ + typedef struct prefix##iter_t *prefix##iter_t; \ ATTR_UNUSED static INLINE maptype* \ prefix##new(void) \ { \ @@ -560,7 +589,7 @@ bitarray_init_zero(unsigned int n_bits) { /* round up to the next int. */ size_t sz = (n_bits+BITARRAY_MASK) >> BITARRAY_SHIFT; - return tor_malloc_zero(sz*sizeof(unsigned int)); + return tor_calloc(sz, sizeof(unsigned int)); } /** Expand <b>ba</b> from holding <b>n_bits_old</b> to <b>n_bits_new</b>, * clearing all new bits. Returns a possibly changed pointer to the @@ -574,7 +603,7 @@ bitarray_expand(bitarray_t *ba, char *ptr; if (sz_new <= sz_old) return ba; - ptr = tor_realloc(ba, sz_new*sizeof(unsigned int)); + 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, @@ -619,11 +648,11 @@ typedef struct { static INLINE void digestset_add(digestset_t *set, const char *digest) { - const uint32_t *p = (const uint32_t *)digest; - const uint32_t d1 = p[0] + (p[1]>>16); - const uint32_t d2 = p[1] + (p[2]>>16); - const uint32_t d3 = p[2] + (p[3]>>16); - const uint32_t d4 = p[3] + (p[0]>>16); + 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)); @@ -635,11 +664,11 @@ digestset_add(digestset_t *set, const char *digest) static INLINE int digestset_contains(const digestset_t *set, const char *digest) { - const uint32_t *p = (const uint32_t *)digest; - const uint32_t d1 = p[0] + (p[1]>>16); - const uint32_t d2 = p[1] + (p[2]>>16); - const uint32_t d3 = p[2] + (p[3]>>16); - const uint32_t d4 = p[3] + (p[0]>>16); + 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)) && @@ -686,5 +715,11 @@ 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 |