]>
git.ipfire.org Git - thirdparty/squid.git/blob - lib/libTrie/TrieNode.h
2 * Copyright (c) 2002,2003 Robert Collins <rbtcollins@hotmail.com>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
20 #ifndef LIBTRIE_TRIENODE_H
21 #define LIBTRIE_TRIENODE_H
23 #include "TrieCharTransform.h"
25 #include <sys/types.h>
28 /* TODO: parameterize this to be more generic -
29 * i.e. M-ary internal node sizes etc
38 TrieNode(TrieNode
const &);
39 TrieNode
&operator= (TrieNode
const &);
42 * If found, return the private data.
43 * If not found, return NULL.
45 inline void *find (char const *, size_t, TrieCharTransform
*, bool const prefix
) const;
48 * returns false if the string is already
49 * present or can't be added.
52 bool add (char const *, size_t, void *, TrieCharTransform
*);
56 /* The char index into internal is an
57 * 8-bit prefix to a string in the trie.
58 * internal[0] is the terminal node for
59 * a string and may not be used
61 TrieNode
* internal
[256];
63 /* If a string ends here, non NULL */
67 /* recursive. TODO? make iterative */
69 TrieNode::find (char const *aString
, size_t theLength
, TrieCharTransform
*transform
, bool const prefix
) const
73 unsigned char pos
= transform
? (*transform
) (*aString
) : *aString
;
80 result
= internal
[index
]->find(aString
+ 1, theLength
- 1, transform
, prefix
);
95 #endif /* LIBTRIE_TRIENODE_H */