blob: 08206833c19fafbeeea808fb96ced809a8677f20 [file] [log] [blame]
HYuana9b85752014-02-26 02:32:30 -06001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (C) 2014 Named Data Networking Project
4 * See COPYING for copyright and distribution information.
5 */
6
7// Name Tree (Name Prefix Hash Table)
8
9#include "name-tree.hpp"
10#include "core/logger.hpp"
11
12namespace nfd {
13
14NFD_LOG_INIT("NameTree");
15
16namespace name_tree {
17
18// Interface of different hash functions
19uint32_t
20hashName(const Name& prefix)
21{
22 // fixed value. Used for debugging only.
23 uint32_t ret = 0;
24
25 // Boost hash
26 // requires the /boost/functional/hash.hpp header file
27 // TODO: improve hash efficiency with Name type
28 boost::hash<std::string> stringHash;
29 ret = stringHash(prefix.toUri());
30
31 return ret;
32}
33
34} // namespace name_tree
35
36NameTree::NameTree(size_t nBuckets)
37 : m_nItems(0)
38 , m_nBuckets(nBuckets)
39 , m_loadFactor(0.5)
40 , m_resizeFactor(2)
Haowei Yuane1079fc2014-03-08 14:41:25 -060041 , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
HYuana9b85752014-02-26 02:32:30 -060042{
43 m_resizeThreshold = static_cast<size_t>(m_loadFactor *
44 static_cast<double>(m_nBuckets));
45
46 // array of node pointers
47 m_buckets = new name_tree::Node*[m_nBuckets];
48 // Initialize the pointer array
49 for (size_t i = 0; i < m_nBuckets; i++)
50 m_buckets[i] = 0;
51}
52
53NameTree::~NameTree()
54{
55 for (size_t i = 0; i < m_nBuckets; i++)
56 {
57 if (m_buckets[i] != 0)
58 delete m_buckets[i];
59 }
60
61 delete [] m_buckets;
62}
63
64// insert() is a private function, and called by only lookup()
65std::pair<shared_ptr<name_tree::Entry>, bool>
66NameTree::insert(const Name& prefix)
67{
68 NFD_LOG_DEBUG("insert " << prefix);
69
70 uint32_t hashValue = name_tree::hashName(prefix);
71 uint32_t loc = hashValue % m_nBuckets;
72
73 NFD_LOG_DEBUG("Name " << prefix << " hash value = " << hashValue << " location = " << loc);
74
75 // Check if this Name has been stored
76 name_tree::Node* node = m_buckets[loc];
77 name_tree::Node* nodePrev = node; // initialize nodePrev to node
78
79 for (node = m_buckets[loc]; node != 0; node = node->m_next)
80 {
81 if (static_cast<bool>(node->m_entry))
82 {
83 if (prefix == node->m_entry->m_prefix)
84 {
85 return std::make_pair(node->m_entry, false); // false: old entry
86 }
87 }
88 nodePrev = node;
89 }
90
91 NFD_LOG_DEBUG("Did not find " << prefix << ", need to insert it to the table");
92
93 // If no bucket is empty occupied, we need to create a new node, and it is
94 // linked from nodePrev
95 node = new name_tree::Node();
96 node->m_prev = nodePrev;
97
98 if (nodePrev == 0)
99 {
100 m_buckets[loc] = node;
101 }
102 else
103 {
104 nodePrev->m_next = node;
105 }
106
107 // Create a new Entry
108 shared_ptr<name_tree::Entry> entry(make_shared<name_tree::Entry>(prefix));
109 entry->setHash(hashValue);
110 node->m_entry = entry; // link the Entry to its Node
111 entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.
112
113 return std::make_pair(entry, true); // true: new entry
114}
115
116// Name Prefix Lookup. Create Name Tree Entry if not found
117shared_ptr<name_tree::Entry>
118NameTree::lookup(const Name& prefix)
119{
120 NFD_LOG_DEBUG("lookup " << prefix);
121
122 shared_ptr<name_tree::Entry> entry;
123 shared_ptr<name_tree::Entry> parent;
124
125 for (size_t i = 0; i <= prefix.size(); i++)
126 {
127 Name temp = prefix.getPrefix(i);
128
129 // insert() will create the entry if it does not exist.
130 std::pair<shared_ptr<name_tree::Entry>, bool> ret = insert(temp);
131 entry = ret.first;
132
133 if (ret.second == true)
134 {
135 m_nItems++; /* Increase the counter */
136 entry->m_parent = parent;
137
138 if (static_cast<bool>(parent))
139 {
140 parent->m_children.push_back(entry);
141 }
142 }
143
144 if (m_nItems > m_resizeThreshold)
145 {
146 resize(m_resizeFactor * m_nBuckets);
147 }
148
149 parent = entry;
150 }
151 return entry;
152}
153
154// Exact Match
155shared_ptr<name_tree::Entry>
156NameTree::findExactMatch(const Name& prefix) const
157{
158 NFD_LOG_DEBUG("findExactMatch " << prefix);
159
160 uint32_t hashValue = name_tree::hashName(prefix);
161 uint32_t loc = hashValue % m_nBuckets;
162
163 NFD_LOG_DEBUG("Name " << prefix << " hash value = " << hashValue <<
164 " location = " << loc);
165
166 shared_ptr<name_tree::Entry> entry;
167 name_tree::Node* node = 0;
168
169 for (node = m_buckets[loc]; node != 0; node = node->m_next)
170 {
171 entry = node->m_entry;
172 if (static_cast<bool>(entry))
173 {
174 if (hashValue == entry->getHash() && prefix == entry->getPrefix())
175 {
176 return entry;
177 }
178 } // if entry
179 } // for node
180
181 // if not found, the default value of entry (null pointer) will be returned
182 entry.reset();
183 return entry;
184}
185
186// Longest Prefix Match
187// Return the longest matching Entry address
188// start from the full name, and then remove 1 name comp each time
189shared_ptr<name_tree::Entry>
Haowei Yuane1079fc2014-03-08 14:41:25 -0600190NameTree::findLongestPrefixMatch(const Name& prefix, const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600191{
192 NFD_LOG_DEBUG("findLongestPrefixMatch " << prefix);
193
194 shared_ptr<name_tree::Entry> entry;
195
196 for (int i = prefix.size(); i >= 0; i--)
197 {
198 entry = findExactMatch(prefix.getPrefix(i));
Junxiao Shi40631842014-03-01 13:52:37 -0700199 if (static_cast<bool>(entry) && entrySelector(*entry))
HYuana9b85752014-02-26 02:32:30 -0600200 return entry;
201 }
202
Junxiao Shi40631842014-03-01 13:52:37 -0700203 return shared_ptr<name_tree::Entry>();
HYuana9b85752014-02-26 02:32:30 -0600204}
205
HangZhangcb4fc832014-03-11 16:57:11 +0800206shared_ptr<name_tree::Entry>
207NameTree::findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
208 const name_tree::EntrySelector& entrySelector) const
209{
210 while (static_cast<bool>(entry))
211 {
212 if (entrySelector(*entry))
213 return entry;
214 entry = entry->getParent();
215 }
216 return shared_ptr<name_tree::Entry>();
217}
218
HYuana9b85752014-02-26 02:32:30 -0600219// return {false: this entry is not empty, true: this entry is empty and erased}
220bool
221NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
222{
223 BOOST_ASSERT(static_cast<bool>(entry));
224
225 NFD_LOG_DEBUG("eraseEntryIfEmpty " << entry->getPrefix());
226
227 // first check if this Entry can be erased
Junxiao Shi40631842014-03-01 13:52:37 -0700228 if (entry->isEmpty())
HYuana9b85752014-02-26 02:32:30 -0600229 {
230 // update child-related info in the parent
231 shared_ptr<name_tree::Entry> parent = entry->getParent();
232
233 if (static_cast<bool>(parent))
234 {
235 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
236 parent->getChildren();
237
238 bool isFound = false;
239 size_t size = parentChildrenList.size();
240 for (size_t i = 0; i < size; i++)
241 {
242 if (parentChildrenList[i] == entry)
243 {
244 parentChildrenList[i] = parentChildrenList[size - 1];
245 parentChildrenList.pop_back();
246 isFound = true;
247 break;
248 }
249 }
250
251 BOOST_ASSERT(isFound == true);
252 }
253
254 // remove this Entry and its Name Tree Node
255 name_tree::Node* node = entry->m_node;
256 name_tree::Node* nodePrev = node->m_prev;
257
258 // configure the previous node
259 if (nodePrev != 0)
260 {
261 // link the previous node to the next node
262 nodePrev->m_next = node->m_next;
263 }
264 else
265 {
266 m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
267 }
268
269 // link the previous node with the next node (skip the erased one)
270 if (node->m_next != 0)
271 {
272 node->m_next->m_prev = nodePrev;
273 node->m_next = 0;
274 }
275
276 BOOST_ASSERT(node->m_next == 0);
277
278 m_nItems--;
279 delete node;
280
281 if (static_cast<bool>(parent))
282 eraseEntryIfEmpty(parent);
283
284 return true;
285
286 } // if this entry is empty
287
288 return false; // if this entry is not empty
289}
290
Haowei Yuane1079fc2014-03-08 14:41:25 -0600291NameTree::const_iterator
292NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600293{
294 NFD_LOG_DEBUG("fullEnumerate");
295
Haowei Yuane1079fc2014-03-08 14:41:25 -0600296 // find the first eligible entry
297 for (size_t i = 0; i < m_nBuckets; i++)
HYuana9b85752014-02-26 02:32:30 -0600298 {
Haowei Yuane1079fc2014-03-08 14:41:25 -0600299 for (name_tree::Node* node = m_buckets[i]; node != 0; node = node->m_next)
300 {
301 if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry))
302 {
303 const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
304 return it;
305 }
306 }
307 }
308
309 // If none of the entry satisfies the requirements, then return the end() iterator.
310 return end();
311}
312
313NameTree::const_iterator
314NameTree::partialEnumerate(const Name& prefix,
315 const name_tree::EntrySubTreeSelector& entrySubTreeSelector) const
316{
317 // the first step is to process the root node
318 shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
319 if (!static_cast<bool>(entry))
320 {
321 return end();
322 }
323
324 std::pair<bool, bool>result = entrySubTreeSelector(*entry);
325 const_iterator it(PARTIAL_ENUMERATE_TYPE,
326 *this,
327 entry,
328 name_tree::AnyEntry(),
329 entrySubTreeSelector);
330
331 it.m_shouldVisitChildren = (result.second && entry->hasChildren());
332
333 if (result.first)
334 {
335 // root node is acceptable
336 return it;
337 }
338 else
339 {
340 // let the ++ operator handle it
341 ++it;
342 return it;
HYuana9b85752014-02-26 02:32:30 -0600343 }
344}
345
Haowei Yuane1079fc2014-03-08 14:41:25 -0600346NameTree::const_iterator
347NameTree::findAllMatches(const Name& prefix,
348 const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600349{
Haowei Yuane1079fc2014-03-08 14:41:25 -0600350 NFD_LOG_DEBUG("NameTree::findAllMatches" << prefix);
HYuana9b85752014-02-26 02:32:30 -0600351
Haowei Yuane1079fc2014-03-08 14:41:25 -0600352 // As we are using Name Prefix Hash Table, and the current LPM() is
353 // implemented as starting from full name, and reduce the number of
354 // components by 1 each time, we could use it here.
355 // For trie-like design, it could be more efficient by walking down the
356 // trie from the root node.
HYuana9b85752014-02-26 02:32:30 -0600357
Haowei Yuane1079fc2014-03-08 14:41:25 -0600358 shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
HYuana9b85752014-02-26 02:32:30 -0600359
Haowei Yuane1079fc2014-03-08 14:41:25 -0600360 if (static_cast<bool>(entry))
361 {
362 const_iterator it(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
363 return it;
364 }
365 // If none of the entry satisfies the requirements, then return the end() iterator.
366 return end();
HYuana9b85752014-02-26 02:32:30 -0600367}
368
369// Hash Table Resize
370void
371NameTree::resize(size_t newNBuckets)
372{
373 NFD_LOG_DEBUG("resize");
374
375 name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
Junxiao Shi40631842014-03-01 13:52:37 -0700376 size_t count = 0;
HYuana9b85752014-02-26 02:32:30 -0600377
378 // referenced ccnx hashtb.c hashtb_rehash()
379 name_tree::Node** pp = 0;
380 name_tree::Node* p = 0;
381 name_tree::Node* pre = 0;
382 name_tree::Node* q = 0; // record p->m_next
Junxiao Shi40631842014-03-01 13:52:37 -0700383 size_t i;
HYuana9b85752014-02-26 02:32:30 -0600384 uint32_t h;
385 uint32_t b;
386
387 for (i = 0; i < newNBuckets; i++)
388 {
389 newBuckets[i] = 0;
390 }
391
392 for (i = 0; i < m_nBuckets; i++)
393 {
394 for (p = m_buckets[i]; p != 0; p = q)
395 {
396 count++;
397 q = p->m_next;
398 BOOST_ASSERT(static_cast<bool>(p->m_entry));
399 h = p->m_entry->m_hash;
400 b = h % newNBuckets;
401 for (pp = &newBuckets[b]; *pp != 0; pp = &((*pp)->m_next))
402 {
403 pre = *pp;
404 continue;
405 }
406 p->m_prev = pre;
407 p->m_next = *pp; // Actually *pp always == 0 in this case
408 *pp = p;
409 }
410 }
411
412 BOOST_ASSERT(count == m_nItems);
413
414 name_tree::Node** oldBuckets = m_buckets;
415 m_buckets = newBuckets;
416 delete oldBuckets;
417
418 m_nBuckets = newNBuckets;
419 m_resizeThreshold = (int)(m_loadFactor * (double)m_nBuckets);
420}
421
422// For debugging
423void
Haowei Yuane1079fc2014-03-08 14:41:25 -0600424NameTree::dump(std::ostream& output) const
HYuana9b85752014-02-26 02:32:30 -0600425{
426 NFD_LOG_DEBUG("dump()");
427
428 name_tree::Node* node = 0;
429 shared_ptr<name_tree::Entry> entry;
430
431 using std::endl;
432
433 for (size_t i = 0; i < m_nBuckets; i++)
434 {
435 for (node = m_buckets[i]; node != 0; node = node->m_next)
436 {
437 entry = node->m_entry;
438
439 // if the Entry exist, dump its information
440 if (static_cast<bool>(entry))
441 {
442 output << "Bucket" << i << "\t" << entry->m_prefix.toUri() << endl;
443 output << "\t\tHash " << entry->m_hash << endl;
444
445 if (static_cast<bool>(entry->m_parent))
446 {
447 output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
448 }
449 else
450 {
451 output << "\t\tROOT";
452 }
453 output << endl;
454
455 if (entry->m_children.size() != 0)
456 {
457 output << "\t\tchildren = " << entry->m_children.size() << endl;
458
459 for (size_t j = 0; j < entry->m_children.size(); j++)
460 {
461 output << "\t\t\tChild " << j << " " <<
462 entry->m_children[j]->getPrefix() << endl;
463 }
464 }
465
466 } // if (static_cast<bool>(entry))
467
468 } // for node
469 } // for int i
470
471 output << "Bucket count = " << m_nBuckets << endl;
472 output << "Stored item = " << m_nItems << endl;
473 output << "--------------------------\n";
474}
475
Haowei Yuane1079fc2014-03-08 14:41:25 -0600476NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
477 const NameTree& nameTree,
478 shared_ptr<name_tree::Entry> entry,
479 const name_tree::EntrySelector& entrySelector,
480 const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
481 : m_nameTree(nameTree)
482 , m_entry(entry)
483 , m_subTreeRoot(entry)
484 , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
485 , m_entrySubTreeSelector(make_shared<name_tree::EntrySubTreeSelector>(entrySubTreeSelector))
486 , m_type(type)
487 , m_shouldVisitChildren(true)
488{
489}
490
491// operator++()
492NameTree::const_iterator
493NameTree::const_iterator::operator++()
494{
495 NFD_LOG_DEBUG("const_iterator::operator++()");
496
497 BOOST_ASSERT(m_entry != m_nameTree.m_end);
498
499 if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
500 {
501 bool isFound = false;
502 // process the entries in the same bucket first
503 while (m_entry->m_node->m_next != 0)
504 {
505 m_entry = m_entry->m_node->m_next->m_entry;
506 if ((*m_entrySelector)(*m_entry))
507 {
508 isFound = true;
509 return *this;
510 }
511 }
512
513 // process other buckets
Junxiao Shiefceadc2014-03-09 18:52:57 -0700514
515 for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
516 newLocation < static_cast<int>(m_nameTree.m_nBuckets);
517 ++newLocation)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600518 {
519 // process each bucket
520 name_tree::Node* node = m_nameTree.m_buckets[newLocation];
521 while (node != 0)
522 {
523 m_entry = node->m_entry;
524 if ((*m_entrySelector)(*m_entry))
525 {
526 isFound = true;
527 return *this;
528 }
529 node = node->m_next;
530 }
531 }
532 BOOST_ASSERT(isFound == false);
533 // Reach to the end()
534 m_entry = m_nameTree.m_end;
535 return *this;
536 }
537
538 if (m_type == PARTIAL_ENUMERATE_TYPE) // partialEnumerate
539 {
540 // We use pre-order traversal.
541 // if at the root, it could have already been accepted, or this
542 // iterator was just declared, and root doesn't satisfy the
543 // requirement
544 // The if() section handles this special case
545 // Essentially, we need to check root's fist child, and the rest will
546 // be the same as normal process
547 if (m_entry == m_subTreeRoot)
548 {
549 if (m_shouldVisitChildren)
550 {
551 m_entry = m_entry->getChildren()[0];
552 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
553 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
554 if(result.first)
555 {
556 return *this;
557 }
558 else
559 {
560 // the first child did not meet the requirement
561 // the rest of the process can just fall through the while loop
562 // as normal
563 }
564 }
565 else
566 {
567 // no children, should return end();
568 // just fall through
569 }
570 }
571
572 // The first thing to do is to visit its child, or go to find its possible
573 // siblings
574 while (m_entry != m_subTreeRoot)
575 {
576 if (m_shouldVisitChildren)
577 {
578 // If this subtree should be visited
579 m_entry = m_entry->getChildren()[0];
580 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
581 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
582 if (result.first) // if this node is acceptable
583 {
584 return *this;
585 }
586 else
587 {
588 // do nothing, as this node is essentially ignored
589 // send this node to the while loop.
590 }
591 }
592 else
593 {
594 // Should try to find its sibling
595 shared_ptr<name_tree::Entry> parent = m_entry->getParent();
596
597 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList = parent->getChildren();
598 bool isFound = false;
599 size_t i = 0;
600 for (i = 0; i < parentChildrenList.size(); i++)
601 {
602 if (parentChildrenList[i] == m_entry)
603 {
604 isFound = true;
605 break;
606 }
607 }
608
609 BOOST_ASSERT(isFound == true);
610 if (i < parentChildrenList.size() - 1) // m_entry not the last child
611 {
612 m_entry = parentChildrenList[i + 1];
613 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
614 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
615 if (result.first) // if this node is acceptable
616 {
617 return *this;
618 }
619 else
620 {
621 // do nothing, as this node is essentially ignored
622 // send this node to the while loop.
623 }
624 }
625 else
626 {
627 // m_entry is the last child, no more sibling, should try to find parent's sibling
628 m_shouldVisitChildren = false;
629 m_entry = parent;
630 }
631 }
632 }
633
634 m_entry = m_nameTree.m_end;
635 return *this;
636 }
637
638 if (m_type == FIND_ALL_MATCHES_TYPE) // findAllMatches
639 {
640 // Assumption: at the beginning, m_entry was initialized with the first
641 // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
642 // by the Data packet)
643
644 while (static_cast<bool>(m_entry->getParent()))
645 {
646 m_entry = m_entry->getParent();
647 if ((*m_entrySelector)(*m_entry))
648 return *this;
649 }
650
651 // Reach to the end (Root)
652 m_entry = m_nameTree.m_end;
653 return *this;
654 }
Junxiao Shiefceadc2014-03-09 18:52:57 -0700655
656 BOOST_ASSERT(false); // unknown type
657 return *this;
Haowei Yuane1079fc2014-03-08 14:41:25 -0600658}
659
HYuana9b85752014-02-26 02:32:30 -0600660} // namespace nfd