diff options
Diffstat (limited to 'src/ext/ht.h')
| -rw-r--r-- | src/ext/ht.h | 96 |
1 files changed, 95 insertions, 1 deletions
diff --git a/src/ext/ht.h b/src/ext/ht.h index 28d1fe49d5..99da773faf 100644 --- a/src/ext/ht.h +++ b/src/ext/ht.h @@ -1,10 +1,100 @@ /* Copyright (c) 2002, Christopher Clark. * Copyright (c) 2005-2006, Nick Mathewson. - * Copyright (c) 2007-2015, The Tor Project, Inc. */ + * Copyright (c) 2007-2017, The Tor Project, Inc. */ /* See license at end. */ /* Based on ideas by Christopher Clark and interfaces from Niels Provos. */ +/* + These macros provide an intrustive implementation for a typesafe chaining + hash table, loosely based on the BSD tree.h and queue.h macros. Here's + how to use them. + + First, pick a the structure that you'll be storing in the hashtable. Let's + say that's "struct dinosaur". To this structure, you add an HT_ENTRY() + member, as such: + + struct dinosaur { + HT_ENTRY(dinosaur) node; // The name inside the () must match the + // struct. + + // These are just fields from the dinosaur structure... + long dinosaur_id; + char *name; + long age; + int is_ornithischian; + int is_herbivorous; + }; + + You can declare the hashtable itself as: + + HT_HEAD(dinosaur_ht, dinosaur); + + This declares a new 'struct dinosaur_ht' type. + + Now you need to declare two functions to help implement the hashtable: one + compares two dinosaurs for equality, and one computes the hash of a + dinosaur. Let's say that two dinosaurs are equal if they have the same ID + and name. + + int + dinosaurs_equal(const struct dinosaur *d1, const struct dinosaur *d2) + { + return d1->dinosaur_id == d2->dinosaur_id && + 0 == strcmp(d1->name, d2->name); + } + + unsigned + dinosaur_hash(const struct dinosaur *d) + { + // This is a very bad hash function. Use siphash24g instead. + return (d->dinosaur_id + d->name[0] ) * 1337 + d->name[1] * 1337; + } + + Now you'll need to declare the functions that manipulate the hash table. + To do this, you put this declaration either in a header file, or inside + a regular module, depending on what visibility you want. + + HT_PROTOTYPE(dinosaur_ht, // The name of the hashtable struct + dinosaur, // The name of the element struct, + node, // The name of HT_ENTRY member + dinosaur_hash, dinosaurs_equal); + + Later, inside a C function, you use this macro to declare the hashtable + functions. + + HT_GENERATE2(dinosaur_ht, dinosaur, node, dinosaur_hash, dinosaurs_equal, + 0.6, tor_reallocarray, tor_free_); + + Note the use of tor_free_, not tor_free. The 0.6 is magic. + + Now you can use the hashtable! You can initialize one with + + struct dinosaur_ht my_dinos = HT_INITIALIZER(); + + Or create one in core with + + struct dinosaur_ht *dinos = tor_malloc(sizeof(dinosaur_ht)); + HT_INIT(dinosaur_ht, dinos); + + To the hashtable, you use the HT_FOO(dinosaur_ht, ...) macros. For + example, to put new_dino into dinos, you say: + + HT_REPLACE(dinosaur_ht, dinos, new_dino); + + If you're searching for an element, you need to use a dummy 'key' element in + the search. For example. + + struct dinosaur dino_key; + dino_key.dinosaur_id = 12345; + dino_key.name = tor_strdup("Atrociraptor"); + + struct dinosaur *found = HT_FIND(dinosaurs_ht, dinos, &dino_key); + + Have fun with your hash table! + + */ + #ifndef HT_H_INCLUDED_ #define HT_H_INCLUDED_ @@ -60,6 +150,8 @@ #define HT_CLEAR(name, head) name##_HT_CLEAR(head) #define HT_INIT(name, head) name##_HT_INIT(head) #define HT_REP_IS_BAD_(name, head) name##_HT_REP_IS_BAD_(head) +#define HT_FOREACH_FN(name, head, fn, data) \ + name##_HT_FOREACH_FN((head), (fn), (data)) /* Helper: */ static inline unsigned ht_improve_hash(unsigned h) @@ -203,6 +295,7 @@ ht_string_hash(const char *s) name##_HT_GROW(head, head->hth_n_entries+1); \ HT_SET_HASH_(elm, field, hashfn); \ p = name##_HT_FIND_P_(head, elm); \ + HT_ASSERT_(p != NULL); /* this holds because we called HT_GROW */ \ r = *p; \ *p = elm; \ if (r && (r!=elm)) { \ @@ -470,6 +563,7 @@ ht_string_hash(const char *s) name##_HT_GROW(var##_head_, var##_head_->hth_n_entries+1); \ HT_SET_HASH_((elm), field, hashfn); \ var = name##_HT_FIND_P_(var##_head_, (elm)); \ + HT_ASSERT_(var); /* Holds because we called HT_GROW */ \ if (*var) { \ y; \ } else { \ |