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