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 #include "src/heap/index-generator.h" 6 7 namespace v8 { 8 namespace internal { 9 IndexGenerator(size_t size)10IndexGenerator::IndexGenerator(size_t size) : size_(size) { 11 if (size == 0) return; 12 base::MutexGuard guard(&lock_); 13 pending_indices_.push(0); 14 ranges_to_split_.push({0, size_}); 15 } 16 GetNext()17base::Optional<size_t> IndexGenerator::GetNext() { 18 base::MutexGuard guard(&lock_); 19 if (!pending_indices_.empty()) { 20 // Return any pending index first. 21 auto index = pending_indices_.top(); 22 pending_indices_.pop(); 23 return index; 24 } 25 if (ranges_to_split_.empty()) return base::nullopt; 26 27 // Split the oldest running range in 2 and return the middle index as 28 // starting point. 29 auto range = ranges_to_split_.front(); 30 ranges_to_split_.pop(); 31 size_t size = range.second - range.first; 32 size_t mid = range.first + size / 2; 33 // Both sides of the range are added to |ranges_to_split_| so they may be 34 // further split if possible. 35 if (mid - range.first > 1) ranges_to_split_.push({range.first, mid}); 36 if (range.second - mid > 1) ranges_to_split_.push({mid, range.second}); 37 return mid; 38 } 39 GiveBack(size_t index)40void IndexGenerator::GiveBack(size_t index) { 41 base::MutexGuard guard(&lock_); 42 // Add |index| to pending indices so GetNext() may return it before anything 43 // else. 44 pending_indices_.push(index); 45 } 46 47 } // namespace internal 48 } // namespace v8 49