lib/libTrie/TrieNode.h

   1 /*
   2  * Copyright (C) 1996-2017 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_TRIENODE_H
  10 #define   LIBTRIE_TRIENODE_H
  11
  12 #include "TrieCharTransform.h"
  13
  14 #include <sys/types.h>
  15 #include <utility>
  16
  17 /* TODO: parameterize this to be more generic -
  18 * i.e. M-ary internal node sizes etc
  19 */
  20
  21 class TrieNode
  22 {
  23
  24 public:
  25     TrieNode();
  26     ~TrieNode();
  27     TrieNode(TrieNode const &);
  28     TrieNode &operator= (TrieNode const &);
  29
  30     /* Find a string.
  31     * If found, return the private data.
  32     * If not found, return NULL.
  33     */
  34     inline void *find (char const *, size_t, TrieCharTransform *, bool const prefix) const;
  35
  36     /* Add a string.
  37     * returns false if the string is already
  38     * present or can't be added.
  39     */
  40
  41     bool add (char const *, size_t, void *, TrieCharTransform *);
  42
  43 private:
  44     /* 256-way Trie */
  45     /* The char index into internal is an
  46     * 8-bit prefix to a string in the trie.
  47     * internal[0] is the terminal node for
  48     * a string and may not be used
  49     */
  50     TrieNode * internal[256];
  51
  52     /* If a string ends here, non NULL */
  53     void *_privateData;
  54 };
  55
  56 /* recursive. TODO? make iterative */
  57 void *
  58 TrieNode::find (char const *aString, size_t theLength, TrieCharTransform *transform, bool const prefix) const
  59 {
  60     if (theLength) {
  61         int index = -1;
  62         unsigned char pos = transform ? (*transform) (*aString) : *aString;
  63
  64         if (internal[pos])
  65             index = pos;
  66
  67         if (index > -1) {
  68             void *result;
  69             result = internal[index]->find(aString + 1, theLength - 1, transform, prefix);
  70
  71             if (result)
  72                 return result;
  73         }
  74
  75         if (prefix)
  76             return _privateData;
  77
  78         return NULL;
  79     } else {
  80         /* terminal node */
  81         return _privateData;
  82     }
  83 }
  84 #endif /* LIBTRIE_TRIENODE_H */
  85