in sdlfont add map for fast search in list.

3 files changed, 237 insertions, 69 deletions

diff --git a/src/gui/sdlfont.cpp b/src/gui/sdlfont.cpp
index 8ffb14b13..37174d8e9 100644
--- a/src/gui/sdlfont.cpp
+++ b/src/gui/sdlfont.cpp
@@ -46,18 +46,62 @@ const int OUTLINE_SIZE = 1;
 
 char *strBuf;
 
-const unsigned int CACHES_NUMBER = 256;
-
 #ifdef UNITTESTS
 int sdlTextChunkCnt = 0;
 #endif
 
+SDLTextChunkSmall::SDLTextChunkSmall(const std::string &text0,
+                                     const gcn::Color &color0,
+                                     const gcn::Color &color1) :
+    text(text0),
+    color(color0),
+    color2(color1)
+{
+}
+
+SDLTextChunkSmall::SDLTextChunkSmall(const SDLTextChunkSmall &old)
+{
+    text = old.text;
+    color = old.color;
+    color2 = old.color2;
+}
+
+bool SDLTextChunkSmall::operator==(const SDLTextChunkSmall &chunk) const
+{
+    return (chunk.text == text && chunk.color == color
+            && chunk.color2 == color2);
+}
+
+bool SDLTextChunkSmall::operator<(const SDLTextChunkSmall &chunk) const
+{
+    if (chunk.text != text)
+        return chunk.text > text;
+
+    const gcn::Color &c = chunk.color;
+    if (c.r != color.r)
+        return c.r > color.r;
+    if (c.g != color.g)
+        return c.g > color.g;
+    if (c.b != color.b)
+        return c.b > color.b;
+
+    const gcn::Color &c2 = chunk.color2;
+    if (c2.r != color2.r)
+        return c2.r > color2.r;
+    if (c2.g != color2.g)
+        return c2.g > color2.g;
+    if (c2.b != color2.b)
+        return c2.b > color2.b;
+    return false;
+}
+
 SDLTextChunk::SDLTextChunk(const std::string &text0, const gcn::Color &color0,
               const gcn::Color &color1) :
     img(nullptr),
     text(text0),
     color(color0),
     color2(color1),
+    prev(nullptr),
     next(nullptr)
 {
 #ifdef UNITTESTS
@@ -181,6 +225,7 @@ void TextChunkList::insertFirst(SDLTextChunk *const item)
         end = item;
     start = item;
     size ++;
+    search[SDLTextChunkSmall(item->text, item->color, item->color2)] = item;
 }
 
 void TextChunkList::moveToFirst(SDLTextChunk *item)
@@ -214,6 +259,8 @@ void TextChunkList::removeBack()
             end->next = nullptr;
         else
             start = nullptr;
+        search.erase(SDLTextChunkSmall(oldEnd->text,
+            oldEnd->color, oldEnd->color2));
         delete oldEnd;
         size --;
     }
@@ -227,6 +274,8 @@ void TextChunkList::removeBack(int n)
         n --;
         SDLTextChunk *oldEnd = item;
         item = item->prev;
+        search.erase(SDLTextChunkSmall(oldEnd->text,
+            oldEnd->color, oldEnd->color2));
         delete oldEnd;
         size --;
     }
@@ -244,6 +293,7 @@ void TextChunkList::removeBack(int n)
 
 void TextChunkList::clear()
 {
+    search.clear();
     SDLTextChunk *item = start;
     while (item)
     {
@@ -256,11 +306,6 @@ void TextChunkList::clear()
     size = 0;
 }
 
-namespace
-{
-    TextChunkList mCache[CACHES_NUMBER];
-}  // namespace
-
 static int fontCounter;
 
 SDLFont::SDLFont(std::string filename, const int size, const int style) :
@@ -378,40 +423,24 @@ void SDLFont::drawString(gcn::Graphics *const graphics,
      */
     col.a = 255;
 
-    SDLTextChunk chunk(text, col, col2);
-
     const unsigned char chr = text[0];
     TextChunkList *const cache = &mCache[chr];
 
-    bool found = false;
-
-#ifdef DEBUG_FONT
-    int cnt = 0;
-#endif
-
-    SDLTextChunk *i = cache->start;
-    while (i)
+    std::map<SDLTextChunkSmall, SDLTextChunk*> &search = cache->search;
+    std::map<SDLTextChunkSmall, SDLTextChunk*>::iterator i
+        = search.find(SDLTextChunkSmall(text, col, col2));
+    if (i != search.end())
     {
-        if (*i == chunk)
+        SDLTextChunk *const chunk2 = (*i).second;
+        cache->moveToFirst(chunk2);
+        Image *const image = chunk2->img;
+        if (image)
         {
-            // Raise priority: move it to front
-            cache->moveToFirst(i);
-            found = true;
-            break;
+            image->setAlpha(alpha);
+            g->drawImage(image, x, y);
         }
-        i = i->next;
-#ifdef DEBUG_FONT
-        cnt ++;
-#endif
     }
-
-#ifdef DEBUG_FONT
-    logger->log(std::string("drawString: ").append(text).append(
-        ", iterations: ").append(toString(cnt)));
-#endif
-
-    // Surface not found
-    if (!found)
+    else
     {
         if (cache->size >= CACHE_SIZE)
         {
@@ -432,15 +461,6 @@ void SDLFont::drawString(gcn::Graphics *const graphics,
         if (image)
             g->drawImage(image, x, y);
     }
-    else
-    {
-        Image *const image = cache->start->img;
-        if (image)
-        {
-            image->setAlpha(alpha);
-            g->drawImage(image, x, y);
-        }
-    }
     BLOCK_END("SDLFont::drawString")
 }
 
diff --git a/src/gui/sdlfont.h b/src/gui/sdlfont.h
index 2e5376148..41edf4145 100644
--- a/src/gui/sdlfont.h
+++ b/src/gui/sdlfont.h
@@ -34,12 +34,31 @@
 #endif
 
 #include <list>
+#include <map>
 #include <string>
 
 #include "localconsts.h"
 
 class Image;
 
+const unsigned int CACHES_NUMBER = 256;
+
+class SDLTextChunkSmall
+{
+    public:
+        SDLTextChunkSmall(const std::string &text0, const gcn::Color &color0,
+                          const gcn::Color &color1);
+
+        SDLTextChunkSmall(const SDLTextChunkSmall &old);
+
+        bool operator==(const SDLTextChunkSmall &chunk) const;
+        bool operator<(const SDLTextChunkSmall &chunk) const;
+
+        std::string text;
+        gcn::Color color;
+        gcn::Color color2;
+};
+
 class SDLTextChunk final
 {
     public:
@@ -79,6 +98,7 @@ class TextChunkList final
         SDLTextChunk *start;
         SDLTextChunk *end;
         uint32_t size;
+        std::map<SDLTextChunkSmall, SDLTextChunk*> search;
 };
 
 /**
@@ -139,6 +159,7 @@ class SDLFont final : public gcn::Font
 
         // Word surfaces cache
         int mCleanTime;
+        mutable TextChunkList mCache[CACHES_NUMBER];
 };
 
 #ifdef UNITTESTS
diff --git a/src/gui/sdlfont_unittest.cc b/src/gui/sdlfont_unittest.cc
index 31b76f131..a372d2867 100644
--- a/src/gui/sdlfont_unittest.cc
+++ b/src/gui/sdlfont_unittest.cc
@@ -34,13 +34,15 @@ TEST(TextChunkList, empty)
     EXPECT_EQ(0, list.size);
     EXPECT_EQ(nullptr, list.start);
     EXPECT_EQ(nullptr, list.end);
+    EXPECT_EQ(0, list.search.size());
 }
 
 TEST(TextChunkList, add1)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk = new SDLTextChunk("test", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 3, 4));
 
     list.insertFirst(chunk);
 
@@ -49,14 +51,21 @@ TEST(TextChunkList, add1)
     EXPECT_EQ(chunk, list.end);
     EXPECT_EQ(nullptr, chunk->prev);
     EXPECT_EQ(nullptr, chunk->next);
+
+    EXPECT_EQ(1, list.search.size());
+
+    EXPECT_EQ(chunk, (*list.search.find(SDLTextChunkSmall(
+        chunk->text, chunk->color, chunk->color2))).second);
 }
 
 TEST(TextChunkList, add2)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(3, 4, 5));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test",
+        gcn::Color(2, 3, 4), gcn::Color(4, 5, 6));
 
     list.insertFirst(chunk2);
     list.insertFirst(chunk1);
@@ -68,13 +77,19 @@ TEST(TextChunkList, add2)
     EXPECT_EQ(chunk2, chunk1->next);
     EXPECT_EQ(chunk1, chunk2->prev);
     EXPECT_EQ(nullptr, chunk2->next);
+    EXPECT_EQ(2, list.search.size());
+    EXPECT_EQ(chunk1, (*list.search.find(SDLTextChunkSmall(
+        chunk1->text, chunk1->color, chunk1->color2))).second);
+    EXPECT_EQ(chunk2, (*list.search.find(SDLTextChunkSmall(
+        chunk2->text, chunk2->color, chunk2->color2))).second);
 }
 
 TEST(TextChunkList, addRemoveBack1)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk = new SDLTextChunk("test", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
 
     list.insertFirst(chunk);
     list.removeBack();
@@ -82,14 +97,17 @@ TEST(TextChunkList, addRemoveBack1)
     EXPECT_EQ(0, list.size);
     EXPECT_EQ(nullptr, list.start);
     EXPECT_EQ(nullptr, list.end);
+    EXPECT_EQ(0, list.search.size());
 }
 
 TEST(TextChunkList, addRemoveBack2)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test2",
+        gcn::Color(1, 2, 4), gcn::Color(1, 2, 5));
 
     list.insertFirst(chunk2);
     list.insertFirst(chunk1);
@@ -100,14 +118,19 @@ TEST(TextChunkList, addRemoveBack2)
     EXPECT_EQ(chunk1, list.end);
     EXPECT_EQ(nullptr, chunk1->prev);
     EXPECT_EQ(nullptr, chunk1->next);
+    EXPECT_EQ(1, list.search.size());
+    EXPECT_EQ(chunk1, (*list.search.find(SDLTextChunkSmall(
+        chunk1->text, chunk1->color, chunk1->color2))).second);
 }
 
 TEST(TextChunkList, addRemoveBack3)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test2",
+        gcn::Color(2, 3, 4), gcn::Color(2, 3, 4));
 
     list.insertFirst(chunk2);
     list.insertFirst(chunk1);
@@ -116,15 +139,19 @@ TEST(TextChunkList, addRemoveBack3)
     EXPECT_EQ(0, list.size);
     EXPECT_EQ(nullptr, list.start);
     EXPECT_EQ(nullptr, list.end);
+    EXPECT_EQ(0, list.search.size());
 }
 
 TEST(TextChunkList, addRemoveBack4)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk3 = new SDLTextChunk("test3", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test2",
+        gcn::Color(2, 3, 4), gcn::Color(2, 3, 4));
+    SDLTextChunk *chunk3 = new SDLTextChunk("test",
+        gcn::Color(3, 4, 5), gcn::Color(3, 4, 5));
 
     list.insertFirst(chunk3);
     list.insertFirst(chunk2);
@@ -137,13 +164,17 @@ TEST(TextChunkList, addRemoveBack4)
     EXPECT_EQ(chunk1, list.end);
     EXPECT_EQ(nullptr, chunk1->prev);
     EXPECT_EQ(nullptr, chunk1->next);
+    EXPECT_EQ(1, list.search.size());
+    EXPECT_EQ(chunk1, (*list.search.find(SDLTextChunkSmall(
+        chunk1->text, chunk1->color, chunk1->color2))).second);
 }
 
 TEST(TextChunkList, moveToFirst1)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk = new SDLTextChunk("test", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 3, 4));
 
     list.insertFirst(chunk);
     list.moveToFirst(chunk);
@@ -159,8 +190,10 @@ TEST(TextChunkList, moveToFirst2)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test",
+        gcn::Color(2, 3, 4), gcn::Color(1, 2, 3));
 
     list.insertFirst(chunk1);
     list.insertFirst(chunk2);
@@ -179,9 +212,12 @@ TEST(TextChunkList, moveToFirst3)
 {
     TextChunkList list;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk3 = new SDLTextChunk("test3", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 4), gcn::Color(1, 2, 3));
+    SDLTextChunk *chunk3 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 5), gcn::Color(1, 2, 3));
 
     list.insertFirst(chunk3);
     list.insertFirst(chunk1);
@@ -237,6 +273,7 @@ TEST(TextChunkList, clear1)
     EXPECT_EQ(nullptr, list.start);
     EXPECT_EQ(nullptr, list.end);
     EXPECT_EQ(chunksLeft, sdlTextChunkCnt);
+    EXPECT_EQ(0, list.search.size());
 }
 
 TEST(TextChunkList, clear2)
@@ -244,9 +281,12 @@ TEST(TextChunkList, clear2)
     TextChunkList list;
     int chunksLeft = sdlTextChunkCnt;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test1", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk3 = new SDLTextChunk("test3", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 0));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 1));
+    SDLTextChunk *chunk3 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 2));
 
     list.insertFirst(chunk1);
     list.insertFirst(chunk2);
@@ -257,6 +297,7 @@ TEST(TextChunkList, clear2)
     EXPECT_EQ(nullptr, list.start);
     EXPECT_EQ(nullptr, list.end);
     EXPECT_EQ(chunksLeft, sdlTextChunkCnt);
+    EXPECT_EQ(0, list.search.size());
 }
 
 TEST(TextChunkList, clear3)
@@ -264,21 +305,27 @@ TEST(TextChunkList, clear3)
     TextChunkList list;
     int chunksLeft = sdlTextChunkCnt;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test1", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk3 = new SDLTextChunk("test3", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 0));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 1));
+    SDLTextChunk *chunk3 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 2));
 
     list.insertFirst(chunk1);
     list.insertFirst(chunk2);
     list.insertFirst(chunk3);
     list.moveToFirst(chunk1);
     EXPECT_EQ(chunksLeft + 3, sdlTextChunkCnt);
+    EXPECT_EQ(3, list.search.size());
 
     list.removeBack();
     EXPECT_EQ(chunksLeft + 2, sdlTextChunkCnt);
+    EXPECT_EQ(2, list.search.size());
 
     list.clear();
     EXPECT_EQ(chunksLeft, sdlTextChunkCnt);
+    EXPECT_EQ(0, list.search.size());
 }
 
 TEST(TextChunkList, clear4)
@@ -286,19 +333,99 @@ TEST(TextChunkList, clear4)
     TextChunkList list;
     int chunksLeft = sdlTextChunkCnt;
 
-    SDLTextChunk *chunk1 = new SDLTextChunk("test1", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk2 = new SDLTextChunk("test2", gcn::Color(), gcn::Color());
-    SDLTextChunk *chunk3 = new SDLTextChunk("test3", gcn::Color(), gcn::Color());
+    SDLTextChunk *chunk1 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 0));
+    SDLTextChunk *chunk2 = new SDLTextChunk("test",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 1));
+    SDLTextChunk *chunk3 = new SDLTextChunk("test3",
+        gcn::Color(1, 2, 3), gcn::Color(2, 0, 2));
 
     list.insertFirst(chunk1);
     list.insertFirst(chunk2);
     list.insertFirst(chunk3);
     list.moveToFirst(chunk2);
     EXPECT_EQ(chunksLeft + 3, sdlTextChunkCnt);
+    EXPECT_EQ(3, list.search.size());
 
     list.removeBack(2);
     EXPECT_EQ(chunksLeft + 1, sdlTextChunkCnt);
+    EXPECT_EQ(1, list.search.size());
 
     list.clear();
     EXPECT_EQ(chunksLeft, sdlTextChunkCnt);
+    EXPECT_EQ(0, list.search.size());
+}
+
+TEST(TextChunkList, sort1)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item3("test line2",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    EXPECT_EQ(false, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
+    EXPECT_EQ(true, item1 < item3);
+    EXPECT_EQ(false, item3 < item1);
+}
+
+TEST(TextChunkList, sort2)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(2, 3, 4), gcn::Color(1, 2, 3));
+    EXPECT_EQ(true, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
+}
+
+TEST(TextChunkList, sort3)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(1, 3, 4), gcn::Color(1, 2, 3));
+    EXPECT_EQ(true, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
+}
+
+TEST(TextChunkList, sort4)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(1, 2, 4), gcn::Color(1, 2, 3));
+    EXPECT_EQ(true, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
+}
+
+TEST(TextChunkList, sort5)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(2, 2, 3));
+    EXPECT_EQ(true, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
+}
+
+TEST(TextChunkList, sort6)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 3, 3));
+    EXPECT_EQ(true, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
+}
+
+TEST(TextChunkList, sort7)
+{
+    SDLTextChunkSmall item1("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 3));
+    SDLTextChunkSmall item2("test line1",
+        gcn::Color(1, 2, 3), gcn::Color(1, 2, 4));
+    EXPECT_EQ(true, item1 < item2);
+    EXPECT_EQ(false, item2 < item1);
 }