From c792c7f62df41c48d0d813a809e5415cbefa38b2 Mon Sep 17 00:00:00 2001 From: Adam Date: Sat, 13 Nov 2010 15:20:56 -0500 Subject: Switched the system for storing users, channels, and sesions to a patricia tree from STL's unordered_map, which was giving horrible performance. --- include/bots.h | 6 +- include/patricia.h | 210 +++++++++++++++++++++++++++++++++++++++++++++++++++++ include/services.h | 4 +- include/users.h | 10 +-- 4 files changed, 216 insertions(+), 14 deletions(-) create mode 100644 include/patricia.h (limited to 'include') 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 > botinfo_map; -typedef unordered_map_namespace::unordered_map botinfo_uid_map; -extern CoreExport botinfo_map BotListByNick; -extern CoreExport botinfo_uid_map BotListByUID; +extern CoreExport patricia_tree > BotListByNick; +extern CoreExport patricia_tree 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 struct patricia_elem +{ + unsigned int bit; + patricia_elem *up, *one, *zero; + typename std::list::iterator node; + Anope::string key; + Data *data; +}; + +template > +class patricia_tree +{ + Compare comp; + + patricia_elem *root; + std::list list; + + public: + + patricia_tree() + { + this->root = NULL; + } + + virtual ~patricia_tree() + { + while (this->root) + this->erase(this->root->key); + } + + typedef typename std::list::iterator iterator; + typedef typename std::list::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 *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 *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 *newelem = new patricia_elem(); + 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 *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 *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 *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 #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 session_map; -extern CoreExport session_map SessionList; +extern CoreExport patricia_tree 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 > user_map; -typedef unordered_map_namespace::unordered_map user_uid_map; - -extern CoreExport user_map UserListByNick; -extern CoreExport user_uid_map UserListByUID; +extern CoreExport patricia_tree > UserListByNick; +extern CoreExport patricia_tree UserListByUID; class CoreExport ChannelStatus : public Flags { -- cgit