From a2af9029410b20748b053bf0ca6f78ee27efef9e Mon Sep 17 00:00:00 2001 From: Andrei Karas Date: Wed, 24 Apr 2013 23:40:18 +0300 Subject: in sdlfont add map for fast search in list. --- src/gui/sdlfont.cpp | 106 +++++++++++++++----------- src/gui/sdlfont.h | 21 ++++++ src/gui/sdlfont_unittest.cc | 179 +++++++++++++++++++++++++++++++++++++------- 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 &search = cache->search; + std::map::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 +#include #include #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 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); } -- cgit v1.2.3-60-g2f50