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