---
name: "dnsjit.lib.trie"
section: "3"
platform: "linux"
package: "dnsjit"
version: "1.5.0-2"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/dnsjit.lib.trie"
---

# dnsjit.lib.trie(3)

Prefix-tree data structure which addresses values by strings or byte arrays

## 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.node/3.md),[**dnsjit.lib.trie.iter**(3)](/dnsjit.lib.trie.iter/3.md)

## 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*