include/inn/tst.h

   1 /*  $Id: tst.h 6083 2002-12-27 07:24:36Z rra $
   2 **
   3 **  Ternary search trie implementation.
   4 **
   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.
   8 **
   9 **  Copyright (c) 2002, Peter A. Friend
  10 **  All rights reserved.
  11 **
  12 **  Redistribution and use in source and binary forms, with or without
  13 **  modification, are permitted provided that the following conditions are
  14 **  met:
  15 **
  16 **  Redistributions of source code must retain the above copyright notice,
  17 **  this list of conditions and the following disclaimer.
  18 **
  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.
  22 **
  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.
  26 **
  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.
  38 */
  39
  40 #ifndef INN_TST_H
  41 #define INN_TST_H 1
  42
  43 #include <inn/defines.h>
  44
  45 BEGIN_DECLS
  46
  47 /* Constants used for return values and options. */
  48 enum tst_constants {
  49     TST_OK,
  50     TST_NULL_KEY,
  51     TST_NULL_DATA,
  52     TST_DUPLICATE_KEY,
  53     TST_REPLACE
  54 };
  55
  56 /* Opaque data type returned by and used by ternary search trie functions. */
  57 struct tst;
  58
  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);
  65
  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.
  72
  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,
  76                void **exist_ptr);
  77
  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);
  80
  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);
  84
  85 /* Free the given ternary search trie and all resources it uses. */
  86 void tst_cleanup(struct tst *);
  87
  88 #endif /* !INN_TST_H */