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
35using namespace v8::internal;
36
37static bool DefaultMatchFun(void* a, void* b) {
38  return a == b;
39}
40
41
42typedef uint32_t (*IntKeyHash)(uint32_t key);
43
44
45class 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
90static uint32_t Hash(uint32_t key)  { return 23; }
91static uint32_t CollisionHash(uint32_t key)  { return key & 0x3; }
92
93
94void 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
174TEST(Set) {
175  TestSet(Hash, 100);
176  TestSet(CollisionHash, 50);
177}
178