1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/media/omx-plugin/include/froyo/utils/List.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,332 @@
1.4 +/*
1.5 + * Copyright (C) 2005 The Android Open Source Project
1.6 + *
1.7 + * Licensed under the Apache License, Version 2.0 (the "License");
1.8 + * you may not use this file except in compliance with the License.
1.9 + * You may obtain a copy of the License at
1.10 + *
1.11 + * http://www.apache.org/licenses/LICENSE-2.0
1.12 + *
1.13 + * Unless required by applicable law or agreed to in writing, software
1.14 + * distributed under the License is distributed on an "AS IS" BASIS,
1.15 + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1.16 + * See the License for the specific language governing permissions and
1.17 + * limitations under the License.
1.18 + */
1.19 +
1.20 +//
1.21 +// Templated list class. Normally we'd use STL, but we don't have that.
1.22 +// This class mimics STL's interfaces.
1.23 +//
1.24 +// Objects are copied into the list with the '=' operator or with copy-
1.25 +// construction, so if the compiler's auto-generated versions won't work for
1.26 +// you, define your own.
1.27 +//
1.28 +// The only class you want to use from here is "List".
1.29 +//
1.30 +#ifndef _LIBS_UTILS_LIST_H
1.31 +#define _LIBS_UTILS_LIST_H
1.32 +
1.33 +#include <stddef.h>
1.34 +#include <stdint.h>
1.35 +
1.36 +namespace android {
1.37 +
1.38 +/*
1.39 + * Doubly-linked list. Instantiate with "List<MyClass> myList".
1.40 + *
1.41 + * Objects added to the list are copied using the assignment operator,
1.42 + * so this must be defined.
1.43 + */
1.44 +template<typename T>
1.45 +class List
1.46 +{
1.47 +protected:
1.48 + /*
1.49 + * One element in the list.
1.50 + */
1.51 + class _Node {
1.52 + public:
1.53 + explicit _Node(const T& val) : mVal(val) {}
1.54 + ~_Node() {}
1.55 + inline T& getRef() { return mVal; }
1.56 + inline const T& getRef() const { return mVal; }
1.57 + inline _Node* getPrev() const { return mpPrev; }
1.58 + inline _Node* getNext() const { return mpNext; }
1.59 + inline void setVal(const T& val) { mVal = val; }
1.60 + inline void setPrev(_Node* ptr) { mpPrev = ptr; }
1.61 + inline void setNext(_Node* ptr) { mpNext = ptr; }
1.62 + private:
1.63 + friend class List;
1.64 + friend class _ListIterator;
1.65 + T mVal;
1.66 + _Node* mpPrev;
1.67 + _Node* mpNext;
1.68 + };
1.69 +
1.70 + /*
1.71 + * Iterator for walking through the list.
1.72 + */
1.73 +
1.74 + template <typename TYPE>
1.75 + struct CONST_ITERATOR {
1.76 + typedef _Node const * NodePtr;
1.77 + typedef const TYPE Type;
1.78 + };
1.79 +
1.80 + template <typename TYPE>
1.81 + struct NON_CONST_ITERATOR {
1.82 + typedef _Node* NodePtr;
1.83 + typedef TYPE Type;
1.84 + };
1.85 +
1.86 + template<
1.87 + typename U,
1.88 + template <class> class Constness
1.89 + >
1.90 + class _ListIterator {
1.91 + typedef _ListIterator<U, Constness> _Iter;
1.92 + typedef typename Constness<U>::NodePtr _NodePtr;
1.93 + typedef typename Constness<U>::Type _Type;
1.94 +
1.95 + explicit _ListIterator(_NodePtr ptr) : mpNode(ptr) {}
1.96 +
1.97 + public:
1.98 + _ListIterator() {}
1.99 + _ListIterator(const _Iter& rhs) : mpNode(rhs.mpNode) {}
1.100 + ~_ListIterator() {}
1.101 +
1.102 + // this will handle conversions from iterator to const_iterator
1.103 + // (and also all convertible iterators)
1.104 + // Here, in this implementation, the iterators can be converted
1.105 + // if the nodes can be converted
1.106 + template<typename V> explicit
1.107 + _ListIterator(const V& rhs) : mpNode(rhs.mpNode) {}
1.108 +
1.109 +
1.110 + /*
1.111 + * Dereference operator. Used to get at the juicy insides.
1.112 + */
1.113 + _Type& operator*() const { return mpNode->getRef(); }
1.114 + _Type* operator->() const { return &(mpNode->getRef()); }
1.115 +
1.116 + /*
1.117 + * Iterator comparison.
1.118 + */
1.119 + inline bool operator==(const _Iter& right) const {
1.120 + return mpNode == right.mpNode; }
1.121 +
1.122 + inline bool operator!=(const _Iter& right) const {
1.123 + return mpNode != right.mpNode; }
1.124 +
1.125 + /*
1.126 + * handle comparisons between iterator and const_iterator
1.127 + */
1.128 + template<typename OTHER>
1.129 + inline bool operator==(const OTHER& right) const {
1.130 + return mpNode == right.mpNode; }
1.131 +
1.132 + template<typename OTHER>
1.133 + inline bool operator!=(const OTHER& right) const {
1.134 + return mpNode != right.mpNode; }
1.135 +
1.136 + /*
1.137 + * Incr/decr, used to move through the list.
1.138 + */
1.139 + inline _Iter& operator++() { // pre-increment
1.140 + mpNode = mpNode->getNext();
1.141 + return *this;
1.142 + }
1.143 + const _Iter operator++(int) { // post-increment
1.144 + _Iter tmp(*this);
1.145 + mpNode = mpNode->getNext();
1.146 + return tmp;
1.147 + }
1.148 + inline _Iter& operator--() { // pre-increment
1.149 + mpNode = mpNode->getPrev();
1.150 + return *this;
1.151 + }
1.152 + const _Iter operator--(int) { // post-increment
1.153 + _Iter tmp(*this);
1.154 + mpNode = mpNode->getPrev();
1.155 + return tmp;
1.156 + }
1.157 +
1.158 + inline _NodePtr getNode() const { return mpNode; }
1.159 +
1.160 + _NodePtr mpNode; /* should be private, but older gcc fails */
1.161 + private:
1.162 + friend class List;
1.163 + };
1.164 +
1.165 +public:
1.166 + List() {
1.167 + prep();
1.168 + }
1.169 + List(const List<T>& src) { // copy-constructor
1.170 + prep();
1.171 + insert(begin(), src.begin(), src.end());
1.172 + }
1.173 + virtual ~List() {
1.174 + clear();
1.175 + delete[] (unsigned char*) mpMiddle;
1.176 + }
1.177 +
1.178 + typedef _ListIterator<T, NON_CONST_ITERATOR> iterator;
1.179 + typedef _ListIterator<T, CONST_ITERATOR> const_iterator;
1.180 +
1.181 + List<T>& operator=(const List<T>& right);
1.182 +
1.183 + /* returns true if the list is empty */
1.184 + inline bool empty() const { return mpMiddle->getNext() == mpMiddle; }
1.185 +
1.186 + /* return #of elements in list */
1.187 + size_t size() const {
1.188 + return size_t(distance(begin(), end()));
1.189 + }
1.190 +
1.191 + /*
1.192 + * Return the first element or one past the last element. The
1.193 + * _Node* we're returning is converted to an "iterator" by a
1.194 + * constructor in _ListIterator.
1.195 + */
1.196 + inline iterator begin() {
1.197 + return iterator(mpMiddle->getNext());
1.198 + }
1.199 + inline const_iterator begin() const {
1.200 + return const_iterator(const_cast<_Node const*>(mpMiddle->getNext()));
1.201 + }
1.202 + inline iterator end() {
1.203 + return iterator(mpMiddle);
1.204 + }
1.205 + inline const_iterator end() const {
1.206 + return const_iterator(const_cast<_Node const*>(mpMiddle));
1.207 + }
1.208 +
1.209 + /* add the object to the head or tail of the list */
1.210 + void push_front(const T& val) { insert(begin(), val); }
1.211 + void push_back(const T& val) { insert(end(), val); }
1.212 +
1.213 + /* insert before the current node; returns iterator at new node */
1.214 + iterator insert(iterator posn, const T& val)
1.215 + {
1.216 + _Node* newNode = new _Node(val); // alloc & copy-construct
1.217 + newNode->setNext(posn.getNode());
1.218 + newNode->setPrev(posn.getNode()->getPrev());
1.219 + posn.getNode()->getPrev()->setNext(newNode);
1.220 + posn.getNode()->setPrev(newNode);
1.221 + return iterator(newNode);
1.222 + }
1.223 +
1.224 + /* insert a range of elements before the current node */
1.225 + void insert(iterator posn, const_iterator first, const_iterator last) {
1.226 + for ( ; first != last; ++first)
1.227 + insert(posn, *first);
1.228 + }
1.229 +
1.230 + /* remove one entry; returns iterator at next node */
1.231 + iterator erase(iterator posn) {
1.232 + _Node* pNext = posn.getNode()->getNext();
1.233 + _Node* pPrev = posn.getNode()->getPrev();
1.234 + pPrev->setNext(pNext);
1.235 + pNext->setPrev(pPrev);
1.236 + delete posn.getNode();
1.237 + return iterator(pNext);
1.238 + }
1.239 +
1.240 + /* remove a range of elements */
1.241 + iterator erase(iterator first, iterator last) {
1.242 + while (first != last)
1.243 + erase(first++); // don't erase than incr later!
1.244 + return iterator(last);
1.245 + }
1.246 +
1.247 + /* remove all contents of the list */
1.248 + void clear() {
1.249 + _Node* pCurrent = mpMiddle->getNext();
1.250 + _Node* pNext;
1.251 +
1.252 + while (pCurrent != mpMiddle) {
1.253 + pNext = pCurrent->getNext();
1.254 + delete pCurrent;
1.255 + pCurrent = pNext;
1.256 + }
1.257 + mpMiddle->setPrev(mpMiddle);
1.258 + mpMiddle->setNext(mpMiddle);
1.259 + }
1.260 +
1.261 + /*
1.262 + * Measure the distance between two iterators. On exist, "first"
1.263 + * will be equal to "last". The iterators must refer to the same
1.264 + * list.
1.265 + *
1.266 + * FIXME: This is actually a generic iterator function. It should be a
1.267 + * template function at the top-level with specializations for things like
1.268 + * vector<>, which can just do pointer math). Here we limit it to
1.269 + * _ListIterator of the same type but different constness.
1.270 + */
1.271 + template<
1.272 + typename U,
1.273 + template <class> class CL,
1.274 + template <class> class CR
1.275 + >
1.276 + ptrdiff_t distance(
1.277 + _ListIterator<U, CL> first, _ListIterator<U, CR> last) const
1.278 + {
1.279 + ptrdiff_t count = 0;
1.280 + while (first != last) {
1.281 + ++first;
1.282 + ++count;
1.283 + }
1.284 + return count;
1.285 + }
1.286 +
1.287 +private:
1.288 + /*
1.289 + * I want a _Node but don't need it to hold valid data. More
1.290 + * to the point, I don't want T's constructor to fire, since it
1.291 + * might have side-effects or require arguments. So, we do this
1.292 + * slightly uncouth storage alloc.
1.293 + */
1.294 + void prep() {
1.295 + mpMiddle = (_Node*) new unsigned char[sizeof(_Node)];
1.296 + mpMiddle->setPrev(mpMiddle);
1.297 + mpMiddle->setNext(mpMiddle);
1.298 + }
1.299 +
1.300 + /*
1.301 + * This node plays the role of "pointer to head" and "pointer to tail".
1.302 + * It sits in the middle of a circular list of nodes. The iterator
1.303 + * runs around the circle until it encounters this one.
1.304 + */
1.305 + _Node* mpMiddle;
1.306 +};
1.307 +
1.308 +/*
1.309 + * Assignment operator.
1.310 + *
1.311 + * The simplest way to do this would be to clear out the target list and
1.312 + * fill it with the source. However, we can speed things along by
1.313 + * re-using existing elements.
1.314 + */
1.315 +template<class T>
1.316 +List<T>& List<T>::operator=(const List<T>& right)
1.317 +{
1.318 + if (this == &right)
1.319 + return *this; // self-assignment
1.320 + iterator firstDst = begin();
1.321 + iterator lastDst = end();
1.322 + const_iterator firstSrc = right.begin();
1.323 + const_iterator lastSrc = right.end();
1.324 + while (firstSrc != lastSrc && firstDst != lastDst)
1.325 + *firstDst++ = *firstSrc++;
1.326 + if (firstSrc == lastSrc) // ran out of elements in source?
1.327 + erase(firstDst, lastDst); // yes, erase any extras
1.328 + else
1.329 + insert(lastDst, firstSrc, lastSrc); // copy remaining over
1.330 + return *this;
1.331 +}
1.332 +
1.333 +}; // namespace android
1.334 +
1.335 +#endif // _LIBS_UTILS_LIST_H
