1 // Copyright 2020 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_HEAP_INDEX_GENERATOR_H_ 6 #define V8_HEAP_INDEX_GENERATOR_H_ 7 8 #include <cstddef> 9 #include <queue> 10 #include <stack> 11 12 #include "src/base/macros.h" 13 #include "src/base/optional.h" 14 #include "src/base/platform/mutex.h" 15 16 namespace v8 { 17 namespace internal { 18 19 // A thread-safe data structure that generates heuristic starting points in a 20 // range to process items in parallel. 21 class V8_EXPORT_PRIVATE IndexGenerator { 22 public: 23 explicit IndexGenerator(size_t size); 24 IndexGenerator(const IndexGenerator&) = delete; 25 IndexGenerator& operator=(const IndexGenerator&) = delete; 26 27 base::Optional<size_t> GetNext(); 28 void GiveBack(size_t index); 29 30 private: 31 base::Mutex lock_; 32 // Pending indices that are ready to be handed out, prioritized over 33 // |pending_ranges_| when non-empty. 34 std::stack<size_t> pending_indices_; 35 // Pending [start, end] (exclusive) ranges to split and hand out indices from. 36 std::queue<std::pair<size_t, size_t>> ranges_to_split_; 37 const size_t size_; 38 }; 39 40 } // namespace internal 41 } // namespace v8 42 43 #endif // V8_HEAP_INDEX_GENERATOR_H_ 44