Switched the system for storing users, channels, and sesions to a patricia

tree from STL's unordered_map, which was giving horrible performance.

11 files changed, 55 insertions, 86 deletions

diff --git a/src/bots.cpp b/src/bots.cpp
index e1d70d05a..9b2cfddb6 100644
--- a/src/bots.cpp
+++ b/src/bots.cpp
@@ -9,8 +9,8 @@
 #include "modules.h"
 #include "commands.h"
 
-botinfo_map BotListByNick;
-botinfo_uid_map BotListByUID;
+patricia_tree<BotInfo, std::equal_to<ci::string> > BotListByNick;
+patricia_tree<BotInfo> BotListByUID;
 
 BotInfo *BotServ = NULL;
 BotInfo *ChanServ = NULL;
@@ -46,9 +46,9 @@ BotInfo::BotInfo(const Anope::string &nnick, const Anope::string &nuser, const A
 	else
 		this->UnsetFlag(BI_CORE);
 
-	BotListByNick[this->nick] = this;
+	BotListByNick.insert(this->nick, this);
 	if (!this->uid.empty())
-		BotListByUID[this->uid] = this;
+		BotListByUID.insert(this->uid, this);
 
 	// If we're synchronised with the uplink already, send the bot.
 	if (Me && Me->IsSynced())
@@ -85,8 +85,8 @@ void BotInfo::SetNewNick(const Anope::string &newnick)
 
 	this->nick = newnick;
 
-	UserListByNick[this->nick] = this;
-	BotListByNick[this->nick] = this;
+	UserListByNick.insert(this->nick, this);
+	BotListByNick.insert(this->nick, this);
 }
 
 void BotInfo::RejoinAll()
diff --git a/src/botserv.cpp b/src/botserv.cpp
index 9149a0027..3d25136da 100644
--- a/src/botserv.cpp
+++ b/src/botserv.cpp
@@ -37,9 +37,9 @@ void get_botserv_stats(long *nrec, long *memuse)
 {
 	long count = 0, mem = 0;
 
-	for (botinfo_map::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
+	for (patricia_tree<BotInfo>::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
 	{
-		BotInfo *bi = it->second;
+		BotInfo *bi = *it;
 
 		++count;
 		mem += sizeof(*bi);
@@ -361,19 +361,9 @@ void botchanmsgs(User *u, ChannelInfo *ci, const Anope::string &buf)
 BotInfo *findbot(const Anope::string &nick)
 {
 	if (isdigit(nick[0]) && ircd->ts6)
-	{
-		botinfo_uid_map::const_iterator it = BotListByUID.find(nick);
-
-		if (it != BotListByUID.end())
-			return it->second;
-		return NULL;
-	}
-
-	botinfo_map::const_iterator it = BotListByNick.find(nick);
+		return BotListByUID.find(nick);
 
-	if (it != BotListByNick.end())
-		return it->second;
-	return NULL;
+	return BotListByNick.find(nick);
 }
 
 /*************************************************************************/
diff --git a/src/init.cpp b/src/init.cpp
index 239b9df48..26f2144fb 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -37,9 +37,9 @@ void introduce_user(const Anope::string &user)
 	}
 
 	/* We make the bots go online */
-	for (user_map::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; ++it)
+	for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; ++it)
 	{
-		User *u = it->second;
+		User *u = *it;
 
 		if (user.empty() || u->nick.equals_ci(user))
 		{
diff --git a/src/logger.cpp b/src/logger.cpp
index e2833b2c8..dbcb9cf60 100644
--- a/src/logger.cpp
+++ b/src/logger.cpp
@@ -36,9 +36,9 @@ void InitLogChannels(ServerConfig *config)
 				c->SetFlag(CH_LOGCHAN);
 				c->SetFlag(CH_PERSIST);
 
-				for (botinfo_map::const_iterator bit = BotListByNick.begin(), bit_end = BotListByNick.end(); bit != bit_end; ++bit)
+				for (patricia_tree<BotInfo>::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
 				{
-					BotInfo *bi = bit->second;
+					BotInfo *bi = *it;
 
 					if (bi->HasFlag(BI_CORE) && !c->FindUser(bi))
 					{
diff --git a/src/main.cpp b/src/main.cpp
index c87b0a7fc..a18d19a56 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -172,14 +172,16 @@ void do_restart_services()
 	if (quitmsg.empty())
 		quitmsg = "Restarting";
 	/* Send a quit for all of our bots */
-	for (botinfo_map::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
+	for (patricia_tree<BotInfo>::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
 	{
+		BotInfo *bi = *it;
+
 		/* Don't use quitmsg here, it may contain information you don't want people to see */
-		ircdproto->SendQuit(it->second, "Restarting");
+		ircdproto->SendQuit(bi, "Restarting");
 		/* Erase bots from the user list so they don't get nuked later on */
-		UserListByNick.erase(it->second->nick);
-		if (!it->second->GetUID().empty())
-			UserListByUID.erase(it->second->GetUID());
+		UserListByNick.erase(bi->nick);
+		if (!bi->GetUID().empty())
+			UserListByUID.erase(bi->GetUID());
 	}
 	ircdproto->SendSquit(Config->ServerName, quitmsg);
 	SocketEngine->Process();
@@ -212,20 +214,22 @@ static void services_shutdown()
 	if (started && UplinkSock)
 	{
 		/* Send a quit for all of our bots */
-		for (botinfo_map::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
+		for (patricia_tree<BotInfo>::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
 		{
+			BotInfo *bi = *it;
+
 			/* Don't use quitmsg here, it may contain information you don't want people to see */
-			ircdproto->SendQuit(it->second, "Shutting down");
+			ircdproto->SendQuit(bi, "Shutting down");
 			/* Erase bots from the user list so they don't get nuked later on */
-			UserListByNick.erase(it->second->nick);
-			if (!it->second->GetUID().empty())
-				UserListByUID.erase(it->second->GetUID());
+			UserListByNick.erase(bi->nick);
+			if (!bi->GetUID().empty())
+				UserListByUID.erase(bi->GetUID());
 		}
 
 		ircdproto->SendSquit(Config->ServerName, quitmsg);
 
 		while (!UserListByNick.empty())
-			delete UserListByNick.begin()->second;
+			delete UserListByNick.front();
 	}
 	SocketEngine->Process();
 	delete UplinkSock;
@@ -491,9 +495,9 @@ int main(int ac, char **av, char **envp)
 				FOREACH_MOD(I_OnServerDisconnect, OnServerDisconnect());
 
 				/* Clear all of our users, but not our bots */
-				for (user_map::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; )
+				for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end;)
 				{
-					User *u = it->second;
+					User *u = *it;
 					++it;
 
 					if (u->server != Me)
diff --git a/src/misc.cpp b/src/misc.cpp
index 3db15962b..7e02cc072 100644
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -618,16 +618,8 @@ bool nickIsServices(const Anope::string &tempnick, bool bot)
 		return true;
 	else if (!Config->s_GlobalNoticer.empty() && nick.equals_ci(Config->s_GlobalNoticer))
 		return true;
-	else if (!Config->s_BotServ.empty() && bot)
-	{
-		for (botinfo_map::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
-		{
-			BotInfo *bi = it->second;
-
-			if (nick.equals_ci(bi->nick))
-				return true;
-		}
-	}
+	else if (!Config->s_BotServ.empty() && bot && BotListByNick.find(nick))
+		return true;
 
 	return false;
 }
diff --git a/src/modes.cpp b/src/modes.cpp
index f28e6a4b4..4795e55fc 100644
--- a/src/modes.cpp
+++ b/src/modes.cpp
@@ -89,9 +89,9 @@ void SetDefaultMLock(ServerConfig *config)
 	}
 
 	/* Apply the new modes to channels */
-	for (botinfo_map::const_iterator it = BotListByNick.begin(); it != BotListByNick.end(); ++it)
+	for (patricia_tree<BotInfo>::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
 	{
-		BotInfo *bi = it->second;
+		BotInfo *bi = *it;
 
 		for (UChannelList::const_iterator cit = bi->chans.begin(); cit != bi->chans.end(); ++cit)
 		{
diff --git a/src/operserv.cpp b/src/operserv.cpp
index 2d509f25f..5f6f8c2be 100644
--- a/src/operserv.cpp
+++ b/src/operserv.cpp
@@ -571,9 +571,9 @@ XLine *SNLineManager::Add(BotInfo *bi, User *u, const Anope::string &mask, time_
 	{
 		Anope::string rreason = "G-Lined: " + reason;
 
-		for (user_map::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; )
+		for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end;)
 		{
-			User *user = it->second;
+			User *user = *it;
 			++it;
 
 			if (!is_oper(user) && Anope::Match(user->realname, x->Mask))
@@ -672,9 +672,9 @@ XLine *SQLineManager::Add(BotInfo *bi, User *u, const Anope::string &mask, time_
 		}
 		else
 		{
-			for (user_map::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; )
+			for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end;)
 			{
-				User *user = it->second;
+				User *user = *it;
 				++it;
 
 				if (!is_oper(user) && Anope::Match(user->nick, x->Mask))
diff --git a/src/servers.cpp b/src/servers.cpp
index 4f506d90d..3a19adcd1 100644
--- a/src/servers.cpp
+++ b/src/servers.cpp
@@ -86,9 +86,9 @@ Server::~Server()
 
 	if (Capab.HasFlag(CAPAB_NOQUIT) || Capab.HasFlag(CAPAB_QS))
 	{
-		for (user_map::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; )
+		for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end;)
 		{
-			User *u = it->second;
+			User *u = *it;
 			++it;
 
 			if (u->server == this)
diff --git a/src/sessions.cpp b/src/sessions.cpp
index f13683050..aa5d1c29b 100644
--- a/src/sessions.cpp
+++ b/src/sessions.cpp
@@ -45,7 +45,7 @@
 
 /*************************************************************************/
 
-session_map SessionList;
+patricia_tree<Session> SessionList;
 
 std::vector<Exception *> exceptions;
 
@@ -58,9 +58,9 @@ void get_session_stats(long &count, long &mem)
 	count = SessionList.size();
 	mem = sizeof(Session) * SessionList.size();
 
-	for (session_map::const_iterator it = SessionList.begin(), it_end = SessionList.end(); it != it_end; ++it)
+	for (patricia_tree<Session>::const_iterator it = SessionList.begin(), it_end = SessionList.end(); it != it_end; ++it)
 	{
-		Session *session = it->second;
+		Session *session = *it;
 
 		mem += session->host.length() + 1;
 	}
@@ -89,11 +89,7 @@ void get_exception_stats(long &count, long &mem)
 
 Session *findsession(const Anope::string &host)
 {
-	session_map::const_iterator it = SessionList.find(host);
-
-	if (it != SessionList.end())
-		return it->second;
-	return NULL;
+	return SessionList.find(host);
 }
 
 /* Attempt to add a host to the session list. If the addition of the new host
@@ -157,7 +153,7 @@ void add_session(const Anope::string &nick, const Anope::string &host, const Ano
 		session->count = 1;
 		session->hits = 0;
 
-		SessionList[session->host] = session;
+		SessionList.insert(session->host, session);
 	}
 }
 
diff --git a/src/users.cpp b/src/users.cpp
index c38aee472..27426819b 100644
--- a/src/users.cpp
+++ b/src/users.cpp
@@ -12,11 +12,8 @@
 #include "services.h"
 #include "modules.h"
 
-/* Hash maps used for users. Note UserListByUID will not be used on non-TS6 IRCds, and should never
- * be assumed to have users
- */
-user_map UserListByNick;
-user_uid_map UserListByUID;
+patricia_tree<User, std::equal_to<ci::string> > UserListByNick;
+patricia_tree<User> UserListByUID;
 
 int32 opcnt = 0;
 uint32 usercnt = 0, maxusercnt = 0;
@@ -45,9 +42,9 @@ User::User(const Anope::string &snick, const Anope::string &sident, const Anope:
 	this->uid = suid;
 	this->isSuperAdmin = 0;
 
-	UserListByNick[snick] = this;
+	UserListByNick.insert(snick, this);
 	if (!suid.empty())
-		UserListByUID[suid] = this;
+		UserListByUID.insert(suid, this);
 
 	this->nc = NULL;
 
@@ -71,7 +68,7 @@ void User::SetNewNick(const Anope::string &newnick)
 
 	this->nick = newnick;
 
-	UserListByNick[this->nick] = this;
+	UserListByNick.insert(this->nick, this);
 
 	OnAccess = false;
 	NickAlias *na = findnick(this->nick);
@@ -680,9 +677,9 @@ void get_user_stats(long &count, long &mem)
 {
 	count = mem = 0;
 
-	for (user_map::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; ++it)
+	for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; ++it)
 	{
-		User *user = it->second;
+		User *user = *it;
 
 		++count;
 		mem += sizeof(*user);
@@ -703,19 +700,9 @@ void get_user_stats(long &count, long &mem)
 User *finduser(const Anope::string &nick)
 {
 	if (isdigit(nick[0]) && ircd->ts6)
-	{
-		user_uid_map::const_iterator it = UserListByUID.find(nick);
-
-		if (it != UserListByUID.end())
-			return it->second;
-		return NULL;
-	}
-
-	user_map::const_iterator it = UserListByNick.find(nick);
+		return UserListByUID.find(nick);
 
-	if (it != UserListByNick.end())
-		return it->second;
-	return NULL;
+	return UserListByNick.find(nick);
 }
 
 /*************************************************************************/