.\" -*- mode: troff; coding: utf-8 -*-
.\" Automatically generated by Pod::Man 5.01 (Pod::Simple 3.43)
.\"
.\" Standard preamble:
.\" ========================================================================
.de Sp \" Vertical space (when we can't use .PP)
.if t .sp .5v
.if n .sp
..
.de Vb \" Begin verbatim text
.ft CW
.nf
.ne \\$1
..
.de Ve \" End verbatim text
.ft R
.fi
..
.\" \*(C` and \*(C' are quotes in nroff, nothing in troff, for use with C<>.
.ie n \{\
.    ds C` ""
.    ds C' ""
'br\}
.el\{\
.    ds C`
.    ds C'
'br\}
.\"
.\" Escape single quotes in literal strings from groff's Unicode transform.
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\"
.\" If the F register is >0, we'll generate index entries on stderr for
.\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index
.\" entries marked with X<> in POD.  Of course, you'll have to process the
.\" output yourself in some meaningful fashion.
.\"
.\" Avoid warning from groff about undefined register 'F'.
.de IX
..
.nr rF 0
.if \n(.g .if rF .nr rF 1
.if (\n(rF:(\n(.g==0)) \{\
.    if \nF \{\
.        de IX
.        tm Index:\\$1\t\\n%\t"\\$2"
..
.        if !\nF==2 \{\
.            nr % 0
.            nr F 2
.        \}
.    \}
.\}
.rr rF
.\" ========================================================================
.\"
.IX Title "libinn_tst 3"
.TH libinn_tst 3 2024-04-01 "INN 2.7.2" "InterNetNews Documentation"
.\" For nroff, turn off justification.  Always turn off hyphenation; it makes
.\" way too many mistakes in technical documents.
.if n .ad l
.nh
.SH NAME
tst \- Ternary search trie functions
.SH SYNOPSIS
.IX Header "SYNOPSIS"
.Vb 1
\&    #include <inn/tst.h>
\&
\&    enum tst_constants {
\&        TST_OK,
\&        TST_NULL_KEY,
\&        TST_NULL_DATA,
\&        TST_DUPLICATE_KEY,
\&        TST_REPLACE
\&    };
\&
\&    struct tst;
\&
\&    struct tst *tst_init(int node_line_width);
\&
\&    void tst_cleanup(struct tst *tst);
\&
\&    int tst_insert(struct tst *tst, const unsigned char *key,
\&                   void *data, int option, void **exist_ptr);
\&
\&    void *tst_search(struct tst *tst, const unsigned char *key);
\&
\&    void *tst_delete(struct tst *tst, const unsigned char *key);
.Ve
.SH DESCRIPTION
.IX Header "DESCRIPTION"
\&\fBtst_init\fR allocates memory for members of \fIstruct tst\fR, and
allocates the first \fInode_line_width\fR nodes.  A NULL pointer is
returned by \fBtst_init\fR if any part of the memory allocation fails.  On
success, a pointer to a \fIstruct tst\fR is returned.
.PP
The value for \fInode_line_width\fR must be chosen very carefully.  One
node is required for every character in the tree.  If you choose a
value that is too small, your application will spend too much time
calling malloc(3) and your node space will be too spread out.  Too large
a value is just a waste of space.
.PP
\&\fBtst_cleanup\fR frees all memory allocated to nodes, internal structures,
as well as \fItst\fR itself.
.PP
\&\fBtst_insert\fR inserts the string \fIkey\fR into the tree.  Behavior when a
duplicate key is inserted is controlled by \fIoption\fR.  If \fIkey\fR is
already in the tree, then \f(CW\*(C`TST_DUPLICATE_KEY\*(C'\fR is returned, and the
data pointer for the existing key is placed in \fIexist_ptr\fR.  If
\&\fIoption\fR is set to \f(CW\*(C`TST_REPLACE\*(C'\fR, then the existing data pointer for
the existing key is replaced by \fIdata\fR.  Note that the old data
pointer will still be placed in \fIexist_ptr\fR.
.PP
If a duplicate key is encountered and \fIoption\fR is not set to
\&\f(CW\*(C`TST_REPLACE\*(C'\fR, then \f(CW\*(C`TST_DUPLICATE_KEY\*(C'\fR is returned.  If \fIkey\fR is
zero length, then \f(CW\*(C`TST_NULL_KEY\*(C'\fR is returned.  A successful insert or
replace returns \f(CW\*(C`TST_OK\*(C'\fR.  A return value of \f(CW\*(C`TST_ERROR\*(C'\fR indicates
that a memory allocation error occurred while trying to grow the node
free.
.PP
Note that the \fIdata\fR argument must never be \f(CW\*(C`NULL\*(C'\fR.  If it is, then
calls to \fBtst_search\fR will fail for a key that exists because the
data value was set to \f(CW\*(C`NULL\*(C'\fR, which is what \fBtst_search\fR returns.  If
you just want a simple existence tree, use the \fBtst\fR pointer as the
data pointer.
.PP
\&\fBtst_search\fR finds the string \fIkey\fR in the tree if it exists and
returns the data pointer associated with that key.
.PP
If \fIkey\fR is not found then \f(CW\*(C`NULL\*(C'\fR is returned, otherwise the data pointer
associated with \fIkey\fR is returned.
.PP
\&\fBtst_delete\fR deletes the string \fIkey\fR from the tree if it exists and
returns the data pointer associated with that key.
.PP
If \fIkey\fR is not found, then \f(CW\*(C`NULL\*(C'\fR is returned, otherwise the data
pointer associated with \fIkey\fR is returned.
.SH HISTORY
.IX Header "HISTORY"
Converted to POD from Peter A.\ Friend's ternary search trie
documentation by Alex Kiernan <alex.kiernan@thus.net> for
InterNetNews\ 2.4.0.
.SH "SEE ALSO"
.IX Header "SEE ALSO"
libinn(3).