From 5e77f3594f3abaf27c10a5b114b6dca2dc2bd3bd Mon Sep 17 00:00:00 2001
From: Dan Goodliffe <dan@randomdan.homeip.net>
Date: Sun, 5 Sep 2021 01:35:41 +0100
Subject: Introduce lightweight flatmap

---
 icespider/core/flatMap.h            | 68 +++++++++++++++++++++++++++++++++++++
 icespider/fcgi/cgiRequestBase.h     | 10 +++---
 icespider/unittests/Jamfile.jam     |  5 +++
 icespider/unittests/testFlatMap.cpp | 55 ++++++++++++++++++++++++++++++
 4 files changed, 133 insertions(+), 5 deletions(-)
 create mode 100644 icespider/core/flatMap.h
 create mode 100644 icespider/unittests/testFlatMap.cpp

diff --git a/icespider/core/flatMap.h b/icespider/core/flatMap.h
new file mode 100644
index 0000000..2b5d5be
--- /dev/null
+++ b/icespider/core/flatMap.h
@@ -0,0 +1,68 @@
+#ifndef ICESPIDER_CORE_FLATMAP_H
+#define ICESPIDER_CORE_FLATMAP_H
+
+#include <utility>
+#include <vector>
+
+namespace IceSpider {
+	template<typename K, typename M, typename Comp = std::less<K>>
+	class flatmap : std::vector<std::pair<std::decay_t<K>, std::decay_t<M>>> {
+	public:
+		using V = std::pair<std::decay_t<K>, std::decay_t<M>>;
+		using S = std::vector<V>;
+
+	private:
+		template<typename N> struct KeyComp {
+			bool
+			operator()(const V & v, const N & n) const
+			{
+				return c(v.first, n);
+			}
+			Comp c;
+		};
+
+	public:
+		flatmap() = default;
+		flatmap(std::size_t n)
+		{
+			reserve(n);
+		}
+
+		auto
+		insert(V v)
+		{
+			return S::insert(lower_bound(v.first), std::move(v));
+		}
+
+		template<typename N>
+		auto
+		lower_bound(const N & n) const
+		{
+			return std::lower_bound(begin(), end(), n, KeyComp<N> {});
+		}
+
+		template<typename N>
+		auto
+		find(const N & n) const
+		{
+			const auto lb = lower_bound(n);
+			if (lb == end()) {
+				return lb;
+			}
+			if (Comp {}(n, lb->first)) {
+				return end();
+			}
+			return lb;
+		}
+
+		using S::begin;
+		using S::empty;
+		using S::end;
+		using S::reserve;
+		using S::size;
+		using iterator = typename S::iterator;
+		using const_iterator = typename S::const_iterator;
+	};
+}
+
+#endif
diff --git a/icespider/fcgi/cgiRequestBase.h b/icespider/fcgi/cgiRequestBase.h
index 6a63a88..0c2b3a1 100644
--- a/icespider/fcgi/cgiRequestBase.h
+++ b/icespider/fcgi/cgiRequestBase.h
@@ -3,8 +3,8 @@
 
 #include <case_less.h>
 #include <core.h>
+#include <flatMap.h>
 #include <ihttpRequest.h>
-#include <map>
 #include <string_view>
 
 namespace IceSpider {
@@ -15,8 +15,8 @@ namespace IceSpider {
 		void initialize();
 
 	public:
-		using VarMap = std::map<std::string_view, const std::string_view>;
-		using HdrMap = std::map<std::string_view, const std::string_view, AdHoc::case_less>;
+		using VarMap = flatmap<std::string_view, const std::string_view>;
+		using HdrMap = flatmap<std::string_view, const std::string_view, AdHoc::case_less>;
 
 		[[nodiscard]] const PathElements & getRequestPath() const override;
 		[[nodiscard]] PathElements & getRequestPath() override;
@@ -35,10 +35,10 @@ namespace IceSpider {
 	private:
 		template<typename MapType> static OptionalString optionalLookup(const std::string_view & key, const MapType &);
 
-		VarMap envmap;
+		VarMap envmap {40};
 		StringMap qsmap;
 		StringMap cookiemap;
-		HdrMap hdrmap;
+		HdrMap hdrmap {15};
 		PathElements pathElements;
 	};
 }
diff --git a/icespider/unittests/Jamfile.jam b/icespider/unittests/Jamfile.jam
index 8dd497a..879d56a 100644
--- a/icespider/unittests/Jamfile.jam
+++ b/icespider/unittests/Jamfile.jam
@@ -149,3 +149,8 @@ lib test-api-lib :
 	<include>.
 	;
 
+run testFlatMap.cpp : : :
+	<library>boost_utf 
+	<define>BOOST_TEST_DYN_LINK
+	<use>../core//icespider-core
+	;
diff --git a/icespider/unittests/testFlatMap.cpp b/icespider/unittests/testFlatMap.cpp
new file mode 100644
index 0000000..12d6900
--- /dev/null
+++ b/icespider/unittests/testFlatMap.cpp
@@ -0,0 +1,55 @@
+#define BOOST_TEST_MODULE FlatMap
+#include <boost/test/unit_test.hpp>
+
+#include <flatMap.h>
+
+using TM = IceSpider::flatmap<std::string_view, int>;
+
+BOOST_TEST_DONT_PRINT_LOG_VALUE(TM::iterator)
+BOOST_TEST_DONT_PRINT_LOG_VALUE(TM::const_iterator)
+
+BOOST_FIXTURE_TEST_SUITE(sv2int, TM)
+
+BOOST_AUTO_TEST_CASE(is_empty)
+{
+	BOOST_CHECK_EQUAL(size(), 0);
+	BOOST_CHECK(empty());
+
+	BOOST_CHECK_EQUAL(find(""), end());
+}
+
+BOOST_AUTO_TEST_CASE(single)
+{
+	insert({"a", 1});
+
+	BOOST_CHECK_EQUAL(size(), 1);
+	BOOST_CHECK(!empty());
+	BOOST_CHECK_EQUAL(begin()->first, "a");
+	BOOST_CHECK_EQUAL(begin()->second, 1);
+	BOOST_CHECK_EQUAL(find("a"), begin());
+	BOOST_CHECK_EQUAL(find("b"), end());
+}
+
+BOOST_AUTO_TEST_CASE(several)
+{
+	insert({"c", 3});
+	BOOST_CHECK_EQUAL(lower_bound("a"), begin());
+
+	insert({"a", 1});
+	BOOST_CHECK_EQUAL(begin()->first, "a");
+
+	insert({"f", 6});
+
+	BOOST_CHECK_EQUAL(size(), 3);
+	BOOST_CHECK(!empty());
+	BOOST_CHECK_EQUAL(begin()->first, "a");
+	BOOST_CHECK_EQUAL(begin()->second, 1);
+	BOOST_CHECK_EQUAL(find("a"), begin());
+	BOOST_CHECK_EQUAL(find("b"), end());
+	BOOST_CHECK_NE(find("c"), end());
+	BOOST_CHECK_EQUAL(find("c")->second, 3);
+	BOOST_CHECK_NE(find("f"), end());
+	BOOST_CHECK_EQUAL(find("f")->second, 6);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
-- 
cgit v1.2.3