diff options
Diffstat (limited to 'src/ext/ht.h')
| -rw-r--r-- | src/ext/ht.h | 57 |
1 files changed, 44 insertions, 13 deletions
diff --git a/src/ext/ht.h b/src/ext/ht.h index 838710784f..19a67a6a41 100644 --- a/src/ext/ht.h +++ b/src/ext/ht.h @@ -1,6 +1,6 @@ /* Copyright (c) 2002, Christopher Clark. * Copyright (c) 2005-2006, Nick Mathewson. - * Copyright (c) 2007-2013, The Tor Project, Inc. */ + * Copyright (c) 2007-2015, The Tor Project, Inc. */ /* See license at end. */ /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ @@ -38,8 +38,9 @@ } #endif +/* || 0 is for -Wparentheses-equality (-Wall?) appeasement under clang */ #define HT_EMPTY(head) \ - ((head)->hth_n_entries == 0) + (((head)->hth_n_entries == 0) || 0) /* How many elements in 'head'? */ #define HT_SIZE(head) \ @@ -120,16 +121,24 @@ ht_string_hash(const char *s) ((void)0) #endif +#define HT_BUCKET_NUM_(head, field, elm, hashfn) \ + (HT_ELT_HASH_(elm,field,hashfn) % head->hth_table_length) + /* Helper: alias for the bucket containing 'elm'. */ #define HT_BUCKET_(head, field, elm, hashfn) \ - ((head)->hth_table[HT_ELT_HASH_(elm,field,hashfn) \ - % head->hth_table_length]) + ((head)->hth_table[HT_BUCKET_NUM_(head, field, elm, hashfn)]) #define HT_FOREACH(x, name, head) \ for ((x) = HT_START(name, head); \ (x) != NULL; \ (x) = HT_NEXT(name, head, x)) +#ifndef HT_NDEBUG +#define HT_ASSERT_(x) tor_assert(x) +#else +#define HT_ASSERT_(x) (void)0 +#endif + #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ void name##_HT_CLEAR(struct name *ht); \ @@ -256,8 +265,11 @@ ht_string_hash(const char *s) { \ unsigned b = 0; \ while (b < head->hth_table_length) { \ - if (head->hth_table[b]) \ + if (head->hth_table[b]) { \ + HT_ASSERT_(b == \ + HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \ return &head->hth_table[b]; \ + } \ ++b; \ } \ return NULL; \ @@ -271,13 +283,17 @@ ht_string_hash(const char *s) name##_HT_NEXT(struct name *head, struct type **elm) \ { \ if ((*elm)->field.hte_next) { \ + HT_ASSERT_(HT_BUCKET_NUM_(head,field,*elm,hashfn) == \ + HT_BUCKET_NUM_(head,field,(*elm)->field.hte_next,hashfn)); \ return &(*elm)->field.hte_next; \ } else { \ - unsigned b = (HT_ELT_HASH_(*elm, field, hashfn) \ - % head->hth_table_length)+1; \ + unsigned b = HT_BUCKET_NUM_(head,field,*elm,hashfn)+1; \ while (b < head->hth_table_length) { \ - if (head->hth_table[b]) \ + if (head->hth_table[b]) { \ + HT_ASSERT_(b == \ + HT_BUCKET_NUM_(head,field,head->hth_table[b],hashfn)); \ return &head->hth_table[b]; \ + } \ ++b; \ } \ return NULL; \ @@ -302,8 +318,8 @@ ht_string_hash(const char *s) } \ } -#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ - reallocfn, freefn) \ +#define HT_GENERATE2(name, type, field, hashfn, eqfn, load, reallocarrayfn, \ + freefn) \ /* Primes that aren't too far from powers of two. We stop at */ \ /* P=402653189 because P*sizeof(void*) is less than SSIZE_MAX */ \ /* even on a 32-bit platform. */ \ @@ -336,7 +352,7 @@ ht_string_hash(const char *s) new_load_limit = (unsigned)(load*new_len); \ } while (new_load_limit <= size && \ prime_idx < (int)name##_N_PRIMES); \ - if ((new_table = mallocfn(new_len*sizeof(struct type*)))) { \ + if ((new_table = reallocarrayfn(NULL, new_len, sizeof(struct type*)))) { \ unsigned b; \ memset(new_table, 0, new_len*sizeof(struct type*)); \ for (b = 0; b < head->hth_table_length; ++b) { \ @@ -356,7 +372,7 @@ ht_string_hash(const char *s) head->hth_table = new_table; \ } else { \ unsigned b, b2; \ - new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \ + new_table = reallocarrayfn(head->hth_table, new_len, sizeof(struct type*)); \ if (!new_table) return -1; \ memset(new_table + head->hth_table_length, 0, \ (new_len - head->hth_table_length)*sizeof(struct type*)); \ @@ -417,7 +433,7 @@ ht_string_hash(const char *s) for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ if (HT_ELT_HASH_(elm, field, hashfn) != hashfn(elm)) \ return 1000 + i; \ - if ((HT_ELT_HASH_(elm, field, hashfn) % head->hth_table_length) != i) \ + if (HT_BUCKET_NUM_(head,field,elm,hashfn) != i) \ return 10000 + i; \ ++n; \ } \ @@ -427,6 +443,21 @@ ht_string_hash(const char *s) return 0; \ } +#define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ + reallocfn, freefn) \ + static void * \ + name##_reallocarray(void *arg, size_t a, size_t b) \ + { \ + if ((b) && (a) > SIZE_MAX / (b)) \ + return NULL; \ + if (arg) \ + return reallocfn((arg),(a)*(b)); \ + else \ + return mallocfn((a)*(b)); \ + } \ + HT_GENERATE2(name, type, field, hashfn, eqfn, load, \ + name##_reallocarray, freefn) + /** Implements an over-optimized "find and insert if absent" block; * not meant for direct usage by typical code, or usage outside the critical * path.*/ |