1#ifndef SEAD_LIST_IMPL_H_
2#define SEAD_LIST_IMPL_H_
3
4#include <basis/seadTypes.h>
5
6namespace sead
7{
8class Random;
9
10class ListNode
11{
12public:
13 ListNode* next() const { return mNext; }
14 ListNode* prev() const { return mPrev; }
15 bool isLinked() const { return mNext || mPrev; }
16
17private:
18 friend class ListImpl;
19
20 void init_() { *this = {}; }
21 void insertBack_(ListNode* node);
22 void insertFront_(ListNode* node);
23 void erase_();
24
25 ListNode* mPrev = nullptr;
26 ListNode* mNext = nullptr;
27};
28
29class ListImpl
30{
31public:
32 __attribute__((always_inline)) ListImpl() : mStartEnd(), mCount(0)
33 {
34 mStartEnd.mNext = &mStartEnd;
35 mStartEnd.mPrev = &mStartEnd;
36 }
37
38 bool isEmpty() const { return mCount == 0; }
39 s32 size() const { return mCount; }
40
41 void reverse();
42 void shuffle();
43 void shuffle(Random* random);
44 bool checkLinks() const;
45
46protected:
47 using CompareCallbackImpl = int (*)(const void*, const void*);
48
49 template <class T, class ComparePredicate>
50 void sort(s32 offset, const ComparePredicate& cmp)
51 {
52 this->mergeSort<T, ComparePredicate>(offset, cmp);
53 }
54
55 template <class T, class ComparePredicate>
56 void mergeSort(s32 offset, const ComparePredicate& cmp)
57 {
58 this->mergeSortImpl_<T, ComparePredicate>(mStartEnd.mNext, mStartEnd.mPrev, size(), offset,
59 cmp);
60 }
61
62 void pushBack(ListNode* item)
63 {
64 mStartEnd.insertFront_(node: item);
65 ++mCount;
66 }
67
68 void pushFront(ListNode* item)
69 {
70 mStartEnd.insertBack_(node: item);
71 ++mCount;
72 }
73
74 ListNode* popBack();
75 ListNode* popFront();
76
77 void insertBefore(ListNode* node, ListNode* node_to_insert)
78 {
79 node->insertFront_(node: node_to_insert);
80 ++mCount;
81 }
82
83 void insertAfter(ListNode* node, ListNode* node_to_insert)
84 {
85 node->insertBack_(node: node_to_insert);
86 ++mCount;
87 }
88
89 void erase(ListNode* item)
90 {
91 item->erase_();
92 --mCount;
93 }
94
95 ListNode* front() const { return mCount > 0 ? mStartEnd.mNext : nullptr; }
96 ListNode* back() const { return mCount > 0 ? mStartEnd.mPrev : nullptr; }
97 ListNode* nth(int n) const;
98 s32 indexOf(const ListNode*) const;
99
100 void swap(ListNode* n1, ListNode* n2);
101 void moveAfter(ListNode* basis, ListNode* n);
102 void moveBefore(ListNode* basis, ListNode* n);
103
104 ListNode* find(const void* ptr, s32 offset, CompareCallbackImpl cmp) const;
105 void uniq(s32 offset, CompareCallbackImpl cmp);
106
107 void clear();
108
109 // FIXME: this should take an rvalue reference for predicate.
110 template <class T, class ComparePredicate>
111 static void mergeSortImpl_(ListNode* front, ListNode* back, s32 num, s32 offset,
112 const ComparePredicate& predicate);
113
114protected:
115 ListNode mStartEnd;
116 s32 mCount;
117};
118
119} // namespace sead
120
121#endif // SEAD_LIST_IMPL_H_
122