blob: d7cb54491ea33d0923f59bafbc1f5b6b8047d704 [file] [log] [blame]
HYuana9b85752014-02-26 02:32:30 -06001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Junxiao Shi2b73ca32014-11-17 19:16:08 -07003 * Copyright (c) 2014, Regents of the University of California,
4 * Arizona Board of Regents,
5 * Colorado State University,
6 * University Pierre & Marie Curie, Sorbonne University,
7 * Washington University in St. Louis,
8 * Beijing Institute of Technology,
9 * The University of Memphis
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 *
11 * This file is part of NFD (Named Data Networking Forwarding Daemon).
12 * See AUTHORS.md for complete list of NFD authors and contributors.
13 *
14 * NFD is free software: you can redistribute it and/or modify it under the terms
15 * of the GNU General Public License as published by the Free Software Foundation,
16 * either version 3 of the License, or (at your option) any later version.
17 *
18 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20 * PURPOSE. See the GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License along with
23 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
Junxiao Shi2b73ca32014-11-17 19:16:08 -070024 */
HYuana9b85752014-02-26 02:32:30 -060025
26#include "name-tree.hpp"
27#include "core/logger.hpp"
Haowei Yuanf52dac72014-03-24 23:35:03 -050028#include "core/city-hash.hpp"
Davide Pesavento52a18f92014-04-10 00:55:01 +020029
HYuana9b85752014-02-26 02:32:30 -060030namespace nfd {
31
32NFD_LOG_INIT("NameTree");
33
34namespace name_tree {
35
Haowei Yuanf52dac72014-03-24 23:35:03 -050036class Hash32
HYuana9b85752014-02-26 02:32:30 -060037{
Haowei Yuanf52dac72014-03-24 23:35:03 -050038public:
39 static size_t
40 compute(const char* buffer, size_t length)
41 {
42 return static_cast<size_t>(CityHash32(buffer, length));
43 }
44};
HYuana9b85752014-02-26 02:32:30 -060045
Haowei Yuanf52dac72014-03-24 23:35:03 -050046class Hash64
47{
48public:
49 static size_t
50 compute(const char* buffer, size_t length)
51 {
52 return static_cast<size_t>(CityHash64(buffer, length));
53 }
54};
HYuana9b85752014-02-26 02:32:30 -060055
Haowei Yuanf52dac72014-03-24 23:35:03 -050056typedef boost::mpl::if_c<sizeof(size_t) >= 8, Hash64, Hash32>::type CityHash;
57
58// Interface of different hash functions
59size_t
60computeHash(const Name& prefix)
61{
62 prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
63
64 size_t hashValue = 0;
65 size_t hashUpdate = 0;
66
67 for (Name::const_iterator it = prefix.begin(); it != prefix.end(); it++)
68 {
69 const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
70 hashUpdate = CityHash::compute(wireFormat, it->size());
71 hashValue ^= hashUpdate;
72 }
73
74 return hashValue;
75}
76
77std::vector<size_t>
78computeHashSet(const Name& prefix)
79{
80 prefix.wireEncode(); // guarantees prefix's wire buffer is not empty
81
82 size_t hashValue = 0;
83 size_t hashUpdate = 0;
84
85 std::vector<size_t> hashValueSet;
86 hashValueSet.push_back(hashValue);
87
88 for (Name::const_iterator it = prefix.begin(); it != prefix.end(); it++)
89 {
90 const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
91 hashUpdate = CityHash::compute(wireFormat, it->size());
92 hashValue ^= hashUpdate;
93 hashValueSet.push_back(hashValue);
94 }
95
96 return hashValueSet;
HYuana9b85752014-02-26 02:32:30 -060097}
98
99} // namespace name_tree
100
101NameTree::NameTree(size_t nBuckets)
102 : m_nItems(0)
103 , m_nBuckets(nBuckets)
Haowei Yuanf52dac72014-03-24 23:35:03 -0500104 , m_minNBuckets(nBuckets)
105 , m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
106 , m_enlargeFactor(2) // double the hash table size
107 , m_shrinkLoadFactor(0.1) // less than 10% buckets loaded
108 , m_shrinkFactor(0.5) // reduce the number of buckets by half
Haowei Yuane1079fc2014-03-08 14:41:25 -0600109 , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
HYuana9b85752014-02-26 02:32:30 -0600110{
Haowei Yuanf52dac72014-03-24 23:35:03 -0500111 m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor *
112 static_cast<double>(m_nBuckets));
113
114 m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor *
HYuana9b85752014-02-26 02:32:30 -0600115 static_cast<double>(m_nBuckets));
116
117 // array of node pointers
118 m_buckets = new name_tree::Node*[m_nBuckets];
119 // Initialize the pointer array
120 for (size_t i = 0; i < m_nBuckets; i++)
121 m_buckets[i] = 0;
122}
123
124NameTree::~NameTree()
125{
126 for (size_t i = 0; i < m_nBuckets; i++)
127 {
Haowei Yuanf52dac72014-03-24 23:35:03 -0500128 if (m_buckets[i] != 0) {
HYuana9b85752014-02-26 02:32:30 -0600129 delete m_buckets[i];
Haowei Yuanf52dac72014-03-24 23:35:03 -0500130 }
HYuana9b85752014-02-26 02:32:30 -0600131 }
132
133 delete [] m_buckets;
134}
135
136// insert() is a private function, and called by only lookup()
137std::pair<shared_ptr<name_tree::Entry>, bool>
138NameTree::insert(const Name& prefix)
139{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700140 NFD_LOG_TRACE("insert " << prefix);
HYuana9b85752014-02-26 02:32:30 -0600141
Haowei Yuanf52dac72014-03-24 23:35:03 -0500142 size_t hashValue = name_tree::computeHash(prefix);
143 size_t loc = hashValue % m_nBuckets;
HYuana9b85752014-02-26 02:32:30 -0600144
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700145 NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << " location = " << loc);
HYuana9b85752014-02-26 02:32:30 -0600146
147 // Check if this Name has been stored
148 name_tree::Node* node = m_buckets[loc];
149 name_tree::Node* nodePrev = node; // initialize nodePrev to node
150
151 for (node = m_buckets[loc]; node != 0; node = node->m_next)
152 {
153 if (static_cast<bool>(node->m_entry))
154 {
155 if (prefix == node->m_entry->m_prefix)
156 {
157 return std::make_pair(node->m_entry, false); // false: old entry
158 }
159 }
160 nodePrev = node;
161 }
162
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700163 NFD_LOG_TRACE("Did not find " << prefix << ", need to insert it to the table");
HYuana9b85752014-02-26 02:32:30 -0600164
165 // If no bucket is empty occupied, we need to create a new node, and it is
166 // linked from nodePrev
167 node = new name_tree::Node();
168 node->m_prev = nodePrev;
169
170 if (nodePrev == 0)
171 {
172 m_buckets[loc] = node;
173 }
174 else
175 {
176 nodePrev->m_next = node;
177 }
178
179 // Create a new Entry
180 shared_ptr<name_tree::Entry> entry(make_shared<name_tree::Entry>(prefix));
181 entry->setHash(hashValue);
182 node->m_entry = entry; // link the Entry to its Node
183 entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.
184
185 return std::make_pair(entry, true); // true: new entry
186}
187
188// Name Prefix Lookup. Create Name Tree Entry if not found
189shared_ptr<name_tree::Entry>
190NameTree::lookup(const Name& prefix)
191{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700192 NFD_LOG_TRACE("lookup " << prefix);
HYuana9b85752014-02-26 02:32:30 -0600193
194 shared_ptr<name_tree::Entry> entry;
195 shared_ptr<name_tree::Entry> parent;
196
197 for (size_t i = 0; i <= prefix.size(); i++)
198 {
199 Name temp = prefix.getPrefix(i);
200
201 // insert() will create the entry if it does not exist.
202 std::pair<shared_ptr<name_tree::Entry>, bool> ret = insert(temp);
203 entry = ret.first;
204
205 if (ret.second == true)
206 {
Haowei Yuanf52dac72014-03-24 23:35:03 -0500207 m_nItems++; // Increase the counter
HYuana9b85752014-02-26 02:32:30 -0600208 entry->m_parent = parent;
209
210 if (static_cast<bool>(parent))
211 {
212 parent->m_children.push_back(entry);
213 }
214 }
215
Haowei Yuanf52dac72014-03-24 23:35:03 -0500216 if (m_nItems > m_enlargeThreshold)
HYuana9b85752014-02-26 02:32:30 -0600217 {
Haowei Yuanf52dac72014-03-24 23:35:03 -0500218 resize(m_enlargeFactor * m_nBuckets);
HYuana9b85752014-02-26 02:32:30 -0600219 }
220
221 parent = entry;
222 }
223 return entry;
224}
225
226// Exact Match
227shared_ptr<name_tree::Entry>
228NameTree::findExactMatch(const Name& prefix) const
229{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700230 NFD_LOG_TRACE("findExactMatch " << prefix);
HYuana9b85752014-02-26 02:32:30 -0600231
Haowei Yuanf52dac72014-03-24 23:35:03 -0500232 size_t hashValue = name_tree::computeHash(prefix);
233 size_t loc = hashValue % m_nBuckets;
HYuana9b85752014-02-26 02:32:30 -0600234
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700235 NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue <<
HYuana9b85752014-02-26 02:32:30 -0600236 " location = " << loc);
237
238 shared_ptr<name_tree::Entry> entry;
239 name_tree::Node* node = 0;
240
241 for (node = m_buckets[loc]; node != 0; node = node->m_next)
242 {
243 entry = node->m_entry;
244 if (static_cast<bool>(entry))
245 {
246 if (hashValue == entry->getHash() && prefix == entry->getPrefix())
247 {
248 return entry;
249 }
250 } // if entry
251 } // for node
252
253 // if not found, the default value of entry (null pointer) will be returned
254 entry.reset();
255 return entry;
256}
257
258// Longest Prefix Match
HYuana9b85752014-02-26 02:32:30 -0600259shared_ptr<name_tree::Entry>
Haowei Yuane1079fc2014-03-08 14:41:25 -0600260NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600261{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700262 NFD_LOG_TRACE("findLongestPrefixMatch " << prefix);
HYuana9b85752014-02-26 02:32:30 -0600263
264 shared_ptr<name_tree::Entry> entry;
Haowei Yuanf52dac72014-03-24 23:35:03 -0500265 std::vector<size_t> hashValueSet = name_tree::computeHashSet(prefix);
HYuana9b85752014-02-26 02:32:30 -0600266
Haowei Yuanf52dac72014-03-24 23:35:03 -0500267 size_t hashValue = 0;
268 size_t loc = 0;
269
270 for (int i = static_cast<int>(prefix.size()); i >= 0; i--)
HYuana9b85752014-02-26 02:32:30 -0600271 {
Haowei Yuanf52dac72014-03-24 23:35:03 -0500272 hashValue = hashValueSet[i];
273 loc = hashValue % m_nBuckets;
274
275 name_tree::Node* node = 0;
276 for (node = m_buckets[loc]; node != 0; node = node->m_next)
277 {
278 entry = node->m_entry;
279 if (static_cast<bool>(entry))
280 {
281 // isPrefixOf() is used to avoid making a copy of the name
282 if (hashValue == entry->getHash() &&
283 entry->getPrefix().isPrefixOf(prefix) &&
284 entrySelector(*entry))
285 {
286 return entry;
287 }
288 } // if entry
289 } // for node
HYuana9b85752014-02-26 02:32:30 -0600290 }
291
Haowei Yuanf52dac72014-03-24 23:35:03 -0500292 // if not found, the default value of entry (null pointer) will be returned
293 entry.reset();
294 return entry;
HYuana9b85752014-02-26 02:32:30 -0600295}
296
HangZhangcb4fc832014-03-11 16:57:11 +0800297shared_ptr<name_tree::Entry>
298NameTree::findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
299 const name_tree::EntrySelector& entrySelector) const
300{
301 while (static_cast<bool>(entry))
302 {
303 if (entrySelector(*entry))
304 return entry;
305 entry = entry->getParent();
306 }
307 return shared_ptr<name_tree::Entry>();
308}
309
HYuana9b85752014-02-26 02:32:30 -0600310// return {false: this entry is not empty, true: this entry is empty and erased}
311bool
312NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
313{
314 BOOST_ASSERT(static_cast<bool>(entry));
315
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700316 NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());
HYuana9b85752014-02-26 02:32:30 -0600317
318 // first check if this Entry can be erased
Junxiao Shi40631842014-03-01 13:52:37 -0700319 if (entry->isEmpty())
HYuana9b85752014-02-26 02:32:30 -0600320 {
321 // update child-related info in the parent
322 shared_ptr<name_tree::Entry> parent = entry->getParent();
323
324 if (static_cast<bool>(parent))
325 {
326 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
327 parent->getChildren();
328
329 bool isFound = false;
330 size_t size = parentChildrenList.size();
331 for (size_t i = 0; i < size; i++)
332 {
333 if (parentChildrenList[i] == entry)
334 {
335 parentChildrenList[i] = parentChildrenList[size - 1];
336 parentChildrenList.pop_back();
337 isFound = true;
338 break;
339 }
340 }
341
Junxiao Shiac7b4372014-12-13 21:47:04 -0700342 BOOST_VERIFY(isFound == true);
HYuana9b85752014-02-26 02:32:30 -0600343 }
344
345 // remove this Entry and its Name Tree Node
346 name_tree::Node* node = entry->m_node;
347 name_tree::Node* nodePrev = node->m_prev;
348
349 // configure the previous node
350 if (nodePrev != 0)
351 {
352 // link the previous node to the next node
353 nodePrev->m_next = node->m_next;
354 }
355 else
356 {
357 m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
358 }
359
360 // link the previous node with the next node (skip the erased one)
361 if (node->m_next != 0)
362 {
363 node->m_next->m_prev = nodePrev;
364 node->m_next = 0;
365 }
366
367 BOOST_ASSERT(node->m_next == 0);
368
369 m_nItems--;
370 delete node;
371
372 if (static_cast<bool>(parent))
373 eraseEntryIfEmpty(parent);
374
Haowei Yuanf52dac72014-03-24 23:35:03 -0500375 size_t newNBuckets = static_cast<size_t>(m_shrinkFactor *
376 static_cast<double>(m_nBuckets));
377
378 if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold)
379 {
380 resize(newNBuckets);
381 }
382
HYuana9b85752014-02-26 02:32:30 -0600383 return true;
384
385 } // if this entry is empty
386
387 return false; // if this entry is not empty
388}
389
Junxiao Shi5ccd0c22014-12-02 23:54:42 -0700390boost::iterator_range<NameTree::const_iterator>
Haowei Yuane1079fc2014-03-08 14:41:25 -0600391NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600392{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700393 NFD_LOG_TRACE("fullEnumerate");
HYuana9b85752014-02-26 02:32:30 -0600394
Haowei Yuane1079fc2014-03-08 14:41:25 -0600395 // find the first eligible entry
Junxiao Shi60607c72014-11-26 22:40:36 -0700396 for (size_t i = 0; i < m_nBuckets; i++) {
397 for (name_tree::Node* node = m_buckets[i]; node != 0; node = node->m_next) {
398 if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry)) {
399 const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
400 return {it, end()};
401 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600402 }
Junxiao Shi60607c72014-11-26 22:40:36 -0700403 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600404
405 // If none of the entry satisfies the requirements, then return the end() iterator.
Junxiao Shi60607c72014-11-26 22:40:36 -0700406 return {end(), end()};
Haowei Yuane1079fc2014-03-08 14:41:25 -0600407}
408
Junxiao Shi5ccd0c22014-12-02 23:54:42 -0700409boost::iterator_range<NameTree::const_iterator>
Haowei Yuane1079fc2014-03-08 14:41:25 -0600410NameTree::partialEnumerate(const Name& prefix,
411 const name_tree::EntrySubTreeSelector& entrySubTreeSelector) const
412{
413 // the first step is to process the root node
414 shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
Junxiao Shi60607c72014-11-26 22:40:36 -0700415 if (!static_cast<bool>(entry)) {
416 return {end(), end()};
417 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600418
419 std::pair<bool, bool>result = entrySubTreeSelector(*entry);
420 const_iterator it(PARTIAL_ENUMERATE_TYPE,
421 *this,
422 entry,
423 name_tree::AnyEntry(),
424 entrySubTreeSelector);
425
426 it.m_shouldVisitChildren = (result.second && entry->hasChildren());
427
Junxiao Shi60607c72014-11-26 22:40:36 -0700428 if (result.first) {
429 // root node is acceptable
430 }
431 else {
432 // let the ++ operator handle it
433 ++it;
434 }
435 return {it, end()};
HYuana9b85752014-02-26 02:32:30 -0600436}
437
Junxiao Shi5ccd0c22014-12-02 23:54:42 -0700438boost::iterator_range<NameTree::const_iterator>
Haowei Yuane1079fc2014-03-08 14:41:25 -0600439NameTree::findAllMatches(const Name& prefix,
440 const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600441{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700442 NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);
HYuana9b85752014-02-26 02:32:30 -0600443
Haowei Yuane1079fc2014-03-08 14:41:25 -0600444 // As we are using Name Prefix Hash Table, and the current LPM() is
445 // implemented as starting from full name, and reduce the number of
446 // components by 1 each time, we could use it here.
447 // For trie-like design, it could be more efficient by walking down the
448 // trie from the root node.
HYuana9b85752014-02-26 02:32:30 -0600449
Haowei Yuane1079fc2014-03-08 14:41:25 -0600450 shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
HYuana9b85752014-02-26 02:32:30 -0600451
Junxiao Shi2b73ca32014-11-17 19:16:08 -0700452 if (static_cast<bool>(entry)) {
453 const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
Junxiao Shi60607c72014-11-26 22:40:36 -0700454 return {begin, end()};
Junxiao Shi2b73ca32014-11-17 19:16:08 -0700455 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600456 // If none of the entry satisfies the requirements, then return the end() iterator.
Junxiao Shi60607c72014-11-26 22:40:36 -0700457 return {end(), end()};
HYuana9b85752014-02-26 02:32:30 -0600458}
459
460// Hash Table Resize
461void
462NameTree::resize(size_t newNBuckets)
463{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700464 NFD_LOG_TRACE("resize");
HYuana9b85752014-02-26 02:32:30 -0600465
466 name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
Junxiao Shi40631842014-03-01 13:52:37 -0700467 size_t count = 0;
HYuana9b85752014-02-26 02:32:30 -0600468
469 // referenced ccnx hashtb.c hashtb_rehash()
470 name_tree::Node** pp = 0;
471 name_tree::Node* p = 0;
472 name_tree::Node* pre = 0;
473 name_tree::Node* q = 0; // record p->m_next
Junxiao Shi40631842014-03-01 13:52:37 -0700474 size_t i;
HYuana9b85752014-02-26 02:32:30 -0600475 uint32_t h;
476 uint32_t b;
477
478 for (i = 0; i < newNBuckets; i++)
479 {
480 newBuckets[i] = 0;
481 }
482
483 for (i = 0; i < m_nBuckets; i++)
484 {
485 for (p = m_buckets[i]; p != 0; p = q)
486 {
487 count++;
488 q = p->m_next;
489 BOOST_ASSERT(static_cast<bool>(p->m_entry));
490 h = p->m_entry->m_hash;
491 b = h % newNBuckets;
Haowei Yuan694bfb62014-04-01 14:44:11 -0500492 pre = 0;
HYuana9b85752014-02-26 02:32:30 -0600493 for (pp = &newBuckets[b]; *pp != 0; pp = &((*pp)->m_next))
494 {
495 pre = *pp;
496 continue;
497 }
498 p->m_prev = pre;
499 p->m_next = *pp; // Actually *pp always == 0 in this case
500 *pp = p;
501 }
502 }
503
504 BOOST_ASSERT(count == m_nItems);
505
506 name_tree::Node** oldBuckets = m_buckets;
507 m_buckets = newBuckets;
Haowei Yuanf52dac72014-03-24 23:35:03 -0500508 delete [] oldBuckets;
HYuana9b85752014-02-26 02:32:30 -0600509
510 m_nBuckets = newNBuckets;
Haowei Yuanf52dac72014-03-24 23:35:03 -0500511
512 m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor *
513 static_cast<double>(m_nBuckets));
514 m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor *
515 static_cast<double>(m_nBuckets));
HYuana9b85752014-02-26 02:32:30 -0600516}
517
518// For debugging
519void
Haowei Yuane1079fc2014-03-08 14:41:25 -0600520NameTree::dump(std::ostream& output) const
HYuana9b85752014-02-26 02:32:30 -0600521{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700522 NFD_LOG_TRACE("dump()");
HYuana9b85752014-02-26 02:32:30 -0600523
524 name_tree::Node* node = 0;
525 shared_ptr<name_tree::Entry> entry;
526
527 using std::endl;
528
529 for (size_t i = 0; i < m_nBuckets; i++)
530 {
531 for (node = m_buckets[i]; node != 0; node = node->m_next)
532 {
533 entry = node->m_entry;
534
535 // if the Entry exist, dump its information
536 if (static_cast<bool>(entry))
537 {
538 output << "Bucket" << i << "\t" << entry->m_prefix.toUri() << endl;
539 output << "\t\tHash " << entry->m_hash << endl;
540
541 if (static_cast<bool>(entry->m_parent))
542 {
543 output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
544 }
545 else
546 {
547 output << "\t\tROOT";
548 }
549 output << endl;
550
551 if (entry->m_children.size() != 0)
552 {
553 output << "\t\tchildren = " << entry->m_children.size() << endl;
554
555 for (size_t j = 0; j < entry->m_children.size(); j++)
556 {
557 output << "\t\t\tChild " << j << " " <<
558 entry->m_children[j]->getPrefix() << endl;
559 }
560 }
561
562 } // if (static_cast<bool>(entry))
563
564 } // for node
565 } // for int i
566
567 output << "Bucket count = " << m_nBuckets << endl;
568 output << "Stored item = " << m_nItems << endl;
569 output << "--------------------------\n";
570}
571
Haowei Yuane1079fc2014-03-08 14:41:25 -0600572NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
573 const NameTree& nameTree,
574 shared_ptr<name_tree::Entry> entry,
575 const name_tree::EntrySelector& entrySelector,
576 const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
577 : m_nameTree(nameTree)
578 , m_entry(entry)
579 , m_subTreeRoot(entry)
580 , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
581 , m_entrySubTreeSelector(make_shared<name_tree::EntrySubTreeSelector>(entrySubTreeSelector))
582 , m_type(type)
583 , m_shouldVisitChildren(true)
584{
585}
586
587// operator++()
588NameTree::const_iterator
589NameTree::const_iterator::operator++()
590{
Alexander Afanasyevbf9edee2014-03-31 23:05:27 -0700591 NFD_LOG_TRACE("const_iterator::operator++()");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600592
593 BOOST_ASSERT(m_entry != m_nameTree.m_end);
594
595 if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
596 {
597 bool isFound = false;
598 // process the entries in the same bucket first
599 while (m_entry->m_node->m_next != 0)
600 {
601 m_entry = m_entry->m_node->m_next->m_entry;
602 if ((*m_entrySelector)(*m_entry))
603 {
604 isFound = true;
605 return *this;
606 }
607 }
608
609 // process other buckets
Junxiao Shiefceadc2014-03-09 18:52:57 -0700610
611 for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
612 newLocation < static_cast<int>(m_nameTree.m_nBuckets);
613 ++newLocation)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600614 {
615 // process each bucket
616 name_tree::Node* node = m_nameTree.m_buckets[newLocation];
617 while (node != 0)
618 {
619 m_entry = node->m_entry;
620 if ((*m_entrySelector)(*m_entry))
621 {
622 isFound = true;
623 return *this;
624 }
625 node = node->m_next;
626 }
627 }
Junxiao Shiac7b4372014-12-13 21:47:04 -0700628 BOOST_VERIFY(isFound == false);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600629 // Reach to the end()
630 m_entry = m_nameTree.m_end;
631 return *this;
632 }
633
634 if (m_type == PARTIAL_ENUMERATE_TYPE) // partialEnumerate
635 {
636 // We use pre-order traversal.
637 // if at the root, it could have already been accepted, or this
638 // iterator was just declared, and root doesn't satisfy the
639 // requirement
640 // The if() section handles this special case
641 // Essentially, we need to check root's fist child, and the rest will
642 // be the same as normal process
643 if (m_entry == m_subTreeRoot)
644 {
645 if (m_shouldVisitChildren)
646 {
647 m_entry = m_entry->getChildren()[0];
648 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
649 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
650 if(result.first)
651 {
652 return *this;
653 }
654 else
655 {
656 // the first child did not meet the requirement
657 // the rest of the process can just fall through the while loop
658 // as normal
659 }
660 }
661 else
662 {
663 // no children, should return end();
664 // just fall through
665 }
666 }
667
668 // The first thing to do is to visit its child, or go to find its possible
669 // siblings
670 while (m_entry != m_subTreeRoot)
671 {
672 if (m_shouldVisitChildren)
673 {
674 // If this subtree should be visited
675 m_entry = m_entry->getChildren()[0];
676 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
677 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
678 if (result.first) // if this node is acceptable
679 {
680 return *this;
681 }
682 else
683 {
684 // do nothing, as this node is essentially ignored
685 // send this node to the while loop.
686 }
687 }
688 else
689 {
690 // Should try to find its sibling
691 shared_ptr<name_tree::Entry> parent = m_entry->getParent();
692
693 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList = parent->getChildren();
694 bool isFound = false;
695 size_t i = 0;
696 for (i = 0; i < parentChildrenList.size(); i++)
697 {
698 if (parentChildrenList[i] == m_entry)
699 {
700 isFound = true;
701 break;
702 }
703 }
704
Junxiao Shiac7b4372014-12-13 21:47:04 -0700705 BOOST_VERIFY(isFound == true);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600706 if (i < parentChildrenList.size() - 1) // m_entry not the last child
707 {
708 m_entry = parentChildrenList[i + 1];
709 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
710 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
711 if (result.first) // if this node is acceptable
712 {
713 return *this;
714 }
715 else
716 {
717 // do nothing, as this node is essentially ignored
718 // send this node to the while loop.
719 }
720 }
721 else
722 {
723 // m_entry is the last child, no more sibling, should try to find parent's sibling
724 m_shouldVisitChildren = false;
725 m_entry = parent;
726 }
727 }
728 }
729
730 m_entry = m_nameTree.m_end;
731 return *this;
732 }
733
734 if (m_type == FIND_ALL_MATCHES_TYPE) // findAllMatches
735 {
736 // Assumption: at the beginning, m_entry was initialized with the first
737 // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
738 // by the Data packet)
739
740 while (static_cast<bool>(m_entry->getParent()))
741 {
742 m_entry = m_entry->getParent();
743 if ((*m_entrySelector)(*m_entry))
744 return *this;
745 }
746
747 // Reach to the end (Root)
748 m_entry = m_nameTree.m_end;
749 return *this;
750 }
Junxiao Shiefceadc2014-03-09 18:52:57 -0700751
752 BOOST_ASSERT(false); // unknown type
753 return *this;
Haowei Yuane1079fc2014-03-08 14:41:25 -0600754}
755
HYuana9b85752014-02-26 02:32:30 -0600756} // namespace nfd