New zone-backed list datastructure to replace ZoneList

test/unittests/zone/zone-chunk-list-unittest.cc

+// Copyright 2016 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <ctime>

[Jakob Kummerow, 2016/10/26 16:08:10]

what's this needed for?

+
+#include "src/zone/zone-chunk-list.h"
+
+#include "src/list-inl.h"
+#include "src/zone/accounting-allocator.h"
+#include "src/zone/zone-containers.h"
+#include "src/zone/zone.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace v8 {
+namespace internal {
+
+const size_t kItemCount = size_t(1) << 10;
+
+TEST(ZoneChunkList, ForwardIterationTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  size_t count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    EXPECT_EQ(static_cast<size_t>(item), count);
+    count++;
+  }
+
+  EXPECT_EQ(count, kItemCount);
+}
+
+TEST(ZoneChunkList, ReverseIterationTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  size_t count = 0;
+
+  for (auto it = zone_chunk_list.rbegin(); it != zone_chunk_list.rend(); ++it) {
+    EXPECT_EQ(static_cast<size_t>(*it), kItemCount - count - 1);
+    count++;
+  }
+
+  EXPECT_EQ(count, kItemCount);
+}
+
+TEST(ZoneChunkList, PushFrontTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_front(static_cast<uintptr_t>(i));
+  }
+
+  size_t count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    EXPECT_EQ(static_cast<size_t>(item), kItemCount - count - 1);
+    count++;
+  }
+
+  EXPECT_EQ(count, kItemCount);
+}
+
+TEST(ZoneChunkList, RewindTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  zone_chunk_list.Rewind(42);
+
+  size_t count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    EXPECT_EQ(static_cast<size_t>(item), count);
+    count++;
+  }
+
+  EXPECT_EQ(count, 42);
+  EXPECT_EQ(count, zone_chunk_list.size());
+
+  zone_chunk_list.Rewind(0);
+
+  count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    USE(item);
+    count++;
+  }
+
+  EXPECT_EQ(count, 0);
+  EXPECT_EQ(count, zone_chunk_list.size());
+
+  zone_chunk_list.Rewind(100);
+
+  count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    EXPECT_EQ(static_cast<size_t>(item), count);
+    count++;
+  }
+
+  EXPECT_EQ(count, 0);
+  EXPECT_EQ(count, zone_chunk_list.size());
+}
+
+TEST(ZoneChunkList, FindTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  const size_t index = kItemCount / 2 + 42;
+
+  EXPECT_EQ(*zone_chunk_list.Find(index), static_cast<uintptr_t>(index));
+
+  *zone_chunk_list.Find(index) = 42;
+
+  EXPECT_EQ(*zone_chunk_list.Find(index), 42);
+}
+
+}  // namespace internal
+}  // namespace v8