Home | History | Annotate | Download | only in tests 
      1 /*
      2  * Copyright (C) 2012 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  * 1. Redistributions of source code must retain the above copyright
      8  *    notice, this list of conditions and the following disclaimer.
      9  * 2. Redistributions in binary form must reproduce the above copyright
     10  *    notice, this list of conditions and the following disclaimer in the
     11  *    documentation and/or other materials provided with the distribution.
     12  *
     13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
     14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
     15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
     17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
     23  * THE POSSIBILITY OF SUCH DAMAGE.
     24  */
     25 
     26 #include "config.h"
     27 
     28 #include "wtf/HashSet.h"
     29 #include <gtest/gtest.h>
     30 
     31 namespace {
     32 
     33 template<int initialCapacity>
     34     struct InitialCapacityTestHashTraits : public WTF::UnsignedWithZeroKeyHashTraits<int> {
     35     static const int minimumTableSize = initialCapacity;
     36 };
     37 
     38 template<unsigned size>
     39 void testInitialCapacity()
     40 {
     41     const unsigned initialCapacity = WTF::HashTableCapacityForSize<size>::value;
     42     HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity> > testSet;
     43 
     44     // Initial capacity is null.
     45     ASSERT_EQ(0, testSet.capacity());
     46 
     47     // Adding items up to size should never change the capacity.
     48     for (size_t i = 0; i < size; ++i) {
     49         testSet.add(i);
     50         ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
     51     }
     52 
     53     // Adding items up to less than half the capacity should not change the capacity.
     54     unsigned capacityLimit = initialCapacity / 2 - 1;
     55     for (size_t i = size; i < capacityLimit; ++i) {
     56         testSet.add(i);
     57         ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
     58     }
     59 
     60     // Adding one more item increase the capacity.
     61     testSet.add(initialCapacity);
     62     EXPECT_GT(static_cast<unsigned>(testSet.capacity()), initialCapacity);
     63 }
     64 
     65 template<unsigned size> void generateTestCapacityUpToSize();
     66 template<> void generateTestCapacityUpToSize<0>()
     67 {
     68 }
     69 template<unsigned size> void generateTestCapacityUpToSize()
     70 {
     71     generateTestCapacityUpToSize<size - 1>();
     72     testInitialCapacity<size>();
     73 }
     74 
     75 TEST(WTF, HashSetInitialCapacity)
     76 {
     77     generateTestCapacityUpToSize<128>();
     78 }
     79 
     80 } // namespace
     81