]>
Commit | Line | Data |
---|---|---|
43ae1d95 | 1 | /* |
dc4eb86a | 2 | * Copyright (C) 1996-2014 The Squid Software Foundation and contributors |
43ae1d95 | 3 | * |
dc4eb86a AJ |
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. | |
43ae1d95 | 7 | */ |
8 | ||
9 | #ifndef LIBTRIE_SQUID_H | |
10 | #define LIBTRIE_SQUID_H | |
11 | ||
7d341c2c | 12 | #include "TrieNode.h" |
43ae1d95 | 13 | #if HAVE_SYS_TYPES_H |
14 | #include <sys/types.h> | |
15 | #endif | |
16 | ||
924f73bc | 17 | class TrieCharTransform; |
18 | ||
43ae1d95 | 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: | |
924f73bc | 27 | Trie(TrieCharTransform *aTransform = 0); |
43ae1d95 | 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 | */ | |
7d341c2c | 36 | inline void *find (char const *, size_t); |
43ae1d95 | 37 | /* find any element of the trie in the buffer from the |
38 | * beginning thereof | |
39 | */ | |
7d341c2c | 40 | inline void *findPrefix (char const *, size_t); |
43ae1d95 | 41 | |
42 | /* Add a string. | |
43 | * returns false if the string is already | |
44 | * present or cannot be added. | |
45 | */ | |
46 | ||
ea2728e3 | 47 | bool add(char const *, size_t, void *); |
43ae1d95 | 48 | |
49 | private: | |
50 | TrieNode *head; | |
924f73bc | 51 | |
52 | /* transfor each 8 bits in the element */ | |
53 | TrieCharTransform *transform; | |
43ae1d95 | 54 | }; |
55 | ||
7d341c2c FC |
56 | void * |
57 | Trie::find (char const *aString, size_t theLength) | |
58 | { | |
59 | if (head) | |
60 | return head->find (aString, theLength, transform, false); | |
43ae1d95 | 61 | |
7d341c2c FC |
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 | } | |
43ae1d95 | 73 | |
74 | #endif /* LIBTRIE_SQUID_H */ | |
f53969cc | 75 |