| // Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| #ifndef RUNTIME_PLATFORM_PRIORITY_QUEUE_H_ |
| #define RUNTIME_PLATFORM_PRIORITY_QUEUE_H_ |
| |
| #include "platform/assert.h" |
| #include "platform/globals.h" |
| #include "platform/hashmap.h" |
| #include "platform/utils.h" |
| |
| namespace dart { |
| |
| // A min-priority queue with deletion support. |
| // |
| // The [PriorityQueue] allows insertion of entries with a priority [P] and a |
| // value [V]. The minimum element can be queried in O(1) time. |
| // Insertion/Deletion operations have O(N) time. |
| // |
| // In addition to the normal insert/minimum/remove-minimum operations this |
| // priority queue allows deletion-by-value. We have therefore an invariant |
| // is that the value must be unique amongst all entries. |
| template <typename P, typename V> |
| class PriorityQueue { |
| public: |
| static constexpr intptr_t kMinimumSize = 16; |
| |
| struct Entry { |
| P priority; |
| V value; |
| }; |
| |
| PriorityQueue() : hashmap_(&MatchFun, kMinimumSize) { |
| min_heap_size_ = kMinimumSize; |
| min_heap_ = |
| reinterpret_cast<Entry*>(malloc(sizeof(Entry) * min_heap_size_)); |
| if (min_heap_ == nullptr) FATAL("Cannot allocate memory."); |
| size_ = 0; |
| } |
| |
| ~PriorityQueue() { free(min_heap_); } |
| |
| // Whether the queue is empty. |
| bool IsEmpty() const { return size_ == 0; } |
| |
| // Inserts a new entry with [priority] and [value], requires there to be no |
| // existing entry with given [value]. |
| void Insert(const P& priority, const V& value) { |
| ASSERT(!ContainsValue(value)); |
| |
| if (size_ == min_heap_size_) { |
| Resize(min_heap_size_ << 1); |
| } |
| |
| Set(size_, {priority, value}); |
| BubbleUp(size_); |
| |
| size_++; |
| } |
| |
| // Returns a reference to the minimum entry. |
| // |
| // The caller can access it's priority and value in read-only mode only. |
| const Entry& Minimum() const { |
| ASSERT(!IsEmpty()); |
| return min_heap_[0]; |
| } |
| |
| // Removes the minimum entry. |
| void RemoveMinimum() { |
| ASSERT(!IsEmpty()); |
| RemoveAt(0); |
| } |
| |
| // Removes an existing entry with the given [value]. |
| // |
| // Returns true if such an entry was removed. |
| bool RemoveByValue(const V& value) { |
| auto entry = FindMapEntry(value); |
| if (entry != nullptr) { |
| const intptr_t offset = ValueOfMapEntry(entry); |
| RemoveAt(offset); |
| |
| ASSERT(hashmap_.size() == size_); |
| return true; |
| } |
| return false; |
| } |
| |
| // Whether the priority queue contains an entry with the given [value]. |
| bool ContainsValue(const V& value) { return FindMapEntry(value) != nullptr; } |
| |
| // Changes the priority of an existing entry with given [value] or adds a |
| // new entry. |
| bool InsertOrChangePriority(const P& priority, const V& value) { |
| auto map_entry = FindMapEntry(value); |
| if (map_entry == nullptr) { |
| Insert(priority, value); |
| return true; |
| } |
| |
| const intptr_t offset = ValueOfMapEntry(map_entry); |
| ASSERT(offset < size_); |
| |
| Entry& entry = min_heap_[offset]; |
| entry.priority = priority; |
| if (offset == 0) { |
| BubbleDown(offset); |
| } else { |
| intptr_t parent = (offset - 1) / 2; |
| intptr_t diff = entry.priority - min_heap_[parent].priority; |
| if (diff < 0) { |
| BubbleUp(offset); |
| } else if (diff > 0) { |
| BubbleDown(offset); |
| } |
| } |
| return false; |
| } |
| |
| #ifdef TESTING |
| intptr_t min_heap_size() { return min_heap_size_; } |
| #endif // TESTING |
| |
| private: |
| // Utility functions dealing with the SimpleHashMap interface. |
| static bool MatchFun(void* key1, void* key2) { return key1 == key2; } |
| |
| SimpleHashMap::Entry* FindMapEntry(const V& key, bool insert = false) { |
| return hashmap_.Lookup(CastKey(key), HashKey(key), insert); |
| } |
| void RemoveMapEntry(const V& key) { |
| ASSERT(FindMapEntry(key) != nullptr); |
| hashmap_.Remove(CastKey(key), HashKey(key)); |
| } |
| void SetMapEntry(const V& key, intptr_t value) { |
| FindMapEntry(key, /*insert=*/true)->value = reinterpret_cast<void*>(value); |
| } |
| static uint32_t HashKey(const V& key) { |
| return static_cast<uint32_t>(reinterpret_cast<intptr_t>(CastKey(key))); |
| } |
| static intptr_t ValueOfMapEntry(SimpleHashMap::Entry* entry) { |
| return reinterpret_cast<intptr_t>(entry->value); |
| } |
| static void* CastKey(const V& key) { |
| return reinterpret_cast<void*>((const_cast<V&>(key))); |
| } |
| |
| void RemoveAt(intptr_t offset) { |
| ASSERT(offset < size_); |
| |
| size_--; |
| |
| if (offset == size_) { |
| RemoveMapEntry(min_heap_[offset].value); |
| } else { |
| Replace(offset, size_); |
| BubbleDown(offset); |
| } |
| |
| if (size_ <= (min_heap_size_ >> 2) && |
| kMinimumSize <= (min_heap_size_ >> 1)) { |
| Resize(min_heap_size_ >> 1); |
| } |
| } |
| |
| void BubbleUp(intptr_t offset) { |
| while (true) { |
| if (offset == 0) return; |
| |
| intptr_t parent = (offset - 1) / 2; |
| if (min_heap_[parent].priority > min_heap_[offset].priority) { |
| Swap(parent, offset); |
| } |
| offset = parent; |
| } |
| } |
| |
| void BubbleDown(intptr_t offset) { |
| while (true) { |
| intptr_t left_child_index = 2 * offset + 1; |
| bool has_left_child = left_child_index < size_; |
| |
| if (!has_left_child) return; |
| |
| intptr_t smallest_index = offset; |
| |
| if (min_heap_[left_child_index].priority < min_heap_[offset].priority) { |
| smallest_index = left_child_index; |
| } |
| |
| intptr_t right_child_index = left_child_index + 1; |
| bool has_right_child = right_child_index < size_; |
| if (has_right_child) { |
| if (min_heap_[right_child_index].priority < |
| min_heap_[smallest_index].priority) { |
| smallest_index = right_child_index; |
| } |
| } |
| |
| if (offset == smallest_index) { |
| return; |
| } |
| |
| Swap(offset, smallest_index); |
| offset = smallest_index; |
| } |
| } |
| |
| void Set(intptr_t offset1, const Entry& entry) { |
| min_heap_[offset1] = entry; |
| SetMapEntry(entry.value, offset1); |
| } |
| |
| void Swap(intptr_t offset1, intptr_t offset2) { |
| Entry temp = min_heap_[offset1]; |
| min_heap_[offset1] = min_heap_[offset2]; |
| min_heap_[offset2] = temp; |
| |
| SetMapEntry(min_heap_[offset1].value, offset1); |
| SetMapEntry(min_heap_[offset2].value, offset2); |
| } |
| |
| void Replace(intptr_t index, intptr_t with_other) { |
| RemoveMapEntry(min_heap_[index].value); |
| |
| const Entry& entry = min_heap_[with_other]; |
| SetMapEntry(entry.value, index); |
| min_heap_[index] = entry; |
| } |
| |
| void Resize(intptr_t new_min_heap_size) { |
| ASSERT(size_ < new_min_heap_size); |
| ASSERT(new_min_heap_size != min_heap_size_); |
| |
| Entry* new_backing = reinterpret_cast<Entry*>( |
| realloc(min_heap_, sizeof(Entry) * new_min_heap_size)); |
| |
| if (new_backing == nullptr) FATAL("Cannot allocate memory."); |
| |
| min_heap_ = new_backing; |
| min_heap_size_ = new_min_heap_size; |
| } |
| |
| // The array is representing a tree structure with guaranteed log(n) height. |
| // It has the property that the value of node N is always equal or smaller |
| // than the value of N's children. Furthermore it is a "dense" tree in the |
| // sense that all rows/layers of the tree are fully occupied except the last |
| // one. The way to represent such "dense" trees is via an array that allows |
| // finding left/right children by <2*index+1><2*index+2> and the parent by |
| // <(index-1)/2>. |
| // |
| // Insertion operations can be performed by adding one more entry at the end |
| // (bottom right) and bubbling it up until the tree invariant is satisfied |
| // again. |
| // |
| // Deletion operations can be performed by replacing the minimum element |
| // (first entry) by the last entry (bottom right) and bubbling it down until |
| // the tree invariant is satisfied again. |
| Entry* min_heap_; |
| intptr_t min_heap_size_; |
| intptr_t size_; |
| SimpleHashMap hashmap_; |
| }; |
| |
| } // namespace dart |
| |
| #endif // RUNTIME_PLATFORM_PRIORITY_QUEUE_H_ |