Low-level Trie Manipulation Utilities

The following utilities are used to implement assert and retract, but they can also be used to implement special purpose operations, like backtrackable assert and retract. All the utilities in this section are very low-level and require good understanding of the trie mechanism in XSB.

The module storage described in Volume 1 provides a higher-level and a more convenient interface to the XSB trie-based storage mechanism.

newtrie(-Root)

intern
Root is instantiated to a handle for a new trie.

trie_intern(+Term,+Root,-Leaf,-Flag,-Skel)

intern
Term is the Prolog term to be interned. Root is the handle for a trie. Leaf is the handle for the interned Term in the trie. Flag is 1 if the term is ``old'' (already exists in the trie); it is 0, if the term is newly inserted. Skel represents the collection of all the variables in Term. It has the form ret(V1,V2,...,VN), exactly as in get_calls.

trie_intern(+Term,-Leaf,-Skel)

intern
Interns Term into the default trie. Does not return the new/old flag.

trie_interned(?Term,+Root,?Leaf,-Skel)

intern
This builtin will backtrack through the terms interned into the trie represented by the handle Root if Leaf is a free variable. Otherwise, if Leaf is bound, it will backtrack over the terms in the trie that unify with the term pointed to by Leaf to. Term is the term to be retrieved; it can be either (partially) bound or free. Skel is the collection of all the variables in Term; it has the form ret(V1,...,Vn).

trie_interned(?Term,?Leaf,-Skel)

intern
Similar to trie_interned/4 but uses the default trie.

trie_unintern(+Root,+Leaf)

intern
Uninterns (deletes) a term from the trie indicated by root. This predicate has to be called with care. Uninterning can be done only when the trie from which the term is being uninterned is not being actively accessed.

trie_unintern_nr(+Root,+Leaf)

intern
This is a safe version of trie_unintern/2. The term pointed to by Leaf is marked as deleted, but is not deleted from the trie. This permits an efficient implementation of backtrackable updates.

unmark_uninterned_nr(+Root,+Leaf)

intern
The term pointed to by Leaf should have been previously marked for deletion using trie_unintern_nr/2. This term is then ``unmarked'' (or undeleted) and becomes again a notmal interned term.

reclaim_uninterned_nr(+Root)

intern
Not yet implemented.
Runs through the chain of leaves of the trie Root and deletes the terms that have been marked for deletion by trie_unintern_nr/2. This is a garbage collection step that should be done just before returning to the top level.

delete_trie(+Root)

intern
Deletes all the terms in the trie pointed to by Root.