1 files changed, 62 insertions, 0 deletions
diff --git a/deps/v8/src/heap/cppgc/free-list.h b/deps/v8/src/heap/cppgc/free-list.h
new file mode 100644
index 00000000000..ba578f38203
--- /dev/null
+++ b/deps/v8/src/heap/cppgc/free-list.h
@@ -0,0 +1,62 @@
+// Copyright 2020 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.
+
+#ifndef V8_HEAP_CPPGC_FREE_LIST_H_
+#define V8_HEAP_CPPGC_FREE_LIST_H_
+
+#include <array>
+
+#include "src/base/macros.h"
+#include "src/heap/cppgc/globals.h"
+#include "src/heap/cppgc/heap-object-header.h"
+
+namespace cppgc {
+namespace internal {
+
+class V8_EXPORT_PRIVATE FreeList {
+ public:
+  struct Block {
+    void* address;
+    size_t size;
+  };
+
+  FreeList();
+
+  FreeList(const FreeList&) = delete;
+  FreeList& operator=(const FreeList&) = delete;
+
+  FreeList(FreeList&& freelist) V8_NOEXCEPT;
+  FreeList& operator=(FreeList&& freelist) V8_NOEXCEPT;
+
+  // Allocates entries which are at least of the provided size.
+  Block Allocate(size_t);
+
+  // Adds block to the freelist. The minimal block size is two words.
+  void Add(Block);
+
+  // Append other freelist into this.
+  void Append(FreeList&&);
+
+  void Clear();
+
+  size_t Size() const;
+  bool IsEmpty() const;
+
+  bool Contains(Block) const;
+
+ private:
+  class Entry;
+
+  bool IsConsistent(size_t) const;
+
+  // All |Entry|s in the nth list have size >= 2^n.
+  std::array<Entry*, kPageSizeLog2> free_list_heads_;
+  std::array<Entry*, kPageSizeLog2> free_list_tails_;
+  size_t biggest_free_list_index_ = 0;
+};
+
+}  // namespace internal
+}  // namespace cppgc
+
+#endif  // V8_HEAP_CPPGC_FREE_LIST_H_