Line data Source code
1 : #ifndef HASHBROWNS_LINKED_LIST_H
2 : #define HASHBROWNS_LINKED_LIST_H
3 :
4 : #include "core/data_structure.h"
5 : #include "core/memory_manager.h"
6 : #include <utility>
7 : #include <string>
8 : #include <stdexcept>
9 : #include <cstddef>
10 : #include <type_traits>
11 :
12 : namespace hashbrowns {
13 :
14 : // Singly-linked list with memory pool allocation
15 : template<typename T = std::pair<int, std::string>>
16 : class SinglyLinkedList : public DataStructure {
17 : private:
18 : struct Node {
19 : T value;
20 : Node* next;
21 : explicit Node(const T& v) : value(v), next(nullptr) {}
22 287 : explicit Node(T&& v) : value(std::move(v)), next(nullptr) {}
23 : };
24 :
25 : Node* head_ = nullptr;
26 : Node* tail_ = nullptr;
27 : size_t size_ = 0;
28 : MemoryPool<Node> pool_;
29 :
30 : public:
31 19 : SinglyLinkedList() = default;
32 34 : ~SinglyLinkedList() override { clear(); }
33 :
34 1 : SinglyLinkedList(const SinglyLinkedList& other) {
35 3 : for (Node* n = other.head_; n; n = n->next) {
36 2 : push_back(n->value);
37 : }
38 1 : }
39 :
40 1 : SinglyLinkedList& operator=(const SinglyLinkedList& other) {
41 1 : if (this != &other) {
42 1 : clear();
43 3 : for (Node* n = other.head_; n; n = n->next) {
44 2 : push_back(n->value);
45 : }
46 : }
47 1 : return *this;
48 : }
49 :
50 1 : SinglyLinkedList(SinglyLinkedList&& other) noexcept {
51 1 : head_ = other.head_;
52 1 : tail_ = other.tail_;
53 1 : size_ = other.size_;
54 1 : other.head_ = other.tail_ = nullptr;
55 1 : other.size_ = 0;
56 1 : }
57 :
58 1 : SinglyLinkedList& operator=(SinglyLinkedList&& other) noexcept {
59 1 : if (this != &other) {
60 1 : clear();
61 1 : head_ = other.head_;
62 1 : tail_ = other.tail_;
63 1 : size_ = other.size_;
64 1 : other.head_ = other.tail_ = nullptr;
65 1 : other.size_ = 0;
66 : }
67 1 : return *this;
68 : }
69 :
70 : // DataStructure interface
71 283 : void insert(int key, const std::string& value) override {
72 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
73 283 : push_back(std::make_pair(key, value));
74 : } else {
75 : throw std::invalid_argument("SinglyLinkedList<T> insert only supported for T=std::pair<int,std::string>");
76 : }
77 283 : }
78 :
79 212 : bool search(int key, std::string& value) const override {
80 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
81 4198 : for (Node* n = head_; n; n = n->next) {
82 4193 : if (n->value.first == key) { value = n->value.second; return true; }
83 : }
84 : }
85 5 : return false;
86 : }
87 :
88 204 : bool remove(int key) override {
89 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
90 204 : Node* prev = nullptr;
91 204 : Node* cur = head_;
92 2015 : while (cur) {
93 2014 : if (cur->value.first == key) {
94 203 : if (prev) prev->next = cur->next; else head_ = cur->next;
95 203 : if (cur == tail_) tail_ = prev;
96 203 : destroy_and_release(cur);
97 203 : --size_;
98 203 : return true;
99 : }
100 1811 : prev = cur; cur = cur->next;
101 : }
102 : }
103 1 : return false;
104 : }
105 :
106 14 : size_t size() const override { return size_; }
107 5 : bool empty() const override { return size_ == 0; }
108 24 : void clear() override {
109 24 : Node* n = head_;
110 108 : while (n) {
111 84 : Node* next = n->next;
112 84 : destroy_and_release(n);
113 84 : n = next;
114 : }
115 24 : head_ = tail_ = nullptr;
116 24 : size_ = 0;
117 24 : }
118 :
119 3 : size_t memory_usage() const override {
120 3 : return size_ * sizeof(Node) + sizeof(*this);
121 : }
122 :
123 3 : std::string type_name() const override { return "SinglyLinkedList"; }
124 3 : std::string insert_complexity() const override { return "O(1) amortized at tail"; }
125 3 : std::string search_complexity() const override { return "O(n)"; }
126 3 : std::string remove_complexity() const override { return "O(n)"; }
127 :
128 : // List-specific API
129 4 : void push_back(const T& v) { emplace_back(v); }
130 283 : void push_back(T&& v) { emplace_back(std::move(v)); }
131 :
132 : template<typename... Args>
133 287 : void emplace_back(Args&&... args) {
134 287 : Node* raw = pool_.allocate();
135 : // placement-new construct
136 287 : new (raw) Node(T(std::forward<Args>(args)...));
137 287 : raw->next = nullptr;
138 287 : if (!tail_) { head_ = tail_ = raw; }
139 271 : else { tail_->next = raw; tail_ = raw; }
140 287 : ++size_;
141 287 : }
142 :
143 : private:
144 287 : void destroy_and_release(Node* node) {
145 287 : if (!node) return;
146 287 : node->~Node();
147 287 : pool_.deallocate(node);
148 : }
149 : };
150 :
151 : // Doubly-linked list with memory pool allocation
152 : template<typename T = std::pair<int, std::string>>
153 : class DoublyLinkedList : public DataStructure {
154 : private:
155 : struct Node {
156 : T value;
157 : Node* prev;
158 : Node* next;
159 : explicit Node(const T& v) : value(v), prev(nullptr), next(nullptr) {}
160 55 : explicit Node(T&& v) : value(std::move(v)), prev(nullptr), next(nullptr) {}
161 : };
162 :
163 : Node* head_ = nullptr;
164 : Node* tail_ = nullptr;
165 : size_t size_ = 0;
166 : MemoryPool<Node> pool_;
167 :
168 : public:
169 9 : DoublyLinkedList() = default;
170 14 : ~DoublyLinkedList() override { clear(); }
171 :
172 1 : DoublyLinkedList(const DoublyLinkedList& other) {
173 3 : for (Node* n = other.head_; n; n = n->next) {
174 2 : push_back(n->value);
175 : }
176 1 : }
177 :
178 1 : DoublyLinkedList& operator=(const DoublyLinkedList& other) {
179 1 : if (this != &other) {
180 1 : clear();
181 3 : for (Node* n = other.head_; n; n = n->next) {
182 2 : push_back(n->value);
183 : }
184 : }
185 1 : return *this;
186 : }
187 :
188 1 : DoublyLinkedList(DoublyLinkedList&& other) noexcept {
189 1 : head_ = other.head_;
190 1 : tail_ = other.tail_;
191 1 : size_ = other.size_;
192 1 : other.head_ = other.tail_ = nullptr;
193 1 : other.size_ = 0;
194 1 : }
195 :
196 1 : DoublyLinkedList& operator=(DoublyLinkedList&& other) noexcept {
197 1 : if (this != &other) {
198 1 : clear();
199 1 : head_ = other.head_;
200 1 : tail_ = other.tail_;
201 1 : size_ = other.size_;
202 1 : other.head_ = other.tail_ = nullptr;
203 1 : other.size_ = 0;
204 : }
205 1 : return *this;
206 : }
207 :
208 : // DataStructure interface
209 51 : void insert(int key, const std::string& value) override {
210 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
211 51 : push_back(std::make_pair(key, value));
212 : } else {
213 : throw std::invalid_argument("DoublyLinkedList<T> insert only supported for T=std::pair<int,std::string>");
214 : }
215 51 : }
216 :
217 34 : bool search(int key, std::string& value) const override {
218 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
219 239 : for (Node* n = head_; n; n = n->next) {
220 234 : if (n->value.first == key) { value = n->value.second; return true; }
221 : }
222 : }
223 5 : return false;
224 : }
225 :
226 26 : bool remove(int key) override {
227 : if constexpr (std::is_same_v<T, std::pair<int, std::string>>) {
228 28 : for (Node* n = head_; n; n = n->next) {
229 27 : if (n->value.first == key) {
230 25 : if (n->prev) n->prev->next = n->next; else head_ = n->next;
231 25 : if (n->next) n->next->prev = n->prev; else tail_ = n->prev;
232 25 : destroy_and_release(n);
233 25 : --size_;
234 25 : return true;
235 : }
236 : }
237 : }
238 1 : return false;
239 : }
240 :
241 14 : size_t size() const override { return size_; }
242 5 : bool empty() const override { return size_ == 0; }
243 14 : void clear() override {
244 14 : Node* n = head_;
245 44 : while (n) {
246 30 : Node* next = n->next;
247 30 : destroy_and_release(n);
248 30 : n = next;
249 : }
250 14 : head_ = tail_ = nullptr;
251 14 : size_ = 0;
252 14 : }
253 :
254 1 : size_t memory_usage() const override {
255 1 : return size_ * sizeof(Node) + sizeof(*this);
256 : }
257 :
258 3 : std::string type_name() const override { return "DoublyLinkedList"; }
259 3 : std::string insert_complexity() const override { return "O(1) amortized at tail"; }
260 3 : std::string search_complexity() const override { return "O(n)"; }
261 3 : std::string remove_complexity() const override { return "O(1) when node known; O(n) to find"; }
262 :
263 : // List-specific API
264 4 : void push_back(const T& v) { emplace_back(v); }
265 51 : void push_back(T&& v) { emplace_back(std::move(v)); }
266 :
267 : template<typename... Args>
268 55 : void emplace_back(Args&&... args) {
269 55 : Node* raw = pool_.allocate();
270 55 : new (raw) Node(T(std::forward<Args>(args)...));
271 55 : raw->prev = tail_;
272 55 : raw->next = nullptr;
273 55 : if (!tail_) { head_ = tail_ = raw; }
274 47 : else { tail_->next = raw; tail_ = raw; }
275 55 : ++size_;
276 55 : }
277 :
278 : private:
279 55 : void destroy_and_release(Node* node) {
280 55 : if (!node) return;
281 55 : node->~Node();
282 55 : pool_.deallocate(node);
283 : }
284 : };
285 :
286 : } // namespace hashbrowns
287 :
288 : #endif // HASHBROWNS_LINKED_LIST_H
|
