rib/rib.cpp - NFD - Gitiles

 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
  * Copyright (c) 2014-2016,  Regents of the University of California,
  *                           Arizona Board of Regents,
  *                           Colorado State University,
  *                           University Pierre & Marie Curie, Sorbonne University,
  *                           Washington University in St. Louis,
  *                           Beijing Institute of Technology,
  *                           The University of Memphis.
  *
  * This file is part of NFD (Named Data Networking Forwarding Daemon).
  * See AUTHORS.md for complete list of NFD authors and contributors.
  *
  * NFD is free software: you can redistribute it and/or modify it under the terms
  * of the GNU General Public License as published by the Free Software Foundation,
  * either version 3 of the License, or (at your option) any later version.
  *
  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  * PURPOSE.  See the GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License along with
  * NFD, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  */

 #include "rib.hpp"

 #include "fib-updater.hpp"
 #include "core/logger.hpp"

 NFD_LOG_INIT("Rib");

 namespace nfd {
 namespace rib {

 static inline bool
 sortRoutes(const Route& lhs, const Route& rhs)
 {
   return lhs.faceId < rhs.faceId;
 }

 Rib::Rib()
   : m_nItems(0)
   , m_isUpdateInProgress(false)
 {
 }

 Rib::~Rib()
 {
 }

 void
 Rib::setFibUpdater(FibUpdater* updater)
 {
   m_fibUpdater = updater;
 }

 Rib::const_iterator
 Rib::find(const Name& prefix) const
 {
   return m_rib.find(prefix);
 }

 Route*
 Rib::find(const Name& prefix, const Route& route) const
 {
   RibTable::const_iterator ribIt = m_rib.find(prefix);

   // Name prefix exists
   if (ribIt != m_rib.end()) {
     shared_ptr<RibEntry> entry = ribIt->second;

     RibEntry::iterator routeIt = entry->findRoute(route);

     if (routeIt != entry->end()) {
       return &((*routeIt));
     }
   }

   return nullptr;
 }

 void
 Rib::insert(const Name& prefix, const Route& route)
 {
   RibTable::iterator ribIt = m_rib.find(prefix);

   // Name prefix exists
   if (ribIt != m_rib.end()) {
     shared_ptr<RibEntry> entry(ribIt->second);

     RibEntry::iterator routeIt = entry->findRoute(route);

     if (routeIt == entry->end()) {
       // New route
       entry->insertRoute(route);
       m_nItems++;

       // Register with face lookup table
       m_faceMap[route.faceId].push_back(entry);
     }
     else {
       // Route exists, update fields
       // First cancel old scheduled event, if any, then set the EventId to new one
       if (static_cast<bool>(routeIt->getExpirationEvent())) {
         NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " "
                                                          << *routeIt);
         scheduler::cancel(routeIt->getExpirationEvent());
       }

       // No checks are required here as the iterator needs to be updated in all cases.
       routeIt->setExpirationEvent(route.getExpirationEvent());

       routeIt->flags = route.flags;
       routeIt->cost = route.cost;
       routeIt->expires = route.expires;
     }
   }
   else {
     // New name prefix
     shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));

     m_rib[prefix] = entry;
     m_nItems++;

     entry->setName(prefix);
     entry->insertRoute(route);

     // Find prefix's parent
     shared_ptr<RibEntry> parent = findParent(prefix);

     // Add self to parent's children
     if (parent != nullptr) {
       parent->addChild(entry);
     }

     RibEntryList children = findDescendants(prefix);

     for (const auto& child : children) {
       if (child->getParent() == parent) {
         // Remove child from parent and inherit parent's child
         if (parent != nullptr) {
           parent->removeChild(child);
         }

         entry->addChild(child);
       }
     }

     // Register with face lookup table
     m_faceMap[route.faceId].push_back(entry);

     // do something after inserting an entry
     afterInsertEntry(prefix);
   }
 }

 void
 Rib::erase(const Name& prefix, const Route& route)
 {
   RibTable::iterator ribIt = m_rib.find(prefix);

   // Name prefix exists
   if (ribIt != m_rib.end()) {
     shared_ptr<RibEntry> entry = ribIt->second;
     RibEntry::iterator routeIt = entry->findRoute(route);

     if (routeIt != entry->end()) {
       auto faceId = route.faceId;
       entry->eraseRoute(routeIt);
       m_nItems--;

       // If this RibEntry no longer has this faceId, unregister from face lookup table
       if (!entry->hasFaceId(faceId)) {
         m_faceMap[faceId].remove(entry);
       }

       // If a RibEntry's route list is empty, remove it from the tree
       if (entry->getRoutes().empty()) {
         eraseEntry(ribIt);
       }
     }
   }
 }

 void
 Rib::onRouteExpiration(const Name& prefix, const Route& route)
 {
   NFD_LOG_DEBUG(route << " for " << prefix << " has expired");

   RibUpdate update;
   update.setAction(RibUpdate::UNREGISTER)
         .setName(prefix)
         .setRoute(route);

   beginApplyUpdate(update, nullptr, nullptr);
 }

 shared_ptr<RibEntry>
 Rib::findParent(const Name& prefix) const
 {
   for (int i = prefix.size() - 1; i >= 0; i--) {
     RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));

     if (it != m_rib.end()) {
       return (it->second);
     }
   }

   return shared_ptr<RibEntry>();
 }

 std::list<shared_ptr<RibEntry> >
 Rib::findDescendants(const Name& prefix) const
 {
   std::list<shared_ptr<RibEntry> > children;

   RibTable::const_iterator it = m_rib.find(prefix);

   if (it != m_rib.end()) {
     ++it;
     for (; it != m_rib.end(); ++it) {
       if (prefix.isPrefixOf(it->first)) {
         children.push_back((it->second));
       }
       else {
         break;
       }
     }
   }

   return children;
 }

 std::list<shared_ptr<RibEntry>>
 Rib::findDescendantsForNonInsertedName(const Name& prefix) const
 {
   std::list<shared_ptr<RibEntry>> children;

   for (std::pair<Name, shared_ptr<RibEntry>> pair : m_rib) {
     if (prefix.isPrefixOf(pair.first)) {
       children.push_back(pair.second);
     }
   }

   return children;
 }

 Rib::RibTable::iterator
 Rib::eraseEntry(RibTable::iterator it)
 {
   // Entry does not exist
   if (it == m_rib.end()) {
     return m_rib.end();
   }

   shared_ptr<RibEntry> entry(it->second);

   shared_ptr<RibEntry> parent = entry->getParent();

   // Remove self from parent's children
   if (parent != nullptr) {
     parent->removeChild(entry);
   }

   for (auto childIt = entry->getChildren().begin(); childIt != entry->getChildren().end(); ) {
     shared_ptr<RibEntry> child = *childIt;

     // Advance iterator so it is not invalidated by removal
     ++childIt;

     // Remove children from self
     entry->removeChild(child);

     // Update parent's children
     if (parent != nullptr) {
       parent->addChild(child);
     }
   }

   RibTable::iterator nextIt = m_rib.erase(it);

   // do something after erasing an entry.
   afterEraseEntry(entry->getName());

   return nextIt;
 }

 Rib::RouteSet
 Rib::getAncestorRoutes(const RibEntry& entry) const
 {
   RouteSet ancestorRoutes(&sortRoutes);

   shared_ptr<RibEntry> parent = entry.getParent();

   while (parent != nullptr) {
     for (const Route& route : parent->getRoutes()) {
       if (route.isChildInherit()) {
         ancestorRoutes.insert(route);
       }
     }

     if (parent->hasCapture()) {
       break;
     }

     parent = parent->getParent();
   }

   return ancestorRoutes;
 }

 Rib::RouteSet
 Rib::getAncestorRoutes(const Name& name) const
 {
   RouteSet ancestorRoutes(&sortRoutes);

   shared_ptr<RibEntry> parent = findParent(name);

   while (parent != nullptr) {
     for (const Route& route : parent->getRoutes()) {
       if (route.isChildInherit()) {
         ancestorRoutes.insert(route);
       }
     }

     if (parent->hasCapture()) {
       break;
     }

     parent = parent->getParent();
   }

   return ancestorRoutes;
 }

 void
 Rib::beginApplyUpdate(const RibUpdate& update,
                       const Rib::UpdateSuccessCallback& onSuccess,
                       const Rib::UpdateFailureCallback& onFailure)
 {
   BOOST_ASSERT(m_fibUpdater != nullptr);

   addUpdateToQueue(update, onSuccess, onFailure);

   sendBatchFromQueue();
 }

 void
 Rib::beginRemoveFace(uint64_t faceId)
 {
   for (const auto& nameAndRoute : findRoutesWithFaceId(faceId)) {
     RibUpdate update;
     update.setAction(RibUpdate::REMOVE_FACE)
           .setName(nameAndRoute.first)
           .setRoute(nameAndRoute.second);

     addUpdateToQueue(update, nullptr, nullptr);
   }

   sendBatchFromQueue();
 }

 void
 Rib::addUpdateToQueue(const RibUpdate& update,
                       const Rib::UpdateSuccessCallback& onSuccess,
                       const Rib::UpdateFailureCallback& onFailure)
 {
   RibUpdateBatch batch(update.getRoute().faceId);
   batch.add(update);

   UpdateQueueItem item{batch, onSuccess, onFailure};
   m_updateBatches.push_back(std::move(item));
 }

 void
 Rib::sendBatchFromQueue()
 {
   if (m_updateBatches.empty() || m_isUpdateInProgress) {
     return;
   }

   m_isUpdateInProgress = true;

   UpdateQueueItem item = std::move(m_updateBatches.front());
   m_updateBatches.pop_front();

   RibUpdateBatch& batch = item.batch;

   // Until task #1698, each RibUpdateBatch contains exactly one RIB update
   BOOST_ASSERT(batch.size() == 1);

   const Rib::UpdateSuccessCallback& managerSuccessCallback = item.managerSuccessCallback;
   const Rib::UpdateFailureCallback& managerFailureCallback = item.managerFailureCallback;

   m_fibUpdater->computeAndSendFibUpdates(batch,
                                          bind(&Rib::onFibUpdateSuccess, this,
                                               batch, _1, managerSuccessCallback),
                                          bind(&Rib::onFibUpdateFailure, this,
                                               managerFailureCallback, _1, _2));

   if (m_onSendBatchFromQueue != nullptr) {
     m_onSendBatchFromQueue(batch);
   }
 }

 void
 Rib::onFibUpdateSuccess(const RibUpdateBatch& batch,
                         const RibUpdateList& inheritedRoutes,
                         const Rib::UpdateSuccessCallback& onSuccess)
 {
   for (const RibUpdate& update : batch) {
     switch (update.getAction()) {
     case RibUpdate::REGISTER:
       insert(update.getName(), update.getRoute());
       break;
     case RibUpdate::UNREGISTER:
     case RibUpdate::REMOVE_FACE:
       erase(update.getName(), update.getRoute());
       break;
     }
   }

   // Add and remove precalculated inherited routes to RibEntries
   modifyInheritedRoutes(inheritedRoutes);

   m_isUpdateInProgress = false;

   if (onSuccess != nullptr) {
     onSuccess();
   }

   // Try to advance the batch queue
   sendBatchFromQueue();
 }

 void
 Rib::onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
                         uint32_t code, const std::string& error)
 {
   m_isUpdateInProgress = false;

   if (onFailure != nullptr) {
     onFailure(code, error);
   }

   // Try to advance the batch queue
   sendBatchFromQueue();
 }

 void
 Rib::modifyInheritedRoutes(const RibUpdateList& inheritedRoutes)
 {
   for (const RibUpdate& update : inheritedRoutes) {
     RibTable::iterator ribIt = m_rib.find(update.getName());

     BOOST_ASSERT(ribIt != m_rib.end());
     shared_ptr<RibEntry> entry(ribIt->second);

     switch (update.getAction()) {
     case RibUpdate::REGISTER:
       entry->addInheritedRoute(update.getRoute());
       break;
     case RibUpdate::UNREGISTER:
       entry->removeInheritedRoute(update.getRoute());
       break;
     case RibUpdate::REMOVE_FACE:
       break;
     }
   }
 }

 std::list<Rib::NameAndRoute>
 Rib::findRoutesWithFaceId(uint64_t faceId)
 {
   std::list<NameAndRoute> routes;

   FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);

   // No RIB entries have this face
   if (lookupIt == m_faceMap.end()) {
     return routes;
   }

   RibEntryList& ribEntries = lookupIt->second;

   // For each RIB entry that has faceId
   for (const shared_ptr<RibEntry>& entry : ribEntries) {
     // Find the routes in the entry
     for (const Route& route : *entry) {
       if (route.faceId == faceId) {
         routes.push_back(NameAndRoute(entry->getName(), route));
       }
     }
   }

   return routes;
 }

 std::ostream&
 operator<<(std::ostream& os, const Rib& rib)
 {
   for (const auto& item : rib) {
     os << item.second << "\n";
   }

   return os;
 }

 } // namespace rib
 } // namespace nfd
	/* -- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -- */
	/**
	* Copyright (c) 2014-2016, Regents of the University of California,
	* Arizona Board of Regents,
	* Colorado State University,
	* University Pierre & Marie Curie, Sorbonne University,
	* Washington University in St. Louis,
	* Beijing Institute of Technology,
	* The University of Memphis.
	*
	* This file is part of NFD (Named Data Networking Forwarding Daemon).
	* See AUTHORS.md for complete list of NFD authors and contributors.
	*
	* NFD is free software: you can redistribute it and/or modify it under the terms
	* of the GNU General Public License as published by the Free Software Foundation,
	* either version 3 of the License, or (at your option) any later version.
	*
	* NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
	* without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
	* PURPOSE. See the GNU General Public License for more details.
	*
	* You should have received a copy of the GNU General Public License along with
	* NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
	*/

	#include "rib.hpp"

	#include "fib-updater.hpp"
	#include "core/logger.hpp"

	NFD_LOG_INIT("Rib");

	namespace nfd {
	namespace rib {

	static inline bool
	sortRoutes(const Route& lhs, const Route& rhs)
	{
	return lhs.faceId < rhs.faceId;
	}

	Rib::Rib()
	: m_nItems(0)
	, m_isUpdateInProgress(false)
	{
	}

	Rib::~Rib()
	{
	}

	void
	Rib::setFibUpdater(FibUpdater* updater)
	{
	m_fibUpdater = updater;
	}

	Rib::const_iterator
	Rib::find(const Name& prefix) const
	{
	return m_rib.find(prefix);
	}

	Route*
	Rib::find(const Name& prefix, const Route& route) const
	{
	RibTable::const_iterator ribIt = m_rib.find(prefix);

	// Name prefix exists
	if (ribIt != m_rib.end()) {
	shared_ptr<RibEntry> entry = ribIt->second;

	RibEntry::iterator routeIt = entry->findRoute(route);

	if (routeIt != entry->end()) {
	return &((*routeIt));
	}
	}

	return nullptr;
	}

	void
	Rib::insert(const Name& prefix, const Route& route)
	{
	RibTable::iterator ribIt = m_rib.find(prefix);

	// Name prefix exists
	if (ribIt != m_rib.end()) {
	shared_ptr<RibEntry> entry(ribIt->second);

	RibEntry::iterator routeIt = entry->findRoute(route);

	if (routeIt == entry->end()) {
	// New route
	entry->insertRoute(route);
	m_nItems++;

	// Register with face lookup table
	m_faceMap[route.faceId].push_back(entry);
	}
	else {
	// Route exists, update fields
	// First cancel old scheduled event, if any, then set the EventId to new one
	if (static_cast<bool>(routeIt->getExpirationEvent())) {
	NFD_LOG_TRACE("Cancelling expiration event for " << entry->getName() << " "
	<< *routeIt);
	scheduler::cancel(routeIt->getExpirationEvent());
	}

	// No checks are required here as the iterator needs to be updated in all cases.
	routeIt->setExpirationEvent(route.getExpirationEvent());

	routeIt->flags = route.flags;
	routeIt->cost = route.cost;
	routeIt->expires = route.expires;
	}
	}
	else {
	// New name prefix
	shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));

	m_rib[prefix] = entry;
	m_nItems++;

	entry->setName(prefix);
	entry->insertRoute(route);

	// Find prefix's parent
	shared_ptr<RibEntry> parent = findParent(prefix);

	// Add self to parent's children
	if (parent != nullptr) {
	parent->addChild(entry);
	}

	RibEntryList children = findDescendants(prefix);

	for (const auto& child : children) {
	if (child->getParent() == parent) {
	// Remove child from parent and inherit parent's child
	if (parent != nullptr) {
	parent->removeChild(child);
	}

	entry->addChild(child);
	}
	}

	// Register with face lookup table
	m_faceMap[route.faceId].push_back(entry);

	// do something after inserting an entry
	afterInsertEntry(prefix);
	}
	}

	void
	Rib::erase(const Name& prefix, const Route& route)
	{
	RibTable::iterator ribIt = m_rib.find(prefix);

	// Name prefix exists
	if (ribIt != m_rib.end()) {
	shared_ptr<RibEntry> entry = ribIt->second;
	RibEntry::iterator routeIt = entry->findRoute(route);

	if (routeIt != entry->end()) {
	auto faceId = route.faceId;
	entry->eraseRoute(routeIt);
	m_nItems--;

	// If this RibEntry no longer has this faceId, unregister from face lookup table
	if (!entry->hasFaceId(faceId)) {
	m_faceMap[faceId].remove(entry);
	}

	// If a RibEntry's route list is empty, remove it from the tree
	if (entry->getRoutes().empty()) {
	eraseEntry(ribIt);
	}
	}
	}
	}

	void
	Rib::onRouteExpiration(const Name& prefix, const Route& route)
	{
	NFD_LOG_DEBUG(route << " for " << prefix << " has expired");

	RibUpdate update;
	update.setAction(RibUpdate::UNREGISTER)
	.setName(prefix)
	.setRoute(route);

	beginApplyUpdate(update, nullptr, nullptr);
	}

	shared_ptr<RibEntry>
	Rib::findParent(const Name& prefix) const
	{
	for (int i = prefix.size() - 1; i >= 0; i--) {
	RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));

	if (it != m_rib.end()) {
	return (it->second);
	}
	}

	return shared_ptr<RibEntry>();
	}

	std::list<shared_ptr<RibEntry> >
	Rib::findDescendants(const Name& prefix) const
	{
	std::list<shared_ptr<RibEntry> > children;

	RibTable::const_iterator it = m_rib.find(prefix);

	if (it != m_rib.end()) {
	++it;
	for (; it != m_rib.end(); ++it) {
	if (prefix.isPrefixOf(it->first)) {
	children.push_back((it->second));
	}
	else {
	break;
	}
	}
	}

	return children;
	}

	std::list<shared_ptr<RibEntry>>
	Rib::findDescendantsForNonInsertedName(const Name& prefix) const
	{
	std::list<shared_ptr<RibEntry>> children;

	for (std::pair<Name, shared_ptr<RibEntry>> pair : m_rib) {
	if (prefix.isPrefixOf(pair.first)) {
	children.push_back(pair.second);
	}
	}

	return children;
	}

	Rib::RibTable::iterator
	Rib::eraseEntry(RibTable::iterator it)
	{
	// Entry does not exist
	if (it == m_rib.end()) {
	return m_rib.end();
	}

	shared_ptr<RibEntry> entry(it->second);

	shared_ptr<RibEntry> parent = entry->getParent();

	// Remove self from parent's children
	if (parent != nullptr) {
	parent->removeChild(entry);
	}

	for (auto childIt = entry->getChildren().begin(); childIt != entry->getChildren().end(); ) {
	shared_ptr<RibEntry> child = *childIt;

	// Advance iterator so it is not invalidated by removal
	++childIt;

	// Remove children from self
	entry->removeChild(child);

	// Update parent's children
	if (parent != nullptr) {
	parent->addChild(child);
	}
	}

	RibTable::iterator nextIt = m_rib.erase(it);

	// do something after erasing an entry.
	afterEraseEntry(entry->getName());

	return nextIt;
	}

	Rib::RouteSet
	Rib::getAncestorRoutes(const RibEntry& entry) const
	{
	RouteSet ancestorRoutes(&sortRoutes);

	shared_ptr<RibEntry> parent = entry.getParent();

	while (parent != nullptr) {
	for (const Route& route : parent->getRoutes()) {
	if (route.isChildInherit()) {
	ancestorRoutes.insert(route);
	}
	}

	if (parent->hasCapture()) {
	break;
	}

	parent = parent->getParent();
	}

	return ancestorRoutes;
	}

	Rib::RouteSet
	Rib::getAncestorRoutes(const Name& name) const
	{
	RouteSet ancestorRoutes(&sortRoutes);

	shared_ptr<RibEntry> parent = findParent(name);

	while (parent != nullptr) {
	for (const Route& route : parent->getRoutes()) {
	if (route.isChildInherit()) {
	ancestorRoutes.insert(route);
	}
	}

	if (parent->hasCapture()) {
	break;
	}

	parent = parent->getParent();
	}

	return ancestorRoutes;
	}

	void
	Rib::beginApplyUpdate(const RibUpdate& update,
	const Rib::UpdateSuccessCallback& onSuccess,
	const Rib::UpdateFailureCallback& onFailure)
	{
	BOOST_ASSERT(m_fibUpdater != nullptr);

	addUpdateToQueue(update, onSuccess, onFailure);

	sendBatchFromQueue();
	}

	void
	Rib::beginRemoveFace(uint64_t faceId)
	{
	for (const auto& nameAndRoute : findRoutesWithFaceId(faceId)) {
	RibUpdate update;
	update.setAction(RibUpdate::REMOVE_FACE)
	.setName(nameAndRoute.first)
	.setRoute(nameAndRoute.second);

	addUpdateToQueue(update, nullptr, nullptr);
	}

	sendBatchFromQueue();
	}

	void
	Rib::addUpdateToQueue(const RibUpdate& update,
	const Rib::UpdateSuccessCallback& onSuccess,
	const Rib::UpdateFailureCallback& onFailure)
	{
	RibUpdateBatch batch(update.getRoute().faceId);
	batch.add(update);

	UpdateQueueItem item{batch, onSuccess, onFailure};
	m_updateBatches.push_back(std::move(item));
	}

	void
	Rib::sendBatchFromQueue()
	{
	if (m_updateBatches.empty() \|\| m_isUpdateInProgress) {
	return;
	}

	m_isUpdateInProgress = true;

	UpdateQueueItem item = std::move(m_updateBatches.front());
	m_updateBatches.pop_front();

	RibUpdateBatch& batch = item.batch;

	// Until task #1698, each RibUpdateBatch contains exactly one RIB update
	BOOST_ASSERT(batch.size() == 1);

	const Rib::UpdateSuccessCallback& managerSuccessCallback = item.managerSuccessCallback;
	const Rib::UpdateFailureCallback& managerFailureCallback = item.managerFailureCallback;

	m_fibUpdater->computeAndSendFibUpdates(batch,
	bind(&Rib::onFibUpdateSuccess, this,
	batch, _1, managerSuccessCallback),
	bind(&Rib::onFibUpdateFailure, this,
	managerFailureCallback, _1, _2));

	if (m_onSendBatchFromQueue != nullptr) {
	m_onSendBatchFromQueue(batch);
	}
	}

	void
	Rib::onFibUpdateSuccess(const RibUpdateBatch& batch,
	const RibUpdateList& inheritedRoutes,
	const Rib::UpdateSuccessCallback& onSuccess)
	{
	for (const RibUpdate& update : batch) {
	switch (update.getAction()) {
	case RibUpdate::REGISTER:
	insert(update.getName(), update.getRoute());
	break;
	case RibUpdate::UNREGISTER:
	case RibUpdate::REMOVE_FACE:
	erase(update.getName(), update.getRoute());
	break;
	}
	}

	// Add and remove precalculated inherited routes to RibEntries
	modifyInheritedRoutes(inheritedRoutes);

	m_isUpdateInProgress = false;

	if (onSuccess != nullptr) {
	onSuccess();
	}

	// Try to advance the batch queue
	sendBatchFromQueue();
	}

	void
	Rib::onFibUpdateFailure(const Rib::UpdateFailureCallback& onFailure,
	uint32_t code, const std::string& error)
	{
	m_isUpdateInProgress = false;

	if (onFailure != nullptr) {
	onFailure(code, error);
	}

	// Try to advance the batch queue
	sendBatchFromQueue();
	}

	void
	Rib::modifyInheritedRoutes(const RibUpdateList& inheritedRoutes)
	{
	for (const RibUpdate& update : inheritedRoutes) {
	RibTable::iterator ribIt = m_rib.find(update.getName());

	BOOST_ASSERT(ribIt != m_rib.end());
	shared_ptr<RibEntry> entry(ribIt->second);

	switch (update.getAction()) {
	case RibUpdate::REGISTER:
	entry->addInheritedRoute(update.getRoute());
	break;
	case RibUpdate::UNREGISTER:
	entry->removeInheritedRoute(update.getRoute());
	break;
	case RibUpdate::REMOVE_FACE:
	break;
	}
	}
	}

	std::list<Rib::NameAndRoute>
	Rib::findRoutesWithFaceId(uint64_t faceId)
	{
	std::list<NameAndRoute> routes;

	FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);

	// No RIB entries have this face
	if (lookupIt == m_faceMap.end()) {
	return routes;
	}

	RibEntryList& ribEntries = lookupIt->second;

	// For each RIB entry that has faceId
	for (const shared_ptr<RibEntry>& entry : ribEntries) {
	// Find the routes in the entry
	for (const Route& route : *entry) {
	if (route.faceId == faceId) {
	routes.push_back(NameAndRoute(entry->getName(), route));
	}
	}
	}

	return routes;
	}

	std::ostream&
	operator<<(std::ostream& os, const Rib& rib)
	{
	for (const auto& item : rib) {
	os << item.second << "\n";
	}

	return os;
	}

	} // namespace rib
	} // namespace nfd