common/trie.h

   1 /******************************************************************************/
   2 /*          pfixtools: a collection of postfix related tools                  */
   3 /*          ~~~~~~~~~                                                         */
   4 /*  ________________________________________________________________________  */
   5 /*                                                                            */
   6 /*  Redistribution and use in source and binary forms, with or without        */
   7 /*  modification, are permitted provided that the following conditions        */
   8 /*  are met:                                                                  */
   9 /*                                                                            */
  10 /*  1. Redistributions of source code must retain the above copyright         */
  11 /*     notice, this list of conditions and the following disclaimer.          */
  12 /*  2. Redistributions in binary form must reproduce the above copyright      */
  13 /*     notice, this list of conditions and the following disclaimer in the    */
  14 /*     documentation and/or other materials provided with the distribution.   */
  15 /*  3. The names of its contributors may not be used to endorse or promote    */
  16 /*     products derived from this software without specific prior written     */
  17 /*     permission.                                                            */
  18 /*                                                                            */
  19 /*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
  20 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
  21 /*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
  22 /*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
  23 /*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
  24 /*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
  25 /*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
  26 /*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
  27 /*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
  28 /*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
  29 /*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
  30 /******************************************************************************/
  31
  32 /*
  33  * Copyright © 2008 Florent Bruneau
  34  */
  35
  36 #ifndef PFIXTOOLS_TRIE_H
  37 #define PFIXTOOLS_TRIE_H
  38
  39 #include "common.h"
  40 #include "array.h"
  41
  42 typedef struct trie_t trie_t;
  43 PARRAY(trie_t)
  44
  45 trie_t *trie_new(void);
  46 void trie_delete(trie_t **trie);
  47
  48 /** Add a string in the trie.
  49  * \ref trie_compile.
  50  */
  51 __attribute__((nonnull(1,2)))
  52 void trie_insert(trie_t *trie, const char *key);
  53
  54 /** Compile the trie.
  55  * A trie must be compiled before lookup is possible. Compiling the trie
  56  * consists in building the tree.
  57  *
  58  * \param memlock if true, the trie is locked into the RAM (mlock).
  59  *
  60  * Usage of a trie:
  61  *   trie_insert(trie, ...);
  62  *   trie_insert(trie, ...);
  63  *   ...
  64  *   trie_insert(trie, ...);
  65  *
  66  *   trie_compile(trie, lock);
  67  *
  68  *   trie_lookup(trie, ...);
  69  *   trie_lookup(trie, ...);
  70  */
  71 __attribute__((nonnull(1)))
  72 void trie_compile(trie_t *trie, bool memlock);
  73
  74 /** Lock the trie into memory.
  75  * \ref trie_unlock
  76  */
  77 __attribute__((nonnull(1)))
  78 void trie_lock(trie_t *trie);
  79
  80 /** Unlock the trie.
  81  * \ref trie_lock
  82  */
  83 __attribute__((nonnull(1)))
  84 void trie_unlock(trie_t *trie);
  85
  86 /** Check if the trie contains \p key.
  87  */
  88 __attribute__((nonnull(1,2)))
  89 bool trie_lookup(const trie_t *trie, const char *key);
  90
  91 /** Check if the trie contains a prefix of \p key.
  92  */
  93 __attribute__((nonnull(1,2)))
  94 bool trie_prefix(const trie_t *trie, const char *key);
  95
  96 /** Show the content of the trie and computes statistics.
  97  */
  98 __attribute__((nonnull(1)))
  99 void trie_inspect(const trie_t *trie, bool show_content);
 100
 101 #endif