[omapd] r186 committed - fixed a bug caused incorrect search graph calculations when extending ...

[om...@googlecode.com]

Revision: 186
Author: fu...@asguardnetworks.com
Date: Thu Jun 20 11:23:04 2013
Log: fixed a bug caused incorrect search graph calculations when
extending subscription search graphs; Added optimizations for metadata
delete handling saving a full search grpah rebuild when only a leaf-link is
removed
http://code.google.com/p/omapd/source/detail?r=186

Modified:
/branches/lfu/clienthandler.cpp
/branches/lfu/main.cpp
/branches/lfu/omapdconfig.cpp
/branches/lfu/omapdconfig.h
/branches/lfu/subscription.cpp
/branches/lfu/subscription.h

=======================================
--- /branches/lfu/clienthandler.cpp Wed Jun 5 09:18:54 2013
+++ /branches/lfu/clienthandler.cpp Thu Jun 20 11:23:04 2013
@@ -1751,8 +1751,22 @@
}
} else {

+ // is this link already in the search graph?
bool isLinkInSub = sub->_linkList.contains(link);
- bool oneIdInSub = sub->_ids.contains(link.first) ||
sub->_ids.contains(link.second);
+ // at least one of the IDs is in the sub search graph ?
+ bool oneIdInSub = (sub->_ids.contains(link.first) ||
sub->_ids.contains(link.second));
+// qDebug() << "~~handling link " << (publishType ==
Meta::PublishDelete ? "DELETE" : "UPDATE") << " in sub " << sub->_name;
+// qDebug() << "~~ids in sub:";
+// QMapIterator<Id, int> idit(sub->_ids);
+// while(idit.hasNext()) qDebug() << "\t" <<
idit.next().key().value();
+// qDebug() << "~~isLinkInSub: " <<
(isLinkInSub ? "true" : "false") << ", oneIdInSub: " <<
(oneIdInSub ? "true" : "false");
+// qDebug() << "~~sub->_ids.contains(link.first): " <<
(sub->_ids.contains(link.first) ? "true" : "false")
+// << ", sub->_ids.contains(link.second): " <<
(sub->_ids.contains(link.second) ? "true" : "false");
+
+ bool needsBuildSearchGraph = true; // must call
buildSearchGraph when true
+ bool needFullRebuild = true; // if
needsBuildSearchGraph: full rebuild or extend
+ bool deleteSingleLink = false; // can delete be optimized
to a simple link deletion
+ int deleteId = 0; // if deleteSingleLink:
which one of the link IDs is going away? (0 means none)

if (isLinkInSub && publishType == Meta::PublishDelete) {
// Case 3.
@@ -1760,11 +1774,50 @@
if
(_omapdConfig->valueFor("debug_level").value<OmapdConfig::IfmapDebugOptions>().testFlag(OmapdConfig::ShowSearchAlgorithm))
{
qDebug() << __PRETTY_FUNCTION__ << ":"
<< "----subscription is dirty with link in SearchGraph:" << link;
}
+
+ // for deletes, we check if the removal of metadata makes
the link go away
+ QList<Meta> curLinkMeta = _mapGraph->metaForLink(link);
+ MapRequest::RequestError error = MapRequest::ErrorNone;
+ QString matchLinkMeta = filteredMetadata(curLinkMeta,
sub->_search.matchLinks(), sub->_search.filterNamespaceDefinitions(),
error);
+ if (! matchLinkMeta.isEmpty()) {
+ // the link isn't going away, so the search graph will
remain the same
+ needsBuildSearchGraph = false;
+ }
+ else {
+ // the link is going away. However, if the link forms
a leaf in the search
+ // graph then the removal will not have a ripple
effect and we can also save a full rebuild
+ int d1 = sub->_ids[link.first];
+ int d2 = sub->_ids[link.second];
+ if(d1 == d2)
+ {
+ // both identifiers have the same depth means we
can always remove this link without
+ // any other part of the search graph breaking away
+ needsBuildSearchGraph = false;
+ deleteSingleLink = true;
+ needFullRebuild = false;
+ }
+ else if(d1 < d2 && sub->linksContaining(link.second)
== 1) // 1 means this id is only used in the link we're deleting
+ {
+ needsBuildSearchGraph = false;
+ deleteSingleLink = true;
+ needFullRebuild = false;
+ deleteId = 2;
+ }
+ else if(d2 < d1 && sub->linksContaining(link.second)
== 1)
+ {
+ needsBuildSearchGraph = false;
+ deleteSingleLink = true;
+ needFullRebuild = false;
+ deleteId = 1;
+ }
+ // in all other cases make a full search graph rebuild
+ }
}

if (isLinkInSub && publishType == Meta::PublishUpdate) {
// Case 2.
subIsDirty = true;
+ qDebug() << "~~oneIdInSub: case 2";
} else if(subIsDirty || (oneIdInSub && publishType ==
Meta::PublishUpdate)) {
// (LFu) - the way this else was written before, it also
covered the case:
// !sub._linkList.contains(link) && publishType ==
Meta::PublishDelete, which we should ignore
@@ -1776,7 +1829,7 @@
// rather than rebuilding it completely. This will cause
non-matching links or links attached to an
// identifier at max search depth to become noops

- bool needFullRebuild = (publishType ==
Meta::PublishUpdate ? false : true);
+ if (publishType == Meta::PublishUpdate) needFullRebuild =
false;

// TODO: we should also be able to optimize removal of a
link, e.g. any link that ends in an identifier
// of max subs search depth can be removed in isolation
(i.e. no subs graph must be calculated)
@@ -1785,25 +1838,44 @@
QSet<Link> existingLinkList = sub->_linkList;
int currentDepth = -1;
Id startId;
- if(needFullRebuild)
+// qDebug() << "~~case 3: needsBuildSearchGraph = " <<
(needsBuildSearchGraph ? "true" : "false")
+// << ", needFullRebuild = " <<
(needFullRebuild ? "true" : "false")
+// << ", deleteSingleLink = " <<
(deleteSingleLink ? "true" : "false");
+ if(needFullRebuild) // full search graph rebuild
{
sub->_ids.clear();
sub->_linkList.clear();
startId = sub->_search.startId();
// qDebug() << "~~making full search graph rebuild for
sub " << sub->_name;
}
- else
+ else if(publishType == Meta::PublishUpdate) // extend the
search graph
{
- // determine the identifier at which the search graph
is extended
- startId = link.first;
- currentDepth = sub->getDepth(startId);
- if(-1 == currentDepth)
+ // determine the identifier with the lowest depth to
start the graph expansion:
+ int depth1 = sub->getDepth(link.first);
+ int depth2 = sub->getDepth(link.second);
+
+ if(-1 == depth2 || (depth1 >= 0 && depth1 <= depth2))
+ {
+ startId = link.first;
+ currentDepth = depth1;
+ }
+ else
{
startId = link.second;
- currentDepth = sub->getDepth(startId);
+ currentDepth = depth2;
}
// qDebug() << "~~making search graph exension for
sub " << sub->_name;
}
+ else if (deleteSingleLink)
+ {
+ // only delete a single link
+ sub->_linkList.remove(link);
+ // delete
+ if(deleteId == 2)
+ sub->_ids.remove(link.second);
+ else if(deleteId == 1)
+ sub->_ids.remove(link.first);
+ }

// qDebug() << "~~making full search graph rebuild for
sub " << sub->_name;

@@ -1811,7 +1883,8 @@
// QTime buildSearchGraphTimer;
// buildSearchGraphTimer.start();

- buildSearchGraph(*sub, startId, (needFullRebuild ?
currentDepth : currentDepth - 1));
+ if(needsBuildSearchGraph)
+ buildSearchGraph(*sub, startId, (needFullRebuild ?
currentDepth : currentDepth - 1));
// qDebug() << "~~processing buildSearchGraph() took " <<
buildSearchGraphTimer.elapsed() << " ms for sub " << sub->_name;

if (sub->_ids != existingIdList) {
@@ -1873,6 +1946,7 @@
addIdentifierResult(*sub, link.first, metaChanges,
resultType, error);
}
}
+
// Add results from extending SearchGraph for this
subscription
if (!idsWithConnectedGraphUpdates.isEmpty() |
| !linksWithConnectedGraphUpdates.isEmpty()) {
if
(_omapdConfig->valueFor("debug_level").value<OmapdConfig::IfmapDebugOptions>().testFlag(OmapdConfig::ShowSearchAlgorithm))
{
=======================================
--- /branches/lfu/main.cpp Thu Jan 3 16:50:42 2013
+++ /branches/lfu/main.cpp Thu Jun 20 11:23:04 2013
@@ -221,5 +221,9 @@
qDebug() << "Started management server";
}

- return a.exec();
+ int exitCode = a.exec();
+
+ OmapdConfig::destroy();
+
+ return exitCode;
}
=======================================
--- /branches/lfu/omapdconfig.cpp Fri May 24 23:06:39 2013
+++ /branches/lfu/omapdconfig.cpp Thu Jun 20 11:23:04 2013
@@ -33,6 +33,14 @@
}
return _instance;
}
+
+void OmapdConfig::destroy()
+{
+ if (_instance != 0) {
+ delete _instance;
+ _instance = NULL;
+ }
+}

OmapdConfig::IfmapDebugOptions OmapdConfig::debugOptions(unsigned int
dbgValue)
{
@@ -189,6 +197,13 @@
{
const char *fnName = "OmapdConfig::~OmapdConfig():";
qDebug() << fnName;
+
+ QListIterator<ClientConfiguration *> it(_clientConfigurations);
+ while(it.hasNext())
+ {
+ delete it.next();
+ }
+ _clientConfigurations.clear();
}

void OmapdConfig::addConfigItem(const QString& key, const QVariant& value)
=======================================
--- /branches/lfu/omapdconfig.h Fri May 24 23:06:39 2013
+++ /branches/lfu/omapdconfig.h Thu Jun 20 11:23:04 2013
@@ -72,6 +72,9 @@
AllowAll = 0x3F // Convenience enum "or" of all allow options
};
Q_DECLARE_FLAGS(AuthzOptions, Authz);
+
+ static void destroy();
+
static AuthzOptions authzOptions(unsigned int authzValue);
static QString authzOptionsString(OmapdConfig::AuthzOptions option);

=======================================
--- /branches/lfu/subscription.cpp Wed Jun 5 09:18:54 2013
+++ /branches/lfu/subscription.cpp Thu Jun 20 11:23:04 2013
@@ -117,6 +117,20 @@

return resultSet;
}
+
+unsigned int Subscription::linksContaining(const Id& id) const
+{
+ unsigned int result = 0;
+ QSetIterator<Link> it(_linkList);
+ while(it.hasNext())
+ {
+ const Link& link = it.next();
+ if(link.first == id || link.second == id)
+ result++;
+ }
+
+ return result;
+}

void Subscription::clearSearchResults()
{
=======================================
--- /branches/lfu/subscription.h Wed Jun 5 09:18:54 2013
+++ /branches/lfu/subscription.h Thu Jun 20 11:23:04 2013
@@ -75,6 +75,8 @@
QSet<Id> identifiersWithout(const QMap<Id, int>& others) const;
// subtracts this subscription's identifiers form others
QSet<Id> subtractFrom(const QMap<Id, int>& others) const;
+ // count the number of links that contain an Id.
+ unsigned int linksContaining(const Id& id) const;

// QSet<Id> _idList;
QSet<Link> _linkList;