Allow checking of overlapped ports. A bit of sensible thought prevents this from being O(n^2)

git-svn-id: http://svn.inspircd.org/repository/trunk/inspircd@5694 e03df62e-2008-0410-955e-edbf42e46eb7

2 files changed, 51 insertions, 3 deletions

diff --git a/include/hashcomp.h b/include/hashcomp.h
index 013523df3..11a491d62 100644
--- a/include/hashcomp.h
+++ b/include/hashcomp.h
@@ -333,10 +333,22 @@ namespace irc
 		/** Ending port in a range of ports
 		 */
 		long range_end;
+		/** Allow overlapped port ranges
+		 */
+		bool overlapped;
+		/** Used to determine overlapping of ports
+		 * without O(n) algorithm being used
+		 */
+		std::map<long, bool> overlap_set;
+		/** Returns true if val overlaps an existing range
+		 */
+		bool Overlaps(long val);
 	 public:
 		/** Create a portparser and fill it with the provided data
+		 * @param source The source text to parse from
+		 * @param allow_overlapped Allow overlapped ranges
 		 */
-		portparser(const std::string &source);
+		portparser(const std::string &source, bool allow_overlapped = true);
 		/** Frees the internal commasepstream object
 		 */
 		~portparser();
diff --git a/src/hashcomp.cpp b/src/hashcomp.cpp
index e1dbad06f..f7a67b13a 100644
--- a/src/hashcomp.cpp
+++ b/src/hashcomp.cpp
@@ -386,9 +386,10 @@ std::string& irc::stringjoiner::GetJoined()
 	return joined;
 }
 
-irc::portparser::portparser(const std::string &source) : in_range(0), range_begin(0), range_end(0)
+irc::portparser::portparser(const std::string &source, bool allow_overlapped) : in_range(0), range_begin(0), range_end(0), overlapped(allow_overlapped)
 {
 	sep = new irc::commasepstream(source);
+	overlap_set.clear();
 }
 
 irc::portparser::~portparser()
@@ -396,13 +397,40 @@ irc::portparser::~portparser()
 	delete sep;
 }
 
+bool irc::portparser::Overlaps(long val)
+{
+	if (!overlapped)
+		return false;
+
+	if (overlap_set.find(val) == overlap_set.end())
+	{
+		overlap_set[val] = true;
+		return false;
+	}
+	else
+		return true;
+}
+
 long irc::portparser::GetToken()
 {
 	if (in_range > 0)
 	{
 		in_range++;
 		if (in_range <= range_end)
-			return in_range;
+		{
+			if (!Overlaps(in_range))
+			{
+				return in_range;
+			}
+			else
+			{
+				while (((Overlaps(in_range)) && (in_range <= range_end)))
+					in_range++;
+				
+				if (in_range <= range_end)
+					return in_range;
+			}
+		}
 		else
 			in_range = 0;
 	}
@@ -412,6 +440,14 @@ long irc::portparser::GetToken()
 	if (x == "")
 		return 0;
 
+	while (Overlaps(atoi(x.c_str())))
+	{
+		x = sep->GetToken();
+
+		if (x == "")
+			return 0;
+	}
+
 	std::string::size_type dash = x.rfind('-');
 	if (dash != std::string::npos)
 	{