code.vuplus.com Git - vuplus_webkit/blob - Tools/TestWebKitAPI/Tests/WTF/RedBlackTree.cpp

   1 /*
   2  * Copyright (C) 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * 1.  Redistributions of source code must retain the above copyright
   9  *     notice, this list of conditions and the following disclaimer.
  10  * 2.  Redistributions in binary form must reproduce the above copyright
  11  *     notice, this list of conditions and the following disclaimer in the
  12  *     documentation and/or other materials provided with the distribution.
  13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
  14  *     its contributors may be used to endorse or promote products derived
  15  *     from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
  18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
  21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "config.h"
  30 #include <JavaScriptCore/RedBlackTree.h>
  31 #include <JavaScriptCore/Vector.h>
  32
  33 using namespace WTF;
  34
  35 namespace TestWebKitAPI {
  36
  37 class RedBlackTreeTest: public testing::Test {
  38 public:
  39     unsigned m_counter;
  40
  41     virtual void SetUp()
  42     {
  43         m_counter = 0;
  44     }
  45
  46     virtual void TearDown()
  47     {
  48     }
  49
  50     struct Pair {
  51         char key;
  52         unsigned value;
  53
  54         Pair() { }
  55
  56         Pair(char key, unsigned value)
  57             : key(key)
  58             , value(value)
  59         {
  60         }
  61
  62         bool operator==(const Pair& other) const
  63         {
  64             return key == other.key;
  65         }
  66
  67         bool operator<(const Pair& other) const
  68         {
  69             return key < other.key;
  70         }
  71     };
  72
  73     typedef Vector<Pair, 16> PairVector;
  74
  75     PairVector findExact(PairVector& asVector, char key)
  76     {
  77         PairVector result;
  78
  79         for (size_t index = 0; index < asVector.size(); ++index) {
  80             if (asVector.at(index).key == key)
  81                 result.append(asVector.at(index));
  82         }
  83
  84         std::sort(result.begin(), result.end());
  85
  86         return result;
  87     }
  88
  89     void remove(PairVector& asVector, size_t index)
  90     {
  91         asVector.at(index) = asVector.last();
  92         asVector.removeLast();
  93     }
  94
  95     PairVector findLeastGreaterThanOrEqual(PairVector& asVector, char key)
  96     {
  97         char bestKey = 0; // assignment to make gcc happy
  98         bool foundKey = false;
  99
 100         for (size_t index = 0; index < asVector.size(); ++index) {
 101             if (asVector.at(index).key >= key) {
 102                 if (asVector.at(index).key < bestKey || !foundKey) {
 103                     foundKey = true;
 104                     bestKey = asVector.at(index).key;
 105                 }
 106             }
 107         }
 108
 109         PairVector result;
 110
 111         if (!foundKey)
 112             return result;
 113
 114         return findExact(asVector, bestKey);
 115     }
 116
 117     void assertFoundAndRemove(PairVector& asVector, char key, unsigned value)
 118     {
 119             bool found = false;
 120             size_t foundIndex = 0; // make compilers happy
 121
 122             for (size_t index = 0; index < asVector.size(); ++index) {
 123                 if (asVector.at(index).key == key
 124                     && asVector.at(index).value == value) {
 125                     EXPECT_TRUE(!found);
 126
 127                     found = true;
 128                     foundIndex = index;
 129                 }
 130             }
 131
 132             EXPECT_TRUE(found);
 133
 134             remove(asVector, foundIndex);
 135     }
 136
 137     // This deliberately passes a copy of the vector.
 138     void assertEqual(RedBlackTree<char, unsigned>& asTree, PairVector asVector)
 139     {
 140         for (RedBlackTree<char, unsigned>::Node* current = asTree.first(); current; current = current->successor())
 141             assertFoundAndRemove(asVector, current->m_key, current->m_value);
 142     }
 143
 144     void assertSameValuesForKey(RedBlackTree<char, unsigned>& asTree, RedBlackTree<char, unsigned>::Node* node, PairVector foundValues, char key)
 145     {
 146         if (node) {
 147             EXPECT_EQ(node->m_key, key);
 148
 149             RedBlackTree<char, unsigned>::Node* prevNode = node;
 150             do {
 151                 node = prevNode;
 152                 prevNode = prevNode->predecessor();
 153             } while (prevNode && prevNode->m_key == key);
 154
 155             EXPECT_EQ(node->m_key, key);
 156             EXPECT_TRUE(!prevNode || prevNode->m_key < key);
 157
 158             do {
 159                 assertFoundAndRemove(foundValues, node->m_key, node->m_value);
 160
 161                 node = node->successor();
 162                 EXPECT_TRUE(!node || node->m_key >= key);
 163             } while (node && node->m_key == key);
 164         }
 165
 166         EXPECT_TRUE(foundValues.isEmpty());
 167     }
 168
 169     // The control string is a null-terminated list of commands. Each
 170     // command is two characters, with the first identifying the operation
 171     // and the second giving a key. The commands are:
 172     //  +x  Add x
 173     //  *x  Find all elements equal to x
 174     //  @x  Find all elements that have the smallest key that is greater than or equal to x
 175     //  !x  Remove all elements equal to x
 176     void testDriver(const char* controlString)
 177     {
 178         PairVector asVector;
 179         RedBlackTree<char, unsigned> asTree;
 180
 181         for (const char* current = controlString; *current; current += 2) {
 182             char command = current[0];
 183             char key = current[1];
 184             unsigned value = ++m_counter;
 185
 186             ASSERT(command);
 187             ASSERT(key);
 188
 189             switch (command) {
 190             case '+': {
 191                 RedBlackTree<char, unsigned>::Node* node = new RedBlackTree<char, unsigned>::Node(key, value);
 192                 asTree.insert(node);
 193                 asVector.append(Pair(key, value));
 194                 break;
 195             }
 196
 197             case '*': {
 198                 RedBlackTree<char, unsigned>::Node* node = asTree.findExact(key);
 199                 if (node)
 200                     EXPECT_EQ(node->m_key, key);
 201                 assertSameValuesForKey(asTree, node, findExact(asVector, key), key);
 202                 break;
 203             }
 204
 205             case '@': {
 206                 RedBlackTree<char, unsigned>::Node* node = asTree.findLeastGreaterThanOrEqual(key);
 207                 if (node) {
 208                     EXPECT_TRUE(node->m_key >= key);
 209                     assertSameValuesForKey(asTree, node, findLeastGreaterThanOrEqual(asVector, key), node->m_key);
 210                 } else
 211                     EXPECT_TRUE(findLeastGreaterThanOrEqual(asVector, key).isEmpty());
 212                 break;
 213             }
 214
 215             case '!': {
 216                 while (true) {
 217                     RedBlackTree<char, unsigned>::Node* node = asTree.remove(key);
 218                     if (node) {
 219                         EXPECT_EQ(node->m_key, key);
 220                         assertFoundAndRemove(asVector, node->m_key, node->m_value);
 221                     } else {
 222                         EXPECT_TRUE(findExact(asVector, key).isEmpty());
 223                         break;
 224                     }
 225                 }
 226                 break;
 227             }
 228
 229             default:
 230                 ASSERT_NOT_REACHED();
 231                 break;
 232             }
 233
 234             EXPECT_EQ(asTree.size(), asVector.size());
 235             assertEqual(asTree, asVector);
 236         }
 237     }
 238 };
 239
 240 TEST_F(RedBlackTreeTest, Empty)
 241 {
 242     testDriver("");
 243 }
 244
 245 TEST_F(RedBlackTreeTest, EmptyGetFindRemove)
 246 {
 247     testDriver("*x@y!z");
 248 }
 249
 250 TEST_F(RedBlackTreeTest, SingleAdd)
 251 {
 252     testDriver("+a");
 253 }
 254
 255 TEST_F(RedBlackTreeTest, SingleAddGetFindRemoveNotFound)
 256 {
 257     testDriver("+a*x@y!z");
 258 }
 259
 260 TEST_F(RedBlackTreeTest, SingleAddGetFindRemove)
 261 {
 262     testDriver("+a*a@a!a");
 263 }
 264
 265 TEST_F(RedBlackTreeTest, TwoAdds)
 266 {
 267     testDriver("+a+b");
 268 }
 269
 270 TEST_F(RedBlackTreeTest, ThreeAdds)
 271 {
 272     testDriver("+a+b+c");
 273 }
 274
 275 TEST_F(RedBlackTreeTest, FourAdds)
 276 {
 277     testDriver("+a+b+c+d");
 278 }
 279
 280 TEST_F(RedBlackTreeTest, LotsOfRepeatAdds)
 281 {
 282     testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d");
 283 }
 284
 285 TEST_F(RedBlackTreeTest, LotsOfRepeatAndUniqueAdds)
 286 {
 287     testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z");
 288 }
 289
 290 TEST_F(RedBlackTreeTest, LotsOfRepeatAndUniqueAddsAndGetsAndRemoves)
 291 {
 292     testDriver("+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+r+s+t+u+v+x+y+z*a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z!a!b!c!d!e!f!g!h!i!j!k!l!m!n!o!p!q!r!s!t!u!v!w!x!y!z");
 293 }
 294
 295 TEST_F(RedBlackTreeTest, SimpleBestFitSearch)
 296 {
 297     testDriver("+d+d+m+w@d@m@w@a@g@q");
 298 }
 299
 300 TEST_F(RedBlackTreeTest, BiggerBestFitSearch)
 301 {
 302     testDriver("+d+d+d+d+d+d+d+d+d+d+f+f+f+f+f+f+f+h+h+i+j+k+l+m+o+p+q+r+z@a@b@c@d@e@f@g@h@i@j@k@l@m@n@o@p@q@r@s@t@u@v@w@x@y@z");
 303 }
 304
 305 } // namespace TestWebKitAPI