Lunatik
Lua API · Data

setModule

A set is a compact, immutable set of strings, queried by binary search.

It stores many short strings as a sorted blob of key bytes plus a uint32 offset array, with no per-key allocation, so it costs about length + 4 bytes per key, and 4 more for a label, instead of the hash node and slab rounding a Lua or rcu table pays per key. Built once, it is then read-only: lookups take no lock and allocate nothing, safe from softirq.

set:has tests exact membership: a single binary search, O(log n). set:match walks a key by . and returns the label of the longest member the key ends in at a level (0 when nothing matches); one binary search per .-separated level, O(d log n) for a d-level key.

See also

Class set

set:has (s) Returns whether a string is in the set.
set:match (s) Returns the label of the longest member s ends in at a level, or 0.

set

fromdata (d, layout) Builds a set over the bytes of a data, without copying them.
new (t) Builds a set from a list of strings or from a map of strings to labels.

Class set in detail

A built set, returned by set.new, set.fromdata or set.image.load; #s is its number of members.
set:has (s)
Returns whether a string is in the set.

Parameters

  • s string the string to test.

Returns

    boolean whether s is in the set.
set:match (s)
Returns the label of the longest member s ends in at a level, or 0.

Walks s by . ("a.b.c" tries "a.b.c", "b.c", "c") and stops at the first level that is a member, so the most specific member decides. This roots the hierarchy on the right.

Parameters

  • s string the string to look up.

Returns

    integer the label of the longest matching level, or 0.

set in detail

fromdata (d, layout)
Builds a set over the bytes of a data, without copying them.

layout holds byte offsets into d, counted from 0: n, the number of members; offsets, where n + 1 u32 offsets sit, member i being bytes off[i] up to off[i+1] of the members; labels, where n u32 labels sit, absent for a list, whose members carry 1; and blob, where the members' bytes begin. The u32 are little-endian and their offsets multiples of 4. Every array is checked to fit in d, and a lookup reads a member only when its offsets keep it inside the bytes from blob on, so no layout or content makes it read outside the data. That is the whole check: members out of order or repeated, offsets that decrease or reach past the data and a label of 0 make the lookups answer wrong, the error of whoever wrote the bytes. d must own its memory: the set makes it read only for good, a refused layout included, and holds it for as long as the set lives, so the bytes a set reads neither move nor change, and the set is read without a lock from any runtime it is passed to. set.image builds this form from a set image.

Parameters

  • d data the data that holds the members.
  • layout table where the set’s arrays sit in d.

Returns

    set the built set.

Raises

external memory for a data that views memory it does not own, as skb:data() does; out of bounds for a layout field outside the data or an array that does not fit in it or whose offset is not a multiple of 4; or on allocation failure.
new (t)
Builds a set from a list of strings or from a map of strings to labels.

A label is an integer in [1, 232), which match returns; the members of a list carry 1, and a list’s duplicates count once. It allocates, so call it where it can sleep (a process-context runtime, or any runtime’s load).

Parameters

  • t table the members, as a list of strings or as a map from each member to its label.

Returns

    set the built set.

Raises

Error on a non-string member, a label outside [1, 232), a list and a map mixed, if the members exceed 4 GiB, or on allocation failure.

Usage

local allowed = set.new({ "alpha", "bravo" })
local policy = set.new({ ["go.com"] = 7, ["abcnews.go.com"] = 9 })
local label = policy:match("www.abcnews.go.com")  --> 9, the longest member decides