/* IBM_PROLOG_BEGIN_TAG */ /* This is an automatically generated prolog. */ /* */ /* $Source: src/include/list $ */ /* */ /* OpenPOWER HostBoot Project */ /* */ /* COPYRIGHT International Business Machines Corp. 2011,2014 */ /* */ /* 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. */ /* */ /* IBM_PROLOG_END_TAG */ #ifndef stl_list #define stl_list #include #if !defined( __STDC_LIMIT_MACROS) #define __STDC_LIMIT_MACROS #endif #include #include #include namespace std { /** * @class ListNode_t * * @note Non template dependent part of a list node. This code will not * get duplicated for each type T */ struct ListNode_t { ListNode_t * iv_next; ListNode_t * iv_prev; /** * Reset the node to point to itself * @post iv_next == iv_post == this */ void reset() { iv_next = this; iv_prev = this; } /** * Swap this node with another node * @param[in] i_otherNode The other node * @note This node is removed from it's chain and linked into the other nodes chain * The other node is removed form it's chain and linked into where this node * used to be. */ void swap(ListNode_t & i_otherNode) { ListNode_t temp; temp.link(*this); // put temp into this chain unlink(); // take this node out of the chain link(i_otherNode); // put this node into i_otherNode chain i_otherNode.unlink(); // take i_otherNode out of the chain i_otherNode.link(temp); // put i_otherNode into temp chain temp.unlink(); // take temp out of chain } /** * link this node into the i_node chain just before i_node. * @param[in] A node in node chain to link this node into */ void link(ListNode_t & i_node) { iv_next = &i_node; iv_prev = i_node.iv_prev; i_node.iv_prev = this; iv_prev->iv_next = this; } /** * Unlink this node from the chain * @post this node is orphaned. */ void unlink() { iv_prev->iv_next = iv_next; iv_next->iv_prev = iv_prev; reset(); } /** * Move given chain slice into this chain before this node * @param[in] pointer to first node in chain to merge it * @param[in] pointer to last node in chin to merge in * @pre i_first & i_last must be in the same chain * @post Given chain merged in before this node, including i_last * The chain i_first,i_last was taken from is healed. */ void merge(ListNode_t * i_first,ListNode_t * i_last) { ListNode_t * nodeP = iv_prev; // Remove the source slice from it's chain i_first->iv_prev->iv_next = i_last->iv_next; i_last->iv_next->iv_prev = i_first->iv_prev; // link in the new slice into this chain nodeP->iv_next = i_first; iv_prev = i_last; i_first->iv_prev = nodeP; i_last->iv_next = this; } /** * Query if node is part of a chain */ bool empty() const { return (iv_next == this) && (iv_prev == this); } }; /** * @class ListNodeData_t * * @note Template dependent part of a list node. */ template struct ListNodeData_t : public ListNode_t { T iv_data; }; /** * @class ListIterator_t * @brief Forward list iterator. * @note Forward iterators support: *
    *
  • operator==
    • *
  • operator!=
    • *
  • operator * (both rvalue, and left of assignemnt operator)
    • *
  • operator->
    • *
  • operator-- (pre and post)
    • *
  • operator++ (pre and post)
    • *
* @note Forward iterators are not random access i.e. don't support operator+ operator- */ template struct ListIterator_t { typedef ListIterator_t _This; typedef ListNodeData_t _Node; typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference; /** * Default constructior */ __attribute__ ((always_inline)) inline ListIterator_t() : iv_node() {} /** * Construct from a node pointer * @pararm[in] i_ln ListNode_t to use */ __attribute__ ((always_inline)) inline explicit ListIterator_t(ListNode_t* i_ln) : iv_node(i_ln) {} /** * Dereference * @return reference to node data */ __attribute__ ((always_inline)) inline reference operator* () const { return static_cast<_Node*>(iv_node)->iv_data; } /** * Dereference * @return pointer to node data */ __attribute__ ((always_inline)) inline pointer operator->() const { return &static_cast<_Node*>(iv_node)->iv_data; } /** * Pre Increment * @return reference to iterator */ __attribute__ ((always_inline)) inline _This& operator++() { iv_node = iv_node->iv_next; return *this; } /** * Post Increment * @return reference to iterator */ __attribute__ ((always_inline)) inline _This operator++(int) { _This tmp = *this; iv_node = iv_node->iv_next; return tmp; } /** * Pre decrement * @return reference to iterator */ __attribute__ ((always_inline)) inline _This& operator--() { iv_node = iv_node->iv_prev; return *this; } /** * Post decrement * @return reference to iterator */ __attribute__ ((always_inline)) inline _This operator--(int) { _This tmp = *this; iv_node = iv_node->iv_prev; return *this; } /** * Comparison * @param[in] Itertor to compare * @return true if ==, else false */ __attribute__ ((always_inline)) inline bool operator==(const _This& i_ln) const { return iv_node == i_ln.iv_node; } /** * Negative Comparison * @param[in] Iterator to compare * @return true if !=, else false; */ __attribute__ ((always_inline)) inline bool operator!=(const _This& i_ln) const { return iv_node != i_ln.iv_node; } ListNode_t * iv_node; ///! pointer to a list node }; /** * @class ListIterator_t * @brief const Forward list iterator. * @note Forward iterators support: *
    *
  • operator==
    • *
  • operator!=
    • *
  • operator * (rvalue only)
    • *
  • operator->
    • *
  • operator-- (pre and post)
    • *
  • operator++ (pre and post)
    • *
* @note Forward iterators are not random access i.e. don't support operator+ operator- */ template struct ListConstIterator_t { typedef ListConstIterator_t _This; typedef const ListNodeData_t _Node; typedef const ListIterator_t const_iterator; typedef T value_type; typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& const_reference; /** * Default constructior */ __attribute__ ((always_inline)) inline ListConstIterator_t() : iv_node() {} /** * Construct from a const node pointer * @pararm[i] ListNode_t to use */ __attribute__ ((always_inline)) inline explicit ListConstIterator_t(const ListNode_t* i_ln) : iv_node(i_ln) {} /** * Construct from another const_iterator * @param[i] const_iterator reference */ __attribute__ ((always_inline)) inline ListConstIterator_t(const_iterator& i_ln) : iv_node(i_ln.iv_node) {} /** * Dereference * @return const_reference to node data */ __attribute__ ((always_inline)) inline const_reference operator* () const { return static_cast<_Node*>(iv_node)->iv_data; } /** * Dereference * @return const pointer to node data */ __attribute__ ((always_inline)) inline pointer operator->() const { return &static_cast<_Node*>(iv_node)->iv_data; } /** * Pre Increment * @return reference to iterator */ __attribute__ ((always_inline)) inline _This& operator++() { iv_node = iv_node->iv_next; return *this; } /** * Post Increment * @return reference to iterator */ __attribute__ ((always_inline)) inline _This operator++(int) { _This tmp = *this; iv_node = iv_node->iv_next; return tmp; } /** * Pre decrement * @return reference to iterator */ __attribute__ ((always_inline)) inline _This& operator--() { iv_node = iv_node->iv_prev; return *this; } /** * Post decrement * @return reference to iterator */ __attribute__ ((always_inline)) inline _This operator--(int) { _This tmp = *this; iv_node = iv_node->iv_prev; return *this; } /** * Comparison * @param[in] Iterator to compare * @return true if ==, else false */ __attribute__ ((always_inline)) inline bool operator==(const _This& i_ln) const { return iv_node == i_ln.iv_node; } /** * Negative Comparison * @param[in] Itertor to compare * @return true if !=, else false; */ __attribute__ ((always_inline)) inline bool operator!=(const _This& i_ln) const { return iv_node != i_ln.iv_node; } public: // data const ListNode_t * iv_node; }; // So const and non-const iterators can be compared template __attribute__((always_inline)) inline bool operator==( const ListIterator_t& i_ln, const ListConstIterator_t& i_lm) { return i_ln.iv_node == i_lm.iv_node; } template __attribute__((always_inline)) inline bool operator!=( const ListIterator_t& i_ln, const ListConstIterator_t& i_lm) { return i_ln.iv_node != i_lm.iv_node; } /** * @class std::list * * @note *

Does not support: *

    *
  • allocators
    • *
  • reverse iterators
    • *
  • rbegin()
    • *
  • rend()
    • *
  • unique()
    • *
  • merge()
    • *
  • sort()
    • *
*/ template class list { public: typedef ListNodeData_t _Node; typedef size_t size_type; typedef T & reference; typedef const T& const_reference; typedef ListIterator_t iterator; typedef ListConstIterator_t const_iterator; protected: ListNode_t iv_node; private: /** * Allocate space for a node * @return pointer to the space for the node */ _Node * allocate_node() { return (_Node *) new uint8_t[sizeof(_Node)]; } /** Free node space * @param[in] pointer to the node */ void deallocate_node(ListNode_t * i_p) { delete (uint8_t *)i_p; } /** * Create a new node * @pararm reference to data element to use * @post Space allocated, element constructed */ _Node * makeNode(const T& i_x) { _Node * np = allocate_node(); new (&(np->iv_data)) T(i_x); return np; } /** * Destroy a node * @param pointer to node * @post destructor on element called, space freed. */ void destroyNode(ListNode_t * i_ln) { _Node * np = static_cast<_Node *>(i_ln); (&(np->iv_data))->~T(); deallocate_node(i_ln); } public: /** * Default ctor */ __attribute__ ((always_inline)) inline explicit list() { iv_node.reset(); } /** * ctor list of size n * @param[in] n element size * @param[in] value element reference used to construct elements */ explicit list (size_type n, const T& value = T()) { iv_node.reset(); while(n--) push_back(value); } /** * ctor from InputTerator * @param[i] first Iterator to first element to copy * @param[i] last Iterator to last element + 1 to copy. */ template list ( InputIterator first, InputIterator last) { iv_node.reset(); while(first != last) push_back(*first++); } /** * copy ctor * @param Referece list to copy. */ list ( const list& x) { iv_node.reset(); for(const_iterator i = x.begin(); i != x.end(); ++i) push_back(*i); } /** * dtor * @post Destructors called, storaged freed. */ __attribute__ ((always_inline)) inline ~list() { clear(); } /** * Assignment * @param[in] x reference list to copy. * @post any previously obtained iterators are invalid */ __attribute__ ((always_inline)) inline list& operator= (const list& x) { list new_list(x); swap(new_list); return *this; } // --- iterators /** * Get iterator to first element in the list */ __attribute__ ((always_inline)) inline iterator begin() { return iterator(iv_node.iv_next); } /** * Get const_iterator to the first element in the list */ __attribute__ ((always_inline)) inline const_iterator begin() const { return const_iterator(iv_node.iv_next); } /** * Get an iterator to the last element in the list + 1 */ __attribute__ ((always_inline)) inline iterator end() { return iterator(&iv_node); } /** * Get a const_iterator to the last element in the list + 1 */ __attribute__ ((always_inline)) inline const_iterator end() const { return const_iterator(&iv_node); } //reverse_iterator rbegin(); //const_reverse_iterator rbegin() const; //reverse_iterator rend(); //const_reverse_iterator rend() const; // ---------------- Capacity /** * Query for empty container * @return bool, true if size()==0 else false. * @pre none * @post none */ __attribute__ ((always_inline)) inline bool empty() const { return iv_node.empty(); } /** * Get the number of elements in the container * @return number of elements in the container */ size_type size() const { size_type size = 0; for(const_iterator i = begin(); i != end(); ++i) ++size; return(size); } /** * Return the maximum potential size the container could reach. * @return number of the maximum element count this container could reach */ __attribute__ ((always_inline)) inline size_type max_size() const { return UINT64_MAX/sizeof(T); } /** * Resize the vector to contain n elements * @param n, new size * @param object used to copy to any added elements if size() is increased * @post All previously obtained iterators are invalid. * @node if n < size(), vector is truncated. * if n > size(), vector is padded with copies of x */ void resize( size_type n, T x = T() ) { size_type sz = size(); if(n < sz) { while(n != sz--) pop_back(); } else if(n > sz) { while(n != sz++) push_back(x); } // else n == size() do nothing } //---------------Element Access /** * Get a reference to the first element in the list */ __attribute__ ((always_inline)) inline reference front() { return *begin(); } /** * Get a const_reference to the first element in the list */ __attribute__ ((always_inline)) inline const_reference front() const { return *begin(); } /** * Get a reference to the last element in the list */ __attribute__ ((always_inline)) inline reference back() { iterator i = end(); --i; return *i; } /** * Get a const_reference to the last element in the list */ __attribute__ ((always_inline)) inline const_reference back() const { const_iterator i = end(); --i; return *i; } //---------- Modifiers /** * Assign a slice of a container to this list * @param[in] first InputIterator to the first element to assign * @pararm[in] last InputIterator to the last element to assign * @post any previously obtained iterators are invalid */ template __attribute__ ((always_inline)) inline void assign( InputIterator first, InputIterator last) { list new_list(first,last); swap(new_list); } /** * Assign a list of n elements of type T * @param[in] n Number of elements to assign * @param[in] x Reference to the element used to create elements. * @post any previously obtained iterators are invalid */ __attribute__ ((always_inline)) inline void assign( size_type n, const T& x) { list new_list(n,x); swap(new_list); } /** * Add an element to the front fo the list * @pararm Element to add */ __attribute__ ((always_inline)) inline void push_front (const T& x) { insert(begin(),x); } /** * Remove the element at the front of the container */ __attribute__ ((always_inline)) inline void pop_front () { erase(begin()); } /** * Add an element to the back of the container * @param[in] x referece to element to add * @post size()+= 1; */ __attribute__ ((always_inline)) inline void push_back (const T& x) { insert(end(),x); } /** * Remove the element at the back of the container */ __attribute__ ((always_inline)) inline void pop_back () { iterator i = end(); --i; erase(i); } /** * Instert an element into the container at the given position * @param[in] pos Iterator position to insert element * @return iterator to newly inserved element */ iterator insert ( iterator pos, const T& x) { ListNode_t * node = makeNode(x); node->link(*pos.iv_node); return iterator(node); } /** * Insert n elements at the given position * @param[in] pos position to insert elements * @param[in] n number of elements to insert * @param[in] ref const_reference of element used to create elements */ void insert(iterator pos, size_type n, const T& ref) { while(n--) insert ( pos, ref); } /** * Insert a copy of a container slice into this container * @param[in] pos iterator to postion to add elements in this list * @param[in] first InputIterator to the first element to copy insert * @param[in] last InputIterator to the last element+1 to copy insert */ template void insert (iterator pos, InputIterator first, InputIterator last) { while(first != last) { pos = insert(pos,*first++); ++pos; } } /** * Erase the element at the given postion * @pararm[i] pos iterator to position to erase/remove * @return iterator to the element following the one removed */ iterator erase (iterator pos) { iterator ret = end(); if(!empty()) { ret = pos; ++ret; (pos.iv_node)->unlink(); destroyNode(pos.iv_node); } return ret; } /** * Erase a range of elements * @param[in] first iterator to the first element to erase * @param[in] last iterator to the last element+1 to erase * @return iterator to the element following the last one removed */ iterator erase (iterator first, iterator last) { while(first != last) first = erase(first); return last; } /** * Swap the elements of this containers with the one provided * @param[in] reference to list container to swap elements with. */ void swap ( list& i_that) { iv_node.swap(i_that.iv_node); } /** * clear all elements from the ist. * @post size() == 0; elements destroyed, space freed. */ void clear() { iterator i = begin(); while( i != end() ) { iterator j = i++; destroyNode(j.iv_node); } iv_node.reset(); } // -------- operations /** * Move elements from another list container to this list container at the given position. * @param[in] pos position in this list to move elements to * @param[in] list object of containing the same type of elements as this one. * @pre x != *this * @post this->size() += x.size(); x.empty() == true */ void splice ( iterator pos, list& x) { if(!x.empty()) { pos.iv_node->merge(x.iv_node.iv_next,x.iv_node.iv_prev); } } /** * Move an element from another list into this list at the given position. * @param[in] pos position destination in this list to move element to * @param[in] x list object containing the same type of elements as this one. * @param[in] i postion source in list x to move element from * @pre x can be *this if pos != i * @post Iterators pointing to moved elements are no longer valid. * this->size() += 1, if (x != *this) x.size() -= 1; */ void splice ( iterator pos, list& x, iterator i) { i.iv_node->unlink(); i.iv_node->link(*pos.iv_node); } /** * Move elements from another list container to this list container at the given position. * @param[in] pos postion in this list container to move elements to. * @param[in] x list object containing the same type of elements as this one. * @param[in] first iterator to first element to move. * @param[in] last iterator to last element to move + 1. * @pre x can be *this as long as pos < first || pos >= last * @post x.size() is reduced by # of elements moved if x is not *this * size() is increased by # of elements moved. * Iterator pointing to moved elements are no longer valid. * @note Moves all elements between first & last, including first, but not including last */ void splice ( iterator pos, list& x, iterator first, iterator last) { --last; pos.iv_node->merge(first.iv_node,last.iv_node); } /** * Remove all elements with the specific value. * @param[in] value that must match to remove * @post Matched objects destroyed and removed from list */ void remove ( const T& value ) { iterator i = begin(); while(i != end()) { iterator j = i++; if(*j == value) erase(j); } } /** * Removes from the list all the elements for which Predicate returns true. * @param[in] predicate function or functor * @post Matched objects destroyed and removed from list * @note Predicate can be implemented as any typed expression taking one * argument of the same type as the list and returning bool. * This may either be a function pointer or an object whose class * implements operator(). */ template void remove_if ( Predicate pred ) { iterator i = begin(); while(i != end()) { iterator j = i++; if(pred(*j)) erase(j); } } /** * Remove all but the first element from every consecutive group of equal elements. * @pre This container is sorted. * @post All but the first element from every consecutive group of equal elements is removed * @note An element is only removed from the list if it is equal to the element * immediately preceding it. * @note Not implemented */ void unique( ); /** * Remove all but the first element from every consecutive group of unique elements * where uniqueness is determined by the BinaryPredicate. * @note The BinaryPredicate takes two values of the same type as in the list, * returns true to remove from the container the element passed as first * argument. * Not implmented */ template void unique ( BinaryPredicate binary_pred); /** * Merges another list into this list, inserting elements into the list at their * repective ordered positions. * @param[in] x container of same type elements as this container. * @pre The containers are sorted. * @post x.size() == 0 * @note Not Implemented */ void merge( list& x ); /** * Merges another list into this list, inserting elements into the list at their * repective ordered positions. * @post x.size() == 0 * @note The comparison function takes two values of the same type as the list * elements, returns true of the first argument is less than the second, otherwise * false * @note Not Implemented */ template void merge ( list& x, Compare comp); /** * Sort the elements in the list from lower to higher * @pre Container element objects must implement operator<. * @note Not Implemented */ void sort(); /** * Sort the elements in the list from lower to higher using compare function * @param Compare function that takes two values the same type as contained in the * list; returns true if first arg goes before second arg, otherwise false. * @note Not Implemented. */ template void sort (Compare comp); /** * Reverse the order of the elements in the list. */ void reverse () { iterator i = begin(); while(i != end()) { iterator j = i++; std::swap(j.iv_node->iv_next,j.iv_node->iv_prev); } std::swap(iv_node.iv_next,iv_node.iv_prev); } }; }; #endif /* vim: set filetype=cpp : */