commit d5c47f043665d4513bad10e3220dc9b5f088c543 Author: Nick Mathewson <nickm@torproject.org> Date: Thu Aug 11 10:18:51 2016 -0400 Add some how-to documentation for ht.h. Closes #19896 --- src/ext/ht.h | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 90 insertions(+) diff --git a/src/ext/ht.h b/src/ext/ht.h index 1b6cbe6..a441d0b 100644 --- a/src/ext/ht.h +++ b/src/ext/ht.h @@ -5,6 +5,96 @@ /* 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_