Tries (also called digital tree, radix tree or
prefix tree maintain a mapping between a variant of a term (see
=@=/2) and a value. They
have been introduced in SWI-Prolog 7.3.21 as part of the implementation
of tabling. The current implementation is rather immature. In
particular, the following limitations currently apply:
- Tries are not thread-safe.
- Tries should not be modified while non-deterministic predicates such
as trie_gen/3
are running on the trie.
- Terms cannot have attributed variables.
- Terms cannot be cyclic. Possibly this will not change
because cyclic terms can only be supported after creating a canonical
form of the term.
We give the definition of these predicates for reference and
debugging tabled predicates. Future versions are likely to get a more
stable and safer implementation. The API to tries should not be
considered stable.
- trie_new(-Trie)
- Create a new trie and unify Trie with a handle to the trie.
The trie handle is a blob. Tries are subject to atom garbage
collection.
- trie_destroy(+Trie)
- Destroy Trie. This removes all nodes from the trie and causes
further access to Trie to raise an existence_error exception.
The handle itself is reclaimed by atom garbage collection.
- [semidet]is_trie(@Trie)
- True when Trie is a trie object. See also current_trie/1.
- [nondet]current_trie(-Trie)
- True if Trie is a currently existing trie. As this enumerates
and then filters all known atoms this predicate is slow and should only
be used for debugging purposes. See also is_trie/1.
- trie_insert(+Trie,
+Key)
- Insert the term Key into Trie. If Key
is already part of Trie the predicates fails
silently. This is the same as trie_insert/3,
but using a fixed reserved Value.
- trie_insert(+Trie,
+Key, +Value)
- Insert the term Key into Trie and associate it
with
Value. Value can be any term. If Key-Value
is already part of Trie, the predicates fails
silently. If Key is in Trie associated with a
different value, a
permission_error is raised.
- trie_update(+Trie,
+Key, +Value)
- As trie_insert/3,
but if Key is in Trie, its associated value is updated.
- trie_insert(+Trie,
+Term, +Value, -Handle)
- As trie_insert/3,
returning a handle to the trie node. This predicate is currently unsafe
as Handle is an integer used to encode a pointer. It was used
to implement a pure Prolog version of the
library(tabling)
library.
- trie_delete(+Trie,
+Key, ?Value)
- Delete Key from Trie if the value associated with Key
unifies with Value.
- trie_lookup(+Trie,
+Key, -Value)
- True if the term Key is in Trie and associated
with
Value.
- trie_term(+Handle,
-Term)
- True when Term is a copy of the term associated with Handle.
The result is undefined (including crashes) if Handle is not
a handle returned by trie_insert_new/3
or the node has been removed afterwards.
- [nondet]trie_gen(+Trie,
?Key)
- True when Key is a member of Trie. See also
trie_gen_compiled/2.
- [nondet]trie_gen(+Trie,
?Key, -Value)
- True when Key is associated with Value in Trie.
Backtracking retrieves all pairs. Currently scans the entire trie, even
if Key is partly known. Currently unsafe if Trie
is modified while the values are being enumerated. See also
trie_gen_compiled/3.
- [nondet]trie_gen_compiled(+Trie,
?Key)
- [nondet]trie_gen_compiled(+Trie,
?Key, -Value)
- Similar to trie_gen/3,
but uses a compiled representation of
Trie. The compiled representation is created lazily and
manipulations of the trie (insert, delete) invalidate the current
compiled representation. The compiled representation generates answers
faster and, as it runs on a snapshot of the trie, is immune to
concurrent modifications of the trie. This predicate is used to generate
answers from answer tries as used for tabled execution. See section
7.
- [nondet]trie_property(?Trie,
?Property)
- True if Trie exists with Property. Intended for
debugging and statistical purposes. Retrieving some of these properties
visit all nodes of the trie. Defined properties are
- value_count(-Count)
- Number of key-value pairs in the trie.
- node_count(-Count)
- Number of nodes in the trie.
- size(-Bytes)
- Required storage space of the trie.
- compiled_size(-Bytes)
- Required storage space for the compiled representation as used by trie_gen_compiled/2,3.
- hashed(-Count)
- Number of nodes that use a hashed index to its children.
- lookup_count(-Count)
- Number of trie_lookup/3
calls (only when compiled with
O_TRIE_STATS).
- gen_call_count(-Count)
- Number of trie_gen/3
calls (only when compiled with
O_TRIE_STATS).
- wait(-Count)
- Number of times a thread waited on this trie for another thread to
complete it (shared tabling, only when compiled with
O_TRIE_STATS).
- deadlock(-Count)
- Number of times this trie was part of a deadlock and its completion was
abandoned (shared tabling, only when compiled with
O_TRIE_STATS).
In addition, a number of additional properties are defined on
answer tries.
- invalidated(-Count)
- Number of times the trie was invalidated (incremental tabling).
- reevaluated(-Count)
- Number of times the trie was re-evaluated (incremental tabling).
- idg_affected_count(-Count)
- Number of answer tries affected by this one (incremental tabling).
- idg_dependent_count(-Count)
- Number of answer tries this one depends on (incremental tabling).
- idg_size(-Bytes)
- Number of bytes in the IDG node representation.
