blob: 51e970408ae4223b35a123074e7f2f195608d8d1 [file] [log] [blame] [edit]
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include "platform/hashmap.h"
#include "platform/assert.h"
#include "platform/globals.h"
#include "vm/unit_test.h"
namespace dart {
// Default initial size of hashmaps used in these tests.
static intptr_t kInitialSize = 8;
typedef uint32_t (*IntKeyHash)(uint32_t key);
class IntSet {
public:
explicit IntSet(IntKeyHash hash)
: hash_(hash), map_(SimpleHashMap::SamePointerValue, kInitialSize) {}
void Insert(int x) {
EXPECT_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
SimpleHashMap::Entry* p =
map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true);
EXPECT(p != nullptr); // insert is set!
EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
// We don't care about p->value.
}
void Remove(int x) {
EXPECT_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
map_.Remove(reinterpret_cast<void*>(x), hash_(x));
}
bool Present(int x) {
SimpleHashMap::Entry* p =
map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false);
if (p != nullptr) {
EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
}
return p != nullptr;
}
void Clear() { map_.Clear(); }
uint32_t occupancy() const {
uint32_t count = 0;
for (SimpleHashMap::Entry* p = map_.Start(); p != nullptr;
p = map_.Next(p)) {
count++;
}
EXPECT_EQ(map_.occupancy_, count);
return count;
}
private:
IntKeyHash hash_;
SimpleHashMap map_;
};
static uint32_t WordHash(uint32_t key) {
return dart::Utils::WordHash(key);
}
static uint32_t Hash(uint32_t key) {
return 23;
}
static uint32_t CollisionHash1(uint32_t key) {
return key & 0x3;
}
static uint32_t CollisionHash2(uint32_t key) {
return kInitialSize - 1;
}
static uint32_t CollisionHash3(uint32_t key) {
return kInitialSize - 2;
}
void TestSet(IntKeyHash hash, int size) {
IntSet set(hash);
EXPECT_EQ(0u, set.occupancy());
set.Insert(1);
set.Insert(2);
set.Insert(3);
set.Insert(4);
EXPECT_EQ(4u, set.occupancy());
set.Insert(2);
set.Insert(3);
EXPECT_EQ(4u, set.occupancy());
EXPECT(set.Present(1));
EXPECT(set.Present(2));
EXPECT(set.Present(3));
EXPECT(set.Present(4));
EXPECT(!set.Present(5));
EXPECT_EQ(4u, set.occupancy());
set.Remove(1);
EXPECT(!set.Present(1));
EXPECT(set.Present(2));
EXPECT(set.Present(3));
EXPECT(set.Present(4));
EXPECT_EQ(3u, set.occupancy());
set.Remove(3);
EXPECT(!set.Present(1));
EXPECT(set.Present(2));
EXPECT(!set.Present(3));
EXPECT(set.Present(4));
EXPECT_EQ(2u, set.occupancy());
set.Remove(4);
EXPECT(!set.Present(1));
EXPECT(set.Present(2));
EXPECT(!set.Present(3));
EXPECT(!set.Present(4));
EXPECT_EQ(1u, set.occupancy());
set.Clear();
EXPECT_EQ(0u, set.occupancy());
// Insert a long series of values.
const uint32_t start = 453;
const uint32_t factor = 13;
const uint32_t offset = 7;
const uint32_t n = size;
uint32_t x = start;
for (uint32_t i = 0; i < n; i++) {
EXPECT_EQ(i, set.occupancy());
set.Insert(x);
x = x * factor + offset;
}
EXPECT_EQ(n, set.occupancy());
// Verify the same sequence of values.
x = start;
for (uint32_t i = 0; i < n; i++) {
EXPECT(set.Present(x));
x = x * factor + offset;
}
EXPECT_EQ(n, set.occupancy());
// Remove all these values.
x = start;
for (uint32_t i = 0; i < n; i++) {
EXPECT_EQ(n - i, set.occupancy());
EXPECT(set.Present(x));
set.Remove(x);
EXPECT(!set.Present(x));
x = x * factor + offset;
// Verify the expected values are still there.
int y = start;
for (uint32_t j = 0; j < n; j++) {
if (j <= i) {
EXPECT(!set.Present(y));
} else {
EXPECT(set.Present(y));
}
y = y * factor + offset;
}
}
EXPECT_EQ(0u, set.occupancy());
}
VM_UNIT_TEST_CASE(SimpleHashMap_Basic) {
TestSet(WordHash, 100);
TestSet(Hash, 100);
TestSet(CollisionHash1, 50);
TestSet(CollisionHash2, 50);
TestSet(CollisionHash3, 50);
}
} // namespace dart