diff options
Diffstat (limited to 'include')
| -rw-r--r-- | include/bots.h | 6 | ||||
| -rw-r--r-- | include/patricia.h | 210 | ||||
| -rw-r--r-- | include/services.h | 4 | ||||
| -rw-r--r-- | include/users.h | 10 |
4 files changed, 216 insertions, 14 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> { |