blob: 430ed3c8684f780636cc0476911bc07dd755c501 [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
206// return {false: this entry is not empty, true: this entry is empty and erased}
207bool
208NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
209{
210 BOOST_ASSERT(static_cast<bool>(entry));
211
212 NFD_LOG_DEBUG("eraseEntryIfEmpty " << entry->getPrefix());
213
214 // first check if this Entry can be erased
Junxiao Shi40631842014-03-01 13:52:37 -0700215 if (entry->isEmpty())
HYuana9b85752014-02-26 02:32:30 -0600216 {
217 // update child-related info in the parent
218 shared_ptr<name_tree::Entry> parent = entry->getParent();
219
220 if (static_cast<bool>(parent))
221 {
222 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
223 parent->getChildren();
224
225 bool isFound = false;
226 size_t size = parentChildrenList.size();
227 for (size_t i = 0; i < size; i++)
228 {
229 if (parentChildrenList[i] == entry)
230 {
231 parentChildrenList[i] = parentChildrenList[size - 1];
232 parentChildrenList.pop_back();
233 isFound = true;
234 break;
235 }
236 }
237
238 BOOST_ASSERT(isFound == true);
239 }
240
241 // remove this Entry and its Name Tree Node
242 name_tree::Node* node = entry->m_node;
243 name_tree::Node* nodePrev = node->m_prev;
244
245 // configure the previous node
246 if (nodePrev != 0)
247 {
248 // link the previous node to the next node
249 nodePrev->m_next = node->m_next;
250 }
251 else
252 {
253 m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
254 }
255
256 // link the previous node with the next node (skip the erased one)
257 if (node->m_next != 0)
258 {
259 node->m_next->m_prev = nodePrev;
260 node->m_next = 0;
261 }
262
263 BOOST_ASSERT(node->m_next == 0);
264
265 m_nItems--;
266 delete node;
267
268 if (static_cast<bool>(parent))
269 eraseEntryIfEmpty(parent);
270
271 return true;
272
273 } // if this entry is empty
274
275 return false; // if this entry is not empty
276}
277
Haowei Yuane1079fc2014-03-08 14:41:25 -0600278NameTree::const_iterator
279NameTree::fullEnumerate(const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600280{
281 NFD_LOG_DEBUG("fullEnumerate");
282
Haowei Yuane1079fc2014-03-08 14:41:25 -0600283 // find the first eligible entry
284 for (size_t i = 0; i < m_nBuckets; i++)
HYuana9b85752014-02-26 02:32:30 -0600285 {
Haowei Yuane1079fc2014-03-08 14:41:25 -0600286 for (name_tree::Node* node = m_buckets[i]; node != 0; node = node->m_next)
287 {
288 if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry))
289 {
290 const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
291 return it;
292 }
293 }
294 }
295
296 // If none of the entry satisfies the requirements, then return the end() iterator.
297 return end();
298}
299
300NameTree::const_iterator
301NameTree::partialEnumerate(const Name& prefix,
302 const name_tree::EntrySubTreeSelector& entrySubTreeSelector) const
303{
304 // the first step is to process the root node
305 shared_ptr<name_tree::Entry> entry = findExactMatch(prefix);
306 if (!static_cast<bool>(entry))
307 {
308 return end();
309 }
310
311 std::pair<bool, bool>result = entrySubTreeSelector(*entry);
312 const_iterator it(PARTIAL_ENUMERATE_TYPE,
313 *this,
314 entry,
315 name_tree::AnyEntry(),
316 entrySubTreeSelector);
317
318 it.m_shouldVisitChildren = (result.second && entry->hasChildren());
319
320 if (result.first)
321 {
322 // root node is acceptable
323 return it;
324 }
325 else
326 {
327 // let the ++ operator handle it
328 ++it;
329 return it;
HYuana9b85752014-02-26 02:32:30 -0600330 }
331}
332
Haowei Yuane1079fc2014-03-08 14:41:25 -0600333NameTree::const_iterator
334NameTree::findAllMatches(const Name& prefix,
335 const name_tree::EntrySelector& entrySelector) const
HYuana9b85752014-02-26 02:32:30 -0600336{
Haowei Yuane1079fc2014-03-08 14:41:25 -0600337 NFD_LOG_DEBUG("NameTree::findAllMatches" << prefix);
HYuana9b85752014-02-26 02:32:30 -0600338
Haowei Yuane1079fc2014-03-08 14:41:25 -0600339 // As we are using Name Prefix Hash Table, and the current LPM() is
340 // implemented as starting from full name, and reduce the number of
341 // components by 1 each time, we could use it here.
342 // For trie-like design, it could be more efficient by walking down the
343 // trie from the root node.
HYuana9b85752014-02-26 02:32:30 -0600344
Haowei Yuane1079fc2014-03-08 14:41:25 -0600345 shared_ptr<name_tree::Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
HYuana9b85752014-02-26 02:32:30 -0600346
Haowei Yuane1079fc2014-03-08 14:41:25 -0600347 if (static_cast<bool>(entry))
348 {
349 const_iterator it(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
350 return it;
351 }
352 // If none of the entry satisfies the requirements, then return the end() iterator.
353 return end();
HYuana9b85752014-02-26 02:32:30 -0600354}
355
356// Hash Table Resize
357void
358NameTree::resize(size_t newNBuckets)
359{
360 NFD_LOG_DEBUG("resize");
361
362 name_tree::Node** newBuckets = new name_tree::Node*[newNBuckets];
Junxiao Shi40631842014-03-01 13:52:37 -0700363 size_t count = 0;
HYuana9b85752014-02-26 02:32:30 -0600364
365 // referenced ccnx hashtb.c hashtb_rehash()
366 name_tree::Node** pp = 0;
367 name_tree::Node* p = 0;
368 name_tree::Node* pre = 0;
369 name_tree::Node* q = 0; // record p->m_next
Junxiao Shi40631842014-03-01 13:52:37 -0700370 size_t i;
HYuana9b85752014-02-26 02:32:30 -0600371 uint32_t h;
372 uint32_t b;
373
374 for (i = 0; i < newNBuckets; i++)
375 {
376 newBuckets[i] = 0;
377 }
378
379 for (i = 0; i < m_nBuckets; i++)
380 {
381 for (p = m_buckets[i]; p != 0; p = q)
382 {
383 count++;
384 q = p->m_next;
385 BOOST_ASSERT(static_cast<bool>(p->m_entry));
386 h = p->m_entry->m_hash;
387 b = h % newNBuckets;
388 for (pp = &newBuckets[b]; *pp != 0; pp = &((*pp)->m_next))
389 {
390 pre = *pp;
391 continue;
392 }
393 p->m_prev = pre;
394 p->m_next = *pp; // Actually *pp always == 0 in this case
395 *pp = p;
396 }
397 }
398
399 BOOST_ASSERT(count == m_nItems);
400
401 name_tree::Node** oldBuckets = m_buckets;
402 m_buckets = newBuckets;
403 delete oldBuckets;
404
405 m_nBuckets = newNBuckets;
406 m_resizeThreshold = (int)(m_loadFactor * (double)m_nBuckets);
407}
408
409// For debugging
410void
Haowei Yuane1079fc2014-03-08 14:41:25 -0600411NameTree::dump(std::ostream& output) const
HYuana9b85752014-02-26 02:32:30 -0600412{
413 NFD_LOG_DEBUG("dump()");
414
415 name_tree::Node* node = 0;
416 shared_ptr<name_tree::Entry> entry;
417
418 using std::endl;
419
420 for (size_t i = 0; i < m_nBuckets; i++)
421 {
422 for (node = m_buckets[i]; node != 0; node = node->m_next)
423 {
424 entry = node->m_entry;
425
426 // if the Entry exist, dump its information
427 if (static_cast<bool>(entry))
428 {
429 output << "Bucket" << i << "\t" << entry->m_prefix.toUri() << endl;
430 output << "\t\tHash " << entry->m_hash << endl;
431
432 if (static_cast<bool>(entry->m_parent))
433 {
434 output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
435 }
436 else
437 {
438 output << "\t\tROOT";
439 }
440 output << endl;
441
442 if (entry->m_children.size() != 0)
443 {
444 output << "\t\tchildren = " << entry->m_children.size() << endl;
445
446 for (size_t j = 0; j < entry->m_children.size(); j++)
447 {
448 output << "\t\t\tChild " << j << " " <<
449 entry->m_children[j]->getPrefix() << endl;
450 }
451 }
452
453 } // if (static_cast<bool>(entry))
454
455 } // for node
456 } // for int i
457
458 output << "Bucket count = " << m_nBuckets << endl;
459 output << "Stored item = " << m_nItems << endl;
460 output << "--------------------------\n";
461}
462
Haowei Yuane1079fc2014-03-08 14:41:25 -0600463NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
464 const NameTree& nameTree,
465 shared_ptr<name_tree::Entry> entry,
466 const name_tree::EntrySelector& entrySelector,
467 const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
468 : m_nameTree(nameTree)
469 , m_entry(entry)
470 , m_subTreeRoot(entry)
471 , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
472 , m_entrySubTreeSelector(make_shared<name_tree::EntrySubTreeSelector>(entrySubTreeSelector))
473 , m_type(type)
474 , m_shouldVisitChildren(true)
475{
476}
477
478// operator++()
479NameTree::const_iterator
480NameTree::const_iterator::operator++()
481{
482 NFD_LOG_DEBUG("const_iterator::operator++()");
483
484 BOOST_ASSERT(m_entry != m_nameTree.m_end);
485
486 if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
487 {
488 bool isFound = false;
489 // process the entries in the same bucket first
490 while (m_entry->m_node->m_next != 0)
491 {
492 m_entry = m_entry->m_node->m_next->m_entry;
493 if ((*m_entrySelector)(*m_entry))
494 {
495 isFound = true;
496 return *this;
497 }
498 }
499
500 // process other buckets
Junxiao Shiefceadc2014-03-09 18:52:57 -0700501
502 for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
503 newLocation < static_cast<int>(m_nameTree.m_nBuckets);
504 ++newLocation)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600505 {
506 // process each bucket
507 name_tree::Node* node = m_nameTree.m_buckets[newLocation];
508 while (node != 0)
509 {
510 m_entry = node->m_entry;
511 if ((*m_entrySelector)(*m_entry))
512 {
513 isFound = true;
514 return *this;
515 }
516 node = node->m_next;
517 }
518 }
519 BOOST_ASSERT(isFound == false);
520 // Reach to the end()
521 m_entry = m_nameTree.m_end;
522 return *this;
523 }
524
525 if (m_type == PARTIAL_ENUMERATE_TYPE) // partialEnumerate
526 {
527 // We use pre-order traversal.
528 // if at the root, it could have already been accepted, or this
529 // iterator was just declared, and root doesn't satisfy the
530 // requirement
531 // The if() section handles this special case
532 // Essentially, we need to check root's fist child, and the rest will
533 // be the same as normal process
534 if (m_entry == m_subTreeRoot)
535 {
536 if (m_shouldVisitChildren)
537 {
538 m_entry = m_entry->getChildren()[0];
539 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
540 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
541 if(result.first)
542 {
543 return *this;
544 }
545 else
546 {
547 // the first child did not meet the requirement
548 // the rest of the process can just fall through the while loop
549 // as normal
550 }
551 }
552 else
553 {
554 // no children, should return end();
555 // just fall through
556 }
557 }
558
559 // The first thing to do is to visit its child, or go to find its possible
560 // siblings
561 while (m_entry != m_subTreeRoot)
562 {
563 if (m_shouldVisitChildren)
564 {
565 // If this subtree should be visited
566 m_entry = m_entry->getChildren()[0];
567 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
568 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
569 if (result.first) // if this node is acceptable
570 {
571 return *this;
572 }
573 else
574 {
575 // do nothing, as this node is essentially ignored
576 // send this node to the while loop.
577 }
578 }
579 else
580 {
581 // Should try to find its sibling
582 shared_ptr<name_tree::Entry> parent = m_entry->getParent();
583
584 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList = parent->getChildren();
585 bool isFound = false;
586 size_t i = 0;
587 for (i = 0; i < parentChildrenList.size(); i++)
588 {
589 if (parentChildrenList[i] == m_entry)
590 {
591 isFound = true;
592 break;
593 }
594 }
595
596 BOOST_ASSERT(isFound == true);
597 if (i < parentChildrenList.size() - 1) // m_entry not the last child
598 {
599 m_entry = parentChildrenList[i + 1];
600 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
601 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
602 if (result.first) // if this node is acceptable
603 {
604 return *this;
605 }
606 else
607 {
608 // do nothing, as this node is essentially ignored
609 // send this node to the while loop.
610 }
611 }
612 else
613 {
614 // m_entry is the last child, no more sibling, should try to find parent's sibling
615 m_shouldVisitChildren = false;
616 m_entry = parent;
617 }
618 }
619 }
620
621 m_entry = m_nameTree.m_end;
622 return *this;
623 }
624
625 if (m_type == FIND_ALL_MATCHES_TYPE) // findAllMatches
626 {
627 // Assumption: at the beginning, m_entry was initialized with the first
628 // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
629 // by the Data packet)
630
631 while (static_cast<bool>(m_entry->getParent()))
632 {
633 m_entry = m_entry->getParent();
634 if ((*m_entrySelector)(*m_entry))
635 return *this;
636 }
637
638 // Reach to the end (Root)
639 m_entry = m_nameTree.m_end;
640 return *this;
641 }
Junxiao Shiefceadc2014-03-09 18:52:57 -0700642
643 BOOST_ASSERT(false); // unknown type
644 return *this;
Haowei Yuane1079fc2014-03-08 14:41:25 -0600645}
646
HYuana9b85752014-02-26 02:32:30 -0600647} // namespace nfd