facebookexperimental / facebookexperimental/libunifex

Is paring heap a better structure for intrusive heap?

Open
#181 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
1.7k
Forks
210
PR merge metrics
No merged PRs in 30d

Description

The following code implements a variant of paring heap:
```c++
template
class intrusive_paring_heap {
public:
intrusive_paring_heap() noexcept : root_(nullptr) {}

bool empty() const noexcept {
return root_ == nullptr;
}

T* top() const noexcept {
assert(!empty());
return root_;
}

void insert(T* item) noexcept {
root_ = merge(root_, item);
}

T* pop() noexcept {
assert(!empty());
auto item = root_;
T *x, *y, *list = nullptr;
while ((x = root_->*Children)) {
if ((root_->*Children = y = x->*Next))
root_->*Children = root_->*Children->*Next;
list = push_front(list, merge(x, y));
}
x = nullptr;
while ((y = list)) {
list = list->*Next;
x = merge(x, y);
}
root_ = x;
if(root_) root_->*Parent = nullptr;
item->*Children = item->*Parent = item->*Next = nullptr;
return item;
}

void remove(T* item) noexcept {
T* parent = item->*Parent;
if (parent == nullptr) {
pop();
}
else {
parent->*Children = remove_node(parent->*Children, item);
if (item->*Children) {
item->*Children->*Parent = nullptr;
root_ = merge(root_, item->*Children);
}
item->*Children = item->*Parent = item->*Next = nullptr;
}
}

private:
T* root_;

static inline T* push_front(T* list, T* x) noexcept {
x->*Next = list;
return x;
}

static inline T* remove_node(T* list, T* x) noexcept {
T* p = list;
if (x == list) return x->*Next;
while (p && p->*Next != x) p = p->*Next;
if (p) p->*Next = x->*Next;
return list;
}

static inline T* merge(T* h1, T* h2) noexcept {
if (!h1) return h2;
if (!h2) return h1;
if (h2->*SortKey < h1->*SortKey) std::swap(h1, h2);
h2->*Next = h1->*Children;
h1->*Children = h2;
h2->*Parent = h1;
h1->*Next = nullptr;
return h1;
}
};
```
However, it seems to have much more branch conditions; and it requires an extra slot of pointer and `nullptr` initialisation.

(It passes all tests but I didn't test more cases. Also, I didn't whether checkout the binary layout is good enough.)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.