20 #ifndef TRIE_WITH_POLICY_H_ 21 #define TRIE_WITH_POLICY_H_ 31 template<
typename FullKey,
typename PayloadTraits,
typename PolicyTraits>
32 class trie_with_policy {
34 typedef trie<FullKey, PayloadTraits, typename PolicyTraits::policy_hook_type> parent_trie;
37 typedef typename parent_trie::const_iterator const_iterator;
39 typedef typename PolicyTraits::
40 template policy<trie_with_policy<FullKey, PayloadTraits, PolicyTraits>, parent_trie,
41 typename PolicyTraits::template container_hook<parent_trie>::type>::type
44 inline trie_with_policy(
size_t bucketSize = 1,
size_t bucketIncrement = 1)
45 : trie_(
name::Component(), bucketSize, bucketIncrement)
50 inline std::pair<iterator, bool>
51 insert(
const FullKey& key,
typename PayloadTraits::insert_type payload)
53 std::pair<iterator, bool> item = trie_.insert(key, payload);
57 bool ok = policy_.insert(s_iterator_to(item.first));
60 return std::make_pair(end(),
false);
64 return std::make_pair(s_iterator_to(item.first),
false);
71 erase(
const FullKey& key)
73 iterator foundItem, lastItem;
75 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
77 if (!reachLast || lastItem->payload() == PayloadTraits::empty_payload)
89 policy_.erase(s_iterator_to(node));
100 template<
typename Modifier>
102 modify(iterator position, Modifier mod)
104 if (position == end())
106 if (position->payload() == PayloadTraits::empty_payload)
109 mod(*position->payload());
110 policy_.update(position);
118 find_exact(
const FullKey& key)
120 iterator foundItem, lastItem;
122 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
124 if (!reachLast || lastItem->payload() == PayloadTraits::empty_payload)
134 longest_prefix_match(
const FullKey& key)
136 iterator foundItem, lastItem;
138 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
139 if (foundItem != trie_.end()) {
140 policy_.lookup(s_iterator_to(foundItem));
148 template<
class Predicate>
150 longest_prefix_match_if(
const FullKey& key, Predicate pred)
152 iterator foundItem, lastItem;
154 std::tie(foundItem, reachLast, lastItem) = trie_.find_if(key, pred);
155 if (foundItem != trie_.end()) {
156 policy_.lookup(s_iterator_to(foundItem));
175 deepest_prefix_match(
const FullKey& key)
177 iterator foundItem, lastItem;
179 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
182 if (lastItem == trie_.end())
186 if (foundItem == trie_.end()) {
187 foundItem = lastItem->find();
189 policy_.lookup(s_iterator_to(foundItem));
200 template<
class Predicate>
202 deepest_prefix_match_if(
const FullKey& key, Predicate pred)
204 iterator foundItem, lastItem;
206 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
209 if (lastItem == trie_.end())
213 foundItem = lastItem->find_if(pred);
214 if (foundItem == trie_.end()) {
217 policy_.lookup(s_iterator_to(foundItem));
231 template<
class Predicate>
233 deepest_prefix_match_if_next_level(
const FullKey& key, Predicate pred)
235 iterator foundItem, lastItem;
237 std::tie(foundItem, reachLast, lastItem) = trie_.find(key);
240 if (lastItem == trie_.end())
244 foundItem = lastItem->find_if_next_level(pred);
245 if (foundItem == trie_.end()) {
248 policy_.lookup(s_iterator_to(foundItem));
274 const policy_container&
286 static inline iterator
297 mutable policy_container policy_;
306 #endif // TRIE_WITH_POLICY_H_ Copyright (c) 2011-2015 Regents of the University of California.
Table::const_iterator iterator
Copyright (c) 2011-2015 Regents of the University of California.