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 CONTRIBUTORS ``AS IS'' AND ANY EXPRESS   */
  20 /*  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED         */
  21 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE    */
  22 /*  DISCLAIMED.  IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY         */
  23 /*  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL        */
  24 /*  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS   */
  25 /*  OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)     */
  26 /*  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,       */
  27 /*  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN  */
  28 /*  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE           */
  29 /*  POSSIBILITY OF SUCH DAMAGE.                                               */
  30 /*                                                                            */
  31 /*   Copyright (c) 2006-2008 the Authors                                      */
  32 /*   see AUTHORS and source files for details                                 */
  33 /******************************************************************************/
  34
  35 /*
  36  * Copyright © 2008 Florent Bruneau
  37  */
  38
  39 #ifndef PFIXTOOLS_TRIE_H
  40 #define PFIXTOOLS_TRIE_H
  41
  42 #include "common.h"
  43 #include "array.h"
  44
  45 typedef struct trie_t trie_t;
  46 PARRAY(trie_t)
  47
  48 trie_t *trie_new(void);
  49 void trie_delete(trie_t **trie);
  50
  51 /** Add a string in the trie.
  52  * \ref trie_compile.
  53  */
  54 __attribute__((nonnull(1,2)))
  55 void trie_insert(trie_t *trie, const char *key);
  56
  57 /** Compile the trie.
  58  * A trie must be compiled before lookup is possible. Compiling the trie
  59  * consists in building the tree.
  60  *
  61  * \param memlock if true, the trie is locked into the RAM (mlock).
  62  *
  63  * Usage of a trie:
  64  *   trie_insert(trie, ...);
  65  *   trie_insert(trie, ...);
  66  *   ...
  67  *   trie_insert(trie, ...);
  68  *
  69  *   trie_compile(trie, lock);
  70  *
  71  *   trie_lookup(trie, ...);
  72  *   trie_lookup(trie, ...);
  73  */
  74 __attribute__((nonnull(1)))
  75 void trie_compile(trie_t *trie, bool memlock);
  76
  77 /** Lock the trie into memory.
  78  * \ref trie_unlock
  79  */
  80 __attribute__((nonnull(1)))
  81 void trie_lock(trie_t *trie);
  82
  83 /** Unlock the trie.
  84  * \ref trie_lock
  85  */
  86 __attribute__((nonnull(1)))
  87 void trie_unlock(trie_t *trie);
  88
  89 /** Check if the trie contains \p key.
  90  */
  91 __attribute__((nonnull(1,2)))
  92 bool trie_lookup(const trie_t *trie, const char *key);
  93
  94 /** Check if the trie contains a prefix of \p key.
  95  */
  96 __attribute__((nonnull(1,2)))
  97 bool trie_prefix(const trie_t *trie, const char *key);
  98
  99 /** Show the content of the trie and computes statistics.
 100  */
 101 __attribute__((nonnull(1)))
 102 void trie_inspect(const trie_t *trie, bool show_content);
 103
 104 #endif