Feature [feature-requests:#1417] Cache maximum key value in

SpecialRepresentations as this allows quick determination of absence for most
multi-byte UTF-8 and DBCS characters.

2 files changed, 15 insertions, 4 deletions

diff --git a/src/PositionCache.cxx b/src/PositionCache.cxx
index e9c07936b..13e4ab2b2 100644
--- a/src/PositionCache.cxx
+++ b/src/PositionCache.cxx
@@ -561,16 +561,18 @@ constexpr unsigned int representationKeyCrLf = KeyFromString("\r\n");
 void SpecialRepresentations::SetRepresentation(std::string_view charBytes, std::string_view value) {
 	if ((charBytes.length() <= 4) && (value.length() <= Representation::maxLength)) {
 		const unsigned int key = KeyFromString(charBytes);
-		const MapRepresentation::iterator it = mapReprs.find(key);
-		if (it == mapReprs.end()) {
+		const bool inserted = mapReprs.insert_or_assign(key, Representation(value)).second;
+		if (inserted) {
 			// New entry so increment for first byte
 			const unsigned char ucStart = charBytes.empty() ? 0 : charBytes[0];
 			startByteHasReprs[ucStart]++;
+			if (key > maxKey) {
+				maxKey = key;
+			}
 			if (key == representationKeyCrLf) {
 				crlf = true;
 			}
 		}
-		mapReprs[key] = Representation(value);
 	}
 }
 
@@ -607,6 +609,9 @@ void SpecialRepresentations::ClearRepresentation(std::string_view charBytes) {
 			mapReprs.erase(it);
 			const unsigned char ucStart = charBytes.empty() ? 0 : charBytes[0];
 			startByteHasReprs[ucStart]--;
+			if (key == maxKey && startByteHasReprs[ucStart] == 0) {
+				maxKey = mapReprs.empty() ? 0 : mapReprs.crbegin()->first;
+			}
 			if (key == representationKeyCrLf) {
 				crlf = false;
 			}
@@ -615,7 +620,11 @@ void SpecialRepresentations::ClearRepresentation(std::string_view charBytes) {
 }
 
 const Representation *SpecialRepresentations::GetRepresentation(std::string_view charBytes) const {
-	const MapRepresentation::const_iterator it = mapReprs.find(KeyFromString(charBytes));
+	const unsigned int key = KeyFromString(charBytes);
+	if (key > maxKey) {
+		return nullptr;
+	}
+	const MapRepresentation::const_iterator it = mapReprs.find(key);
 	if (it != mapReprs.end()) {
 		return &(it->second);
 	}
@@ -636,6 +645,7 @@ void SpecialRepresentations::Clear() {
 	mapReprs.clear();
 	constexpr unsigned short none = 0;
 	std::fill(startByteHasReprs, std::end(startByteHasReprs), none);
+	maxKey = 0;
 	crlf = false;
 }
 
diff --git a/src/PositionCache.h b/src/PositionCache.h
index 9a9f2e6fc..4ee501841 100644
--- a/src/PositionCache.h
+++ b/src/PositionCache.h
@@ -201,6 +201,7 @@ typedef std::map<unsigned int, Representation> MapRepresentation;
 class SpecialRepresentations {
 	MapRepresentation mapReprs;
 	unsigned short startByteHasReprs[0x100] {};
+	unsigned int maxKey = 0;
 	bool crlf = false;
 public:
 	void SetRepresentation(std::string_view charBytes, std::string_view value);