axa_trie
contains AXA trie or patricia tree macros, data type definitions and function declarations.
These trie functions use patricia trees to recognize IP addresses and DNS domain names. IP address CIDR blocks or domains, each with a 32-bit value, are added to, looked up in, and deleted from trees. The result of a look-up is an array of 0 or more "hits" or values. Look-ups or reading is done without any locking, except periodically when the readers signal their disinterest in old data.
A successful look-up produces an array of hits for each of the matching CIDR blocks or domains. For example, lookup up "test.example.com" might yield an array consisting of all of the values for the "test.example.com" and "com" nodes in the trie.
IPv4, IPv6, and domain names are.maintained internally in separate three tries that can be viewed as a single trie from the outside.
|
struct | tval_list |
| an array of values for a trie node More...
|
|
struct | hit |
| A single value for a key found in the trie and hints about the source of the data that matched the key. More...
|
|
struct | hitlist_t |
| The successful result of looking up a key is an array of "hits". More...
|
|
union | trie_key_t |
| A trie key. More...
|
|
struct | trie_node |
| The shape of a trie node does not matter except to the trie code and to trie users that manage lists of obsolete nodes for lock-free searching. More...
|
|
struct | trie_roots_t |
| This is the handle on an AXA trie. More...
|
|
|
enum | trie_type_t |
| Each externally visible trie consists of one each of these internal types. More...
|
|
|
bool | axa_tval_delete (trie_roots_t *roots, tval_list_t **tval_listp, tval_t val) |
| Delete a value from an array of trie node values. More...
|
|
void | axa_tval_add (trie_roots_t *roots, tval_list_t **tval_listp, tval_t new, uint padded_len, bool lock_free) |
| Add a value to an array of values. More...
|
|
size_t | axa_trie_to_watch (axa_p_watch_t *w, const trie_node_t *node, trie_type_t node_type, bool is_wild) |
| Convert the key in a trie node to an AXA watch. More...
|
|
void | axa_trie_node_free (trie_node_t *node) |
| Free a trie node including its arrays of values. More...
|
|
void | axa_trie_node_delete (trie_roots_t *roots, trie_type_t trie_type, trie_node_t *node, bool is_wild, tval_t tval) |
| Remove a value from an AXA trie node and then delete the node from the trie if it is empty. More...
|
|
bool | axa_trie_watch_add (axa_emsg_t *emsg, trie_roots_t *roots, trie_node_t **node, const axa_p_watch_t *watch, size_t watch_len, tval_t tval) |
| Add a watch to an AXA trie. More...
|
|
void | axa_trie_search_su (trie_roots_t *roots, const axa_socku_t *su, hitlist_t **hitlistp, axa_nmsg_idx_t field_idx, axa_nmsg_idx_t val_idx) |
| Search an AXA trie for an IP address. More...
|
|
bool | axa_trie_search_dom (axa_emsg_t *emsg, trie_roots_t *roots, const uint8_t *name, uint name_len, hitlist_t **hitlistp, axa_nmsg_idx_t field_idx, axa_nmsg_idx_t val_idx) |
| Search an AXA trie for a DNS domain. More...
|
|
void | axa_tries_free (trie_roots_t *roots) |
| Free an AXA trie. More...
|
|
void | axa_hitlist_append (const trie_roots_t *roots, hitlist_t **hitlistp, const tval_list_t *tval_list, axa_nmsg_idx_t field_idx, axa_nmsg_idx_t val_idx) |
| Append an array of values such as from a trie node to a "hit list". More...
|
|
#define MAX_TRIE_IPV4_PREFIX 64 |
IPv4 keys are one 64-bit word.
#define MAX_TRIE_IPV6_PREFIX 128 |
A single value for a key found in the trie and hints about the source of the data that matched the key.
Each externally visible trie consists of one each of these internal types.
Enumerator |
---|
TRIE_IPV4 |
IPv4 addresses.
|
TRIE_IPV6 |
IPv6 addresses.
|
TRIE_DOM |
DNS domains.
|
Delete a value from an array of trie node values.
- Parameters
-
[in] | roots | handle on the trie. |
[in] | tval_listp | pointer to array from which the value should be removed |
[in] | val | remove the first instance of this value if present |
- Return values
-
true | if an instance of the value was found and removed |
false | if an instance of the value was not found |
Add a value to an array of values.
- Parameters
-
[in] | roots | handle on the trie. |
[in] | tval_listp | pointer to array to which the value should be added |
[in] | new | value to add |
[in] | padded_len | 0 or new length of the array including optional padding for future additions |
[in] | lock_free | true if lock-free searching is supported by the trie. |
Convert the key in a trie node to an AXA watch.
- Parameters
-
[out] | w | existing watch that will be filled. |
[in] | node | convert the key in this AXA trie node |
[in] | node_type | TRIE_IPV4, TRIE_IPV6, or TRIE_DOM |
[in] | is_wild | true if the resulting watch should be for an IP address CIDR block or a DNS wild card |
- Returns
- overall size of the watch
Free a trie node including its arrays of values.
The node must have already been deleted from the trie.
- Parameters
-
Remove a value from an AXA trie node and then delete the node from the trie if it is empty.
- Parameters
-
[in] | roots | handle on the trie |
[in] | trie_type | TRIE_IPV4, TRIE_IPV6, or TRIE_DOM |
[in] | node | to be changed |
[in] | is_wild | true if the value is for a CIDR block or DNS wild card |
[in] | tval | value to be removed |
Add a watch to an AXA trie.
Create a node with a key derived from the watch if the node does not already exist and then add value to the node.
- Parameters
-
[out] | emsg | will contain the reason for a false result. |
[in] | roots | handle on the trie |
[out] | node | will point to the node if not NULL. |
[in] | watch | provides the IP address or domain name for the key |
[in] | watch_len | is the length of the watch. It is usually less than sizeof(axa_p_watch_t) because maximum sized domain names are rare. |
[in] | tval | is the value that will be added to either the "wild" or "exact" array of values in the node. |
- Return values
-
true | if no errors were encountered. Node will be set if not NULL |
false | error was was encountered and emsg will contain the reason |
Search an AXA trie for an IP address.
- Parameters
-
[in] | roots | handle on the trie |
[in] | su | points to an axa_socku_t union containing the IP address |
[in,out] | hitlistp | the array of values in found trie nodes is appended to this array. It is created if *hitlistp is NULL and a value is found. More than one trie node can contribute values; for example a search for 10.2.3.4 can match nodes with keys 10.0.0.0/8, 10.2.0.0/16, and 10.2.3.4. |
[in] | field_idx | is associated with each value added to the hitlistp array to let the caller remember which NMSG value caused each "hit" |
[in] | val_idx | is associated with each value added to the hitlistp array |
Search an AXA trie for a DNS domain.
- Parameters
-
[out] | emsg | will contain the reason for a false result. |
[in] | roots | handle on the trie |
[in] | name | points to the domain in wire format |
[in] | name_len | is the length of the domain |
[in,out] | hitlistp | The array of values in found trie nodes is appended to this array. It is created if *hitlistp is NULL and a value is found. More than one trie node can contribute values; for example a search for www.example.com can match nodes with keys www.example.com and *.com. |
[in] | field_idx | is associated with each value added to the hit list to let the caller remember which NMSG value caused each "hit" |
[in] | val_idx | is associated with each value added to the hitlistp array |
- Return values
-
true | if no errors were encountered. |
false | error such as a bad domain namewas was encountered. emsg will contain the reason. |
Free an AXA trie.
- Parameters
-
[in] | roots | handle on the trie to be destroyed. |
Append an array of values such as from a trie node to a "hit list".
- Parameters
-
[in] | roots | handle on the trie |
[in,out] | hitlistp | is the "hit list" array to which the value list will be added. |
[in] | tval_list | is the list of values |
[in] | field_idx | is associated with each value added to the hit list to let the caller remember which NMSG value caused each "hit". |
[in] | val_idx | is associated with each value added to the hitlistp array |