commit cfab9f0755e3f7f0b49879ed9771fd2d325051a2 Author: Nick Mathewson nickm@torproject.org Date: Mon Dec 3 13:10:33 2012 -0500

Add a data-invariant linear-search map structure

I'm going to use this for looking op keys server-side for ntor. --- src/common/di_ops.c | 72 ++++++++++++++++++++++++++++++++++++++++++++ src/common/di_ops.h | 14 ++++++++ src/test/test_containers.c | 45 +++++++++++++++++++++++++++ 3 files changed, 131 insertions(+), 0 deletions(-)

diff --git a/src/common/di_ops.c b/src/common/di_ops.c index 418d6e3..b73a3cc 100644 --- a/src/common/di_ops.c +++ b/src/common/di_ops.c @@ -8,6 +8,8 @@

#include "orconfig.h" #include "di_ops.h" +#include "torlog.h" +#include "util.h"

/** * Timing-safe version of memcmp. As memcmp, compare the <b>sz</b> bytes at @@ -131,3 +133,73 @@ tor_memeq(const void *a, const void *b, size_t sz) return 1 & ((any_difference - 1) >> 8); }

+/* Implement di_digest256_map_t as a linked list of entries. */ +struct di_digest256_map_t { + struct di_digest256_map_t *next; + uint8_t key[32]; + void *val; +}; + +/** Release all storage held in <b>map</b>, calling free_fn on each value + * as we go. */ +void +dimap_free(di_digest256_map_t *map, dimap_free_fn free_fn) +{ + while (map) { + di_digest256_map_t *victim = map; + map = map->next; + if (free_fn) + free_fn(victim->val); + tor_free(victim); + } +} + +/** Adjust the map at *<b>map</b>, adding an entry for <b>key</b> -> + * <b>val</b>, where <b>key</b> is a DIGEST256_LEN-byte key. + * + * The caller MUST NOT add a key that already appears in the map. + */ +void +dimap_add_entry(di_digest256_map_t **map, + const uint8_t *key, void *val) +{ + di_digest256_map_t *new_ent; + { + void *old_val = dimap_search(*map, key, NULL); + tor_assert(! old_val); + tor_assert(val); + } + new_ent = tor_malloc_zero(sizeof(di_digest256_map_t)); + new_ent->next = *map; + memcpy(new_ent->key, key, 32); + new_ent->val = val; + *map = new_ent; +} + +/** Search the map at <b>map</b> for an entry whose key is <b>key</b> (a + * DIGEST256_LEN-byte key) returning the corresponding value if we found one, + * and returning <b>dflt_val</b> if the key wasn't found. + * + * This operation takes an amount of time dependent only on the length of + * <b>map</b>, not on the position or presence of <b>key</b> within <b>map</b>. + */ +void * +dimap_search(const di_digest256_map_t *map, const uint8_t *key, + void *dflt_val) +{ + uintptr_t result = (uintptr_t)dflt_val; + + while (map) { + uintptr_t r = (uintptr_t) tor_memeq(map->key, key, 32); + r -= 1; /* Now r is (uintptr_t)-1 if memeq returned false, and + * 0 if memeq returned true. */ + + result &= r; + result |= ((uintptr_t)(map->val)) & ~r; + + map = map->next; + } + + return (void *)result; +} + diff --git a/src/common/di_ops.h b/src/common/di_ops.h index 8f0bb69..a86f56c 100644 --- a/src/common/di_ops.h +++ b/src/common/di_ops.h @@ -27,5 +27,19 @@ int tor_memeq(const void *a, const void *b, size_t sz); #define fast_memeq(a,b,c) (0==memcmp((a),(b),(c))) #define fast_memneq(a,b,c) (0!=memcmp((a),(b),(c)))

+/** A type for a map from DIGEST256_LEN-byte blobs to void*, such that + * data lookups take an amount of time proportional only to the size + * of the map, and not to the position or presence of the item in the map. + * + * Not efficient for large maps! */ +typedef struct di_digest256_map_t di_digest256_map_t; +typedef void (*dimap_free_fn)(void *); + +void dimap_free(di_digest256_map_t *map, dimap_free_fn free_fn); +void dimap_add_entry(di_digest256_map_t **map, + const uint8_t *key, void *val); +void *dimap_search(const di_digest256_map_t *map, const uint8_t *key, + void *dflt_val); + #endif

diff --git a/src/test/test_containers.c b/src/test/test_containers.c index 399ef8e..b41b3c6 100644 --- a/src/test/test_containers.c +++ b/src/test/test_containers.c @@ -782,6 +782,50 @@ test_container_order_functions(void) ; }

+static void +test_di_map(void *arg) +{ + di_digest256_map_t *map = NULL; + const uint8_t key1[] = "In view of the fact that it was "; + const uint8_t key2[] = "superficially convincing, being "; + const uint8_t key3[] = "properly enciphered in a one-tim"; + const uint8_t key4[] = "e cipher scheduled for use today"; + char *v1 = tor_strdup(", it came close to causing a disaster..."); + char *v2 = tor_strdup("I regret to have to advise you that the mission"); + char *v3 = tor_strdup("was actually initiated..."); + /* -- John Brunner, _The Shockwave Rider_ */ + + (void)arg; + + /* Try searching on an empty map. */ + tt_ptr_op(NULL, ==, dimap_search(map, key1, NULL)); + tt_ptr_op(NULL, ==, dimap_search(map, key2, NULL)); + tt_ptr_op(v3, ==, dimap_search(map, key2, v3)); + dimap_free(map, NULL); + map = NULL; + + /* Add a single entry. */ + dimap_add_entry(&map, key1, v1); + tt_ptr_op(NULL, ==, dimap_search(map, key2, NULL)); + tt_ptr_op(v3, ==, dimap_search(map, key2, v3)); + tt_ptr_op(v1, ==, dimap_search(map, key1, NULL)); + + /* Now try it with three entries in the map. */ + dimap_add_entry(&map, key2, v2); + dimap_add_entry(&map, key3, v3); + tt_ptr_op(v1, ==, dimap_search(map, key1, NULL)); + tt_ptr_op(v2, ==, dimap_search(map, key2, NULL)); + tt_ptr_op(v3, ==, dimap_search(map, key3, NULL)); + tt_ptr_op(NULL, ==, dimap_search(map, key4, NULL)); + tt_ptr_op(v1, ==, dimap_search(map, key4, v1)); + + done: + tor_free(v1); + tor_free(v2); + tor_free(v3); + dimap_free(map, NULL); +} + #define CONTAINER_LEGACY(name) \ { #name, legacy_test_helper, 0, &legacy_setup, test_container_ ## name }

@@ -796,6 +840,7 @@ struct testcase_t container_tests[] = { CONTAINER_LEGACY(strmap), CONTAINER_LEGACY(pqueue), CONTAINER_LEGACY(order_functions), + { "di_map", test_di_map, 0, NULL, NULL }, END_OF_TESTCASES };