summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorbrain <brain@e03df62e-2008-0410-955e-edbf42e46eb7>2005-12-06 10:18:22 +0000
committerbrain <brain@e03df62e-2008-0410-955e-edbf42e46eb7>2005-12-06 10:18:22 +0000
commit1941dc3386d5524e812cf7a208bd72051e4e510a (patch)
tree794c3fc21eb22b371a304293737435d0b42870fd /src
parent626f01e70ee05ba7e595f909da2c1f4a0c63ec0f (diff)
Heavily optimized tree search
git-svn-id: http://svn.inspircd.org/repository/trunk/inspircd@2209 e03df62e-2008-0410-955e-edbf42e46eb7
Diffstat (limited to 'src')
-rw-r--r--src/modules/m_spanningtree.cpp158
1 files changed, 95 insertions, 63 deletions
diff --git a/src/modules/m_spanningtree.cpp b/src/modules/m_spanningtree.cpp
index 836b8b19f..e80a65c59 100644
--- a/src/modules/m_spanningtree.cpp
+++ b/src/modules/m_spanningtree.cpp
@@ -14,6 +14,8 @@
* ---------------------------------------------------
*/
+/* $ModDesc: Povides a spanning tree server link protocol */
+
using namespace std;
#include <stdio.h>
@@ -62,6 +64,9 @@ class TreeSocket;
TreeServer *TreeRoot;
+typedef nspace::hash_map<std::string, TreeServer*> server_hash;
+server_hash serverlist;
+
bool DoOneToOne(std::string prefix, std::string command, std::deque<std::string> params, std::string target);
bool DoOneToAllButSender(std::string prefix, std::string command, std::deque<std::string> params, std::string omit);
bool DoOneToMany(std::string prefix, std::string command, std::deque<std::string> params);
@@ -101,6 +106,7 @@ class TreeServer
UserCount = OperCount = 0;
VersionString = GetVersionString();
Route = NULL;
+ AddHashEntry();
}
TreeServer(std::string Name, std::string Desc, TreeServer* Above, TreeSocket* Sock) : Parent(Above), ServerName(Name), ServerDesc(Desc), Socket(Sock)
@@ -110,27 +116,74 @@ class TreeServer
this->SetNextPingTime(time(NULL) + 60);
this->SetPingFlag();
- log(DEBUG,"*** CREATE NEW SERVER %s ABOVE IS %s",Name.c_str(),Above->GetName().c_str());
+ /* find the 'route' for this server (e.g. the one directly connected
+ * to the local server, which we can use to reach it)
+ *
+ * In the following example, consider we have just added a TreeServer
+ * class for server G on our network, of which we are server A.
+ * To route traffic to G (marked with a *) we must send the data to
+ * B (marked with a +) so this algorithm initializes the 'Route'
+ * value to point at whichever server traffic must be routed through
+ * to get here. If we were to try this algorithm with server B,
+ * the Route pointer would point at its own object ('this').
+ *
+ * A
+ * / \
+ * + B C
+ * / \ \
+ * D E F
+ * / \
+ * * G H
+ *
+ * We only run this algorithm when a server is created, as
+ * the routes remain constant while ever the server exists, and
+ * do not need to be re-calculated.
+ */
- // find the 'route' for this server (e.g. the one directly connected
- // to the local server, which we can use to reach it)
Route = Above;
if (Route == TreeRoot)
{
- log(DEBUG,"(0) Route is %s",this->GetName().c_str());
Route = this;
}
else
{
- log(DEBUG,"(1) Route is %s",Route->GetName().c_str());
- while (Route->GetParent() != TreeRoot)
+ while (this->Route->GetParent() != TreeRoot)
{
- Route = Route->GetParent();
- log(DEBUG,"(2) Route is %s",Route->GetName().c_str());
+ this->Route = Route->GetParent();
}
}
- log(DEBUG," ROUTE FOR %s is %s",Name.c_str(),Route->GetName().c_str());
+ /* Because recursive code is slow and takes a lot of resources,
+ * we store two representations of the server tree. The first
+ * is a recursive structure where each server references its
+ * children and its parent, which is used for netbursts and
+ * netsplits to dump the whole dataset to the other server,
+ * and the second is used for very fast lookups when routing
+ * messages and is instead a hash_map, where each item can
+ * be referenced by its server name. The AddHashEntry()
+ * call below automatically inserts each TreeServer class
+ * into the hash_map as it is created. There is a similar
+ * maintainance call in the destructor to tidy up deleted
+ * servers.
+ */
+
+ this->AddHashEntry();
+ }
+
+ void AddHashEntry()
+ {
+ server_hash::iterator iter;
+ iter = serverlist.find(this->ServerName);
+ if (iter == clientlist.end())
+ serverlist[this->ServerName] = this;
+ }
+
+ void DelHashEntry()
+ {
+ server_hash::iterator iter;
+ iter = serverlist.find(this->ServerName);
+ if (iter != clientlist.end())
+ serverlist.erase(iter);
}
TreeServer* GetRoute()
@@ -234,7 +287,10 @@ class TreeServer
return false;
}
- // removes child nodes of this node, and of that node, etc etc
+ /* Removes child nodes of this node, and of that node, etc etc.
+ * This is used during netsplits to automatically tidy up the
+ * server tree. It is slow, we don't use it for much else.
+ */
bool Tidy()
{
bool stillchildren = true;
@@ -253,6 +309,11 @@ class TreeServer
}
return true;
}
+
+ ~TreeServer()
+ {
+ this->DelHashEntry();
+ }
};
class Link
@@ -267,71 +328,49 @@ class Link
time_t NextConnectTime;
};
-/* $ModDesc: Povides a spanning tree server link protocol */
-
Server *Srv;
ConfigReader *Conf;
std::vector<Link> LinkBlocks;
-TreeServer* RouteEnumerate(TreeServer* Current, std::string ServerName)
+TreeServer* FindServer(std::string ServerName)
{
- if (Current->GetName() == ServerName)
- return Current->GetRoute();
- for (unsigned int q = 0; q < Current->ChildCount(); q++)
+ server_hash::iterator iter;
+ iter = serverlist.find(ServerName);
+ if (iter != clientlist.end())
{
- TreeServer* found = RouteEnumerate(Current->GetChild(q),ServerName);
- if (found)
- return found->GetRoute();
+ return iter->second;
+ }
+ else
+ {
+ return NULL;
}
- return NULL;
}
-// Returns the locally connected server we must route a
-// message through to reach server 'ServerName'. This
-// only applies to one-to-one and not one-to-many routing.
+/* Returns the locally connected server we must route a
+ * message through to reach server 'ServerName'. This
+ * only applies to one-to-one and not one-to-many routing.
+ * See the comments for the constructor of TreeServer
+ * for more details.
+ */
TreeServer* BestRouteTo(std::string ServerName)
{
if (ServerName.c_str() == TreeRoot->GetName())
- {
return NULL;
+ TreeServer* Found = FindServer(ServerName);
+ if (Found)
+ {
+ return Found->GetRoute();
}
- // first, find the server by recursively walking the tree
- TreeServer* Found = RouteEnumerate(TreeRoot,ServerName);
- return Found;
-}
-
-bool LookForServer(TreeServer* Current, std::string ServerName)
-{
- if (ServerName == Current->GetName())
- return true;
- for (unsigned int q = 0; q < Current->ChildCount(); q++)
+ else
{
- if (LookForServer(Current->GetChild(q),ServerName))
- return true;
+ return NULL;
}
- return false;
}
TreeServer* Found;
-void RFindServer(TreeServer* Current, std::string ServerName)
-{
- if ((ServerName == Current->GetName()) && (!Found))
- {
- Found = Current;
- return;
- }
- if (!Found)
- {
- for (unsigned int q = 0; q < Current->ChildCount(); q++)
- {
- if (!Found)
- RFindServer(Current->GetChild(q),ServerName);
- }
- }
- return;
-}
-
+/* TODO: These need optimizing to use an iterator of serverlist
+ */
void RFindServerMask(TreeServer* Current, std::string ServerName)
{
if (Srv->MatchText(Current->GetName(),ServerName) && (!Found))
@@ -349,13 +388,6 @@ void RFindServerMask(TreeServer* Current, std::string ServerName)
}
}
-TreeServer* FindServer(std::string ServerName)
-{
- Found = NULL;
- RFindServer(TreeRoot,ServerName);
- return Found;
-}
-
TreeServer* FindServerMask(std::string ServerName)
{
Found = NULL;
@@ -365,7 +397,7 @@ TreeServer* FindServerMask(std::string ServerName)
bool IsServer(std::string ServerName)
{
- return LookForServer(TreeRoot,ServerName);
+ return (FindServer(ServerName) != NULL);
}
class TreeSocket : public InspSocket