Dtrie

[Theodus]

This is an implementation of a persistent hash array mapped trie that expands or shrinks to provide efficient memory allocation. Details on the papers that this project is based on can be found at github.com/theodus/dtrie.

Benchmarks:
BenchmarkInsert-4 5000000 547 ns/op 164 B/op 2 allocs/op
BenchmarkGet-4 10000000 250 ns/op 8 B/op 1 allocs/op
BenchmarkRemove-4 10000000 253 ns/op 8 B/op 1 allocs/op
BenchmarkUpdate-4 5000000 383 ns/op 55 B/op 3 allocs/op

[alexandercampbell-wk]

@Theodus looks like there's an issue in one of the tests:

=== RUN TestIterate-2
--- FAIL: TestIterate-2 (0.36s)
    Error Trace:    dtrie_test.go:158
    Error:      Should be true

[Theodus]

Sorry about that. I hadn't tested the original for Go 1.3 compatibility.

[alexandercampbell-wk]

Thanks for including this link!

[dustinhiatt-wf]

+1

[alexandercampbell-wk]

You should be able to simplify this switch with

switch v := value.(type) {
case uint8:
        return uint32(v)
case uint16:
        return uint32(v)
...
}

[alexandercampbell-wk]

One minor stylistic comment. Otherwise, this looks good to me. Thanks for your PR!

[tylertreat-wf]

lgtm

[alexandercampbell-wk]

+1

[dustinhiatt-wf]

+!