169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch// Copyright 2011 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#include <string.h> 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/v8.h" 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "test/cctest/cctest.h" 32a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 33a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockusing namespace v8::internal; 34a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 35a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Use a testing allocator that clears memory before deletion. 36a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockclass ZeroingAllocationPolicy { 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block public: 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void* New(size_t size) { 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Stash the size in the first word to use for Delete. 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block size_t true_size = size + sizeof(size_t); 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block size_t* result = reinterpret_cast<size_t*>(malloc(true_size)); 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (result == NULL) return result; 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block *result = true_size; 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return result + 1; 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 47a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block static void Delete(void* ptr) { 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block size_t* true_ptr = reinterpret_cast<size_t*>(ptr) - 1; 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block memset(true_ptr, 0, *true_ptr); 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block free(true_ptr); 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block}; 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Check that we can add (a reference to) an element of the list 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// itself. 57a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockTEST(ListAdd) { 58a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Add elements to the list to grow it to its capacity. 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block List<int, ZeroingAllocationPolicy> list(4); 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(1); 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(2); 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(3); 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(4); 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Add an existing element, the backing store should have to grow. 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(list[0]); 67a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(1, list[4]); 68a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 69a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Test that we can add all elements from a list to another list. 72a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockTEST(ListAddAll) { 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block List<int, ZeroingAllocationPolicy> list(4); 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(0); 75a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(1); 76a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.Add(2); 77a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 78a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(3, list.length()); 79a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < 3; i++) { 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(i, list[i]); 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 82a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 83a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block List<int, ZeroingAllocationPolicy> other_list(4); 84a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 85a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Add no elements to list since other_list is empty. 86a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.AddAll(other_list); 87a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(3, list.length()); 88a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < 3; i++) { 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(i, list[i]); 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Add three elements to other_list. 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block other_list.Add(0); 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block other_list.Add(1); 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block other_list.Add(2); 96a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Copy the three elements from other_list to list. 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block list.AddAll(other_list); 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(6, list.length()); 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (int i = 0; i < 6; i++) { 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block CHECK_EQ(i % 3, list[i]); 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 1049ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick 1059ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick 1069ac36c9faca11611ada13b4054edbaa0738661d0Iain MerrickTEST(RemoveLast) { 1079ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick List<int> list(4); 1089ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(0, list.length()); 1099ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.Add(1); 1109ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(1, list.length()); 1119ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(1, list.last()); 1129ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.RemoveLast(); 1139ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(0, list.length()); 1149ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.Add(2); 1159ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.Add(3); 1169ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(2, list.length()); 1179ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(3, list.last()); 1189ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.RemoveLast(); 1199ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(1, list.length()); 1209ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(2, list.last()); 1219ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.RemoveLast(); 1229ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(0, list.length()); 1239ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick 1249ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick const int kElements = 100; 1259ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick for (int i = 0; i < kElements; i++) list.Add(i); 1269ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick for (int j = kElements - 1; j >= 0; j--) { 1279ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(j + 1, list.length()); 1289ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(j, list.last()); 1299ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.RemoveLast(); 1309ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(j, list.length()); 1319ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick } 1329ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick} 1339ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick 1349ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(Allocate) { 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch List<int> list(4); 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list.Add(1); 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, list.length()); 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list.Allocate(100); 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(100, list.length()); 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_LE(100, list.capacity()); 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch list[99] = 123; 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(123, list[99]); 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 1479ac36c9faca11611ada13b4054edbaa0738661d0Iain MerrickTEST(Clear) { 1489ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick List<int> list(4); 1499ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(0, list.length()); 1509ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick for (int i = 0; i < 4; ++i) list.Add(i); 1519ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(4, list.length()); 1529ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick list.Clear(); 1539ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick CHECK_EQ(0, list.length()); 1549ac36c9faca11611ada13b4054edbaa0738661d0Iain Merrick} 15569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 15669a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch 15769a99ed0b2b2ef69d393c371b03db3a98aaf880eBen MurdochTEST(DeleteEmpty) { 15869a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch { 15969a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch List<int>* list = new List<int>(0); 16069a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch delete list; 16169a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 16269a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch { 16369a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch List<int> list(0); 16469a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch } 16569a99ed0b2b2ef69d393c371b03db3a98aaf880eBen Murdoch} 166