lib/libTrie/Trie.h

   1 /*
   2  * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #ifndef   LIBTRIE_SQUID_H
  10 #define   LIBTRIE_SQUID_H
  11
  12 #include "TrieNode.h"
  13 #if HAVE_SYS_TYPES_H
  14 #include <sys/types.h>
  15 #endif
  16
  17 class TrieCharTransform;
  18
  19 /* TODO: parameterize this to be more generic -
  20 * i.e. M-ary internal node sizes etc
  21 */
  22
  23 class Trie
  24 {
  25
  26 public:
  27     Trie(TrieCharTransform *aTransform = 0);
  28     ~Trie();
  29     Trie (Trie const &);
  30     Trie &operator= (Trie const &);
  31
  32     /* Find an exact match in the trie.
  33     * If found, return the private data.
  34     * If not found, return NULL.
  35     */
  36     inline void *find (char const *, size_t);
  37     /* find any element of the trie in the buffer from the
  38     * beginning thereof
  39     */
  40     inline void *findPrefix (char const *, size_t);
  41
  42     /* Add a string.
  43     * returns false if the string is already
  44     * present or cannot be added.
  45     */
  46
  47     bool add(char const *, size_t, void *);
  48
  49 private:
  50     TrieNode *head;
  51
  52     /* transfor each 8 bits in the element */
  53     TrieCharTransform *transform;
  54 };
  55
  56 void *
  57 Trie::find (char const *aString, size_t theLength)
  58 {
  59     if (head)
  60         return head->find (aString, theLength, transform, false);
  61
  62     return NULL;
  63 }
  64
  65 void *
  66 Trie::findPrefix (char const *aString, size_t theLength)
  67 {
  68     if (head)
  69         return head->find (aString, theLength, transform, true);
  70
  71     return NULL;
  72 }
  73
  74 #endif /* LIBTRIE_SQUID_H */
  75