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