Hello Kernel people, et. al.,
I've been researching range querying over multi-dimensional keys,
(mainly related to its application in searching for ("delta","epsilon")
tuple timestamp range queries over a database of timers, events.)
This led me to the current key,value pair lookup code in the NetBSD
source so far. Some of what I found seems fragmented, sometimes
specialised, partially documented, possibly in disrepair.
Although daunting, it seems to be a worthy task to consolidate and
document the bits that need some attention/love.
I'm including a set of sources that I have identified - I'm sure I've
left some out. If so, please point me at them.
Network route matching related (key would be IP/prefix address):
- src/sys/net/radix.[ch]
- src/sbin/routed/radix.c
- src/sys/net/npf/lpm.[ch]
string matching:
Focussed on parallelism:
- src/sys/sys/thmap.h
- src/sys/kern/subr_thmap.c
Generic:
N-way Trie:
- src/common/lib/libc/gen/ptree.c
Radix Tr[ie]e
- src/common/lib/libc/gen/radixtree.c
RB Tree:
- src/common/lib/libc/gen/rb.c
Radix Priority Search Tree:
- src/common/lib/libc/gen/rpst.c
I'd like to understand if anyone here has looked
organising/consolidating these, and updating them to the state of the
art anytime recently, and if anyone has suggestions for new additions.
I'd also appreciate pointers to design patterns around a generalised
interface for these, that wouldn't take away from them.
Many Thanks for any comments.
--
Math/(~cherry)
