From 9b6ac0a1ea92b1ec99acdd021087f6d8fdc75f14 Mon Sep 17 00:00:00 2001 From: Garrett D'Amore Date: Tue, 22 Aug 2017 12:11:21 -0700 Subject: Add support for 64-bit ids in idhash. We intend to use this with transports where dynamic "port numbers" might be 32-bits. This would allow us to formulate a 64-bit number representing a conversation, and be able to find that conversation by the 64-bit value. Note that the hashed values are probably not perfectly optimal, as only the low order bits are particularly significant in the hash. We might want to consider XOR'ing in the upper bits to address that. --- tests/idhash.c | 241 +++++++++++++++++++++++++++++++-------------------------- 1 file changed, 133 insertions(+), 108 deletions(-) (limited to 'tests') diff --git a/tests/idhash.c b/tests/idhash.c index 45c0439a..21f66c58 100644 --- a/tests/idhash.c +++ b/tests/idhash.c @@ -15,117 +15,144 @@ Main({ nni_init(); - Test("General ID Hash", - { - int rv; - - Convey("Given an id hash", { - nni_idhash *h = NULL; - - So(nni_idhash_init(&h) == 0); - So(h != NULL); - So(nni_idhash_count(h) == 0); - - Reset({ nni_idhash_fini(h); }); - - Convey("We can insert an element", { - char *five = "five"; - char *four = "four"; - rv = nni_idhash_insert(h, 5, five); - So(nni_idhash_count(h) == 1); - So(rv == 0); - - Convey("And we can find it", { - void *ptr; - rv = nni_idhash_find(h, 5, &ptr); - So(rv == 0); - So(ptr == five); - }); - Convey("We can delete it", { - void *ptr; - rv = nni_idhash_remove(h, 5); - So(rv == 0); - rv = nni_idhash_find(h, 5, &ptr); - So(rv == NNG_ENOENT); - }); - Convey("We can change the value", { - void *ptr; - So(nni_idhash_insert(h, 5, four) == - 0); - So(nni_idhash_count(h) == 1); - So(nni_idhash_find(h, 5, &ptr) == - 0); - So(ptr == four); - }); - Convey("We can insert a hash collision", { - void *ptr; - So(nni_idhash_insert( - h, 13, four) == 0); - So(nni_idhash_count(h) == 2); - So(nni_idhash_find(h, 5, &ptr) == - 0); - So(ptr == five); - So(nni_idhash_find(h, 13, &ptr) == - 0); - So(ptr == four); - Convey("And delete intermediate", { - So(nni_idhash_remove( - h, 5) == 0); - ptr = NULL; - So(nni_idhash_find( - h, 13, &ptr) == 0); - So(ptr == four); - }); - }); - - }); - Convey("We cannot find bogus values", { - void *ptr; - ptr = NULL; - rv = nni_idhash_find(h, 42, &ptr); - So(rv == NNG_ENOENT); - So(ptr == NULL); - }); - }); - }) - - Test("Resize ID Hash", { - int expect[1024]; - int i; - - for (i = 0; i < 1024; i++) { - expect[i] = i; - } - Convey("Given an id hash", { - nni_idhash *h; - - So(nni_idhash_init(&h) == 0); - So(nni_idhash_count(h) == 0); - - Reset({ nni_idhash_fini(h); }); - - Convey("We can insert 1024 items", { - for (i = 0; i < 1024; i++) { - nni_idhash_insert( - h, i, &expect[i]); - } - So(nni_idhash_count(h) == 1024); - - Convey("We can remove them", { - for (i = 0; i < 1024; i++) { - nni_idhash_remove(h, i); - } - So(nni_idhash_count(h) == 0); - }); - }); - }); - }); + atexit(nni_fini); + Test("General ID Hash", { + int rv; + + Convey("Given an id hash", { + nni_idhash *h = NULL; + + So(nni_idhash_init(&h) == 0); + So(h != NULL); + So(nni_idhash_count(h) == 0); + + Reset({ nni_idhash_fini(h); }); + + Convey("We can insert an element", { + char *five = "five"; + char *four = "four"; + rv = nni_idhash_insert(h, 5, five); + So(nni_idhash_count(h) == 1); + So(rv == 0); + + Convey("And we can find it", { + void *ptr; + rv = nni_idhash_find(h, 5, &ptr); + So(rv == 0); + So(ptr == five); + }); + Convey("We can delete it", { + void *ptr; + rv = nni_idhash_remove(h, 5); + So(rv == 0); + rv = nni_idhash_find(h, 5, &ptr); + So(rv == NNG_ENOENT); + }); + Convey("We can change the value", { + void *ptr; + So(nni_idhash_insert(h, 5, four) == 0); + So(nni_idhash_count(h) == 1); + So(nni_idhash_find(h, 5, &ptr) == 0); + So(ptr == four); + }); + Convey("We can insert a hash collision", { + void *ptr; + So(nni_idhash_insert(h, 13, four) == + 0); + So(nni_idhash_count(h) == 2); + So(nni_idhash_find(h, 5, &ptr) == 0); + So(ptr == five); + So(nni_idhash_find(h, 13, &ptr) == 0); + So(ptr == four); + Convey("And delete intermediate", { + So(nni_idhash_remove(h, 5) == + 0); + ptr = NULL; + So(nni_idhash_find( + h, 13, &ptr) == 0); + So(ptr == four); + }); + }); + + }); + Convey("We cannot find bogus values", { + void *ptr; + ptr = NULL; + rv = nni_idhash_find(h, 42, &ptr); + So(rv == NNG_ENOENT); + So(ptr == NULL); + }); + + Convey("Range checks work", { + char *bad = "bad"; + + nni_idhash_set_limits(h, 1, 10, 1); + So(nni_idhash_insert(h, 20, bad) == + NNG_EINVAL); + }); + + Convey("64-bit hash values work", { + char * huge = "huge"; + void * ptr = NULL; + uint64_t hugenum = 0x1234567890ULL; + + nni_idhash_set_limits(h, 1, 1ULL << 63, 1); + So(nni_idhash_insert(h, hugenum, huge) == 0); + So(nni_idhash_find(h, hugenum, &ptr) == 0); + So((char *) ptr == huge); + }); + + Convey("64-bit dynvals work", { + char * huge = "dynhuge"; + void * ptr = NULL; + uint64_t id; + + nni_idhash_set_limits( + h, 1ULL << 32, 1ULL << 63, 1); + So(nni_idhash_alloc(h, &id, huge) == 0); + So(id > 0xffffffff); + So(nni_idhash_find(h, id, &ptr) == 0); + So((char *) ptr == huge); + }); + }); + }); + + Test("Resize ID Hash", { + int expect[1024]; + int i; + + for (i = 0; i < 1024; i++) { + expect[i] = i; + } + Convey("Given an id hash", { + nni_idhash *h; + + So(nni_idhash_init(&h) == 0); + So(nni_idhash_count(h) == 0); + + Reset({ nni_idhash_fini(h); }); + + Convey("We can insert 1024 items", { + for (i = 0; i < 1024; i++) { + nni_idhash_insert(h, i, &expect[i]); + } + So(nni_idhash_count(h) == 1024); + + Convey("We can remove them", { + for (i = 0; i < 1024; i++) { + nni_idhash_remove(h, i); + } + So(nni_idhash_count(h) == 0); + }); + }); + }); + }); Test("Dynamic ID generation", { Convey("Given a small ID hash", { nni_idhash *h; int expect[5]; - uint32_t id; + uint64_t id; int i; So(nni_idhash_init(&h) == 0); Reset({ nni_idhash_fini(h); }); @@ -156,6 +183,4 @@ Main({ }); }); }); - - nni_fini(); }); -- cgit v1.2.3-70-g09d2