116 lines
2.8 KiB
C++
116 lines
2.8 KiB
C++
/*
|
|
* Copyright (c) Facebook, Inc. and its affiliates.
|
|
*
|
|
* Licensed under the Apache License Version 2.0 with LLVM Exceptions
|
|
* (the "License"); you may not use this file except in compliance with
|
|
* the License. You may obtain a copy of the License at
|
|
*
|
|
* https://llvm.org/LICENSE.txt
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
* See the License for the specific language governing permissions and
|
|
* limitations under the License.
|
|
*/
|
|
#pragma once
|
|
|
|
|
|
#include <unifex/detail/prologue.hpp>
|
|
|
|
namespace unifex {
|
|
|
|
// A doubly-linked intrusive list maintained in ascending order of the 'SortKey'
|
|
// field of the list items.
|
|
template <typename T, T* T::*Next, T* T::*Prev, typename Key, Key T::*SortKey>
|
|
class intrusive_heap {
|
|
public:
|
|
intrusive_heap() noexcept : head_(nullptr) {}
|
|
|
|
~intrusive_heap() {
|
|
T* item = head_;
|
|
if (item != nullptr) {
|
|
UNIFEX_ASSERT(item->*Prev == nullptr);
|
|
}
|
|
while (item != nullptr) {
|
|
if (item->*Next != nullptr) {
|
|
UNIFEX_ASSERT(item->*Next->*Prev == item);
|
|
}
|
|
item = item->*Next;
|
|
}
|
|
|
|
UNIFEX_ASSERT(empty());
|
|
}
|
|
|
|
bool empty() const noexcept {
|
|
return head_ == nullptr;
|
|
}
|
|
|
|
T* top() const noexcept {
|
|
UNIFEX_ASSERT(!empty());
|
|
return head_;
|
|
}
|
|
|
|
T* pop() noexcept {
|
|
UNIFEX_ASSERT(!empty());
|
|
T* item = head_;
|
|
head_ = item->*Next;
|
|
if (head_ != nullptr) {
|
|
head_->*Prev = nullptr;
|
|
}
|
|
return item;
|
|
}
|
|
|
|
void insert(T* item) noexcept {
|
|
// Simple insertion sort to insert item in the right place in the list
|
|
// to keep the list sorted by 'item->*SortKey'.
|
|
// TODO: Replace this with a non-toy data-structure.
|
|
if (head_ == nullptr) {
|
|
head_ = item;
|
|
item->*Next = nullptr;
|
|
item->*Prev = nullptr;
|
|
} else if (item->*SortKey < head_->*SortKey) {
|
|
item->*Next = head_;
|
|
item->*Prev = nullptr;
|
|
head_->*Prev = item;
|
|
head_ = item;
|
|
} else {
|
|
auto* insertAfter = head_;
|
|
while (insertAfter->*Next != nullptr &&
|
|
insertAfter->*Next->*SortKey <= item->*SortKey) {
|
|
insertAfter = insertAfter->*Next;
|
|
}
|
|
|
|
auto* insertBefore = insertAfter->*Next;
|
|
|
|
item->*Prev = insertAfter;
|
|
item->*Next = insertBefore;
|
|
insertAfter->*Next = item;
|
|
if (insertBefore != nullptr) {
|
|
insertBefore->*Prev = item;
|
|
}
|
|
}
|
|
}
|
|
|
|
void remove(T* item) noexcept {
|
|
auto* prev = item->*Prev;
|
|
auto* next = item->*Next;
|
|
if (prev != nullptr) {
|
|
prev->*Next = next;
|
|
} else {
|
|
UNIFEX_ASSERT(head_ == item);
|
|
head_ = next;
|
|
}
|
|
if (next != nullptr) {
|
|
next->*Prev = prev;
|
|
}
|
|
}
|
|
|
|
private:
|
|
T* head_;
|
|
};
|
|
|
|
} // namespace unifex
|
|
|
|
#include <unifex/detail/epilogue.hpp>
|