O(n^n) is bad. O(log n) is better.

[user/henk/code/inspircd.git] / src / modules / m_spanningtree.cpp

diff --git a/src/modules/m_spanningtree.cpp b/src/modules/m_spanningtree.cpp
index 42a939a7db4ef22404b9110dd76f0c1d743f09f1..37132059c4a8a16d994592e71ec3a37a4d1ed1e5 100644 (file)
--- a/src/modules/m_spanningtree.cpp
+++ b/src/modules/m_spanningtree.cpp
@@ -86,6 +86,7 @@ class ModuleSpanningTree;
  */
 typedef nspace::hash_map<std::string, TreeServer*, nspace::hash<string>, irc::StrHashComp> server_hash;
 
+typedef std::map<TreeServer*,TreeServer*> TreeServerList;
 
 /** The Link class might as well be a struct,
  * but this is C++ and we don't believe in structs (!).
@@ -179,10 +180,10 @@ class SpanningTreeUtilities
        void ReadConfiguration(bool rebind);
        /** Add a server to the server list for GetListOfServersForChannel
         */
-       void AddThisServer(TreeServer* server, std::deque<TreeServer*> &list);
+       void AddThisServer(TreeServer* server, TreeServerList &list);
        /** Compile a list of servers which contain members of channel c
         */
-       void GetListOfServersForChannel(chanrec* c, std::deque<TreeServer*> &list, const CUList &exempt_list);
+       void GetListOfServersForChannel(chanrec* c, TreeServerList &list, char status, const CUList &exempt_list);
        /** Find a server by name
         */
        TreeServer* FindServer(const std::string &ServerName);
@@ -3776,22 +3777,31 @@ SpanningTreeUtilities::~SpanningTreeUtilities()
        delete TreeRoot;
 }
 
-void SpanningTreeUtilities::AddThisServer(TreeServer* server, std::deque<TreeServer*> &list)
+void SpanningTreeUtilities::AddThisServer(TreeServer* server, TreeServerList &list)
 {
-       for (unsigned int c = 0; c < list.size(); c++)
-       {
-               if (list[c] == server)
-               {
-                       return;
-               }
-       }
-       list.push_back(server);
+       if (list.find(server) == list.end())
+               list[server] = server;
 }
 
 /** returns a list of DIRECT servernames for a specific channel */
-void SpanningTreeUtilities::GetListOfServersForChannel(chanrec* c, std::deque<TreeServer*> &list, const CUList &exempt_list)
+void SpanningTreeUtilities::GetListOfServersForChannel(chanrec* c, TreeServerList &list, char status, const CUList &exempt_list)
 {
-       CUList *ulist = c->GetUsers();
+       CUList *ulist;
+       switch (status)
+       {
+               case '@':
+                       ulist = c->GetOppedUsers();
+               break;
+               case '%':
+                       ulist = c->GetHalfoppedUsers();
+               break;
+               case '+':
+                       ulist = c->GetVoicedUsers();
+               break;
+               default:
+                       ulist = c->GetUsers();
+               break;
+       }
        for (CUList::iterator i = ulist->begin(); i != ulist->end(); i++)
        {
                if ((i->second->GetFd() < 0) && (exempt_list.find(i->second) == exempt_list.end()))
@@ -3806,6 +3816,7 @@ void SpanningTreeUtilities::GetListOfServersForChannel(chanrec* c, std::deque<Tr
 
 bool SpanningTreeUtilities::DoOneToAllButSenderRaw(const std::string &data, const std::string &omit, const std::string &prefix, const irc::string &command, std::deque<std::string> &params)
 {
+       char pfx = 0;
        TreeServer* omitroute = this->BestRouteTo(omit);
        if ((command == "NOTICE") || (command == "PRIVMSG"))
        {
@@ -3814,6 +3825,7 @@ bool SpanningTreeUtilities::DoOneToAllButSenderRaw(const std::string &data, cons
                        /* Prefixes */
                        if ((*(params[0].c_str()) == '@') || (*(params[0].c_str()) == '%') || (*(params[0].c_str()) == '+'))
                        {
+                               pfx = params[0][0];
                                params[0] = params[0].substr(1, params[0].length()-1);
                        }
                        if ((*(params[0].c_str()) != '#') && (*(params[0].c_str()) != '$'))
@@ -3840,16 +3852,18 @@ bool SpanningTreeUtilities::DoOneToAllButSenderRaw(const std::string &data, cons
                        else
                        {
                                chanrec* c = ServerInstance->FindChan(params[0]);
-                               if (c)
+                               userrec* u = ServerInstance->FindNick(prefix);
+                               if (c && u)
                                {
-                                       CUList empty;
-                                       std::deque<TreeServer*> list;
-                                       GetListOfServersForChannel(c,list,empty);
-                                       unsigned int lsize = list.size();
-                                       for (unsigned int i = 0; i < lsize; i++)
+                                       CUList elist;
+                                       TreeServerList list;
+                                       FOREACH_MOD(I_OnBuildExemptList, OnBuildExemptList((command == "PRIVMSG" ? MSG_PRIVMSG : MSG_NOTICE), c, u, pfx, elist));
+                                       GetListOfServersForChannel(c,list,pfx,elist);
+
+                                       for (TreeServerList::iterator i = list.begin(); i != list.end(); i++)
                                        {
-                                               TreeSocket* Sock = list[i]->GetSocket();
-                                               if ((Sock) && (list[i]->GetName() != omit) && (omitroute != list[i]))
+                                               TreeSocket* Sock = i->second->GetSocket();
+                                               if ((Sock) && (i->second->GetName() != omit) && (omitroute != i->second))
                                                {
                                                        Sock->WriteLine(data);
                                                }
@@ -4808,12 +4822,12 @@ class ModuleSpanningTree : public Module
                                        std::string cname = c->name;
                                        if (status)
                                                cname = status + cname;
-                                       std::deque<TreeServer*> list;
-                                       Utils->GetListOfServersForChannel(c,list,exempt_list);
-                                       unsigned int ucount = list.size();
-                                       for (unsigned int i = 0; i < ucount; i++)
+                                       TreeServerList list;
+                                       Utils->GetListOfServersForChannel(c,list,status,exempt_list);
+
+                                       for (TreeServerList::iterator i = list.begin(); i != list.end(); i++)
                                        {
-                                               TreeSocket* Sock = list[i]->GetSocket();
+                                               TreeSocket* Sock = i->second->GetSocket();
                                                if (Sock)
                                                        Sock->WriteLine(":"+std::string(user->nick)+" NOTICE "+cname+" :"+text);
                                        }
@@ -4859,12 +4873,12 @@ class ModuleSpanningTree : public Module
                                        std::string cname = c->name;
                                        if (status)
                                                cname = status + cname;
-                                       std::deque<TreeServer*> list;
-                                       Utils->GetListOfServersForChannel(c,list,exempt_list);
-                                       unsigned int ucount = list.size();
-                                       for (unsigned int i = 0; i < ucount; i++)
+                                       TreeServerList list;
+                                       Utils->GetListOfServersForChannel(c,list,status,exempt_list);
+
+                                       for (TreeServerList::iterator i = list.begin(); i != list.end(); i++)
                                        {
-                                               TreeSocket* Sock = list[i]->GetSocket();
+                                               TreeSocket* Sock = i->second->GetSocket();
                                                if (Sock)
                                                        Sock->WriteLine(":"+std::string(user->nick)+" PRIVMSG "+cname+" :"+text);
                                        }