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