(svn r25570) -Add: cache for ParagraphLayouts.

3 files changed, 146 insertions, 43 deletions

diff --git a/src/gfx_layout.cpp b/src/gfx_layout.cpp
index cba5a7ddd..01be1e014 100644
--- a/src/gfx_layout.cpp
+++ b/src/gfx_layout.cpp
@@ -21,6 +21,9 @@
 #endif /* WITH_ICU */
 
 
+/** Cache of ParagraphLayout lines. */
+Layouter::LineCache Layouter::linecache;
+
 /** Cache of Font instances. */
 Layouter::FontColourMap Layouter::fonts[FS_END];
 
@@ -134,6 +137,8 @@ ParagraphLayout *Layouter::GetParagraphLayout(UChar *buff, UChar *buff_end, Font
 	}
 
 	LEErrorCode status = LE_NO_ERROR;
+	/* ParagraphLayout does not copy "buff", so it must stay valid.
+	 * "runs" is copied according to the ICU source, but the documentation does not specify anything, so this might break somewhen. */
 	return new ParagraphLayout(buff, length, &runs, NULL, NULL, NULL, _current_text_dir == TD_RTL ? UBIDI_DEFAULT_RTL : UBIDI_DEFAULT_LTR, false, status);
 }
 
@@ -278,6 +283,14 @@ ParagraphLayout::ParagraphLayout(WChar *buffer, int length, FontMap &runs) : buf
 }
 
 /**
+ * Reset the position to the start of the paragraph.
+ */
+void ParagraphLayout::reflow()
+{
+	this->buffer = this->buffer_begin;
+}
+
+/**
  * Construct a new line with a maximum width.
  * @param max_width The maximum width of the string.
  * @return A Line, or NULL when at the end of the paragraph.
@@ -300,7 +313,7 @@ ParagraphLayout::Line *ParagraphLayout::nextLine(int max_width)
 	}
 
 	const WChar *begin = this->buffer;
-	WChar *last_space = NULL;
+	const WChar *last_space = NULL;
 	const WChar *last_char = begin;
 	int width = 0;
 
@@ -412,62 +425,77 @@ ParagraphLayout *Layouter::GetParagraphLayout(WChar *buff, WChar *buff_end, Font
  */
 Layouter::Layouter(const char *str, int maxw, TextColour colour, FontSize fontsize)
 {
-	const CharType *buffer_last = lastof(this->buffer);
-	CharType *buff = this->buffer;
-
 	FontState state(colour, fontsize);
 	WChar c = 0;
 
 	do {
-		Font *f = GetFont(state.fontsize, state.cur_colour);
-		CharType *buff_begin = buff;
-		FontMap fontMapping;
-
-		/*
-		 * Go through the whole string while adding Font instances to the font map
-		 * whenever the font changes, and convert the wide characters into a format
-		 * usable by ParagraphLayout.
-		 */
-		for (; buff < buffer_last;) {
-			c = Utf8Consume(const_cast<const char **>(&str));
-			if (c == '\0' || c == '\n') {
-				break;
-			} else if (c >= SCC_BLUE && c <= SCC_BLACK) {
-				state.SetColour((TextColour)(c - SCC_BLUE));
-			} else if (c == SCC_PREVIOUS_COLOUR) { // Revert to the previous colour.
-				state.SetPreviousColour();
-			} else if (c == SCC_TINYFONT) {
-				state.SetFontSize(FS_SMALL);
-			} else if (c == SCC_BIGFONT) {
-				state.SetFontSize(FS_LARGE);
-			} else {
-				buff += AppendToBuffer(buff, buffer_last, c);
-				continue;
+		/* Scan string for end of line */
+		const char *lineend = str;
+		for (;;) {
+			size_t len = Utf8Decode(&c, lineend);
+			if (c == '\0' || c == '\n') break;
+			lineend += len;
+		}
+
+		LineCacheItem& line = GetCachedParagraphLayout(str, lineend - str, state);
+		if (line.layout != NULL) {
+			/* Line is in cache */
+			str = lineend + 1;
+			state = line.state_after;
+			line.layout->reflow();
+		} else {
+			/* Line is new, layout it */
+			const CharType *buffer_last = lastof(line.buffer);
+			CharType *buff_begin = line.buffer;
+			CharType *buff = buff_begin;
+			FontMap &fontMapping = line.runs;
+			Font *f = GetFont(state.fontsize, state.cur_colour);
+
+			/*
+			 * Go through the whole string while adding Font instances to the font map
+			 * whenever the font changes, and convert the wide characters into a format
+			 * usable by ParagraphLayout.
+			 */
+			for (; buff < buffer_last;) {
+				c = Utf8Consume(const_cast<const char **>(&str));
+				if (c == '\0' || c == '\n') {
+					break;
+				} else if (c >= SCC_BLUE && c <= SCC_BLACK) {
+					state.SetColour((TextColour)(c - SCC_BLUE));
+				} else if (c == SCC_PREVIOUS_COLOUR) { // Revert to the previous colour.
+					state.SetPreviousColour();
+				} else if (c == SCC_TINYFONT) {
+					state.SetFontSize(FS_SMALL);
+				} else if (c == SCC_BIGFONT) {
+					state.SetFontSize(FS_LARGE);
+				} else {
+					buff += AppendToBuffer(buff, buffer_last, c);
+					continue;
+				}
+
+				if (!fontMapping.Contains(buff - buff_begin)) {
+					fontMapping.Insert(buff - buff_begin, f);
+				}
+				f = GetFont(state.fontsize, state.cur_colour);
 			}
 
+			/* Better safe than sorry. */
+			*buff = '\0';
+
 			if (!fontMapping.Contains(buff - buff_begin)) {
 				fontMapping.Insert(buff - buff_begin, f);
 			}
-			f = GetFont(state.fontsize, state.cur_colour);
-		}
-
-		/* Better safe than sorry. */
-		*buff = '\0';
-
-		if (!fontMapping.Contains(buff - buff_begin)) {
-			fontMapping.Insert(buff - buff_begin, f);
+			line.layout = GetParagraphLayout(buff_begin, buff, fontMapping);
+			line.state_after = state;
 		}
-		ParagraphLayout *p = GetParagraphLayout(buff_begin, buff, fontMapping);
 
 		/* Copy all lines into a local cache so we can reuse them later on more easily. */
 		ParagraphLayout::Line *l;
-		while ((l = p->nextLine(maxw)) != NULL) {
+		while ((l = line.layout->nextLine(maxw)) != NULL) {
 			*this->Append() = l;
 		}
 
-		delete p;
-
-	} while (c != '\0' && buff < buffer_last);
+	} while (c != '\0');
 }
 
 /**
@@ -507,4 +535,40 @@ void Layouter::ResetFontCache(FontSize size)
 		delete it->second;
 	}
 	fonts[size].Clear();
+
+	/* We must reset the linecache since it references the just freed fonts */
+	ResetLineCache();
+}
+
+/**
+ * Get reference to cache item.
+ * If the item does not exist yet, it is default constructed.
+ * @param str Source string of the line (including colour and font size codes).
+ * @param len Length of \a str in bytes (no termination).
+ * @param state State of the font at the beginning of the line.
+ * @return Reference to cache item.
+ */
+Layouter::LineCacheItem &Layouter::GetCachedParagraphLayout(const char *str, size_t len, const FontState &state)
+{
+	LineCacheKey key;
+	key.state_before = state;
+	key.str.assign(str, len);
+	return linecache[key];
+}
+
+/**
+ * Clear line cache.
+ */
+void Layouter::ResetLineCache()
+{
+	linecache.clear();
+}
+
+/**
+ * Reduce the size of linecache if necessary to prevent infinite growth.
+ */
+void Layouter::ReduceLineCache()
+{
+	/* TODO LRU cache would be fancy, but not exactly necessary */
+	if (linecache.size() > 4096) ResetLineCache();
 }
diff --git a/src/gfx_layout.h b/src/gfx_layout.h
index ea9c34aae..1215954cb 100644
--- a/src/gfx_layout.h
+++ b/src/gfx_layout.h
@@ -16,6 +16,9 @@
 #include "gfx_func.h"
 #include "core/smallmap_type.hpp"
 
+#include <map>
+#include <string>
+
 #ifdef WITH_ICU
 #include "layout/ParagraphLayout.h"
 #define ICU_FONTINSTANCE : public LEFontInstance
@@ -32,6 +35,7 @@ struct FontState {
 	TextColour cur_colour;   ///< Current text colour.
 	TextColour prev_colour;  ///< Text colour from before the last colour switch.
 
+	FontState() : fontsize(FS_END), cur_colour(TC_INVALID), prev_colour(TC_INVALID) {}
 	FontState(TextColour colour, FontSize fontsize) : fontsize(fontsize), cur_colour(colour), prev_colour(colour) {}
 
 	/**
@@ -143,10 +147,11 @@ public:
 	};
 
 	const WChar *buffer_begin; ///< Begin of the buffer.
-	WChar *buffer;             ///< The current location in the buffer.
+	const WChar *buffer;       ///< The current location in the buffer.
 	FontMap &runs;             ///< The fonts we have to use for this paragraph.
 
 	ParagraphLayout(WChar *buffer, int length, FontMap &runs);
+	void reflow();
 	Line *nextLine(int max_width);
 };
 #endif /* !WITH_ICU */
@@ -166,7 +171,36 @@ class Layouter : public AutoDeleteSmallVector<ParagraphLayout::Line *, 4> {
 	size_t AppendToBuffer(CharType *buff, const CharType *buffer_last, WChar c);
 	ParagraphLayout *GetParagraphLayout(CharType *buff, CharType *buff_end, FontMap &fontMapping);
 
-	CharType buffer[DRAW_STRING_BUFFER]; ///< Buffer for the text that is going to be drawn.
+	/** Key into the linecache */
+	struct LineCacheKey {
+		FontState state_before;  ///< Font state at the beginning of the line.
+		std::string str;         ///< Source string of the line (including colour and font size codes).
+
+		/** Comparison operator for std::map */
+		bool operator<(const LineCacheKey &other) const
+		{
+			if (this->state_before.fontsize != other.state_before.fontsize) return this->state_before.fontsize < other.state_before.fontsize;
+			if (this->state_before.cur_colour != other.state_before.cur_colour) return this->state_before.cur_colour < other.state_before.cur_colour;
+			if (this->state_before.prev_colour != other.state_before.prev_colour) return this->state_before.prev_colour < other.state_before.prev_colour;
+			return this->str < other.str;
+		}
+	};
+	/** Item in the linecache */
+	struct LineCacheItem {
+		/* Stuff that cannot be freed until the ParagraphLayout is freed */
+		CharType buffer[DRAW_STRING_BUFFER]; ///< Accessed by both ICU's and our ParagraphLayout::nextLine.
+		FontMap runs;                        ///< Accessed by our ParagraphLayout::nextLine.
+
+		FontState state_after;   ///< Font state after the line.
+		ParagraphLayout *layout; ///< Layout of the line.
+
+		LineCacheItem() : layout(NULL) {}
+		~LineCacheItem() { delete layout; }
+	};
+	typedef std::map<LineCacheKey, LineCacheItem> LineCache;
+	static LineCache linecache;
+
+	static LineCacheItem &GetCachedParagraphLayout(const char *str, size_t len, const FontState &state);
 
 	typedef SmallMap<TextColour, Font *> FontColourMap;
 	static FontColourMap fonts[FS_END];
@@ -177,6 +211,8 @@ public:
 	Dimension GetBounds();
 
 	static void ResetFontCache(FontSize size);
+	static void ResetLineCache();
+	static void ReduceLineCache();
 };
 
 #endif /* GFX_LAYOUT_H */
diff --git a/src/openttd.cpp b/src/openttd.cpp
index 07124b84f..90c5d56db 100644
--- a/src/openttd.cpp
+++ b/src/openttd.cpp
@@ -61,6 +61,7 @@
 #include "game/game_config.hpp"
 #include "town.h"
 #include "subsidy_func.h"
+#include "gfx_layout.h"
 
 
 #include "linkgraph/linkgraphschedule.h"
@@ -1318,6 +1319,8 @@ void StateGameLoop()
 
 	ClearStorageChanges(false);
 
+	Layouter::ReduceLineCache();
+
 	if (_game_mode == GM_EDITOR) {
 		RunTileLoop();
 		CallVehicleTicks();