Merge branch 'master+flatmap'

6 files changed, 395 insertions, 8 deletions

diff --git a/include/configparser.h b/include/configparser.h
index f46d143ae..02619e759 100644
--- a/include/configparser.h
+++ b/include/configparser.h
@@ -41,7 +41,7 @@ enum ParseFlags
 struct ParseStack
 {
 	std::vector<std::string> reading;
-	std::map<std::string, std::string> vars;
+	insp::flat_map<std::string, std::string> vars;
 	ConfigDataHash& output;
 	ConfigFileCache& FilesOutput;
 	std::stringstream& errstr;
diff --git a/include/configreader.h b/include/configreader.h
index 88279004f..57d7ab069 100644
--- a/include/configreader.h
+++ b/include/configreader.h
@@ -162,8 +162,9 @@ struct CommandLineConf
 class CoreExport OperInfo : public refcountbase
 {
  public:
-	std::set<std::string> AllowedOperCommands;
-	std::set<std::string> AllowedPrivs;
+	typedef insp::flat_set<std::string> PrivSet;
+	PrivSet AllowedOperCommands;
+	PrivSet AllowedPrivs;
 
 	/** Allowed user modes from oper classes. */
 	std::bitset<64> AllowedUserModes;
@@ -230,7 +231,7 @@ class CoreExport ServerConfig
 
 	/** Index of valid oper blocks and types
 	 */
-	typedef std::map<std::string, reference<OperInfo> > OperIndex;
+	typedef insp::flat_map<std::string, reference<OperInfo> > OperIndex;
 
 	/** Get a configuration tag
 	 * @param tag The name of the tag to get
diff --git a/include/extensible.h b/include/extensible.h
index 87fe65ccb..86e0d6b07 100644
--- a/include/extensible.h
+++ b/include/extensible.h
@@ -75,7 +75,7 @@ class CoreExport ExtensionItem : public ServiceProvider, public usecountbase
 class CoreExport Extensible : public classbase
 {
  public:
-	typedef std::map<reference<ExtensionItem>,void*> ExtensibleStore;
+	typedef insp::flat_map<reference<ExtensionItem>, void*> ExtensibleStore;
 
 	// Friend access for the protected getter/setter
 	friend class ExtensionItem;
diff --git a/include/flat_map.h b/include/flat_map.h
new file mode 100644
index 000000000..bef1404e4
--- /dev/null
+++ b/include/flat_map.h
@@ -0,0 +1,383 @@
+/*
+ * InspIRCd -- Internet Relay Chat Daemon
+ *
+ *   Copyright (C) 2014 Attila Molnar <attilamolnar@hush.com>
+ *
+ * This file is part of InspIRCd.  InspIRCd is free software: you can
+ * redistribute it and/or modify it under the terms of the GNU General Public
+ * License as published by the Free Software Foundation, version 2.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+
+#pragma once
+
+#include <vector>
+
+namespace insp
+{
+
+namespace detail
+{
+
+template <typename T, typename Comp>
+class map_pair_compare : public Comp
+{
+	typedef T value_type;
+	typedef typename value_type::first_type key_type;
+
+ public:
+	bool operator()(const value_type& x, const value_type& y) const
+	{
+		return Comp::operator()(x.first, y.first);
+	}
+
+	bool operator()(const value_type& x, const key_type& y) const
+	{
+		return Comp::operator()(x.first, y);
+	}
+
+	bool operator()(const key_type& x, const value_type& y) const
+	{
+		return Comp::operator()(x, y.first);
+	}
+};
+
+template <typename Val, typename Comp>
+class map_value_compare : public std::binary_function<Val, Val, bool>
+{
+ public:
+	// Constructor should be private
+
+	bool operator()(const Val& x, const Val& y) const
+	{
+		Comp c;
+		return c(x.first, y.first);
+	}
+};
+
+template <typename T, typename Comp, typename Key = T, typename ElementComp = Comp>
+class flat_map_base
+{
+ protected:
+	typedef std::vector<T> storage_type;
+	storage_type vect;
+
+ public:
+	typedef typename storage_type::iterator iterator;
+	typedef typename storage_type::const_iterator const_iterator;
+	typedef typename storage_type::reverse_iterator reverse_iterator;
+	typedef typename storage_type::const_reverse_iterator const_reverse_iterator;
+
+	typedef typename storage_type::size_type size_type;
+	typedef typename storage_type::difference_type difference_type;
+	typedef Key key_type;
+	typedef T value_type;
+
+	typedef Comp key_compare;
+	typedef ElementComp value_compare;
+
+	flat_map_base() { }
+
+	flat_map_base(const flat_map_base& other)
+		: vect(other.vect)
+	{
+	}
+
+	size_type size() const { return vect.size(); }
+	bool empty() const { return vect.empty(); }
+	size_type capacity() const { return vect.capacity(); }
+	size_type max_size() const { return vect.max_size(); }
+
+	void clear() { vect.clear(); }
+	void reserve(size_type n) { vect.reserve(n); }
+
+	iterator begin() { return vect.begin(); }
+	iterator end() { return vect.end(); }
+	reverse_iterator rbegin() { return vect.rbegin(); }
+	reverse_iterator rend() { return vect.rend(); }
+
+	const_iterator begin() const { return vect.begin(); }
+	const_iterator end() const { return vect.end(); }
+	const_reverse_iterator rbegin() const { return vect.rbegin(); }
+	const_reverse_iterator rend() const { return vect.rend(); }
+
+	key_compare key_comp() const { return Comp(); }
+
+	iterator erase(iterator it) { return vect.erase(it); }
+	iterator erase(iterator first, iterator last) { return vect.erase(first, last); }
+	size_type erase(const key_type& x)
+	{
+		size_type n = vect.size();
+		std::pair<iterator, iterator> itpair = equal_range(x);
+		vect.erase(itpair.first, itpair.second);
+		return n - vect.size();
+	}
+
+	iterator find(const key_type& x)
+	{
+		value_compare c;
+		iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
+		if ((it != vect.end()) && (!c(x, *it)))
+			return it;
+		return vect.end();
+	}
+
+	const_iterator find(const key_type& x) const
+	{
+		// Same as above but this time we return a const_iterator
+		value_compare c;
+		const_iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
+		if ((it != vect.end()) && (!c(x, *it)))
+			return it;
+		return vect.end();
+	}
+
+	std::pair<iterator, iterator> equal_range(const key_type& x)
+	{
+		return std::equal_range(vect.begin(), vect.end(), x, value_compare());
+	}
+
+	std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
+	{
+		return std::equal_range(vect.begin(), vect.end(), x, value_compare());
+	}
+
+	iterator lower_bound(const key_type& x)
+	{
+		return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
+	}
+
+	const_iterator lower_bound(const key_type& x) const
+	{
+		return std::lower_bound(vect.begin(), vect.end(), x, value_compare());
+	}
+
+	iterator upper_bound(const key_type& x)
+	{
+		return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
+	}
+
+	const_iterator upper_bound(const key_type& x) const
+	{
+		return std::upper_bound(vect.begin(), vect.end(), x, value_compare());
+	}
+
+	size_type count(const key_type& x) const
+	{
+		std::pair<const_iterator, const_iterator> itpair = equal_range(x);
+		return std::distance(itpair.first, itpair.second);
+	}
+
+ protected:
+	std::pair<iterator, bool> insert_single(const value_type& x)
+	{
+		bool inserted = false;
+
+		value_compare c;
+		iterator it = std::lower_bound(vect.begin(), vect.end(), x, c);
+		if ((it == vect.end()) || (c(x, *it)))
+		{
+			inserted = true;
+			it = vect.insert(it, x);
+		}
+		return std::make_pair(it, inserted);
+	}
+
+	iterator insert_multi(const value_type& x)
+	{
+		iterator it = std::lower_bound(vect.begin(), vect.end(), x, value_compare());
+		return vect.insert(it, x);
+	}
+};
+
+} // namespace detail
+
+template <typename T, typename Comp = std::less<T> >
+class flat_set : public detail::flat_map_base<T, Comp>
+{
+	typedef detail::flat_map_base<T, Comp> base_t;
+
+ public:
+	typedef typename base_t::iterator iterator;
+	typedef typename base_t::value_type value_type;
+
+	flat_set() { }
+
+	template <typename InputIterator>
+	flat_set(InputIterator first, InputIterator last)
+	{
+		this->insert(first, last);
+	}
+
+	flat_set(const flat_set& other)
+		: base_t(other)
+	{
+	}
+
+	std::pair<iterator, bool> insert(const value_type& x)
+	{
+		return this->insert_single(x);
+	}
+
+	template <typename InputIterator>
+	void insert(InputIterator first, InputIterator last)
+	{
+		for (; first != last; ++first)
+			this->insert_single(*first);
+	}
+
+	void swap(flat_set& other)
+	{
+		base_t::vect.swap(other.vect);
+	}
+};
+
+template <typename T, typename Comp = std::less<T> >
+class flat_multiset : public detail::flat_map_base<T, Comp>
+{
+	typedef detail::flat_map_base<T, Comp> base_t;
+
+ public:
+	typedef typename base_t::iterator iterator;
+	typedef typename base_t::value_type value_type;
+
+	flat_multiset() { }
+
+	template <typename InputIterator>
+	flat_multiset(InputIterator first, InputIterator last)
+	{
+		this->insert(first, last);
+	}
+
+	flat_multiset(const flat_multiset& other)
+		: base_t(other)
+	{
+	}
+
+	iterator insert(const value_type& x)
+	{
+		return this->insert_multi(x);
+	}
+
+	template <typename InputIterator>
+	void insert(InputIterator first, InputIterator last)
+	{
+		for (; first != last; ++first)
+			insert_multi(*first);
+	}
+
+	void swap(flat_multiset& other)
+	{
+		base_t::vect.swap(other.vect);
+	}
+};
+
+template <typename T, typename U, typename Comp = std::less<T> >
+class flat_map : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> >
+{
+	typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> > base_t;
+
+ public:
+	typedef typename base_t::iterator iterator;
+	typedef typename base_t::key_type key_type;
+	typedef typename base_t::value_type value_type;
+	typedef U mapped_type;
+	typedef typename base_t::value_compare value_compare;
+
+	flat_map() { }
+
+	template <typename InputIterator>
+	flat_map(InputIterator first, InputIterator last)
+	{
+		insert(first, last);
+	}
+
+	flat_map(const flat_map& other)
+		: base_t(other)
+	{
+	}
+
+	std::pair<iterator, bool> insert(const value_type& x)
+	{
+		return this->insert_single(x);
+	}
+
+	template <typename InputIterator>
+	void insert(InputIterator first, InputIterator last)
+	{
+		for (; first != last; ++first)
+			this->insert_single(*first);
+	}
+
+	void swap(flat_map& other)
+	{
+		base_t::vect.swap(other.vect);
+	}
+
+	mapped_type& operator[](const key_type& x)
+	{
+		return insert(std::make_pair(x, mapped_type())).first->second;
+	}
+
+	value_compare value_comp() const
+	{
+		return value_compare();
+	}
+};
+
+template <typename T, typename U, typename Comp = std::less<T> >
+class flat_multimap : public detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> >
+{
+	typedef detail::flat_map_base<std::pair<T, U>, Comp, T, detail::map_pair_compare<std::pair<T, U>, Comp> > base_t;
+
+ public:
+	typedef typename base_t::iterator iterator;
+	typedef typename base_t::value_type value_type;
+	typedef U mapped_type;
+	typedef typename base_t::value_compare value_compare;
+
+	flat_multimap() { }
+
+	template <typename InputIterator>
+	flat_multimap(InputIterator first, InputIterator last)
+	{
+		this->insert(first, last);
+	}
+
+	flat_multimap(const flat_multimap& other)
+		: base_t(other)
+	{
+	}
+
+	iterator insert(const value_type& x)
+	{
+		return this->insert_multi(x);
+	}
+
+	template <typename InputIterator>
+	void insert(InputIterator first, InputIterator last)
+	{
+		for (; first != last; ++first)
+			this->insert_multi(*first);
+	}
+
+	void swap(flat_multimap& other)
+	{
+		base_t::vect.swap(other.vect);
+	}
+
+	value_compare value_comp() const
+	{
+		return value_compare();
+	}
+};
+
+} // namespace insp
diff --git a/include/inspircd.h b/include/inspircd.h
index eaca34a9b..ef19c6d26 100644
--- a/include/inspircd.h
+++ b/include/inspircd.h
@@ -44,6 +44,7 @@
 #include <vector>
 
 #include "intrusive_list.h"
+#include "flat_map.h"
 #include "compat.h"
 #include "aligned_storage.h"
 #include "typedefs.h"
diff --git a/include/mode.h b/include/mode.h
index 364562dd7..eebfbedd6 100644
--- a/include/mode.h
+++ b/include/mode.h
@@ -473,8 +473,6 @@ class CoreExport ModeWatcher : public classbase
 	virtual void AfterMode(User* source, User* dest, Channel* channel, const std::string& parameter, bool adding);
 };
 
-typedef std::multimap<std::string, ModeWatcher*>::iterator ModeWatchIter;
-
 /** The mode parser handles routing of modes and handling of mode strings.
  * It marshalls, controls and maintains both ModeWatcher and ModeHandler classes,
  * parses client to server MODE strings for user and channel modes, and performs
@@ -490,6 +488,10 @@ class CoreExport ModeParser : public fakederef<ModeParser>
 	typedef TR1NS::unordered_map<std::string, ModeHandler*, irc::insensitive, irc::StrHashComp> ModeHandlerMap;
 
  private:
+	/** Type of the container that maps mode names to ModeWatchers
+	 */
+ 	typedef insp::flat_multimap<std::string, ModeWatcher*> ModeWatcherMap;
+
 	/** Last item in the ModeType enum
 	 */
 	static const unsigned int MODETYPE_LAST = 2;
@@ -524,7 +526,7 @@ class CoreExport ModeParser : public fakederef<ModeParser>
 
 	/** Mode watcher classes
 	 */
-	std::multimap<std::string, ModeWatcher*> modewatchermap;
+	ModeWatcherMap modewatchermap;
 
 	/** Last processed mode change
 	 */