1 /*
2 * Copyright (c) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 #ifndef HIPERF_HASHLIST_HPP
16 #define HIPERF_HASHLIST_HPP
17
18 #include "hashlist.h"
19
20 namespace OHOS {
21 namespace Developtools {
22 namespace NativeDaemon {
23 // implementation of template class LinkNode
LinkNode(const Key & key)24 template <typename Key, typename Val> LinkNode<Key, Val>::LinkNode(const Key& key) : key_ {key} {}
25
26 template <typename Key, typename Val>
LinkNode(const Key & key,const Val & val)27 LinkNode<Key, Val>::LinkNode(const Key& key, const Val& val) : key_ {key}, val_ {val}
28 {
29 }
30
31 template <typename Key, typename Val>
LinkNode(const Key & key,Val && val)32 LinkNode<Key, Val>::LinkNode(const Key& key, Val&& val) : key_ {key}, val_ {std::move(val)}
33 {
34 }
35
36 template <typename Key, typename Val>
LinkNode(const LinkNode & node)37 LinkNode<Key, Val>::LinkNode(const LinkNode& node) : link_ {node.link_}, key_ {node.key_}, val_ {node.val_}
38 {
39 }
40
41 template <typename Key, typename Val>
LinkNode(LinkNode && node)42 LinkNode<Key, Val>::LinkNode(LinkNode&& node)
43 : link_ {std::move(node.link_)}, key_ {std::move(node.key_)}, val_ {std::move(node.val_)}
44 {
45 }
46
47 template <typename Key, typename Val> auto LinkNode<Key, Val>::operator=(const LinkNode& node) -> LinkNode<Key, Val>&
48 {
49 link_ = node.link_;
50 key_ = node.key_;
51 val_ = node.val_;
52 }
53
54 template <typename Key, typename Val> auto LinkNode<Key, Val>::operator=(LinkNode&& node) -> LinkNode<Key, Val>&
55 {
56 link_ = std::move(node.link_);
57 key_ = std::move(node.key_);
58 val_ = std::move(node.val_);
59 }
60
61 template <typename Key, typename Val> auto LinkNode<Key, Val>::GetLinkNode(Val* pval) -> LinkNode<Key, Val> *
62 {
63 if (pval) {
64 LinkNode<Key, Val>* pnode {nullptr};
65 Val* offset = &pnode->val_;
66 auto nodeAddr = reinterpret_cast<char*>(pval) - reinterpret_cast<char*>(offset);
67 return reinterpret_cast<LinkNode<Key, Val>*>(nodeAddr);
68 }
69 return nullptr;
70 }
71
72 template <typename Key, typename Val> auto LinkNode<Key, Val>::GetLinkNode(Link* plink) -> LinkNode<Key, Val> *
73 {
74 if (plink) {
75 LinkNode<Key, Val>* pnode {nullptr};
76 Link* offset = &pnode->link_;
77 auto nodeAddr = reinterpret_cast<char*>(plink) - reinterpret_cast<char*>(offset);
78 return reinterpret_cast<LinkNode<Key, Val>*>(nodeAddr);
79 }
80 return nullptr;
81 }
82 // end of LinkNode
83
84 // implementation of template class Iterator
85 template <typename Key, typename Val>
Iterator(LinkNode<Key,Val> * pnode,HashList * phashList)86 HashList<Key, Val>::Iterator::Iterator(LinkNode<Key, Val>* pnode, HashList* phashList)
87 : pnode_ {pnode}, phashList_ {phashList}
88 {
89 if (phashList_ == nullptr) {
90 pnode_ = nullptr;
91 }
92 }
93
94 template <typename Key, typename Val>
Iterator(const LinkNode<Key,Val> * pnode,const HashList * phashList)95 HashList<Key, Val>::Iterator::Iterator(const LinkNode<Key, Val>* pnode, const HashList* phashList)
96 : pnode_ {const_cast<LinkNode<Key, Val>*>(pnode)}, phashList_ {const_cast<HashList*>(phashList)}
97 {
98 if (phashList_ == nullptr) {
99 pnode_ = nullptr;
100 }
101 }
102
103 template <typename Key, typename Val>
Iterator(const Iterator & itr)104 HashList<Key, Val>::Iterator::Iterator(const Iterator& itr) : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
105 {
106 }
107
108 template <typename Key, typename Val>
Iterator(Iterator && itr)109 HashList<Key, Val>::Iterator::Iterator(Iterator&& itr) : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
110 {
111 itr.pnode_ = nullptr;
112 itr.phashList_ = nullptr;
113 }
114
115 template <typename Key, typename Val>
116 auto HashList<Key, Val>::Iterator::operator=(const Iterator& itr) -> HashList<Key, Val>::Iterator&
117 {
118 Iterator temp {itr};
119 swap(temp);
120 return *this;
121 }
122
123 template <typename Key, typename Val>
124 auto HashList<Key, Val>::Iterator::operator=(Iterator&& itr) -> HashList<Key, Val>::Iterator&
125 {
126 Iterator temp {std::move(itr)};
127 swap(temp);
128 return *this;
129 }
130
131 template <typename Key, typename Val>
132 auto HashList<Key, Val>::Iterator::operator++() noexcept -> HashList<Key, Val>::Iterator&
133 {
134 if (pnode_ == nullptr or phashList_ == nullptr) {
135 phashList_ = nullptr;
136 return *this;
137 }
138 Link* plink = pnode_->link_.next_;
139 if (plink == &phashList_->tail_) {
140 pnode_ = nullptr;
141 return *this;
142 }
143 auto pnode = LinkNode<Key, Val>::GetLinkNode(plink);
144 pnode_ = pnode;
145 return *this;
146 }
147
148 template <typename Key, typename Val>
149 auto HashList<Key, Val>::Iterator::operator++(int) noexcept -> HashList<Key, Val>::Iterator
150 {
151 Iterator res {*this};
152 if (pnode_ == nullptr or phashList_ == nullptr) {
153 phashList_ = nullptr;
154 return res;
155 }
156 Link* plink = pnode_->link_.next_;
157 if (plink == &phashList_->tail_) {
158 pnode_ = nullptr;
159 return res;
160 }
161 auto pnode = LinkNode<Key, Val>::GetLinkNode(plink);
162 pnode_ = pnode;
163 return res;
164 }
165
166 template <typename Key, typename Val>
167 auto HashList<Key, Val>::Iterator::operator--() noexcept -> HashList<Key, Val>::Iterator&
168 {
169 if (phashList_ == nullptr) {
170 return *this;
171 }
172 Link* plink {nullptr};
173 if (pnode_ == nullptr) {
174 plink = phashList_->tail_.prev_;
175 } else {
176 plink = pnode_->link_.prev_;
177 }
178 if (plink == &phashList_->head_) {
179 pnode_ = nullptr;
180 phashList_ = nullptr;
181 return *this;
182 }
183 pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
184 return *this;
185 }
186
187 template <typename Key, typename Val>
188 auto HashList<Key, Val>::Iterator::operator--(int) noexcept -> HashList<Key, Val>::Iterator
189 {
190 Iterator res {*this};
191 if (phashList_ == nullptr) {
192 return res;
193 }
194 Link* plink {nullptr};
195 if (pnode_ == nullptr) {
196 plink = phashList_->tail_.prev_;
197 } else {
198 plink = pnode_->link_.prev_;
199 }
200 if (plink == &phashList_->head_) {
201 pnode_ = nullptr;
202 phashList_ = nullptr;
203 return res;
204 }
205 pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
206 return res;
207 }
208
209 template <typename Key, typename Val>
210 bool HashList<Key, Val>::Iterator::operator<(const HashList<Key, Val>::Iterator& itr) const noexcept
211 {
212 if (IsDangled() or itr.IsDangled()) {
213 return false;
214 }
215 if (phashList_ != itr.phashList_) {
216 return false;
217 }
218 Iterator tempItr {*this};
219 if (tempItr == itr) {
220 return false;
221 }
222 while (!tempItr.IsDangled()) {
223 tempItr++;
224 if (tempItr == itr) {
225 return true;
226 }
227 }
228 return false;
229 }
230
231 template <typename Key, typename Val>
232 bool HashList<Key, Val>::Iterator::operator==(const HashList<Key, Val>::Iterator& itr) const noexcept
233 {
234 if (IsDangled() or itr.IsDangled()) {
235 return false;
236 }
237 if (phashList_ != itr.phashList_) {
238 return false;
239 }
240 return pnode_ == itr.pnode_;
241 }
242
243 template <typename Key, typename Val> Val& HashList<Key, Val>::Iterator::operator*()
244 {
245 return pnode_->val_;
246 }
247
248 template <typename Key, typename Val> const Val& HashList<Key, Val>::Iterator::operator*() const
249 {
250 return pnode_->val_;
251 }
252
253 template <typename Key, typename Val> Val* HashList<Key, Val>::Iterator::operator->()
254 {
255 return &pnode_->val_;
256 }
257
258 template <typename Key, typename Val> const Val* HashList<Key, Val>::Iterator::operator->() const
259 {
260 return &pnode_->val_;
261 }
262
swap(HashList<Key,Val>::Iterator & other)263 template <typename Key, typename Val> void HashList<Key, Val>::Iterator::swap(HashList<Key, Val>::Iterator& other)
264 {
265 using std::swap;
266 swap(pnode_, other.pnode_);
267 swap(phashList_, other.phashList_);
268 }
269 // end of Iterator
270
271 // Implementation of ReverseIterator
272 template <typename Key, typename Val>
ReverseIterator(LinkNode<Key,Val> * pnode,HashList * phashList)273 HashList<Key, Val>::ReverseIterator::ReverseIterator(LinkNode<Key, Val>* pnode, HashList* phashList)
274 : pnode_ {pnode}, phashList_ {phashList}
275 {
276 if (phashList_ == nullptr) {
277 pnode_ = nullptr;
278 }
279 }
280
281 template <typename Key, typename Val>
ReverseIterator(const LinkNode<Key,Val> * pnode,const HashList * phashList)282 HashList<Key, Val>::ReverseIterator::ReverseIterator(const LinkNode<Key, Val>* pnode, const HashList* phashList)
283 : pnode_ {const_cast<LinkNode<Key, Val>*>(pnode)}, phashList_ {const_cast<HashList*>(phashList)}
284 {
285 if (phashList_ == nullptr) {
286 pnode_ = nullptr;
287 }
288 }
289
290 template <typename Key, typename Val>
ReverseIterator(const ReverseIterator & itr)291 HashList<Key, Val>::ReverseIterator::ReverseIterator(const ReverseIterator& itr)
292 : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
293 {
294 }
295
296 template <typename Key, typename Val>
ReverseIterator(ReverseIterator && itr)297 HashList<Key, Val>::ReverseIterator::ReverseIterator(ReverseIterator&& itr)
298 : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
299 {
300 itr.pnode_ = nullptr;
301 itr.phashList_ = nullptr;
302 }
303
304 template <typename Key, typename Val>
305 auto HashList<Key, Val>::ReverseIterator::operator=(const ReverseIterator& itr) -> HashList<Key, Val>::ReverseIterator&
306 {
307 ReverseIterator temp {itr};
308 swap(temp);
309 return *this;
310 }
311
312 template <typename Key, typename Val>
313 auto HashList<Key, Val>::ReverseIterator::operator=(ReverseIterator&& itr) -> HashList<Key, Val>::ReverseIterator&
314 {
315 ReverseIterator temp {std::move(itr)};
316 swap(temp);
317 return *this;
318 }
319
320 template <typename Key, typename Val>
321 auto HashList<Key, Val>::ReverseIterator::operator++() noexcept -> HashList<Key, Val>::ReverseIterator&
322 {
323 if (pnode_ == nullptr or phashList_ == nullptr) {
324 phashList_ = nullptr;
325 return *this;
326 }
327 Link* plink = &pnode_->link_;
328 plink = plink->prev_;
329 if (plink == &phashList_->head_) {
330 pnode_ = nullptr;
331 return *this;
332 }
333 pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
334 return *this;
335 }
336
337 template <typename Key, typename Val>
338 auto HashList<Key, Val>::ReverseIterator::operator++(int) noexcept -> HashList<Key, Val>::ReverseIterator
339 {
340 ReverseIterator res {*this};
341 if (pnode_ == nullptr or phashList_ == nullptr) {
342 phashList_ = nullptr;
343 return res;
344 }
345 Link* plink = &pnode_->link_;
346 plink = plink->prev_;
347 if (plink == &phashList_->head_) {
348 pnode_ = nullptr;
349 return res;
350 }
351 pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
352 return res;
353 }
354
355 template <typename Key, typename Val>
356 auto HashList<Key, Val>::ReverseIterator::operator--() noexcept -> HashList<Key, Val>::ReverseIterator&
357 {
358 if (phashList_ == nullptr) {
359 return *this;
360 }
361 Link* plink {nullptr};
362 if (pnode_ == nullptr) {
363 plink = phashList_->head_.next_;
364 } else {
365 plink = pnode_->link_.next_;
366 }
367 if (plink == &phashList_->tail_) {
368 pnode_ = nullptr;
369 phashList_ = nullptr;
370 return *this;
371 }
372 pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
373 return *this;
374 }
375
376 template <typename Key, typename Val>
377 auto HashList<Key, Val>::ReverseIterator::operator--(int) noexcept -> HashList<Key, Val>::ReverseIterator
378 {
379 ReverseIterator res {*this};
380 if (phashList_ == nullptr) {
381 return res;
382 }
383 Link* plink {nullptr};
384 if (pnode_ == nullptr) {
385 plink = phashList_->head_.next_;
386 } else {
387 plink = pnode_->link_.next_;
388 }
389 if (plink == &phashList_->tail_) {
390 pnode_ = nullptr;
391 phashList_ = nullptr;
392 return res;
393 }
394 pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
395 return res;
396 }
397
398 template <typename Key, typename Val>
399 bool HashList<Key, Val>::ReverseIterator::operator<(const HashList<Key, Val>::ReverseIterator& itr) const noexcept
400 {
401 if (IsDangled() or itr.IsDangled()) {
402 return false;
403 }
404 if (phashList_ != itr.phashList_) {
405 return false;
406 }
407 HashList<Key, Val>::ReverseIterator tempItr {*this};
408 if (tempItr == itr) {
409 return false;
410 }
411 while (!tempItr.IsDangled()) {
412 tempItr++;
413 if (tempItr == itr) {
414 return true;
415 }
416 }
417 return false;
418 }
419
420 template <typename Key, typename Val>
421 bool HashList<Key, Val>::ReverseIterator::operator==(const HashList<Key, Val>::ReverseIterator& itr) const noexcept
422 {
423 if (IsDangled() or itr.IsDangled()) {
424 return false;
425 }
426 if (phashList_ != itr.phashList_) {
427 return false;
428 }
429 return pnode_ == itr.pnode_;
430 }
431
432 template <typename Key, typename Val> Val& HashList<Key, Val>::ReverseIterator::operator*()
433 {
434 return pnode_->val_;
435 }
436
437 template <typename Key, typename Val> const Val& HashList<Key, Val>::ReverseIterator::operator*() const
438 {
439 return pnode_->val_;
440 }
441
442 template <typename Key, typename Val> Val* HashList<Key, Val>::ReverseIterator::operator->()
443 {
444 return &pnode_->val_;
445 }
446
447 template <typename Key, typename Val> const Val* HashList<Key, Val>::ReverseIterator::operator->() const
448 {
449 return &pnode_->val_;
450 }
451
452 template <typename Key, typename Val>
swap(HashList<Key,Val>::ReverseIterator & other)453 void HashList<Key, Val>::ReverseIterator::swap(HashList<Key, Val>::ReverseIterator& other)
454 {
455 using std::swap;
456 swap(pnode_, other.pnode_);
457 swap(phashList_, other.phashList_);
458 }
459 // end of ReverseIterator
460
461 // implementation of template class HashList
HashList()462 template <typename Key, typename Val> HashList<Key, Val>::HashList()
463 {
464 head_.next_ = &tail_;
465 tail_.prev_ = &head_;
466 }
467
~HashList()468 template <typename Key, typename Val> HashList<Key, Val>::~HashList()
469 {
470 while (head_.next_ != &tail_ and head_.next_ != nullptr) {
471 LinkNode<Key, Val>* curLinkNode = LinkNode<Key, Val>::GetLinkNode(head_.next_);
472 if (curLinkNode) {
473 head_.next_ = curLinkNode->link_.next_;
474 head_.next_->prev_ = &head_;
475 delete curLinkNode;
476 curLinkNode = nullptr;
477 } else {
478 break;
479 }
480 }
481 head_.next_ = &tail_;
482 tail_.prev_ = &head_;
483 valueTab_.clear();
484 }
485
HashList(const HashList & source)486 template <typename Key, typename Val> HashList<Key, Val>::HashList(const HashList& source)
487 {
488 // in this implememtation, no feedback of copy failure,
489 // user should check if copy succeeded
490 Link* curLink = &head_;
491 for (const auto& itr = source.begin(); itr < source.end(); ++itr) {
492 LinkNode<Key, Val>* curNode = LinkNode<Key, Val>::GetLinkNode(*itr);
493 if (curNode) {
494 LinkNode<Key, Val>* pnode = new (std::nothrow) LinkNode<Key, Val> {*curNode};
495 if (pnode) {
496 curLink->next_ = pnode->link_;
497 pnode->link_->prev_ = curLink;
498 curLink = curLink->next_;
499 valueTab_[pnode->key] = pnode;
500 pnode = nullptr;
501 } else {
502 break;
503 }
504 } else {
505 break;
506 }
507 }
508 curLink->next_ = &tail_;
509 tail_.prev_ = curLink;
510 }
511
512 template <typename Key, typename Val>
HashList(HashList<Key,Val> && source)513 HashList<Key, Val>::HashList(HashList<Key, Val>&& source)
514 : head_ {std::move(source.head_)}, tail_ {std::move(source.tail_)}, valueTab_ {std::move(source.valueTab_)}
515 {
516 source = HashList();
517 }
518
519 template <typename Key, typename Val> auto HashList<Key, Val>::operator=(const HashList& source) -> HashList<Key, Val>&
520 {
521 if (this == &source) {
522 return *this;
523 }
524 Link* curLink = &head_;
525 for (const auto& itr = source.begin(); itr < source.end(); ++itr) {
526 LinkNode<Key, Val>* curNode = LinkNode<Key, Val>::GetLinkNode(*itr);
527 if (curNode) {
new(std::nothrow)528 LinkNode<Key, Val>* pnode = new (std::nothrow) LinkNode<Key, Val> {*curNode};
529 if (pnode) {
530 curLink->next_ = pnode->link_;
531 pnode->link_->prev_ = curLink;
532 curLink = curLink->next_;
533 valueTab_[pnode->key] = pnode;
534 pnode = nullptr;
535 } else {
536 break;
537 }
538 } else {
539 break;
540 }
541 }
542 curLink->next_ = &tail_;
543 tail_.prev_ = curLink;
544 return *this;
545 }
546
547 template <typename Key, typename Val> auto HashList<Key, Val>::operator=(HashList&& source) -> HashList<Key, Val>&
548 {
549 if (this == &source) {
550 return *this;
551 }
552 head_ = std::move(source.head_);
553 tail_ = std::move(source.tail_);
554 valueTab_ = std::move(source.valueTab_);
555 source = HashList();
556 return *this;
557 }
558
559 template <typename Key, typename Val> auto HashList<Key, Val>::begin() -> HashList<Key, Val>::Iterator
560 {
561 if (empty()) {
562 return end();
563 }
564 return Iterator(LinkNode<Key, Val>::GetLinkNode(head_.next_), this);
565 }
566
567 template <typename Key, typename Val> auto HashList<Key, Val>::cbegin() const -> const HashList<Key, Val>::Iterator
568 {
569 if (empty()) {
570 return cend();
571 }
572 return Iterator(LinkNode<Key, Val>::GetLinkNode(head_.next_), this);
573 }
574
575 template <typename Key, typename Val> auto HashList<Key, Val>::end() -> HashList<Key, Val>::Iterator
576 {
577 return Iterator(nullptr, this);
578 }
579
580 template <typename Key, typename Val> auto HashList<Key, Val>::cend() const -> const HashList<Key, Val>::Iterator
581 {
582 return Iterator(nullptr, this);
583 }
584
585 template <typename Key, typename Val> auto HashList<Key, Val>::rbegin() -> HashList<Key, Val>::ReverseIterator
586 {
587 if (empty()) {
588 return rend();
589 }
590 return ReverseIterator(LinkNode<Key, Val>::GetLinkNode(tail_.prev_), this);
591 }
592
593 template <typename Key, typename Val>
594 auto HashList<Key, Val>::crbegin() const -> const HashList<Key, Val>::ReverseIterator
595 {
596 if (empty()) {
597 return crend();
598 }
599 return ReverseIterator(LinkNode<Key, Val>::GetLinkNode(tail_.prev_), this);
600 }
601
602 template <typename Key, typename Val> auto HashList<Key, Val>::rend() -> HashList<Key, Val>::ReverseIterator
603 {
604 return ReverseIterator(nullptr, this);
605 }
606
607 template <typename Key, typename Val>
608 auto HashList<Key, Val>::crend() const -> const HashList<Key, Val>::ReverseIterator
609 {
610 return ReverseIterator(nullptr, this);
611 }
612
front()613 template <typename Key, typename Val> Val& HashList<Key, Val>::front()
614 {
615 if (empty()) {
616 static Val temp {};
617 return temp;
618 }
619 LinkNode<Key, Val>* pnode = LinkNode<Key, Val>::GetLinkNode(head_.next_);
620 return pnode->val_;
621 }
622
front()623 template <typename Key, typename Val> const Val& HashList<Key, Val>::front() const
624 {
625 return front();
626 }
627
back(bool prepend)628 template <typename Key, typename Val> Val& HashList<Key, Val>::back(bool prepend)
629 {
630 if (empty()) {
631 static Val temp {};
632 return temp;
633 }
634 auto pnode = LinkNode<Key, Val>::GetLinkNode(tail_.prev_);
635 if (prepend) {
636 MoveToHead(pnode);
637 }
638 return pnode->val_;
639 }
640
641 template <typename Key, typename Val> Val& HashList<Key, Val>::operator[](const Key& key)
642 {
643 LinkNode<Key, Val>* pnode {nullptr};
644 if (valueTab_.find(key) == valueTab_.end()) {
645 pnode = new (std::nothrow) LinkNode<Key, Val>(key);
646 } else {
647 pnode = valueTab_[key];
648 }
649 if (pnode) {
650 MoveToHead(pnode);
651 }
652 return pnode->val_;
653 }
654
655 template <typename Key, typename Val> auto HashList<Key, Val>::find(const Key& key) -> HashList<Key, Val>::Iterator
656 {
657 const auto& itr = valueTab_.find(key);
658 if (itr == valueTab_.end()) {
659 return end();
660 }
661 return Iterator(itr->second, this);
662 }
663
push_front(const Key & key,const Val & val)664 template <typename Key, typename Val> void HashList<Key, Val>::push_front(const Key& key, const Val& val)
665 {
666 if (valueTab_.find(key) == valueTab_.end()) {
667 LinkNode<Key, Val>* pnode = new (std::nothrow) LinkNode<Key, Val>(key, val);
668 if (pnode) {
669 MoveToHead(pnode);
670 valueTab_[pnode->key_] = pnode;
671 }
672 } else {
673 MoveToHead(valueTab_[key]);
674 this->operator[](key) = val;
675 }
676 }
677
push_front(const Key & key,Val && val)678 template <typename Key, typename Val> void HashList<Key, Val>::push_front(const Key& key, Val&& val)
679 {
680 if (valueTab_.find(key) == valueTab_.end()) {
681 LinkNode<Key, Val>* pnode = new (std::nothrow) LinkNode<Key, Val>(key, std::move(val));
682 if (pnode) {
683 MoveToHead(pnode);
684 valueTab_[pnode->key_] = pnode;
685 }
686 } else {
687 MoveToHead(valueTab_[key]);
688 this->operator[](key) = val;
689 }
690 }
691
push_back(const Key & key,const Val & val)692 template <typename Key, typename Val> void HashList<Key, Val>::push_back(const Key& key, const Val& val)
693 {
694 if (valueTab_.find(key) == valueTab_.end()) {
695 LinkNode<Key, Val>* pnode = new (std::nothrow) LinkNode<Key, Val>(key, val);
696 if (pnode) {
697 MoveToTail(pnode);
698 valueTab_[pnode->key_] = pnode;
699 }
700 } else {
701 MoveToTail(valueTab_[key]);
702 this->operator[](key) = val;
703 }
704 }
705
push_back(const Key & key,Val && val)706 template <typename Key, typename Val> void HashList<Key, Val>::push_back(const Key& key, Val&& val)
707 {
708 if (valueTab_.find(key) == valueTab_.end()) {
709 LinkNode<Key, Val>* pnode = new (std::nothrow) LinkNode<Key, Val>(key, std::move(val));
710 if (pnode) {
711 MoveToTail(pnode);
712 valueTab_[pnode->key_] = pnode;
713 }
714 } else {
715 MoveToTail(valueTab_[key]);
716 this->operator[](key) = val;
717 }
718 }
719
pop_front()720 template <typename Key, typename Val> void HashList<Key, Val>::pop_front()
721 {
722 if (empty()) {
723 return;
724 }
725 LinkNode<Key, Val>* pnode = LinkNode<Key, Val>::GetLinkNode(head_.next_);
726 valueTab_.erase(pnode->key_);
727 EraseNode(head_.next_);
728 }
729
pop_back()730 template <typename Key, typename Val> void HashList<Key, Val>::pop_back()
731 {
732 if (empty()) {
733 return;
734 }
735 LinkNode<Key, Val>* pnode = LinkNode<Key, Val>::GetLinkNode(tail_.prev_);
736 valueTab_.erase(pnode->key_);
737 EraseNode(tail_.prev_);
738 }
739
740 template <typename Key, typename Val>
741 auto HashList<Key, Val>::insert(const Iterator pos, const Key& key, const Val& val) -> HashList<Key, Val>::Iterator
742 {
743 // assume pos is valid, otherwise the result is undefined
744 LinkNode<Key, Val>* pnode {nullptr};
745 if (valueTab_.find(key) == valueTab_.end()) {
746 pnode = new (std::nothrow) LinkNode<Key, Val>(key, val);
747 if (InsertNewNode(pos, pnode)) {
748 valueTab_[key] = pnode;
749 return Iterator(pnode, this);
750 } else {
751 return end();
752 }
753 }
754 pnode = valueTab_[key];
755 pnode->val_ = val;
756 if (MoveNode(pos, pnode)) {
757 return Iterator(pnode, this);
758 }
759 return end();
760 }
761
762 template <typename Key, typename Val>
763 auto HashList<Key, Val>::insert(const Iterator pos, const Key& key, Val&& val) -> HashList<Key, Val>::Iterator
764 {
765 // assume pos is valid, otherwise the result is undefined
766 LinkNode<Key, Val>* pnode {nullptr};
767 if (valueTab_.find(key) == valueTab_.end()) {
768 pnode = new (std::nothrow) LinkNode<Key, Val>(key, std::move(val));
769 if (InsertNewNode(pos, pnode)) {
770 valueTab_[key] = pnode;
771 return Iterator(pnode, this);
772 } else {
773 return end();
774 }
775 }
776 pnode = valueTab_[key];
777 pnode->val_ = val;
778 if (MoveNode(pos, pnode)) {
779 return Iterator(pnode, this);
780 }
781 return end();
782 }
783
784 template <typename Key, typename Val> auto HashList<Key, Val>::erase(const Key& key) -> HashList<Key, Val>::Iterator
785 {
786 if (valueTab_.find(key) == valueTab_.end()) {
787 auto pos = end();
788 ++pos;
789 return pos;
790 }
791 LinkNode<Key, Val>* pnode = valueTab_[key];
792 valueTab_.erase(key);
793 Link* plink = pnode->link_.next_;
794 Iterator tempItr {LinkNode<Key, Val>::GetLinkNode(plink), this};
795 EraseNode(pnode);
796 return tempItr;
797 }
798
799 template <typename Key, typename Val> auto HashList<Key, Val>::erase(const Iterator pos)
800 -> HashList<Key, Val>::Iterator
801 {
802 // assume pos is valid, otherwise the result is undefined
803 Iterator tempItr {pos};
804 ++tempItr;
805 LinkNode<Key, Val>* pnode = pos.GetNode();
806 valueTab_.erase(pnode->key_);
807 EraseNode(pnode);
808 return tempItr;
809 }
810
811 template <typename Key, typename Val>
812 auto HashList<Key, Val>::erase(const Iterator first, const Iterator last) -> HashList<Key, Val>::Iterator
813 {
814 // assume pos is valid, otherwise the result is undefined
815 if (first <= last) {
816 Iterator curPos {first};
817 while (curPos < last) {
818 curPos = erase(curPos);
819 }
820 return last;
821 }
822 auto pos = end();
823 ++pos;
824 return pos;
825 }
826
827 template <typename Key, typename Val>
InsertNewNode(const Iterator & pos,LinkNode<Key,Val> * & pnode)828 bool HashList<Key, Val>::InsertNewNode(const Iterator& pos, LinkNode<Key, Val>*& pnode)
829 {
830 if (pnode == nullptr) {
831 return false;
832 }
833 using namespace std::rel_ops;
834 if (begin() <= pos and pos <= end()) {
835 Link* prevLink {nullptr};
836 Link* nextLink {nullptr};
837 Link* currLink {nullptr};
838 if (pos == end()) {
839 prevLink = tail_.prev_;
840 nextLink = &tail_;
841 currLink = &pnode->link_;
842 } else {
843 LinkNode<Key, Val>* pnextNode = pos.GetNode();
844 nextLink = &pnextNode->link_;
845 prevLink = pnextNode->link_.prev_;
846 currLink = &pnode->link_;
847 }
848 prevLink->next_ = currLink;
849 currLink->next_ = nextLink;
850 nextLink->prev_ = currLink;
851 currLink->prev_ = prevLink;
852 return true;
853 }
854 delete pnode;
855 return false;
856 }
857
MoveNode(const Iterator & pos,LinkNode<Key,Val> * & pnode)858 template <typename Key, typename Val> bool HashList<Key, Val>::MoveNode(const Iterator& pos,
859 LinkNode<Key, Val>*& pnode)
860 {
861 if (pnode == nullptr) {
862 return false;
863 }
864 Link* prevLink = pnode->link_.prev_;
865 Link* nextLink = pnode->link_.next_;
866 if (prevLink == nullptr or nextLink == nullptr) {
867 return false;
868 }
869 prevLink->next_ = nextLink;
870 nextLink->prev_ = prevLink;
871 return InsertNewNode(pos, pnode);
872 }
873
MoveToHead(LinkNode<Key,Val> * & pnode)874 template <typename Key, typename Val> void HashList<Key, Val>::MoveToHead(LinkNode<Key, Val>*& pnode)
875 {
876 if (pnode) {
877 if (pnode->link_.prev_ and pnode->link_.next_) {
878 Link* prev = pnode->link_.prev_;
879 Link* next = pnode->link_.next_;
880 prev->next_ = next;
881 next->prev_ = prev;
882 pnode->link_.next_ = head_.next_;
883 head_.next_->prev_ = &pnode->link_;
884 head_.next_ = &pnode->link_;
885 pnode->link_.prev_ = &head_;
886 }
887 if (!pnode->link_.prev_ and !pnode->link_.next_) {
888 pnode->link_.next_ = head_.next_;
889 head_.next_->prev_ = &pnode->link_;
890 head_.next_ = &pnode->link_;
891 pnode->link_.prev_ = &head_;
892 }
893 }
894 }
895
MoveToTail(LinkNode<Key,Val> * & pnode)896 template <typename Key, typename Val> void HashList<Key, Val>::MoveToTail(LinkNode<Key, Val>*& pnode)
897 {
898 if (pnode) {
899 if (pnode->link_.prev_ and pnode->link_.next_) {
900 Link* prev = pnode->link_.prev_;
901 Link* next = pnode->link_.next_;
902 prev->next_ = next;
903 next->prev_ = prev;
904 pnode->link_.prev_ = tail_.prev_;
905 tail_.prev_->next_ = &pnode->link_;
906 pnode->link_.next_ = &tail_;
907 tail_.prev_ = &pnode->link_;
908 }
909 if (!pnode->link_.prev_ and !pnode->link_.next_) {
910 pnode->link_.prev_ = tail_.prev_;
911 tail_.prev_->next_ = &pnode->link_;
912 pnode->link_.next_ = &tail_;
913 tail_.prev_ = &pnode->link_;
914 }
915 }
916 }
917
EraseNode(LinkNode<Key,Val> * & pnode)918 template <typename Key, typename Val> void HashList<Key, Val>::EraseNode(LinkNode<Key, Val>*& pnode)
919 {
920 if (pnode) {
921 if (pnode->link_.prev_ and pnode->link_.next_) {
922 Link* prev = pnode->link_.prev_;
923 Link* next = pnode->link_.next_;
924 prev->next_ = next;
925 next->prev_ = prev;
926 }
927 delete pnode;
928 pnode = nullptr;
929 }
930 }
931
EraseNode(Link * & plink)932 template <typename Key, typename Val> void HashList<Key, Val>::EraseNode(Link*& plink)
933 {
934 LinkNode<Key, Val>* pnode = LinkNode<Key, Val>::GetLinkNode(plink);
935 EraseNode(pnode);
936 }
937 } // namespace NativeDaemon
938 } // namespace Developtools
939 } // namespace OHOS
940 #endif