src/v8/test/cctest/test-hashmap.cc

   1 // Copyright 2008 the V8 project authors. All rights reserved.
   2 // Redistribution and use in source and binary forms, with or without
   3 // modification, are permitted provided that the following conditions are
   4 // met:
   5 //
   6 //     * Redistributions of source code must retain the above copyright
   7 //       notice, this list of conditions and the following disclaimer.
   8 //     * Redistributions in binary form must reproduce the above
   9 //       copyright notice, this list of conditions and the following
  10 //       disclaimer in the documentation and/or other materials provided
  11 //       with the distribution.
  12 //     * Neither the name of Google Inc. nor the names of its
  13 //       contributors may be used to endorse or promote products derived
  14 //       from this software without specific prior written permission.
  15 //
  16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27
  28 #include <stdlib.h>
  29
  30 #include "src/v8.h"
  31 #include "test/cctest/cctest.h"
  32
  33 #include "src/hashmap.h"
  34
  35 using namespace v8::internal;
  36
  37 static bool DefaultMatchFun(void* a, void* b) {
  38   return a == b;
  39 }
  40
  41
  42 typedef uint32_t (*IntKeyHash)(uint32_t key);
  43
  44
  45 class IntSet {
  46  public:
  47   explicit IntSet(IntKeyHash hash) : hash_(hash), map_(DefaultMatchFun)  {}
  48
  49   void Insert(int x) {
  50     CHECK_NE(0, x);  // 0 corresponds to (void*)NULL - illegal key value
  51     HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true);
  52     CHECK(p != NULL);  // insert is set!
  53     CHECK_EQ(reinterpret_cast<void*>(x), p->key);
  54     // we don't care about p->value
  55   }
  56
  57   void Remove(int x) {
  58     CHECK_NE(0, x);  // 0 corresponds to (void*)NULL - illegal key value
  59     map_.Remove(reinterpret_cast<void*>(x), hash_(x));
  60   }
  61
  62   bool Present(int x) {
  63     HashMap::Entry* p =
  64         map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false);
  65     if (p != NULL) {
  66       CHECK_EQ(reinterpret_cast<void*>(x), p->key);
  67     }
  68     return p != NULL;
  69   }
  70
  71   void Clear() {
  72     map_.Clear();
  73   }
  74
  75   uint32_t occupancy() const {
  76     uint32_t count = 0;
  77     for (HashMap::Entry* p = map_.Start(); p != NULL; p = map_.Next(p)) {
  78       count++;
  79     }
  80     CHECK_EQ(map_.occupancy(), static_cast<double>(count));
  81     return count;
  82   }
  83
  84  private:
  85   IntKeyHash hash_;
  86   HashMap map_;
  87 };
  88
  89
  90 static uint32_t Hash(uint32_t key)  { return 23; }
  91 static uint32_t CollisionHash(uint32_t key)  { return key & 0x3; }
  92
  93
  94 void TestSet(IntKeyHash hash, int size) {
  95   IntSet set(hash);
  96   CHECK_EQ(0, set.occupancy());
  97
  98   set.Insert(1);
  99   set.Insert(2);
 100   set.Insert(3);
 101   CHECK_EQ(3, set.occupancy());
 102
 103   set.Insert(2);
 104   set.Insert(3);
 105   CHECK_EQ(3, set.occupancy());
 106
 107   CHECK(set.Present(1));
 108   CHECK(set.Present(2));
 109   CHECK(set.Present(3));
 110   CHECK(!set.Present(4));
 111   CHECK_EQ(3, set.occupancy());
 112
 113   set.Remove(1);
 114   CHECK(!set.Present(1));
 115   CHECK(set.Present(2));
 116   CHECK(set.Present(3));
 117   CHECK_EQ(2, set.occupancy());
 118
 119   set.Remove(3);
 120   CHECK(!set.Present(1));
 121   CHECK(set.Present(2));
 122   CHECK(!set.Present(3));
 123   CHECK_EQ(1, set.occupancy());
 124
 125   set.Clear();
 126   CHECK_EQ(0, set.occupancy());
 127
 128   // Insert a long series of values.
 129   const int start = 453;
 130   const int factor = 13;
 131   const int offset = 7;
 132   const uint32_t n = size;
 133
 134   int x = start;
 135   for (uint32_t i = 0; i < n; i++) {
 136     CHECK_EQ(i, static_cast<double>(set.occupancy()));
 137     set.Insert(x);
 138     x = x * factor + offset;
 139   }
 140   CHECK_EQ(n, static_cast<double>(set.occupancy()));
 141
 142   // Verify the same sequence of values.
 143   x = start;
 144   for (uint32_t i = 0; i < n; i++) {
 145     CHECK(set.Present(x));
 146     x = x * factor + offset;
 147   }
 148   CHECK_EQ(n, static_cast<double>(set.occupancy()));
 149
 150   // Remove all these values.
 151   x = start;
 152   for (uint32_t i = 0; i < n; i++) {
 153     CHECK_EQ(n - i, static_cast<double>(set.occupancy()));
 154     CHECK(set.Present(x));
 155     set.Remove(x);
 156     CHECK(!set.Present(x));
 157     x = x * factor + offset;
 158
 159     // Verify the the expected values are still there.
 160     int y = start;
 161     for (uint32_t j = 0; j < n; j++) {
 162       if (j <= i) {
 163         CHECK(!set.Present(y));
 164       } else {
 165         CHECK(set.Present(y));
 166       }
 167       y = y * factor + offset;
 168     }
 169   }
 170   CHECK_EQ(0, set.occupancy());
 171 }
 172
 173
 174 TEST(Set) {
 175   TestSet(Hash, 100);
 176   TestSet(CollisionHash, 50);
 177 }