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