From 4d02780f4c9d7659cf13cdf2e8ac4de28b7f722f Mon Sep 17 00:00:00 2001
From: Gunnar Beutner <gunnar.beutner@netways.de>
Date: Mon, 6 Aug 2012 12:03:38 +0200
Subject: [PATCH] Improved performance for Dictionary::Get.

---
 base/dictionary.cpp | 35 ++++++++++++++++++++++++++++++-----
 base/dictionary.h   |  1 +
 base/qstring.cpp    | 20 ++++++++++++++++++++
 base/qstring.h      |  5 +++++
 4 files changed, 56 insertions(+), 5 deletions(-)

diff --git a/base/dictionary.cpp b/base/dictionary.cpp
index 3ac9845fb..4b3c61678 100644
--- a/base/dictionary.cpp
+++ b/base/dictionary.cpp
@@ -22,23 +22,48 @@
 
 using namespace icinga;
 
+struct DictionaryKeyLessComparer
+{
+	bool operator()(const pair<String, Value>& a, const char *b)
+	{
+		return a.first < b;
+	}
+
+	bool operator()(const char *a, const pair<String, Value>& b)
+	{
+		return a < b.first;
+	}
+};
+
 /**
- * Retrieves a value from the dictionary.
+ * Restrieves a value from a dictionary.
  *
  * @param key The key whose value should be retrieved.
- * @returns The value or an empty value if the key was not found.
+ * @returns The value of an empty value if the key was not found.
  */
-Value Dictionary::Get(const String& key) const
+Value Dictionary::Get(const char *key) const
 {
 	map<String, Value>::const_iterator it;
-	it = m_Data.find(key);
 
-	if (it == m_Data.end())
+	it = std::lower_bound(m_Data.begin(), m_Data.end(), key, DictionaryKeyLessComparer());
+
+	if (it == m_Data.end() || DictionaryKeyLessComparer()(key, *it))
 		return Empty;
 
 	return it->second;
 }
 
+/**
+ * Retrieves a value from the dictionary.
+ *
+ * @param key The key whose value should be retrieved.
+ * @returns The value or an empty value if the key was not found.
+ */
+Value Dictionary::Get(const String& key) const
+{
+	return Get(key.CStr());
+}
+
 /**
  * Sets a value in the dictionary.
  *
diff --git a/base/dictionary.h b/base/dictionary.h
index 6dc8b2115..76ee95d50 100644
--- a/base/dictionary.h
+++ b/base/dictionary.h
@@ -36,6 +36,7 @@ public:
 
 	typedef map<String, Value>::iterator Iterator;
 
+	Value Get(const char *key) const;
 	Value Get(const String& key) const;
 	void Set(const String& key, const Value& value);
 	String Add(const Value& value);
diff --git a/base/qstring.cpp b/base/qstring.cpp
index bd26dc30e..a979002a7 100644
--- a/base/qstring.cpp
+++ b/base/qstring.cpp
@@ -199,6 +199,26 @@ bool icinga::operator!=(const char *lhs, const String& rhs)
 	return lhs != static_cast<std::string>(rhs);
 }
 
+bool icinga::operator<(const String& lhs, const char *rhs)
+{
+	return static_cast<std::string>(lhs) < rhs;
+}
+
+bool icinga::operator<(const char *lhs, const String& rhs)
+{
+	return lhs < static_cast<std::string>(rhs);
+}
+
+bool icinga::operator>(const String& lhs, const char *rhs)
+{
+	return static_cast<std::string>(lhs) > rhs;
+}
+
+bool icinga::operator>(const char *lhs, const String& rhs)
+{
+	return lhs > static_cast<std::string>(rhs);
+}
+
 String::Iterator icinga::range_begin(String& x)
 {
 	return x.Begin();
diff --git a/base/qstring.h b/base/qstring.h
index 6f1854062..c76fcf6a2 100644
--- a/base/qstring.h
+++ b/base/qstring.h
@@ -89,6 +89,11 @@ I2_BASE_API bool operator!=(const String& lhs, const String& rhs);
 I2_BASE_API bool operator!=(const String& lhs, const char *rhs);
 I2_BASE_API bool operator!=(const char *lhs, const String& rhs);
 
+I2_BASE_API bool operator<(const String& lhs, const char *rhs);
+I2_BASE_API bool operator<(const char *lhs, const String& rhs);
+I2_BASE_API bool operator>(const String& lhs, const char *rhs);
+I2_BASE_API bool operator>(const char *lhs, const String& rhs);
+
 I2_BASE_API String::Iterator range_begin(String& x);
 I2_BASE_API String::ConstIterator range_begin(const String& x);
 I2_BASE_API String::Iterator range_end(String& x);
-- 
2.40.0