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 "v8.h"
31#include "hashmap.h"
32#include "cctest.h"
33
34using namespace v8::internal;
35
36static bool DefaultMatchFun(void* a, void* b) {
37  return a == b;
38}
39
40
41typedef uint32_t (*IntKeyHash)(uint32_t key);
42
43
44class IntSet {
45 public:
46  explicit IntSet(IntKeyHash hash) : hash_(hash), map_(DefaultMatchFun)  {}
47
48  void Insert(int x) {
49    CHECK_NE(0, x);  // 0 corresponds to (void*)NULL - illegal key value
50    HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true);
51    CHECK(p != NULL);  // insert is set!
52    CHECK_EQ(reinterpret_cast<void*>(x), p->key);
53    // we don't care about p->value
54  }
55
56  void Remove(int x) {
57    CHECK_NE(0, x);  // 0 corresponds to (void*)NULL - illegal key value
58    map_.Remove(reinterpret_cast<void*>(x), hash_(x));
59  }
60
61  bool Present(int x) {
62    HashMap::Entry* p =
63        map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false);
64    if (p != NULL) {
65      CHECK_EQ(reinterpret_cast<void*>(x), p->key);
66    }
67    return p != NULL;
68  }
69
70  void Clear() {
71    map_.Clear();
72  }
73
74  uint32_t occupancy() const {
75    uint32_t count = 0;
76    for (HashMap::Entry* p = map_.Start(); p != NULL; p = map_.Next(p)) {
77      count++;
78    }
79    CHECK_EQ(map_.occupancy(), static_cast<double>(count));
80    return count;
81  }
82
83 private:
84  IntKeyHash hash_;
85  HashMap map_;
86};
87
88
89static uint32_t Hash(uint32_t key)  { return 23; }
90static uint32_t CollisionHash(uint32_t key)  { return key & 0x3; }
91
92
93void TestSet(IntKeyHash hash, int size) {
94  IntSet set(hash);
95  CHECK_EQ(0, set.occupancy());
96
97  set.Insert(1);
98  set.Insert(2);
99  set.Insert(3);
100  CHECK_EQ(3, set.occupancy());
101
102  set.Insert(2);
103  set.Insert(3);
104  CHECK_EQ(3, set.occupancy());
105
106  CHECK(set.Present(1));
107  CHECK(set.Present(2));
108  CHECK(set.Present(3));
109  CHECK(!set.Present(4));
110  CHECK_EQ(3, set.occupancy());
111
112  set.Remove(1);
113  CHECK(!set.Present(1));
114  CHECK(set.Present(2));
115  CHECK(set.Present(3));
116  CHECK_EQ(2, set.occupancy());
117
118  set.Remove(3);
119  CHECK(!set.Present(1));
120  CHECK(set.Present(2));
121  CHECK(!set.Present(3));
122  CHECK_EQ(1, set.occupancy());
123
124  set.Clear();
125  CHECK_EQ(0, set.occupancy());
126
127  // Insert a long series of values.
128  const int start = 453;
129  const int factor = 13;
130  const int offset = 7;
131  const uint32_t n = size;
132
133  int x = start;
134  for (uint32_t i = 0; i < n; i++) {
135    CHECK_EQ(i, static_cast<double>(set.occupancy()));
136    set.Insert(x);
137    x = x * factor + offset;
138  }
139  CHECK_EQ(n, static_cast<double>(set.occupancy()));
140
141  // Verify the same sequence of values.
142  x = start;
143  for (uint32_t i = 0; i < n; i++) {
144    CHECK(set.Present(x));
145    x = x * factor + offset;
146  }
147  CHECK_EQ(n, static_cast<double>(set.occupancy()));
148
149  // Remove all these values.
150  x = start;
151  for (uint32_t i = 0; i < n; i++) {
152    CHECK_EQ(n - i, static_cast<double>(set.occupancy()));
153    CHECK(set.Present(x));
154    set.Remove(x);
155    CHECK(!set.Present(x));
156    x = x * factor + offset;
157
158    // Verify the the expected values are still there.
159    int y = start;
160    for (uint32_t j = 0; j < n; j++) {
161      if (j <= i) {
162        CHECK(!set.Present(y));
163      } else {
164        CHECK(set.Present(y));
165      }
166      y = y * factor + offset;
167    }
168  }
169  CHECK_EQ(0, set.occupancy());
170}
171
172
173TEST(Set) {
174  TestSet(Hash, 100);
175  TestSet(CollisionHash, 50);
176}
177