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
  41 typedef struct trie_t trie_t;
  42 PARRAY(trie_t)
  43
  44 trie_t *trie_new(void);
  45 void trie_delete(trie_t **trie);
  46
  47 /** Add a string in the trie.
  48  * \ref trie_compile.
  49  */
  50 __attribute__((nonnull(1,2)))
  51 void trie_insert(trie_t *trie, const char *key);
  52
  53 /** Compile the trie.
  54  * A trie must be compiled before lookup is possible. Compiling the trie
  55  * consists in building the tree.
  56  *
  57  * \param memlock if true, the trie is locked into the RAM (mlock).
  58  *
  59  * Usage of a trie:
  60  *   trie_insert(trie, ...);
  61  *   trie_insert(trie, ...);
  62  *   ...
  63  *   trie_insert(trie, ...);
  64  *
  65  *   trie_compile(trie, lock);
  66  *
  67  *   trie_lookup(trie, ...);
  68  *   trie_lookup(trie, ...);
  69  */
  70 __attribute__((nonnull(1)))
  71 void trie_compile(trie_t *trie, bool memlock);
  72
  73 /** Lock the trie into memory.
  74  * \ref trie_unlock
  75  */
  76 __attribute__((nonnull(1)))
  77 void trie_lock(trie_t *trie);
  78
  79 /** Unlock the trie.
  80  * \ref trie_lock
  81  */
  82 __attribute__((nonnull(1)))
  83 void trie_unlock(trie_t *trie);
  84
  85 /** Check if the trie contains \p key.
  86  */
  87 __attribute__((nonnull(1,2)))
  88 bool trie_lookup(const trie_t *trie, const char *key);
  89
  90 /** Check if the trie contains a prefix of \p key.
  91  */
  92 __attribute__((nonnull(1,2)))
  93 bool trie_prefix(const trie_t *trie, const char *key);
  94
  95 /** Show the content of the trie and computes statistics.
  96  */
  97 __attribute__((nonnull(1)))
  98 void trie_inspect(const trie_t *trie, bool show_content);
  99
 100 #endif