1 /* $Id: tst.h 6083 2002-12-27 07:24:36Z rra $
3 ** Ternary search trie implementation.
5 ** This implementation is based on the implementation by Peter A. Friend
6 ** (version 1.3), but has been assimilated into INN and modified to use INN
7 ** formatting conventions.
9 ** Copyright (c) 2002, Peter A. Friend
10 ** All rights reserved.
12 ** Redistribution and use in source and binary forms, with or without
13 ** modification, are permitted provided that the following conditions are
16 ** Redistributions of source code must retain the above copyright notice,
17 ** this list of conditions and the following disclaimer.
19 ** Redistributions in binary form must reproduce the above copyright notice,
20 ** this list of conditions and the following disclaimer in the documentation
21 ** and/or other materials provided with the distribution.
23 ** Neither the name of Peter A. Friend nor the names of its contributors may
24 ** be used to endorse or promote products derived from this software without
25 ** specific prior written permission.
27 ** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
28 ** IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
29 ** THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
30 ** PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
31 ** CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
32 ** EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
33 ** PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
34 ** PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
35 ** LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
36 ** NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37 ** SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 #include <inn/defines.h>
47 /* Constants used for return values and options. */
56 /* Opaque data type returned by and used by ternary search trie functions. */
59 /* Allocate a new ternary search trie. width is the number of nodes allocated
60 at a time and should be chosen carefully. One node is required for every
61 character in the tree. If you choose a value that is too small, your
62 application will spend too much time calling malloc and your node space
63 will be too spread out. Too large a value is just a waste of space. */
64 struct tst *tst_init(int width);
66 /* Insert a value into the tree. If the key already exists in the tree,
67 option determiens the behavior. If set to TST_REPLACE, the data for that
68 key is replaced with the new data value and the old value is returned in
69 exist_ptr. Otherwise, TST_DUPLICATE_KEY is returned. If key is zero
70 length, TST_NULL_KEY is returned. If data is NULL, TST_NULL_DATA is
71 returned. On success, TST_OK is returned.
73 The data argument may not be NULL. For a simple existence tree, use the
74 struct tst pointer as the data. */
75 int tst_insert(struct tst *, const unsigned char *key, void *data, int option,
78 /* Search for a key and return the associated data, or NULL if not found. */
79 void *tst_search(struct tst *, const unsigned char *key);
81 /* Delete the given key out of the trie, returning the data that it pointed
82 to. If the key was not found, returns NULL. */
83 void *tst_delete(struct tst *, const unsigned char *key);
85 /* Free the given ternary search trie and all resources it uses. */
86 void tst_cleanup(struct tst *);
88 #endif /* !INN_TST_H */