[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor/master] Add a data-invariant linear-search map structure
commit cfab9f0755e3f7f0b49879ed9771fd2d325051a2
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
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
};
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits