1 /*
2  * Copyright (C) 2005 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 //
18 // Templated list class.  Normally we'd use STL, but we don't have that.
19 // This class mimics STL's interfaces.
20 //
21 // Objects are copied into the list with the '=' operator or with copy-
22 // construction, so if the compiler's auto-generated versions won't work for
23 // you, define your own.
24 //
25 // The only class you want to use from here is "List".
26 //
27 
28 #pragma once
29 
30 #include <stddef.h>
31 #include <stdint.h>
32 
33 namespace keymaster {
34 
35 /*
36  * Doubly-linked list.  Instantiate with "List<MyClass> myList".
37  *
38  * Objects added to the list are copied using the assignment operator,
39  * so this must be defined.
40  */
41 template <typename T> class List {
42   protected:
43     /*
44      * One element in the list.
45      */
46     class _Node {
47       public:
_Node(const T & val)48         explicit _Node(const T& val) : mVal(val) {}
~_Node()49         ~_Node() {}
getRef()50         inline T& getRef() { return mVal; }
getRef()51         inline const T& getRef() const { return mVal; }
getPrev()52         inline _Node* getPrev() const { return mpPrev; }
getNext()53         inline _Node* getNext() const { return mpNext; }
setVal(const T & val)54         inline void setVal(const T& val) { mVal = val; }
setPrev(_Node * ptr)55         inline void setPrev(_Node* ptr) { mpPrev = ptr; }
setNext(_Node * ptr)56         inline void setNext(_Node* ptr) { mpNext = ptr; }
57 
58       private:
59         friend class List;
60         friend class _ListIterator;
61         T mVal;
62         _Node* mpPrev;
63         _Node* mpNext;
64     };
65 
66     /*
67      * Iterator for walking through the list.
68      */
69 
70     template <typename TYPE> struct CONST_ITERATOR {
71         typedef _Node const* NodePtr;
72         typedef const TYPE Type;
73     };
74 
75     template <typename TYPE> struct NON_CONST_ITERATOR {
76         typedef _Node* NodePtr;
77         typedef TYPE Type;
78     };
79 
80     template <typename U, template <class> class Constness> class _ListIterator {
81         typedef _ListIterator<U, Constness> _Iter;
82         typedef typename Constness<U>::NodePtr _NodePtr;
83         typedef typename Constness<U>::Type _Type;
84 
_ListIterator(_NodePtr ptr)85         explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
86 
87       public:
_ListIterator()88         _ListIterator() {}
_ListIterator(const _Iter & rhs)89         _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
~_ListIterator()90         ~_ListIterator() {}
91 
92         // this will handle conversions from iterator to const_iterator
93         // (and also all convertible iterators)
94         // Here, in this implementation, the iterators can be converted
95         // if the nodes can be converted
_ListIterator(const V & rhs)96         template <typename V> explicit _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
97 
98         /*
99          * Dereference operator.  Used to get at the juicy insides.
100          */
101         _Type& operator*() const { return mpNode->getRef(); }
102         _Type* operator->() const { return &(mpNode->getRef()); }
103 
104         /*
105          * Iterator comparison.
106          */
107         inline bool operator==(const _Iter& right) const { return mpNode == right.mpNode; }
108 
109         inline bool operator!=(const _Iter& right) const { return mpNode != right.mpNode; }
110 
111         /*
112          * handle comparisons between iterator and const_iterator
113          */
114         template <typename OTHER> inline bool operator==(const OTHER& right) const {
115             return mpNode == right.mpNode;
116         }
117 
118         template <typename OTHER> inline bool operator!=(const OTHER& right) const {
119             return mpNode != right.mpNode;
120         }
121 
122         /*
123          * Incr/decr, used to move through the list.
124          */
125         inline _Iter& operator++() {  // pre-increment
126             mpNode = mpNode->getNext();
127             return *this;
128         }
129         const _Iter operator++(int) {  // post-increment
130             _Iter tmp(*this);
131             mpNode = mpNode->getNext();
132             return tmp;
133         }
134         inline _Iter& operator--() {  // pre-increment
135             mpNode = mpNode->getPrev();
136             return *this;
137         }
138         const _Iter operator--(int) {  // post-increment
139             _Iter tmp(*this);
140             mpNode = mpNode->getPrev();
141             return tmp;
142         }
143 
getNode()144         inline _NodePtr getNode() const { return mpNode; }
145 
146         _NodePtr mpNode; /* should be private, but older gcc fails */
147       private:
148         friend class List;
149     };
150 
151   public:
List()152     List() { prep(); }
List(const List<T> & src)153     List(const List<T>& src) {  // copy-constructor
154         prep();
155         insert(begin(), src.begin(), src.end());
156     }
~List()157     virtual ~List() {
158         clear();
159         delete[](unsigned char*) mpMiddle;
160     }
161 
162     typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
163     typedef _ListIterator<T, CONST_ITERATOR> const_iterator;
164 
165     List<T>& operator=(const List<T>& right);
166 
167     /* returns true if the list is empty */
empty()168     inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
169 
170     /* return #of elements in list */
size()171     size_t size() const { return size_t(distance(begin(), end())); }
172 
173     /*
174      * Return the first element or one past the last element.  The
175      * _Node* we're returning is converted to an "iterator" by a
176      * constructor in _ListIterator.
177      */
begin()178     inline iterator begin() { return iterator(mpMiddle->getNext()); }
begin()179     inline const_iterator begin() const {
180         return const_iterator(const_cast<_Node const*>(mpMiddle->getNext()));
181     }
end()182     inline iterator end() { return iterator(mpMiddle); }
end()183     inline const_iterator end() const { return const_iterator(const_cast<_Node const*>(mpMiddle)); }
184 
185     /* add the object to the head or tail of the list */
push_front(const T & val)186     void push_front(const T& val) { insert(begin(), val); }
push_back(const T & val)187     void push_back(const T& val) { insert(end(), val); }
188 
189     /* insert before the current node; returns iterator at new node */
insert(iterator posn,const T & val)190     iterator insert(iterator posn, const T& val) {
191         _Node* newNode = new (std::nothrow) _Node(val);  // alloc & copy-construct
192         newNode->setNext(posn.getNode());
193         newNode->setPrev(posn.getNode()->getPrev());
194         posn.getNode()->getPrev()->setNext(newNode);
195         posn.getNode()->setPrev(newNode);
196         return iterator(newNode);
197     }
198 
199     /* insert a range of elements before the current node */
insert(iterator posn,const_iterator first,const_iterator last)200     void insert(iterator posn, const_iterator first, const_iterator last) {
201         for (; first != last; ++first)
202             insert(posn, *first);
203     }
204 
205     /* remove one entry; returns iterator at next node */
erase(iterator posn)206     iterator erase(iterator posn) {
207         _Node* pNext = posn.getNode()->getNext();
208         _Node* pPrev = posn.getNode()->getPrev();
209         pPrev->setNext(pNext);
210         pNext->setPrev(pPrev);
211         delete posn.getNode();
212         return iterator(pNext);
213     }
214 
215     /* remove a range of elements */
erase(iterator first,iterator last)216     iterator erase(iterator first, iterator last) {
217         while (first != last)
218             erase(first++);  // don't erase than incr later!
219         return iterator(last);
220     }
221 
222     /* remove all contents of the list */
clear()223     void clear() {
224         _Node* pCurrent = mpMiddle->getNext();
225         _Node* pNext;
226 
227         while (pCurrent != mpMiddle) {
228             pNext = pCurrent->getNext();
229             delete pCurrent;
230             pCurrent = pNext;
231         }
232         mpMiddle->setPrev(mpMiddle);
233         mpMiddle->setNext(mpMiddle);
234     }
235 
236     /*
237      * Measure the distance between two iterators.  On exist, "first"
238      * will be equal to "last".  The iterators must refer to the same
239      * list.
240      *
241      * FIXME: This is actually a generic iterator function. It should be a
242      * template function at the top-level with specializations for things like
243      * vector<>, which can just do pointer math). Here we limit it to
244      * _ListIterator of the same type but different constness.
245      */
246     template <typename U, template <class> class CL, template <class> class CR>
distance(_ListIterator<U,CL> first,_ListIterator<U,CR> last)247     ptrdiff_t distance(_ListIterator<U, CL> first, _ListIterator<U, CR> last) const {
248         ptrdiff_t count = 0;
249         while (first != last) {
250             ++first;
251             ++count;
252         }
253         return count;
254     }
255 
256   private:
257     /*
258      * I want a _Node but don't need it to hold valid data.  More
259      * to the point, I don't want T's constructor to fire, since it
260      * might have side-effects or require arguments.  So, we do this
261      * slightly uncouth storage alloc.
262      */
prep()263     void prep() {
264         mpMiddle = (_Node*)new (std::nothrow) unsigned char[sizeof(_Node)];
265         mpMiddle->setPrev(mpMiddle);
266         mpMiddle->setNext(mpMiddle);
267     }
268 
269     /*
270      * This node plays the role of "pointer to head" and "pointer to tail".
271      * It sits in the middle of a circular list of nodes.  The iterator
272      * runs around the circle until it encounters this one.
273      */
274     _Node* mpMiddle;
275 };
276 
277 /*
278  * Assignment operator.
279  *
280  * The simplest way to do this would be to clear out the target list and
281  * fill it with the source.  However, we can speed things along by
282  * re-using existing elements.
283  */
284 template <class T> List<T>& List<T>::operator=(const List<T>& right) {
285     if (this == &right) return *this;  // self-assignment
286     iterator firstDst = begin();
287     iterator lastDst = end();
288     const_iterator firstSrc = right.begin();
289     const_iterator lastSrc = right.end();
290     while (firstSrc != lastSrc && firstDst != lastDst)
291         *firstDst++ = *firstSrc++;
292     if (firstSrc == lastSrc)       // ran out of elements in source?
293         erase(firstDst, lastDst);  // yes, erase any extras
294     else
295         insert(lastDst, firstSrc, lastSrc);  // copy remaining over
296     return *this;
297 }
298 
299 };  // namespace keymaster
300