xref: /developtools/hiperf/include/hashlist.h (revision 48f512ce) 
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
16#ifndef HIPERF_HASHLIST_H
17#define HIPERF_HASHLIST_H
18
19#include <unordered_map>
20
21namespace OHOS {
22namespace Developtools {
23namespace HiPerf {
24class Link {
25public:
26    Link() = default;
27    ~Link() = default;
28    Link(const Link &link) : prev_ {link.prev_}, next_ {link.next_} {}
29    Link(Link &&link) : prev_ {link.prev_}, next_ {link.next_}
30    {
31        link.prev_ = nullptr;
32        link.next_ = nullptr;
33    }
34    Link &operator=(const Link &link)
35    {
36        prev_ = link.prev_;
37        next_ = link.next_;
38        return *this;
39    }
40    Link &operator=(Link &&link)
41    {
42        prev_ = link.prev_;
43        link.prev_ = nullptr;
44        next_ = link.next_;
45        link.next_ = nullptr;
46        return *this;
47    }
48    Link *prev_ {nullptr};
49    Link *next_ {nullptr};
50};
51
52template<typename Key, typename Val>
53class LinkNode {
54public:
55    Link link_ {};
56    Key key_ {};
57    Val val_ {};
58
59    explicit LinkNode() = default;
60    ~LinkNode() = default;
61    explicit LinkNode(const Key &key);
62    explicit LinkNode(const Key &key, const Val &val);
63    explicit LinkNode(const Key &key, Val &&val);
64    LinkNode(const LinkNode &node);
65    LinkNode(LinkNode &&node);
66    LinkNode &operator=(const LinkNode &node);
67    LinkNode &operator=(LinkNode &&node);
68    static LinkNode<Key, Val> *GetLinkNode(Val *pval);
69    static LinkNode<Key, Val> *GetLinkNode(Link *plink);
70};
71
72template<typename Key, typename Val>
73class HashList {
74public:
75    class Iterator {
76    public:
77        Iterator() = default;
78        ~Iterator() = default;
79        explicit Iterator(LinkNode<Key, Val> *pnode, HashList *phashList);
80        explicit Iterator(const LinkNode<Key, Val> *pnode, const HashList *phashList);
81        Iterator(const Iterator &itr);
82        Iterator(Iterator &&itr);
83        Iterator &operator=(const Iterator &itr);
84        Iterator &operator=(Iterator &&itr);
85        Iterator &operator++() noexcept;
86        Iterator operator++(int) noexcept;
87        Iterator &operator--() noexcept;
88        Iterator operator--(int) noexcept;
89        bool operator<(const Iterator &itr) const noexcept;
90        bool operator==(const Iterator &itr) const noexcept;
91        Val &operator*();
92        const Val &operator*() const;
93        Val *operator->();
94        const Val *operator->() const;
95        void swap(HashList<Key, Val>::Iterator &other);
96        LinkNode<Key, Val> *GetNode() const
97        {
98            return pnode_;
99        }
100
101    private:
102        bool IsDangled() const noexcept
103        {
104            return phashList_ == nullptr;
105        }
106
107        LinkNode<Key, Val> *pnode_ {nullptr};
108        HashList *phashList_ {nullptr};
109    };
110
111    class ReverseIterator {
112    public:
113        ReverseIterator() = default;
114        ~ReverseIterator() = default;
115        explicit ReverseIterator(LinkNode<Key, Val> *pnode, HashList *phashList);
116        explicit ReverseIterator(const LinkNode<Key, Val> *pnode, const HashList *phashList);
117        ReverseIterator(const ReverseIterator &itr);
118        ReverseIterator(ReverseIterator &&itr);
119        ReverseIterator &operator=(const ReverseIterator &itr);
120        ReverseIterator &operator=(ReverseIterator &&itr);
121        ReverseIterator &operator++() noexcept;
122        ReverseIterator operator++(int) noexcept;
123        ReverseIterator &operator--() noexcept;
124        ReverseIterator operator--(int) noexcept;
125        bool operator<(const ReverseIterator &itr) const noexcept;
126        bool operator==(const ReverseIterator &itr) const noexcept;
127        Val &operator*();
128        const Val &operator*() const;
129        Val *operator->();
130        const Val *operator->() const;
131        void swap(HashList<Key, Val>::ReverseIterator &other);
132
133        LinkNode<Key, Val> *GetNode()
134        {
135            return pnode_;
136        }
137
138    private:
139        bool IsDangled() const noexcept
140        {
141            return phashList_ == nullptr;
142        }
143
144        LinkNode<Key, Val> *pnode_ {nullptr};
145        HashList *phashList_ {nullptr};
146    };
147
148public:
149    explicit HashList(const std::size_t numItem = 0);
150    ~HashList();
151
152    HashList(const HashList &source) = delete;
153    HashList &operator=(const HashList &source) = delete;
154    HashList(HashList &&source);
155    HashList &operator=(HashList &&source);
156
157    // capacity
158    inline std::size_t size() const
159    {
160        return valueTab_.size();
161    }
162    inline bool empty() const
163    {
164        return (dataHead_.next_ == &dataHead_) and (dataHead_.prev_ == &dataHead_);
165    }
166    inline std::size_t capacity() const
167    {
168        return numItem_;
169    }
170    inline bool IsFull() const
171    {
172        return freeHead_.next_ == &freeHead_;
173    }
174    inline std::size_t count(const Key &key) const
175    {
176        return valueTab_.count(key);
177    }
178
179    int reserve(const std::size_t numItem);
180    // iterators
181    Iterator begin();
182    const Iterator cbegin() const;
183    Iterator end();
184    const Iterator cend() const;
185    ReverseIterator rbegin();
186    const ReverseIterator crbegin() const;
187    ReverseIterator rend();
188    const ReverseIterator crend() const;
189    // element access
190    Val &front();
191    const Val &front() const;
192    Val &back(bool prepend = false);
193    Val &operator[](const Key &key);
194    // lookup
195    Iterator find(const Key &key);
196    // modifiers
197    void push_front(const Key &key, const Val &val);
198    void push_front(const Key &key, Val &&val);
199    void push_back(const Key &key, const Val &val);
200    void push_back(const Key &key, Val &&val);
201    void pop_front();
202    void pop_back();
203    Iterator erase(const Key &key);
204    Iterator erase(const Iterator pos);
205    Iterator erase(const Iterator first, const Iterator last);
206
207private:
208    void MoveToHead(LinkNode<Key, Val> *&pnode);
209    void MoveToTail(LinkNode<Key, Val> *&pnode);
210    bool MoveNode(const Iterator &pos, LinkNode<Key, Val> *&pnode);
211    LinkNode<Key, Val> *AllocateNode(const Key &key);
212    LinkNode<Key, Val> *AllocateNode(const Key &key, const Val &val);
213    LinkNode<Key, Val> *AllocateNode(const Key &key, Val &&val);
214    void ReclaimNode(LinkNode<Key, Val> *&pnode);
215
216    std::size_t numItem_ {0};
217    LinkNode<Key, Val> *pData_ {nullptr};
218    Link dataHead_ {};
219    Link freeHead_ {};
220    std::unordered_map<Key, LinkNode<Key, Val> *> valueTab_ {};
221};
222
223// implementation of template class LinkNode
224template<typename Key, typename Val>
225LinkNode<Key, Val>::LinkNode(const Key &key) : key_ {key} {}
226
227template<typename Key, typename Val>
228LinkNode<Key, Val>::LinkNode(const Key &key, const Val &val) : key_ {key}, val_ {val} {}
229
230template<typename Key, typename Val>
231LinkNode<Key, Val>::LinkNode(const Key &key, Val &&val) : key_ {key}, val_ {std::move(val)} {}
232
233template<typename Key, typename Val>
234LinkNode<Key, Val>::LinkNode(const LinkNode& node)
235    :link_ {node.link_},
236    key_ {node.key_},
237    val_ {node.val_}
238{}
239
240template<typename Key, typename Val>
241LinkNode<Key, Val>::LinkNode(LinkNode&& node)
242    :link_ {std::move(node.link_)},
243    key_ {std::move(node.key_)},
244    val_ {std::move(node.val_)}
245{}
246
247template<typename Key, typename Val>
248auto LinkNode<Key, Val>::operator=(const LinkNode& node)
249-> LinkNode<Key, Val>&
250{
251    link_ = node.link_;
252    key_ = node.key_;
253    val_ = node.val_;
254}
255
256template<typename Key, typename Val>
257auto LinkNode<Key, Val>::operator=(LinkNode&& node)
258-> LinkNode<Key, Val>&
259{
260    link_ = std::move(node.link_);
261    key_ = std::move(node.key_);
262    val_ = std::move(node.val_);
263}
264
265template<typename Key, typename Val>
266auto LinkNode<Key, Val>::GetLinkNode(Val *pval)
267-> LinkNode<Key, Val>*
268{
269    if (pval) {
270        LinkNode<Key, Val> *pnode {nullptr};
271        Val* offset = &pnode->val_;
272        auto nodeAddr = reinterpret_cast<char*>(pval) - reinterpret_cast<char*>(offset);
273        return reinterpret_cast<LinkNode<Key, Val>*>(nodeAddr);
274    }
275    return nullptr;
276}
277
278template<typename Key, typename Val>
279auto LinkNode<Key, Val>::GetLinkNode(Link *plink)
280-> LinkNode<Key, Val>*
281{
282    if (plink) {
283        LinkNode<Key, Val> *pnode {nullptr};
284        Link* offset = &pnode->link_;
285        auto  nodeAddr = reinterpret_cast<char*>(plink) - reinterpret_cast<char*>(offset);
286        return reinterpret_cast<LinkNode<Key, Val>*>(nodeAddr);
287    }
288    return nullptr;
289}
290// end of LinkNode
291
292// implementation of template class Iterator
293template<typename Key, typename Val>
294HashList<Key, Val>::Iterator::Iterator(LinkNode<Key, Val> *pnode, HashList *phashList)
295    : pnode_ {pnode}, phashList_ {phashList}
296{
297    if (phashList_ == nullptr) {
298        pnode_ = nullptr;
299    }
300}
301
302template<typename Key, typename Val>
303HashList<Key, Val>::Iterator::Iterator(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
312template<typename Key, typename Val>
313HashList<Key, Val>::Iterator::Iterator(const Iterator& itr)
314    : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
315{}
316
317template<typename Key, typename Val>
318HashList<Key, Val>::Iterator::Iterator(Iterator&& itr)
319    : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
320{
321    itr.pnode_ = nullptr;
322    itr.phashList_ = nullptr;
323}
324
325template<typename Key, typename Val>
326auto HashList<Key, Val>::Iterator::operator=(const Iterator& itr)
327-> HashList<Key, Val>::Iterator&
328{
329    Iterator temp {itr};
330    swap(temp);
331    return *this;
332}
333
334template<typename Key, typename Val>
335auto HashList<Key, Val>::Iterator::operator=(Iterator&& itr)
336-> HashList<Key, Val>::Iterator&
337{
338    Iterator temp {std::move(itr)};
339    swap(temp);
340    return *this;
341}
342
343template<typename Key, typename Val>
344auto HashList<Key, Val>::Iterator::operator++() noexcept
345-> HashList<Key, Val>::Iterator &
346{
347    if (pnode_ == nullptr or phashList_ == nullptr) {
348        phashList_ = nullptr;
349        return *this;
350    }
351    Link* plink = pnode_->link_.next_;
352    if (plink == &phashList_->dataHead_) {
353        pnode_ = nullptr;
354        return *this;
355    }
356    auto pnode = LinkNode<Key, Val>::GetLinkNode(plink);
357    pnode_ = pnode;
358    return *this;
359}
360
361template<typename Key, typename Val>
362auto HashList<Key, Val>::Iterator::operator++(int) noexcept
363-> HashList<Key, Val>::Iterator
364{
365    Iterator res {*this};
366    if (pnode_ == nullptr or phashList_ == nullptr) {
367        phashList_ = nullptr;
368        return res;
369    }
370    Link* plink = pnode_->link_.next_;
371    if (plink == &phashList_->dataHead_) {
372        pnode_ = nullptr;
373        return res;
374    }
375    auto pnode = LinkNode<Key, Val>::GetLinkNode(plink);
376    pnode_ = pnode;
377    return res;
378}
379
380template<typename Key, typename Val>
381auto HashList<Key, Val>::Iterator::operator--() noexcept
382-> HashList<Key, Val>::Iterator &
383{
384    if (phashList_ == nullptr) {
385        return *this;
386    }
387    Link* plink {nullptr};
388    if (pnode_ == nullptr) {
389        plink = phashList_->dataHead_.prev_;
390    } else {
391        plink = pnode_->link_.prev_;
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
402template<typename Key, typename Val>
403auto HashList<Key, Val>::Iterator::operator--(int) noexcept
404-> HashList<Key, Val>::Iterator
405{
406    Iterator res {*this};
407    if (phashList_ == nullptr) {
408        return res;
409    }
410    Link* plink {nullptr};
411    if (pnode_ == nullptr) {
412        plink = phashList_->dataHead_.prev_;
413    } else {
414        plink = pnode_->link_.prev_;
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
425template<typename Key, typename Val>
426bool HashList<Key, Val>::Iterator::operator<(const HashList<Key, Val>::Iterator &itr) const noexcept
427{
428    if (IsDangled() or itr.IsDangled()) {
429        return false;
430    }
431    if (phashList_ != itr.phashList_) {
432        return false;
433    }
434    Iterator tempItr {*this};
435    if (tempItr == itr) {
436        return false;
437    }
438    while (!tempItr.IsDangled()) {
439        tempItr++;
440        if (tempItr == itr) {
441            return true;
442        }
443    }
444    return false;
445}
446
447template<typename Key, typename Val>
448bool HashList<Key, Val>::Iterator::operator==(const HashList<Key, Val>::Iterator &itr) const noexcept
449{
450    if (IsDangled() or itr.IsDangled()) {
451        return false;
452    }
453    if (phashList_ != itr.phashList_) {
454        return false;
455    }
456    return pnode_ == itr.pnode_;
457}
458
459template<typename Key, typename Val>
460Val& HashList<Key, Val>::Iterator::operator*()
461{
462    return pnode_->val_;
463}
464
465template<typename Key, typename Val>
466const Val& HashList<Key, Val>::Iterator::operator*() const
467{
468    return pnode_->val_;
469}
470
471template<typename Key, typename Val>
472Val* HashList<Key, Val>::Iterator::operator->()
473{
474    return &pnode_->val_;
475}
476
477template<typename Key, typename Val>
478const Val* HashList<Key, Val>::Iterator::operator->() const
479{
480    return &pnode_->val_;
481}
482
483template<typename Key, typename Val>
484void HashList<Key, Val>::Iterator::swap(HashList<Key, Val>::Iterator& other)
485{
486    using std::swap;
487    swap(pnode_, other.pnode_);
488    swap(phashList_, other.phashList_);
489}
490// end of Iterator
491
492// Implementation of ReverseIterator
493template<typename Key, typename Val>
494HashList<Key, Val>::ReverseIterator::ReverseIterator(LinkNode<Key, Val> *pnode, HashList *phashList)
495    : pnode_ {pnode}, phashList_ {phashList}
496{
497    if (phashList_ == nullptr) {
498        pnode_ = nullptr;
499    }
500}
501
502template<typename Key, typename Val>
503HashList<Key, Val>::ReverseIterator::ReverseIterator(const LinkNode<Key, Val> *pnode, const HashList *phashList)
504    : pnode_ {const_cast<LinkNode<Key, Val> *>(pnode)},
505    phashList_ {const_cast<HashList *>(phashList)}
506{
507    if (phashList_ == nullptr) {
508        pnode_ = nullptr;
509    }
510}
511
512template<typename Key, typename Val>
513HashList<Key, Val>::ReverseIterator::ReverseIterator(const ReverseIterator &itr)
514    : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
515{}
516
517template<typename Key, typename Val>
518HashList<Key, Val>::ReverseIterator::ReverseIterator(ReverseIterator &&itr)
519    : pnode_ {itr.pnode_}, phashList_ {itr.phashList_}
520{
521    itr.pnode_ = nullptr;
522    itr.phashList_ = nullptr;
523}
524
525template<typename Key, typename Val>
526auto HashList<Key, Val>::ReverseIterator::operator=(const ReverseIterator& itr)
527-> HashList<Key, Val>::ReverseIterator&
528{
529    ReverseIterator temp {itr};
530    swap(temp);
531    return *this;
532}
533
534template<typename Key, typename Val>
535auto HashList<Key, Val>::ReverseIterator::operator=(ReverseIterator&& itr)
536-> HashList<Key, Val>::ReverseIterator&
537{
538    ReverseIterator temp {std::move(itr)};
539    swap(temp);
540    return *this;
541}
542
543template<typename Key, typename Val>
544auto HashList<Key, Val>::ReverseIterator::operator++() noexcept
545-> HashList<Key, Val>::ReverseIterator &
546{
547    if (pnode_ == nullptr or phashList_ == nullptr) {
548        phashList_ = nullptr;
549        return *this;
550    }
551    Link* plink = &pnode_->link_;
552    plink = plink->prev_;
553    if (plink == &phashList_->dataHead_) {
554        pnode_ = nullptr;
555        return *this;
556    }
557    pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
558    return *this;
559}
560
561template<typename Key, typename Val>
562auto HashList<Key, Val>::ReverseIterator::operator++(int) noexcept
563-> HashList<Key, Val>::ReverseIterator
564{
565    ReverseIterator res {*this};
566    if (pnode_ == nullptr or phashList_ == nullptr) {
567        phashList_ = nullptr;
568        return res;
569    }
570    Link* plink = &pnode_->link_;
571    plink = plink->prev_;
572    if (plink == &phashList_->dataHead_) {
573        pnode_ = nullptr;
574        return res;
575    }
576    pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
577    return res;
578}
579
580template<typename Key, typename Val>
581auto HashList<Key, Val>::ReverseIterator::operator--() noexcept
582-> HashList<Key, Val>::ReverseIterator &
583{
584    if (phashList_ == nullptr) {
585        return *this;
586    }
587    Link* plink {nullptr};
588    if (pnode_ == nullptr) {
589        plink = phashList_->dataHead_.next_;
590    } else {
591        plink = pnode_->link_.next_;
592    }
593    if (plink == &phashList_->dataHead_) {
594        pnode_ = nullptr;
595        phashList_ = nullptr;
596        return *this;
597    }
598    pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
599    return *this;
600}
601
602template<typename Key, typename Val>
603auto HashList<Key, Val>::ReverseIterator::operator--(int) noexcept
604-> HashList<Key, Val>::ReverseIterator
605{
606    ReverseIterator res {*this};
607    if (phashList_ == nullptr) {
608        return res;
609    }
610    Link* plink {nullptr};
611    if (pnode_ == nullptr) {
612        plink = phashList_->dataHead_.next_;
613    } else {
614        plink = pnode_->link_.next_;
615    }
616    if (plink == &phashList_->dataHead_) {
617        pnode_ = nullptr;
618        phashList_ = nullptr;
619        return res;
620    }
621    pnode_ = LinkNode<Key, Val>::GetLinkNode(plink);
622    return res;
623}
624
625template<typename Key, typename Val>
626bool HashList<Key, Val>::ReverseIterator::operator<(
627    const HashList<Key, Val>::ReverseIterator &itr) const noexcept
628{
629    if (IsDangled() or itr.IsDangled()) {
630        return false;
631    }
632    if (phashList_ != itr.phashList_) {
633        return false;
634    }
635    HashList<Key, Val>::ReverseIterator tempItr {*this};
636    if (tempItr == itr) {
637        return false;
638    }
639    while (!tempItr.IsDangled()) {
640        tempItr++;
641        if (tempItr == itr) {
642            return true;
643        }
644    }
645    return false;
646}
647
648template<typename Key, typename Val>
649bool HashList<Key, Val>::ReverseIterator::operator==(
650    const HashList<Key, Val>::ReverseIterator &itr) const noexcept
651{
652    if (IsDangled() or itr.IsDangled()) {
653        return false;
654    }
655    if (phashList_ != itr.phashList_) {
656        return false;
657    }
658    return pnode_ == itr.pnode_;
659}
660
661template<typename Key, typename Val>
662Val& HashList<Key, Val>::ReverseIterator::operator*()
663{
664    return pnode_->val_;
665}
666
667template<typename Key, typename Val>
668const Val& HashList<Key, Val>::ReverseIterator::operator*() const
669{
670    return pnode_->val_;
671}
672
673template<typename Key, typename Val>
674Val* HashList<Key, Val>::ReverseIterator::operator->()
675{
676    return &pnode_->val_;
677}
678
679template<typename Key, typename Val>
680const Val* HashList<Key, Val>::ReverseIterator::operator->() const
681{
682    return &pnode_->val_;
683}
684
685template<typename Key, typename Val>
686void HashList<Key, Val>::ReverseIterator::swap(HashList<Key, Val>::ReverseIterator& other)
687{
688    using std::swap;
689    swap(pnode_, other.pnode_);
690    swap(phashList_, other.phashList_);
691}
692// end of ReverseIterator
693
694// implementation of template class HashList
695template<typename Key, typename Val>
696HashList<Key, Val>::HashList(const std::size_t numItem) : numItem_ {numItem}
697{
698    dataHead_.next_ = &dataHead_;
699    dataHead_.prev_ = &dataHead_;
700    if (numItem_) {
701        valueTab_.reserve(numItem_);
702        pData_ = new(std::nothrow) LinkNode<Key, Val>[numItem_];
703        if (pData_) {
704            freeHead_.next_ = &(pData_[0].link_);
705            std::size_t last {numItem_ - 1};
706            for (std::size_t index = 0; index < last;) {
707                LinkNode<Key, Val> &curNnode = pData_[index];
708                curNnode.link_.next_ = &(pData_[++index].link_);
709            }
710            pData_[last].link_.next_ = &freeHead_;
711        } else {
712            numItem_ = 0;
713            freeHead_.next_ = &freeHead_;
714            freeHead_.prev_ = &freeHead_;
715        }
716    }
717}
718
719template<typename Key, typename Val>
720int HashList<Key, Val>::reserve(const std::size_t numItem)
721{
722    if (numItem_ != 0) {
723        return -1;
724    }
725    if (numItem) {
726        numItem_ = numItem;
727        valueTab_.reserve(numItem_);
728        pData_ = new(std::nothrow) LinkNode<Key, Val>[numItem_];
729        dataHead_.next_ = &dataHead_;
730        dataHead_.prev_ = &dataHead_;
731        if (pData_) {
732            freeHead_.next_ = &(pData_[0].link_);
733            std::size_t last {numItem_ - 1};
734            for (std::size_t index = 0; index < last;) {
735                LinkNode<Key, Val> &curNnode = pData_[index];
736                curNnode.link_.next_ = &(pData_[++index].link_);
737            }
738            pData_[last].link_.next_ = &freeHead_;
739        } else {
740            numItem_ = 0;
741            freeHead_.next_ = &freeHead_;
742            freeHead_.prev_ = &freeHead_;
743        }
744    }
745    return numItem_;
746}
747
748template<typename Key, typename Val>
749HashList<Key, Val>::~HashList()
750{
751    if (pData_) {
752        delete[] pData_;
753        pData_ = nullptr;
754    }
755    valueTab_.clear();
756    dataHead_.next_ = &dataHead_;
757    dataHead_.prev_ = &dataHead_;
758    freeHead_.next_ = nullptr;
759    freeHead_.prev_ = nullptr;
760    numItem_ = 0;
761}
762
763template<typename Key, typename Val>
764HashList<Key, Val>::HashList(HashList<Key, Val> &&source)
765    : numItem_ {source.numItem_},
766    pData_ {source.pData_},
767    dataHead_ {std::move(source.dataHead_)},
768    freeHead_ {std::move(source.freeHead_)},
769    valueTab_ {std::move(source.valueTab_)}
770{
771    source.pData_ = nullptr;
772}
773
774template<typename Key, typename Val>
775auto HashList<Key, Val>::operator=(HashList &&source)
776-> HashList<Key, Val>&
777{
778    if (this == &source) {
779        return *this;
780    }
781    if (pData_) {
782        delete[] pData_;
783        pData_ = nullptr;
784    }
785    numItem_ = source.numItem_;
786    pData_ = source.pData_;
787    source.pData_ = nullptr;
788    dataHead_ = std::move(source.dataHead_);
789    freeHead_ = std::move(source.freeHead_);
790    valueTab_ = std::move(source.valueTab_);
791    return *this;
792}
793
794template<typename Key, typename Val>
795auto HashList<Key, Val>::begin()
796-> HashList<Key, Val>::Iterator
797{
798    if (empty()) {
799        return end();
800    }
801    return Iterator(LinkNode<Key, Val>::GetLinkNode(dataHead_.next_), this);
802}
803
804template<typename Key, typename Val>
805auto HashList<Key, Val>::cbegin() const
806-> const HashList<Key, Val>::Iterator
807{
808    if (empty()) {
809        return cend();
810    }
811    return Iterator(LinkNode<Key, Val>::GetLinkNode(dataHead_.next_), this);
812}
813
814template<typename Key, typename Val>
815auto HashList<Key, Val>::end()
816-> HashList<Key, Val>::Iterator
817{
818    return Iterator(nullptr, this);
819}
820
821template<typename Key, typename Val>
822auto HashList<Key, Val>::cend() const
823-> const HashList<Key, Val>::Iterator
824{
825    return Iterator(nullptr, this);
826}
827
828template<typename Key, typename Val>
829auto HashList<Key, Val>::rbegin()
830-> HashList<Key, Val>::ReverseIterator
831{
832    if (empty()) {
833        return rend();
834    }
835    return ReverseIterator(LinkNode<Key, Val>::GetLinkNode(dataHead_.prev_), this);
836}
837
838template<typename Key, typename Val>
839auto HashList<Key, Val>::crbegin() const
840-> const HashList<Key, Val>::ReverseIterator
841{
842    if (empty()) {
843        return crend();
844    }
845    return ReverseIterator(LinkNode<Key, Val>::GetLinkNode(dataHead_.prev_), this);
846}
847
848template<typename Key, typename Val>
849auto HashList<Key, Val>::rend()
850-> HashList<Key, Val>::ReverseIterator
851{
852    return ReverseIterator(nullptr, this);
853}
854
855template<typename Key, typename Val>
856auto HashList<Key, Val>::crend() const
857-> const HashList<Key, Val>::ReverseIterator
858{
859    return ReverseIterator(nullptr, this);
860}
861
862template<typename Key, typename Val>
863Val& HashList<Key, Val>::front()
864{
865    LinkNode<Key, Val> *pnode = LinkNode<Key, Val>::GetLinkNode(dataHead_.next_);
866    return pnode->val_;
867}
868
869template<typename Key, typename Val>
870const Val& HashList<Key, Val>::front() const
871{
872    return front();
873}
874
875template<typename Key, typename Val>
876Val& HashList<Key, Val>::back(bool prepend)
877{
878    auto pnode = LinkNode<Key, Val>::GetLinkNode(dataHead_.prev_);
879    if (prepend) {
880        MoveToHead(pnode);
881    }
882    return pnode->val_;
883}
884
885template<typename Key, typename Val>
886Val& HashList<Key, Val>::operator[](const Key &key)
887{
888    LinkNode<Key, Val> *pnode {nullptr};
889    if (valueTab_.find(key) == valueTab_.end()) {
890        pnode = AllocateNode(key);
891        valueTab_[key] = pnode;
892    } else {
893        pnode = valueTab_[key];
894    }
895    if (pnode == nullptr) {
896        static Val val = Val();
897        return val;
898    } else {
899        MoveToHead(pnode);
900    }
901    return pnode->val_;
902}
903
904template<typename Key, typename Val>
905auto HashList<Key, Val>::find(const Key &key)
906-> HashList<Key, Val>::Iterator
907{
908    const auto &itr = valueTab_.find(key);
909    if (itr == valueTab_.end()) {
910        return end();
911    }
912    return Iterator(itr->second, this);
913}
914
915template<typename Key, typename Val>
916void HashList<Key, Val>::push_front(const Key& key, const Val& val)
917{
918    if (valueTab_.find(key) == valueTab_.end()) {
919        LinkNode<Key, Val>* pnode = AllocateNode(key, val);
920        MoveToHead(pnode);
921        valueTab_[pnode->key_] = pnode;
922    } else {
923        MoveToHead(valueTab_[key]);
924        this->operator[](key) =  val;
925    }
926}
927
928template<typename Key, typename Val>
929void HashList<Key, Val>::push_front(const Key& key, Val&& val)
930{
931    if (valueTab_.find(key) == valueTab_.end()) {
932        LinkNode<Key, Val>* pnode = AllocateNode(key, std::move(val));
933        MoveToHead(pnode);
934        valueTab_[pnode->key_] = pnode;
935    } else {
936        MoveToHead(valueTab_[key]);
937        this->operator[](key) =  val;
938    }
939}
940
941template<typename Key, typename Val>
942void HashList<Key, Val>::push_back(const Key& key, const Val& val)
943{
944    if (valueTab_.find(key) == valueTab_.end()) {
945        LinkNode<Key, Val>* pnode = AllocateNode(key, val);
946        MoveToTail(pnode);
947        valueTab_[pnode->key_] = pnode;
948    } else {
949        MoveToTail(valueTab_[key]);
950        this->operator[](key) =  val;
951    }
952}
953
954template<typename Key, typename Val>
955void HashList<Key, Val>::push_back(const Key& key, Val&& val)
956{
957    if (valueTab_.find(key) == valueTab_.end()) {
958        LinkNode<Key, Val>* pnode = AllocateNode(key, std::move(val));
959        MoveToTail(pnode);
960        valueTab_[pnode->key_] = pnode;
961    } else {
962        MoveToTail(valueTab_[key]);
963        this->operator[](key) =  val;
964    }
965}
966
967template<typename Key, typename Val>
968void HashList<Key, Val>::pop_front()
969{
970    if (empty()) {
971        return;
972    }
973    LinkNode<Key, Val>* pnode = LinkNode<Key, Val>::GetLinkNode(dataHead_.next_);
974    valueTab_.erase(pnode->key_);
975    ReclaimNode(pnode);
976}
977
978template<typename Key, typename Val>
979void HashList<Key, Val>::pop_back()
980{
981    if (empty()) {
982        return;
983    }
984    LinkNode<Key, Val>* pnode = LinkNode<Key, Val>::GetLinkNode(dataHead_.prev_);
985    if (pnode != nullptr) {
986        valueTab_.erase(pnode->key_);
987        ReclaimNode(pnode);
988    }
989}
990
991template<typename Key, typename Val>
992auto HashList<Key, Val>::erase(const Key& key)
993-> HashList<Key, Val>::Iterator
994{
995    if (valueTab_.find(key) == valueTab_.end()) {
996        return end();
997    }
998    LinkNode<Key, Val> *pnode = valueTab_[key];
999    valueTab_.erase(key);
1000    Link* plink = pnode->link_.next_;
1001    Iterator tempItr {LinkNode<Key, Val>::GetLinkNode(plink), this};
1002    ReclaimNode(pnode);
1003    return tempItr;
1004}
1005
1006template<typename Key, typename Val>
1007auto HashList<Key, Val>::erase(const Iterator pos)
1008-> HashList<Key, Val>::Iterator
1009{
1010    // assume pos is valid, otherwise the result is undefined
1011    Iterator tempItr {pos};
1012    ++tempItr;
1013    LinkNode<Key, Val> *pnode = pos.GetNode();
1014    valueTab_.erase(pnode->key_);
1015    ReclaimNode(pnode);
1016    return tempItr;
1017}
1018
1019template<typename Key, typename Val>
1020auto HashList<Key, Val>::erase(const Iterator first, const Iterator last)
1021-> HashList<Key, Val>::Iterator
1022{
1023    // assume pos is valid, otherwise the result is undefined
1024    if (first <= last) {
1025        Iterator curPos {first};
1026        while (curPos < last) {
1027            curPos = erase(curPos);
1028        }
1029        return last;
1030    }
1031    return end();
1032}
1033
1034template<typename Key, typename Val>
1035bool HashList<Key, Val>::MoveNode(const Iterator& pos, LinkNode<Key, Val> *&pnode)
1036{
1037    LinkNode<Key, Val> *curNode = pos.GetNode();
1038    if (curNode == pnode) {
1039        return true;
1040    }
1041    if (pnode->link_.next_ == &curNode->link_) {
1042        return true;
1043    }
1044    Link* prevLink = pnode->link_.prev_;
1045    Link* nextLink = pnode->link_.next_;
1046    if (prevLink and nextLink) {
1047        prevLink->next_ = nextLink;
1048        nextLink->prev_ = prevLink;
1049    }
1050    Link *currLink = &curNode->link_;
1051    prevLink = currLink->prev_;
1052    nextLink = &pnode->link_;
1053    prevLink->next_ = nextLink;
1054    nextLink->prev_ = prevLink;
1055    nextLink->next_ = currLink;
1056    currLink->prev_ = nextLink;
1057    return true;
1058}
1059
1060template<typename Key, typename Val>
1061void HashList<Key, Val>::MoveToHead(LinkNode<Key, Val> *&pnode)
1062{
1063    if (pnode->link_.prev_ and pnode->link_.next_) {
1064        Link* prev = pnode->link_.prev_;
1065        Link* next = pnode->link_.next_;
1066        prev->next_ = next;
1067        next->prev_ = prev;
1068    }
1069    pnode->link_.next_ = dataHead_.next_;
1070    dataHead_.next_->prev_ = &pnode->link_;
1071    dataHead_.next_ = &pnode->link_;
1072    pnode->link_.prev_ = &dataHead_;
1073}
1074
1075template<typename Key, typename Val>
1076void HashList<Key, Val>::MoveToTail(LinkNode<Key, Val> *&pnode)
1077{
1078    if (pnode->link_.prev_ and pnode->link_.next_) {
1079        Link* prev = pnode->link_.prev_;
1080        Link* next = pnode->link_.next_;
1081        prev->next_ = next;
1082        next->prev_ = prev;
1083    }
1084    pnode->link_.prev_ = dataHead_.prev_;
1085    dataHead_.prev_->next_ = &pnode->link_;
1086    pnode->link_.next_ = &dataHead_;
1087    dataHead_.prev_ = &pnode->link_;
1088}
1089
1090template<typename Key, typename Val>
1091auto HashList<Key, Val>::AllocateNode(const Key &key)
1092->LinkNode<Key, Val> *
1093{
1094    if (IsFull()) {
1095        pop_back();
1096    }
1097    LinkNode<Key, Val> *pnode = LinkNode<Key, Val>::GetLinkNode(freeHead_.next_);
1098    freeHead_.next_ = freeHead_.next_->next_;
1099    if (pnode != nullptr) {
1100        pnode->link_.next_ = nullptr;
1101        pnode->link_.prev_ = nullptr;
1102        pnode->key_ = key;
1103        pnode->val_ = Val();
1104    }
1105    return pnode;
1106}
1107
1108template<typename Key, typename Val>
1109auto HashList<Key, Val>::AllocateNode(const Key &key, const Val &val)
1110->LinkNode<Key, Val> *
1111{
1112    if (IsFull()) {
1113        pop_back();
1114    }
1115    LinkNode<Key, Val> *pnode = LinkNode<Key, Val>::GetLinkNode(freeHead_.next_);
1116    freeHead_.next_ = freeHead_.next_->next_;
1117    pnode->link_.next_ = nullptr;
1118    pnode->link_.prev_ = nullptr;
1119    pnode->key_ = key;
1120    pnode->val_ = val;
1121    return pnode;
1122}
1123
1124template<typename Key, typename Val>
1125auto HashList<Key, Val>::AllocateNode(const Key &key, Val &&val)
1126->LinkNode<Key, Val> *
1127{
1128    if (IsFull()) {
1129        pop_back();
1130    }
1131    LinkNode<Key, Val> *pnode = LinkNode<Key, Val>::GetLinkNode(freeHead_.next_);
1132    freeHead_.next_ = freeHead_.next_->next_;
1133    pnode->link_.next_ = nullptr;
1134    pnode->link_.prev_ = nullptr;
1135    pnode->key_ = key;
1136    pnode->val_ = std::move(val);
1137    return pnode;
1138}
1139
1140template<typename Key, typename Val>
1141void HashList<Key, Val>::ReclaimNode(LinkNode<Key, Val> *&pnode)
1142{
1143    Link *prevLink = pnode->link_.prev_;
1144    Link *nextLink = pnode->link_.next_;
1145    prevLink->next_ = nextLink;
1146    nextLink->prev_ = prevLink;
1147    pnode->link_.prev_ = nullptr;
1148    pnode->link_.next_ = freeHead_.next_;
1149    freeHead_.next_ = &pnode->link_;
1150    return;
1151}
1152} // namespace HiPerf
1153} // namespace Developtools
1154} // namespace OHOS
1155#endif // HIPERF_HASHLIST_H
1156