dnsjit.lib.trie

NAME

dnsjit.lib.trie - Prefix-tree data structure which addresses values by strings or byte arrays

SYNOPSIS

Binary-key trie with integer values

local trie = require("dnsjit.lib.trie").new("uint64_t", true, 4)
-- assume we have a bunch of dnsjit.core.object.ip packets to process
for _, pkt in pairs(pkts) do
local node = trie:get_ins(pkt.src)
local value = node:get() -- new nodes’ values are initialized to 0
node:set(value + 1)
end
-- iterate over unique IPs and print number of packets received from each
local iter = trie:iter()
local node = iter:node()
local p = require("dnsjit.lib.ip")
while node ˜= nil do
local ip_bytes = node:key()
local npkts = tonumber(node:get())
print(ip.tostring(ip_bytes).." sent "..npkts.." packets")
iter:next()
node = iter:node()
end

String-key trie with cdata values

local trie = require("dnsjit.lib.trie").new("core_object_t*")
local obj1 -- assume this contains cdata of type core_object_t*
local node = trie:get_ins("obj1")
node:set(obj1)
node = trie:get_try("obj1")
assert(node:get() == obj1)

DESCRIPTION

Prefix-tree data structure that stores values indexed by strings or byte arrays, such as IP addresses. Values of size up to sizeof(size_t) can be stored directly, otherwise a pointer must be used.

Functions

Trie.new(ctype, binary, keylen)

Create a new Trie that stores ctype values as data. By default, keys are handled as strings. To use trie with byte arrays, set binary to true. Optionally, keylen may be specified as a default keylen for binary keys. For string keys, their string length is used by default.

Trie:log()

Return the Log object to control logging of this instance or module.

Trie:clear()

Clear the trie instance (make it empty).

Trie:weight()

Return the number of keys in the trie.

Trie:get_try(key, keylen)

Search the trie and return nil of failure.

Trie:get_ins(key, keylen)

Search the trie and insert an empty node (with value set to 0) on failure.

Trie:get_first()

Return the first node (minimum).

Trie:iter()

Return a trie iterator. It is only valid as long as the key-set remains unchanged.

SEE ALSO

dnsjit.lib.trie.node(3),dnsjit.lib.trie.iter(3)

AUTHORS and CONTRIBUTORS

Jerry Lundström (DNS-OARC), Tomáš KÅÞek (CZ.NIC), Petr Å paÄek (ISC)

Maintained by DNS-OARC

https://www.dns-oarc.net/

BUGS

For issues and feature requests please use:

https://github.com/DNS-OARC/dnsjit/issues

For question and help please use:

admin@dns-oarc.net