michael@0: /* Based on work Copyright 2002 Christopher Clark */ michael@0: /* Copyright 2005-2012 Nick Mathewson */ michael@0: /* Copyright 2009-2012 Niels Provos and Nick Mathewson */ michael@0: /* See license at end. */ michael@0: michael@0: /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ michael@0: michael@0: #ifndef _EVENT_HT_H michael@0: #define _EVENT_HT_H michael@0: michael@0: #define HT_HEAD(name, type) \ michael@0: struct name { \ michael@0: /* The hash table itself. */ \ michael@0: struct type **hth_table; \ michael@0: /* How long is the hash table? */ \ michael@0: unsigned hth_table_length; \ michael@0: /* How many elements does the table contain? */ \ michael@0: unsigned hth_n_entries; \ michael@0: /* How many elements will we allow in the table before resizing it? */ \ michael@0: unsigned hth_load_limit; \ michael@0: /* Position of hth_table_length in the primes table. */ \ michael@0: int hth_prime_idx; \ michael@0: } michael@0: michael@0: #define HT_INITIALIZER() \ michael@0: { NULL, 0, 0, 0, -1 } michael@0: michael@0: #ifdef HT_CACHE_HASH_VALUES michael@0: #define HT_ENTRY(type) \ michael@0: struct { \ michael@0: struct type *hte_next; \ michael@0: unsigned hte_hash; \ michael@0: } michael@0: #else michael@0: #define HT_ENTRY(type) \ michael@0: struct { \ michael@0: struct type *hte_next; \ michael@0: } michael@0: #endif michael@0: michael@0: #define HT_EMPTY(head) \ michael@0: ((head)->hth_n_entries == 0) michael@0: michael@0: /* How many elements in 'head'? */ michael@0: #define HT_SIZE(head) \ michael@0: ((head)->hth_n_entries) michael@0: michael@0: #define HT_FIND(name, head, elm) name##_HT_FIND((head), (elm)) michael@0: #define HT_INSERT(name, head, elm) name##_HT_INSERT((head), (elm)) michael@0: #define HT_REPLACE(name, head, elm) name##_HT_REPLACE((head), (elm)) michael@0: #define HT_REMOVE(name, head, elm) name##_HT_REMOVE((head), (elm)) michael@0: #define HT_START(name, head) name##_HT_START(head) michael@0: #define HT_NEXT(name, head, elm) name##_HT_NEXT((head), (elm)) michael@0: #define HT_NEXT_RMV(name, head, elm) name##_HT_NEXT_RMV((head), (elm)) michael@0: #define HT_CLEAR(name, head) name##_HT_CLEAR(head) michael@0: #define HT_INIT(name, head) name##_HT_INIT(head) michael@0: /* Helper: */ michael@0: static inline unsigned michael@0: ht_improve_hash(unsigned h) michael@0: { michael@0: /* Aim to protect against poor hash functions by adding logic here michael@0: * - logic taken from java 1.4 hashtable source */ michael@0: h += ~(h << 9); michael@0: h ^= ((h >> 14) | (h << 18)); /* >>> */ michael@0: h += (h << 4); michael@0: h ^= ((h >> 10) | (h << 22)); /* >>> */ michael@0: return h; michael@0: } michael@0: michael@0: #if 0 michael@0: /** Basic string hash function, from Java standard String.hashCode(). */ michael@0: static inline unsigned michael@0: ht_string_hash(const char *s) michael@0: { michael@0: unsigned h = 0; michael@0: int m = 1; michael@0: while (*s) { michael@0: h += ((signed char)*s++)*m; michael@0: m = (m<<5)-1; /* m *= 31 */ michael@0: } michael@0: return h; michael@0: } michael@0: #endif michael@0: michael@0: /** Basic string hash function, from Python's str.__hash__() */ michael@0: static inline unsigned michael@0: ht_string_hash(const char *s) michael@0: { michael@0: unsigned h; michael@0: const unsigned char *cp = (const unsigned char *)s; michael@0: h = *cp << 7; michael@0: while (*cp) { michael@0: h = (1000003*h) ^ *cp++; michael@0: } michael@0: /* This conversion truncates the length of the string, but that's ok. */ michael@0: h ^= (unsigned)(cp-(const unsigned char*)s); michael@0: return h; michael@0: } michael@0: michael@0: #ifdef HT_CACHE_HASH_VALUES michael@0: #define _HT_SET_HASH(elm, field, hashfn) \ michael@0: do { (elm)->field.hte_hash = hashfn(elm); } while (0) michael@0: #define _HT_SET_HASHVAL(elm, field, val) \ michael@0: do { (elm)->field.hte_hash = (val); } while (0) michael@0: #define _HT_ELT_HASH(elm, field, hashfn) \ michael@0: ((elm)->field.hte_hash) michael@0: #else michael@0: #define _HT_SET_HASH(elm, field, hashfn) \ michael@0: ((void)0) michael@0: #define _HT_ELT_HASH(elm, field, hashfn) \ michael@0: (hashfn(elm)) michael@0: #define _HT_SET_HASHVAL(elm, field, val) \ michael@0: ((void)0) michael@0: #endif michael@0: michael@0: /* Helper: alias for the bucket containing 'elm'. */ michael@0: #define _HT_BUCKET(head, field, elm, hashfn) \ michael@0: ((head)->hth_table[_HT_ELT_HASH(elm,field,hashfn) % head->hth_table_length]) michael@0: michael@0: #define HT_FOREACH(x, name, head) \ michael@0: for ((x) = HT_START(name, head); \ michael@0: (x) != NULL; \ michael@0: (x) = HT_NEXT(name, head, x)) michael@0: michael@0: #define HT_PROTOTYPE(name, type, field, hashfn, eqfn) \ michael@0: int name##_HT_GROW(struct name *ht, unsigned min_capacity); \ michael@0: void name##_HT_CLEAR(struct name *ht); \ michael@0: int _##name##_HT_REP_IS_BAD(const struct name *ht); \ michael@0: static inline void \ michael@0: name##_HT_INIT(struct name *head) { \ michael@0: head->hth_table_length = 0; \ michael@0: head->hth_table = NULL; \ michael@0: head->hth_n_entries = 0; \ michael@0: head->hth_load_limit = 0; \ michael@0: head->hth_prime_idx = -1; \ michael@0: } \ michael@0: /* Helper: returns a pointer to the right location in the table \ michael@0: * 'head' to find or insert the element 'elm'. */ \ michael@0: static inline struct type ** \ michael@0: _##name##_HT_FIND_P(struct name *head, struct type *elm) \ michael@0: { \ michael@0: struct type **p; \ michael@0: if (!head->hth_table) \ michael@0: return NULL; \ michael@0: p = &_HT_BUCKET(head, field, elm, hashfn); \ michael@0: while (*p) { \ michael@0: if (eqfn(*p, elm)) \ michael@0: return p; \ michael@0: p = &(*p)->field.hte_next; \ michael@0: } \ michael@0: return p; \ michael@0: } \ michael@0: /* Return a pointer to the element in the table 'head' matching 'elm', \ michael@0: * or NULL if no such element exists */ \ michael@0: static inline struct type * \ michael@0: name##_HT_FIND(const struct name *head, struct type *elm) \ michael@0: { \ michael@0: struct type **p; \ michael@0: struct name *h = (struct name *) head; \ michael@0: _HT_SET_HASH(elm, field, hashfn); \ michael@0: p = _##name##_HT_FIND_P(h, elm); \ michael@0: return p ? *p : NULL; \ michael@0: } \ michael@0: /* Insert the element 'elm' into the table 'head'. Do not call this \ michael@0: * function if the table might already contain a matching element. */ \ michael@0: static inline void \ michael@0: name##_HT_INSERT(struct name *head, struct type *elm) \ michael@0: { \ michael@0: struct type **p; \ michael@0: if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ michael@0: name##_HT_GROW(head, head->hth_n_entries+1); \ michael@0: ++head->hth_n_entries; \ michael@0: _HT_SET_HASH(elm, field, hashfn); \ michael@0: p = &_HT_BUCKET(head, field, elm, hashfn); \ michael@0: elm->field.hte_next = *p; \ michael@0: *p = elm; \ michael@0: } \ michael@0: /* Insert the element 'elm' into the table 'head'. If there already \ michael@0: * a matching element in the table, replace that element and return \ michael@0: * it. */ \ michael@0: static inline struct type * \ michael@0: name##_HT_REPLACE(struct name *head, struct type *elm) \ michael@0: { \ michael@0: struct type **p, *r; \ michael@0: if (!head->hth_table || head->hth_n_entries >= head->hth_load_limit) \ michael@0: name##_HT_GROW(head, head->hth_n_entries+1); \ michael@0: _HT_SET_HASH(elm, field, hashfn); \ michael@0: p = _##name##_HT_FIND_P(head, elm); \ michael@0: r = *p; \ michael@0: *p = elm; \ michael@0: if (r && (r!=elm)) { \ michael@0: elm->field.hte_next = r->field.hte_next; \ michael@0: r->field.hte_next = NULL; \ michael@0: return r; \ michael@0: } else { \ michael@0: ++head->hth_n_entries; \ michael@0: return NULL; \ michael@0: } \ michael@0: } \ michael@0: /* Remove any element matching 'elm' from the table 'head'. If such \ michael@0: * an element is found, return it; otherwise return NULL. */ \ michael@0: static inline struct type * \ michael@0: name##_HT_REMOVE(struct name *head, struct type *elm) \ michael@0: { \ michael@0: struct type **p, *r; \ michael@0: _HT_SET_HASH(elm, field, hashfn); \ michael@0: p = _##name##_HT_FIND_P(head,elm); \ michael@0: if (!p || !*p) \ michael@0: return NULL; \ michael@0: r = *p; \ michael@0: *p = r->field.hte_next; \ michael@0: r->field.hte_next = NULL; \ michael@0: --head->hth_n_entries; \ michael@0: return r; \ michael@0: } \ michael@0: /* Invoke the function 'fn' on every element of the table 'head', \ michael@0: * using 'data' as its second argument. If the function returns \ michael@0: * nonzero, remove the most recently examined element before invoking \ michael@0: * the function again. */ \ michael@0: static inline void \ michael@0: name##_HT_FOREACH_FN(struct name *head, \ michael@0: int (*fn)(struct type *, void *), \ michael@0: void *data) \ michael@0: { \ michael@0: unsigned idx; \ michael@0: struct type **p, **nextp, *next; \ michael@0: if (!head->hth_table) \ michael@0: return; \ michael@0: for (idx=0; idx < head->hth_table_length; ++idx) { \ michael@0: p = &head->hth_table[idx]; \ michael@0: while (*p) { \ michael@0: nextp = &(*p)->field.hte_next; \ michael@0: next = *nextp; \ michael@0: if (fn(*p, data)) { \ michael@0: --head->hth_n_entries; \ michael@0: *p = next; \ michael@0: } else { \ michael@0: p = nextp; \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: /* Return a pointer to the first element in the table 'head', under \ michael@0: * an arbitrary order. This order is stable under remove operations, \ michael@0: * but not under others. If the table is empty, return NULL. */ \ michael@0: static inline struct type ** \ michael@0: name##_HT_START(struct name *head) \ michael@0: { \ michael@0: unsigned b = 0; \ michael@0: while (b < head->hth_table_length) { \ michael@0: if (head->hth_table[b]) \ michael@0: return &head->hth_table[b]; \ michael@0: ++b; \ michael@0: } \ michael@0: return NULL; \ michael@0: } \ michael@0: /* Return the next element in 'head' after 'elm', under the arbitrary \ michael@0: * order used by HT_START. If there are no more elements, return \ michael@0: * NULL. If 'elm' is to be removed from the table, you must call \ michael@0: * this function for the next value before you remove it. \ michael@0: */ \ michael@0: static inline struct type ** \ michael@0: name##_HT_NEXT(struct name *head, struct type **elm) \ michael@0: { \ michael@0: if ((*elm)->field.hte_next) { \ michael@0: return &(*elm)->field.hte_next; \ michael@0: } else { \ michael@0: unsigned b = (_HT_ELT_HASH(*elm, field, hashfn) % head->hth_table_length)+1; \ michael@0: while (b < head->hth_table_length) { \ michael@0: if (head->hth_table[b]) \ michael@0: return &head->hth_table[b]; \ michael@0: ++b; \ michael@0: } \ michael@0: return NULL; \ michael@0: } \ michael@0: } \ michael@0: static inline struct type ** \ michael@0: name##_HT_NEXT_RMV(struct name *head, struct type **elm) \ michael@0: { \ michael@0: unsigned h = _HT_ELT_HASH(*elm, field, hashfn); \ michael@0: *elm = (*elm)->field.hte_next; \ michael@0: --head->hth_n_entries; \ michael@0: if (*elm) { \ michael@0: return elm; \ michael@0: } else { \ michael@0: unsigned b = (h % head->hth_table_length)+1; \ michael@0: while (b < head->hth_table_length) { \ michael@0: if (head->hth_table[b]) \ michael@0: return &head->hth_table[b]; \ michael@0: ++b; \ michael@0: } \ michael@0: return NULL; \ michael@0: } \ michael@0: } michael@0: michael@0: #define HT_GENERATE(name, type, field, hashfn, eqfn, load, mallocfn, \ michael@0: reallocfn, freefn) \ michael@0: static unsigned name##_PRIMES[] = { \ michael@0: 53, 97, 193, 389, \ michael@0: 769, 1543, 3079, 6151, \ michael@0: 12289, 24593, 49157, 98317, \ michael@0: 196613, 393241, 786433, 1572869, \ michael@0: 3145739, 6291469, 12582917, 25165843, \ michael@0: 50331653, 100663319, 201326611, 402653189, \ michael@0: 805306457, 1610612741 \ michael@0: }; \ michael@0: static unsigned name##_N_PRIMES = \ michael@0: (unsigned)(sizeof(name##_PRIMES)/sizeof(name##_PRIMES[0])); \ michael@0: /* Expand the internal table of 'head' until it is large enough to \ michael@0: * hold 'size' elements. Return 0 on success, -1 on allocation \ michael@0: * failure. */ \ michael@0: int \ michael@0: name##_HT_GROW(struct name *head, unsigned size) \ michael@0: { \ michael@0: unsigned new_len, new_load_limit; \ michael@0: int prime_idx; \ michael@0: struct type **new_table; \ michael@0: if (head->hth_prime_idx == (int)name##_N_PRIMES - 1) \ michael@0: return 0; \ michael@0: if (head->hth_load_limit > size) \ michael@0: return 0; \ michael@0: prime_idx = head->hth_prime_idx; \ michael@0: do { \ michael@0: new_len = name##_PRIMES[++prime_idx]; \ michael@0: new_load_limit = (unsigned)(load*new_len); \ michael@0: } while (new_load_limit <= size && \ michael@0: prime_idx < (int)name##_N_PRIMES); \ michael@0: if ((new_table = mallocfn(new_len*sizeof(struct type*)))) { \ michael@0: unsigned b; \ michael@0: memset(new_table, 0, new_len*sizeof(struct type*)); \ michael@0: for (b = 0; b < head->hth_table_length; ++b) { \ michael@0: struct type *elm, *next; \ michael@0: unsigned b2; \ michael@0: elm = head->hth_table[b]; \ michael@0: while (elm) { \ michael@0: next = elm->field.hte_next; \ michael@0: b2 = _HT_ELT_HASH(elm, field, hashfn) % new_len; \ michael@0: elm->field.hte_next = new_table[b2]; \ michael@0: new_table[b2] = elm; \ michael@0: elm = next; \ michael@0: } \ michael@0: } \ michael@0: if (head->hth_table) \ michael@0: freefn(head->hth_table); \ michael@0: head->hth_table = new_table; \ michael@0: } else { \ michael@0: unsigned b, b2; \ michael@0: new_table = reallocfn(head->hth_table, new_len*sizeof(struct type*)); \ michael@0: if (!new_table) return -1; \ michael@0: memset(new_table + head->hth_table_length, 0, \ michael@0: (new_len - head->hth_table_length)*sizeof(struct type*)); \ michael@0: for (b=0; b < head->hth_table_length; ++b) { \ michael@0: struct type *e, **pE; \ michael@0: for (pE = &new_table[b], e = *pE; e != NULL; e = *pE) { \ michael@0: b2 = _HT_ELT_HASH(e, field, hashfn) % new_len; \ michael@0: if (b2 == b) { \ michael@0: pE = &e->field.hte_next; \ michael@0: } else { \ michael@0: *pE = e->field.hte_next; \ michael@0: e->field.hte_next = new_table[b2]; \ michael@0: new_table[b2] = e; \ michael@0: } \ michael@0: } \ michael@0: } \ michael@0: head->hth_table = new_table; \ michael@0: } \ michael@0: head->hth_table_length = new_len; \ michael@0: head->hth_prime_idx = prime_idx; \ michael@0: head->hth_load_limit = new_load_limit; \ michael@0: return 0; \ michael@0: } \ michael@0: /* Free all storage held by 'head'. Does not free 'head' itself, or \ michael@0: * individual elements. */ \ michael@0: void \ michael@0: name##_HT_CLEAR(struct name *head) \ michael@0: { \ michael@0: if (head->hth_table) \ michael@0: freefn(head->hth_table); \ michael@0: head->hth_table_length = 0; \ michael@0: name##_HT_INIT(head); \ michael@0: } \ michael@0: /* Debugging helper: return false iff the representation of 'head' is \ michael@0: * internally consistent. */ \ michael@0: int \ michael@0: _##name##_HT_REP_IS_BAD(const struct name *head) \ michael@0: { \ michael@0: unsigned n, i; \ michael@0: struct type *elm; \ michael@0: if (!head->hth_table_length) { \ michael@0: if (!head->hth_table && !head->hth_n_entries && \ michael@0: !head->hth_load_limit && head->hth_prime_idx == -1) \ michael@0: return 0; \ michael@0: else \ michael@0: return 1; \ michael@0: } \ michael@0: if (!head->hth_table || head->hth_prime_idx < 0 || \ michael@0: !head->hth_load_limit) \ michael@0: return 2; \ michael@0: if (head->hth_n_entries > head->hth_load_limit) \ michael@0: return 3; \ michael@0: if (head->hth_table_length != name##_PRIMES[head->hth_prime_idx]) \ michael@0: return 4; \ michael@0: if (head->hth_load_limit != (unsigned)(load*head->hth_table_length)) \ michael@0: return 5; \ michael@0: for (n = i = 0; i < head->hth_table_length; ++i) { \ michael@0: for (elm = head->hth_table[i]; elm; elm = elm->field.hte_next) { \ michael@0: if (_HT_ELT_HASH(elm, field, hashfn) != hashfn(elm)) \ michael@0: return 1000 + i; \ michael@0: if ((_HT_ELT_HASH(elm, field, hashfn) % head->hth_table_length) != i) \ michael@0: return 10000 + i; \ michael@0: ++n; \ michael@0: } \ michael@0: } \ michael@0: if (n != head->hth_n_entries) \ michael@0: return 6; \ michael@0: return 0; \ michael@0: } michael@0: michael@0: /** Implements an over-optimized "find and insert if absent" block; michael@0: * not meant for direct usage by typical code, or usage outside the critical michael@0: * path.*/ michael@0: #define _HT_FIND_OR_INSERT(name, field, hashfn, head, eltype, elm, var, y, n) \ michael@0: { \ michael@0: struct name *_##var##_head = head; \ michael@0: struct eltype **var; \ michael@0: if (!_##var##_head->hth_table || \ michael@0: _##var##_head->hth_n_entries >= _##var##_head->hth_load_limit) \ michael@0: name##_HT_GROW(_##var##_head, _##var##_head->hth_n_entries+1); \ michael@0: _HT_SET_HASH((elm), field, hashfn); \ michael@0: var = _##name##_HT_FIND_P(_##var##_head, (elm)); \ michael@0: if (*var) { \ michael@0: y; \ michael@0: } else { \ michael@0: n; \ michael@0: } \ michael@0: } michael@0: #define _HT_FOI_INSERT(field, head, elm, newent, var) \ michael@0: { \ michael@0: _HT_SET_HASHVAL(newent, field, (elm)->field.hte_hash); \ michael@0: newent->field.hte_next = NULL; \ michael@0: *var = newent; \ michael@0: ++((head)->hth_n_entries); \ michael@0: } michael@0: michael@0: /* michael@0: * Copyright 2005, Nick Mathewson. Implementation logic is adapted from code michael@0: * by Cristopher Clark, retrofit to allow drop-in memory management, and to michael@0: * use the same interface as Niels Provos's tree.h. This is probably still michael@0: * a derived work, so the original license below still applies. michael@0: * michael@0: * Copyright (c) 2002, Christopher Clark michael@0: * All rights reserved. michael@0: * michael@0: * Redistribution and use in source and binary forms, with or without michael@0: * modification, are permitted provided that the following conditions michael@0: * are met: michael@0: * michael@0: * * Redistributions of source code must retain the above copyright michael@0: * notice, this list of conditions and the following disclaimer. michael@0: * michael@0: * * Redistributions in binary form must reproduce the above copyright michael@0: * notice, this list of conditions and the following disclaimer in the michael@0: * documentation and/or other materials provided with the distribution. michael@0: * michael@0: * * Neither the name of the original author; nor the names of any contributors michael@0: * may be used to endorse or promote products derived from this software michael@0: * without specific prior written permission. michael@0: * michael@0: * michael@0: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS michael@0: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT michael@0: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR michael@0: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER michael@0: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, michael@0: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, michael@0: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR michael@0: * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF michael@0: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING michael@0: * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS michael@0: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. michael@0: */ michael@0: michael@0: #endif michael@0: