diff options
author | dgilbert <dgilbert@us.ibm.com> | 2011-05-09 12:28:02 -0500 |
---|---|---|
committer | A. Patrick Williams III <iawillia@us.ibm.com> | 2011-05-18 10:41:46 -0500 |
commit | 358def6287d9f11e2a80e6e15557d45ff50ec13a (patch) | |
tree | bf684616ace7d6331bcf87f32398109a10b5dbfa /src/include/list | |
parent | 5f28dffa51ef4fe402e1e8609fd8afa44e834db6 (diff) | |
download | talos-hostboot-358def6287d9f11e2a80e6e15557d45ff50ec13a.tar.gz talos-hostboot-358def6287d9f11e2a80e6e15557d45ff50ec13a.zip |
Initial STL code delivery with code review changes.
Change-Id: Ib4226e1351acce15cacbe643eb2fb4f0dfb56855
Reviewed-on: http://gfwr801.rchland.ibm.com:8080/gerrit/68
Tested-by: Jenkins Server
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>
Diffstat (limited to 'src/include/list')
-rw-r--r-- | src/include/list | 1005 |
1 files changed, 1005 insertions, 0 deletions
diff --git a/src/include/list b/src/include/list new file mode 100644 index 000000000..cd3a83f0a --- /dev/null +++ b/src/include/list @@ -0,0 +1,1005 @@ +#ifndef stl_list +#define stl_list + +#include <stddef.h> +#if !defined( __STDC_LIMIT_MACROS) +#define __STDC_LIMIT_MACROS +#endif +#include <stdint.h> +#include <new> +#include <algorithm> + +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 <typename T> + struct ListNodeData_t : public ListNode_t + { + T iv_data; + }; + + /** + * @class ListIterator_t + * @brief Forward list iterator. + * @note Forward iterators support: + * <ul> + * <li> operator== </li> + * <li> operator!= </li> + * <li> operator * (both rvalue, and left of assignemnt operator) </li> + * <li> operator-> </li> + * <li> operator-- (pre and post) </li> + * <li> operator++ (pre and post) </li> + * </ul> + * @note Forward iterators are not random access i.e. don't support operator+ operator- + */ + template<typename T> + struct ListIterator_t + { + typedef ListIterator_t<T> _This; + typedef ListNodeData_t<T> _Node; + + typedef T* pointer; + typedef T& reference; + + /** + * Default constructior + */ + __attribute__ ((always_inline)) + ListIterator_t() : iv_node() + {} + + + /** + * Construct from a node pointer + * @pararm[in] i_ln ListNode_t to use + */ + __attribute__ ((always_inline)) + explicit ListIterator_t(ListNode_t* i_ln) : iv_node(i_ln) + {} + + /** + * Dereference + * @return reference to node data + */ + __attribute__ ((always_inline)) + reference operator* () const + { + return static_cast<_Node*>(iv_node)->iv_data; + } + + /** + * Dereference + * @return pointer to node data + */ + __attribute__ ((always_inline)) + pointer operator->() const + { + return &static_cast<_Node*>(iv_node)->iv_data; + } + + /** + * Pre Increment + * @return reference to iterator + */ + __attribute__ ((always_inline)) + _This& operator++() + { + iv_node = iv_node->iv_next; return *this; + } + + /** + * Post Increment + * @return reference to iterator + */ + __attribute__ ((always_inline)) + _This operator++(int) + { + _This tmp = *this; + iv_node = iv_node->iv_next; + return tmp; + } + + /** + * Pre decrement + * @return reference to iterator + */ + __attribute__ ((always_inline)) + _This& operator--() + { + iv_node = iv_node->iv_prev; + return *this; + } + + /** + * Post decrement + * @return reference to iterator + */ + __attribute__ ((always_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)) + 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)) + 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: + * <ul> + * <li> operator== </li> + * <li> operator!= </li> + * <li> operator * (rvalue only) </li> + * <li> operator-> </li> + * <li> operator-- (pre and post) </li> + * <li> operator++ (pre and post) </li> + * </ul> + * @note Forward iterators are not random access i.e. don't support operator+ operator- + */ + template<typename T> + struct ListConstIterator_t + { + typedef ListConstIterator_t<T> _This; + typedef const ListNodeData_t<T> _Node; + typedef const ListIterator_t<T> const_iterator; + + typedef const T* pointer; + typedef const T& const_reference; + + /** + * Default constructior + */ + __attribute__ ((always_inline)) + ListConstIterator_t() : iv_node() + {} + + /** + * Construct from a const node pointer + * @pararm[i] ListNode_t to use + */ + __attribute__ ((always_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)) + ListConstIterator_t(const_iterator& i_ln) : iv_node(i_ln.iv_node) + {} + + /** + * Dereference + * @return const_reference to node data + */ + __attribute__ ((always_inline)) + const_reference operator* () const + { + return static_cast<_Node*>(iv_node)->iv_data; + } + + /** + * Dereference + * @return const pointer to node data + */ + __attribute__ ((always_inline)) + pointer operator->() const + { + return &static_cast<_Node*>(iv_node)->iv_data; + } + + /** + * Pre Increment + * @return reference to iterator + */ + __attribute__ ((always_inline)) + _This& operator++() + { + iv_node = iv_node->iv_next; return *this; + } + + /** + * Post Increment + * @return reference to iterator + */ + __attribute__ ((always_inline)) + _This operator++(int) + { + _This tmp = *this; + iv_node = iv_node->iv_next; + return tmp; + } + + /** + * Pre decrement + * @return reference to iterator + */ + __attribute__ ((always_inline)) + _This& operator--() + { + iv_node = iv_node->iv_prev; + return *this; + } + + /** + * Post decrement + * @return reference to iterator + */ + __attribute__ ((always_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)) + 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)) + 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<typename VAL> __attribute__((always_inline)) + bool + operator==( const ListIterator_t<VAL>& i_ln, + const ListConstIterator_t<VAL>& i_lm) + { + return i_ln.iv_node == i_lm.iv_node; + } + + template<typename VAL> __attribute__((always_inline)) + bool + operator !=( const ListIterator_t<VAL>& i_ln, + const ListConstIterator_t<VAL>& i_lm) + { + return i_ln.iv_node != i_lm.iv_node; + } + + /** + * @class std::list + * + * @note + * <p>Does not support: + * <ul> + * <li> allocators </li> + * <li> reverse iterators </li> + * <li> rbegin() </li> + * <li> rend() </li> + * <li> unique() </li> + * <li> merge() </li> + * <li> sort() </li> + * </ul> + */ + template<typename T> + class list + { + public: + typedef ListNodeData_t<T> _Node; + typedef size_t size_type; + typedef T & reference; + typedef const T& const_reference; + typedef ListIterator_t<T> iterator; + typedef ListConstIterator_t<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)) + 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 <class InputIterator > + list ( InputIterator first, InputIterator last) + { + iv_node.reset(); + while(first != last) push_back(*first++); + } + + /** + * copy ctor + * @param Referece list to copy. + */ + list ( const list<T>& 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)) + ~list() + { + clear(); + } + + /** + * Assignment + * @param[in] x reference list to copy. + * @post any previously obtained iterators are invalid + */ + __attribute__ ((always_inline)) + list<T>& operator= (const list<T>& x) + { + list<T> new_list(x); + swap(new_list); + return *this; + } + + // --- iterators + + /** + * Get iterator to first element in the list + */ + __attribute__ ((always_inline)) + iterator begin() { return iterator(iv_node.iv_next); } + + /** + * Get const_iterator to the first element in the list + */ + __attribute__ ((always_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)) + iterator end() { return iterator(&iv_node); } + + /** + * Get a const_iterator to the last element in the list + 1 + */ + __attribute__ ((always_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)) + 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)) + 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)) + reference front() + { + return *begin(); + } + + /** + * Get a const_reference to the first element in the list + */ + __attribute__ ((always_inline)) + const_reference front() const + { + return *begin(); + } + + /** + * Get a reference to the last element in the list + */ + __attribute__ ((always_inline)) + reference back() + { + iterator i = end(); + --i; + return *i; + } + + /** + * Get a const_reference to the last element in the list + */ + __attribute__ ((always_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 <class InputIterator> + __attribute__ ((always_inline)) + void assign( InputIterator first, InputIterator last) + { + list<T> 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)) + void assign( size_type n, const T& x) + { + list<T> new_list(n,x); + swap(new_list); + } + + /** + * Add an element to the front fo the list + * @pararm Element to add + */ + __attribute__ ((always_inline)) + void push_front (const T& x) + { + insert(begin(),x); + } + + /** + * Remove the element at the front of the container + */ + __attribute__ ((always_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)) + void push_back (const T& x) + { + insert(end(),x); + } + + /** + * Remove the element at the back of the container + */ + __attribute__ ((always_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 <class InputIterator> + 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<T>& 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<T>& 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<T>& 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<T>& 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 <class Predicate> + 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 <class BinaryPredicate> + 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<T>& 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 <class Compare> + void merge ( list<T>& 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 <class Compare> + 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 |