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

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

23 files changed, 293 insertions, 122 deletions

diff --git a/include/bots.h b/include/bots.h
index 0a84cce71..2c1757a47 100644
--- a/include/bots.h
+++ b/include/bots.h
@@ -12,10 +12,8 @@
 
 class BotInfo;
 
-typedef unordered_map_namespace::unordered_map<Anope::string, BotInfo *, ci::hash, std::equal_to<ci::string> > botinfo_map;
-typedef unordered_map_namespace::unordered_map<Anope::string, BotInfo *, Anope::hash> botinfo_uid_map;
-extern CoreExport botinfo_map BotListByNick;
-extern CoreExport botinfo_uid_map BotListByUID;
+extern CoreExport patricia_tree<BotInfo, std::equal_to<ci::string> > BotListByNick;
+extern CoreExport patricia_tree<BotInfo> BotListByUID;
 
 /** Flags settable on a bot
  */
diff --git a/include/patricia.h b/include/patricia.h
new file mode 100644
index 000000000..73f5c22b9
--- /dev/null
+++ b/include/patricia.h
@@ -0,0 +1,210 @@
+
+/* Gets the bit-th bit from key */
+#define GET_BIT(key, bit) (key[bit / 8] & (1 << (bit & 7)))
+/* Checks if the bit-th bit from key1 and key2 differ, returns 1 if they do */
+#define GET_BIT_XOR(key1, key2, bit) ((key1[bit / 8] ^ key2[bit / 8]) & (1 << (bit & 7)))
+
+template<typename Data> struct patricia_elem
+{
+	unsigned int bit;
+	patricia_elem<Data> *up, *one, *zero;
+	typename std::list<Data *>::iterator node;
+	Anope::string key;
+	Data *data;
+};
+
+template<typename Data, typename Compare = std::equal_to<Anope::string> >
+class patricia_tree
+{
+	Compare comp;
+
+	patricia_elem<Data> *root;
+	std::list<Data *> list;
+
+ public:
+
+	patricia_tree()
+	{
+		this->root = NULL;
+	}
+
+	virtual ~patricia_tree()
+	{
+		while (this->root)
+			this->erase(this->root->key);
+	}
+
+	typedef typename std::list<Data *>::iterator iterator;
+	typedef typename std::list<Data *>::const_iterator const_iterator;
+
+	inline iterator begin() { return this->list.begin(); }
+	inline iterator end() { return this->list.end(); }
+
+	inline const const_iterator begin() const { return this->list.begin(); }
+	inline const const_iterator end() const { return this->list.end(); }
+
+	inline Data *front() { return this->list.front(); }
+	inline Data *back() { return this->list.back(); }
+
+	inline size_t size() const { return this->list.size(); }
+	inline bool empty() const { return this->list.empty(); }
+
+	Data *find(const Anope::string &key)
+	{
+		size_t keylen = key.length();
+		patricia_elem<Data> *prev = NULL, *cur = this->root;
+		bool bitval;
+		while (cur && (!prev || prev->bit < cur->bit))
+		{
+			prev = cur;
+
+			if (cur->bit / 8 < keylen)
+				bitval = GET_BIT(key, cur->bit);
+			else
+				bitval = false;
+
+			cur = bitval ? cur->one : cur->zero;
+		}
+
+		if (cur && comp(cur->key, key))
+			return cur->data;
+
+		return NULL;
+	}
+
+	void insert(const Anope::string &key, Data *data)
+	{
+		if (key.empty() || data == NULL)
+			throw CoreExport;
+
+		size_t keylen = key.length();
+		patricia_elem<Data> *prev = NULL, *cur = this->root;
+		bool bitval;
+		while (cur && (!prev || prev->bit < cur->bit))
+		{
+			prev = cur;
+
+			if (cur->bit / 8 < keylen)
+				bitval = GET_BIT(key, cur->bit);
+			else
+				bitval = false;
+
+			cur = bitval ? cur->one : cur->zero;
+		}
+
+		if (cur && comp(cur->key, key))
+			return;
+
+		patricia_elem<Data> *newelem = new patricia_elem<Data>();
+		newelem->up = prev;
+		newelem->key = key;
+		newelem->data = data;
+
+		if (!cur)
+			newelem->bit = prev ? prev->bit + 1 : 0;
+		else
+			for (newelem->bit = 0; GET_BIT_XOR(key, cur->key, newelem->bit) == 0; ++newelem->bit);
+
+		patricia_elem<Data> *place = prev;
+		while (place && newelem->bit < place->bit)
+		{
+			prev = place;
+			place = place->up;
+		}
+
+		if (GET_BIT(key, newelem->bit))
+		{
+			newelem->one = newelem;
+			newelem->zero = place == prev ? cur : prev;
+		}
+		else
+		{
+			newelem->zero = newelem;
+			newelem->one = place == prev ? cur : prev;
+		}
+
+		if (place != prev)
+		{
+			prev->up = newelem;
+			newelem->up = place;
+		}
+
+		if (place)
+		{
+			bitval = GET_BIT(key, place->bit);
+			if (bitval)
+				place->one = newelem;
+			else
+				place->zero = newelem;
+		}
+		else
+			this->root = newelem;
+
+		this->list.push_front(data);
+		newelem->node = this->list.begin();
+	}
+
+	Data *erase(const Anope::string &key)
+	{
+		size_t keylen = key.length();
+		patricia_elem<Data> *prev = NULL, *cur = this->root;
+		bool bitval;
+		while (cur && (!prev || prev->bit < cur->bit))
+		{
+			prev = cur;
+
+			if (cur->bit / 8 < keylen)
+				bitval = GET_BIT(key, cur->bit);
+			else
+				bitval = false;
+
+			cur = bitval ? cur->one : cur->zero;
+		}
+
+		if (!cur || comp(cur->key, key) == false)
+			return NULL;
+
+		patricia_elem<Data> *other = (bitval ? prev->zero : prev->one);
+
+		if (!prev->up)
+			this->root = other;
+		else if (prev->up->zero == prev)
+			prev->up->zero = other;
+		else
+			prev->up->one = other;
+
+		if (prev->zero && prev->zero->up == prev)
+			prev->zero->up = prev->up;
+		if (prev->one && prev->one->up == prev)
+			prev->one->up = prev->up;
+
+		if (cur != prev)
+		{
+			if (!cur->up)
+				this->root = prev;
+			else if (cur->up->zero == cur)
+				cur->up->zero = prev;
+			else
+				cur->up->one = prev;
+
+			if (cur->zero && cur->zero->up == cur)
+				cur->zero->up = prev;
+			if (cur->one && cur->one->up == cur)
+				cur->one->up = prev;
+
+			prev->one = cur->one;
+			prev->zero = cur->zero;
+			prev->up = cur->up;
+			prev->bit = cur->bit;
+		}
+
+		this->list.erase(cur->node);
+
+		Data *data = cur->data;
+		delete cur;
+
+		return data;
+	}
+};
+
+
diff --git a/include/services.h b/include/services.h
index 1b14f5e88..182444238 100644
--- a/include/services.h
+++ b/include/services.h
@@ -195,6 +195,7 @@ extern "C" void __pfnBkCheck() {}
 #include <set>
 
 #include "anope.h"
+#include "patricia.h"
 
 /** This class can be used on its own to represent an exception, or derived to represent a module-specific exception.
  * When a module whishes to abort, e.g. within a constructor, it should throw an exception using ModuleException or
@@ -844,8 +845,7 @@ struct Exception
 
 /*************************************************************************/
 
-typedef unordered_map_namespace::unordered_map<Anope::string, Session *, Anope::hash> session_map;
-extern CoreExport session_map SessionList;
+extern CoreExport patricia_tree<Session> SessionList;
 
 struct Session
 {
diff --git a/include/users.h b/include/users.h
index 776ce450c..6aed13548 100644
--- a/include/users.h
+++ b/include/users.h
@@ -8,14 +8,8 @@
 #ifndef USERS_H
 #define USERS_H
 
-/* Hash maps used for users. Note UserListByUID will not be used on non-TS6 IRCds, and should never
- * be assumed to have users
- */
-typedef unordered_map_namespace::unordered_map<Anope::string, User *, ci::hash, std::equal_to<ci::string> > user_map;
-typedef unordered_map_namespace::unordered_map<Anope::string, User *, Anope::hash> user_uid_map;
-
-extern CoreExport user_map UserListByNick;
-extern CoreExport user_uid_map UserListByUID;
+extern CoreExport patricia_tree<User, std::equal_to<ci::string> > UserListByNick;
+extern CoreExport patricia_tree<User> UserListByUID;
 
 class CoreExport ChannelStatus : public Flags<ChannelModeName, CMODE_END * 2>
 {
diff --git a/modules/core/bs_botlist.cpp b/modules/core/bs_botlist.cpp
index 425cf48ab..a8487b03b 100644
--- a/modules/core/bs_botlist.cpp
+++ b/modules/core/bs_botlist.cpp
@@ -30,9 +30,9 @@ class CommandBSBotList : public Command
 			return MOD_CONT;
 		}
 
-		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;
 
 			if (!bi->HasFlag(BI_PRIVATE))
 			{
@@ -47,9 +47,9 @@ class CommandBSBotList : public Command
 		{
 			u->SendMessage(BotServ, BOT_BOTLIST_PRIVATE_HEADER);
 
-			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;
 
 				if (bi->HasFlag(BI_PRIVATE))
 				{
diff --git a/modules/core/cs_akick.cpp b/modules/core/cs_akick.cpp
index 579c013f2..175b20047 100644
--- a/modules/core/cs_akick.cpp
+++ b/modules/core/cs_akick.cpp
@@ -207,9 +207,9 @@ class CommandCSAKick : public Command
 		{
 			/* Match against all currently online users with equal or
 			 * higher access. - Viper */
-			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 *u2 = it->second;
+				User *u2 = *it;
 
 				if ((check_access(u2, ci, CA_FOUNDER) || get_access(u2, ci) >= get_access(u, ci)) && match_usermask(mask, u2))
 				{
diff --git a/modules/core/db_plain.cpp b/modules/core/db_plain.cpp
index 1c8de7fee..19acd810d 100644
--- a/modules/core/db_plain.cpp
+++ b/modules/core/db_plain.cpp
@@ -924,9 +924,9 @@ class DBPlain : public Module
 			FOREACH_MOD(I_OnDatabaseWriteMetadata, OnDatabaseWriteMetadata(WriteMetadata, na));
 		}
 
-		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;
 
 			db << "BI " << bi->nick << " " << bi->GetIdent() << " " << bi->host << " " << bi->created << " " << bi->chancount << " :" << bi->realname << endl;
 			if (bi->HasFlag(BI_PRIVATE))
diff --git a/modules/core/os_noop.cpp b/modules/core/os_noop.cpp
index 04bf0a7e4..56b69fcb7 100644
--- a/modules/core/os_noop.cpp
+++ b/modules/core/os_noop.cpp
@@ -38,9 +38,9 @@ class CommandOSNOOP : public Command
 			u->SendMessage(OperServ, OPER_NOOP_SET, server.c_str());
 
 			/* Kill all the IRCops of the server */
-			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; ++it)
 			{
-				User *u2 = it->second;
+				User *u2 = *it;
 				++it;
 
 				if (u2 && is_oper(u2) && Anope::Match(u2->server->GetName(), server, true))
diff --git a/modules/core/os_session.cpp b/modules/core/os_session.cpp
index 17b2a7aa1..fc85c304b 100644
--- a/modules/core/os_session.cpp
+++ b/modules/core/os_session.cpp
@@ -134,9 +134,9 @@ class CommandOSSession : public Command
 			u->SendMessage(OperServ, OPER_SESSION_LIST_HEADER, mincount);
 			u->SendMessage(OperServ, OPER_SESSION_LIST_COLHEAD);
 
-			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;
 
 				if (session->count >= mincount)
 					u->SendMessage(OperServ, OPER_SESSION_LIST_FORMAT, session->count, session->host.c_str());
diff --git a/modules/core/os_staff.cpp b/modules/core/os_staff.cpp
index f5c80b3ad..6b8b1cb43 100644
--- a/modules/core/os_staff.cpp
+++ b/modules/core/os_staff.cpp
@@ -33,9 +33,9 @@ class CommandOSStaff : public Command
 			if (na)
 			{
 				/* We have to loop all users as some may be logged into an account but not a nick */
-				for (user_map::iterator uit = UserListByNick.begin(), uit_end = UserListByNick.end(); uit != uit_end; ++uit)
+				for (patricia_tree<User>::const_iterator uit = UserListByNick.begin(), uit_end = UserListByNick.end(); uit != uit_end; ++uit)
 				{
-					User *u2 = uit->second;
+					User *u2 = *uit;
 
 					if (u2->Account() && u2->Account() == na->nc)
 					{
diff --git a/modules/core/os_userlist.cpp b/modules/core/os_userlist.cpp
index 4c3355006..ab1f3adab 100644
--- a/modules/core/os_userlist.cpp
+++ b/modules/core/os_userlist.cpp
@@ -50,9 +50,9 @@ class CommandOSUserList : public Command
 		{
 			u->SendMessage(OperServ, OPER_USERLIST_HEADER);
 
-			for (user_map::const_iterator uit = UserListByNick.begin(), uit_end = UserListByNick.end(); uit != uit_end; ++uit)
+			for (patricia_tree<User>::const_iterator it = UserListByNick.begin(), it_end = UserListByNick.end(); it != it_end; ++it)
 			{
-				User *u2 = uit->second;
+				User *u2 = *it;
 
 				if (!pattern.empty())
 				{
@@ -60,8 +60,8 @@ class CommandOSUserList : public Command
 					if (!Anope::Match(mask, pattern))
 						continue;
 					if (!Modes.empty())
-						for (std::list<UserModeName>::iterator it = Modes.begin(), it_end = Modes.end(); it != it_end; ++it)
-							if (!u2->HasMode(*it))
+						for (std::list<UserModeName>::iterator mit = Modes.begin(), mit_end = Modes.end(); mit != mit_end; ++mit)
+							if (!u2->HasMode(*mit))
 								continue;
 				}
 				u->SendMessage(OperServ, OPER_USERLIST_RECORD, u2->nick.c_str(), u2->GetIdent().c_str(), u2->GetDisplayedHost().c_str());
diff --git a/modules/extra/db_mysql.cpp b/modules/extra/db_mysql.cpp
index fc9f47df9..6f18077f8 100644
--- a/modules/extra/db_mysql.cpp
+++ b/modules/extra/db_mysql.cpp
@@ -951,9 +951,9 @@ class DBMySQL : public Module
 			FOREACH_MOD(I_OnDatabaseWriteMetadata, OnDatabaseWriteMetadata(WriteChannelMetadata, CurChannel));
 		}
 
-		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)
 		{
-			CurBot = it->second;
+			CurBot = *it;
 			FOREACH_MOD(I_OnDatabaseWriteMetadata, OnDatabaseWriteMetadata(WriteBotMetadata, CurBot));
 
 			/* This is for the core bots, bots added by users are already handled by an event */
@@ -1525,8 +1525,8 @@ static void SaveDatabases()
 
 	me->RunQuery("TRUNCATE TABLE `anope_bs_core`");
 
-	for (botinfo_map::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
-		me->OnBotCreate(it->second);
+	for (patricia_tree<BotInfo>::const_iterator it = BotListByNick.begin(), it_end = BotListByNick.end(); it != it_end; ++it)
+		me->OnBotCreate(*it);
 
 	me->RunQuery("TRUNCATE TABLE `anope_cs_info`");
 	me->RunQuery("TRUNCATE TABLE `anope_bs_badwords`");
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);
 }
 
 /*************************************************************************/