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