diff options
Diffstat (limited to 'src/ext/ht.h')
| -rw-r--r-- | src/ext/ht.h | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/src/ext/ht.h b/src/ext/ht.h index 28d1fe49d5..a441d0b685 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_ @@ -203,6 +293,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 +561,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 { \ |