diff options
author | Stephen Cprek <smcprek@us.ibm.com> | 2016-09-30 16:55:15 -0500 |
---|---|---|
committer | Daniel M. Crowell <dcrowell@us.ibm.com> | 2016-10-30 22:44:23 -0400 |
commit | a6f34cd9b2c79e803e564b917951b63f9252d02a (patch) | |
tree | a3afd7a876addc0b5a27b97fb37dc06c46103bfc /src/include | |
parent | 99552570de2dfc1f11f22746c5cdb86820f154b8 (diff) | |
download | talos-hostboot-a6f34cd9b2c79e803e564b917951b63f9252d02a.tar.gz talos-hostboot-a6f34cd9b2c79e803e564b917951b63f9252d02a.zip |
Implement std::array
Change-Id: I86149816b46f213502801fb710dc2f68d4a4b0f7
Reviewed-on: http://ralgit01.raleigh.ibm.com/gerrit1/30647
Tested-by: Jenkins Server <pfd-jenkins+hostboot@us.ibm.com>
Reviewed-by: Martin Gloff <mgloff@us.ibm.com>
Tested-by: FSP CI Jenkins <fsp-CI-jenkins+hostboot@us.ibm.com>
Reviewed-by: Andres A. Lugo-Reyes <aalugore@us.ibm.com>
Reviewed-by: A. P. Williams III <iawillia@us.ibm.com>
Reviewed-by: Daniel M. Crowell <dcrowell@us.ibm.com>
Diffstat (limited to 'src/include')
-rw-r--r-- | src/include/algorithm | 140 | ||||
-rw-r--r-- | src/include/array | 507 |
2 files changed, 647 insertions, 0 deletions
diff --git a/src/include/algorithm b/src/include/algorithm index 9641a797a..cc3886ff5 100644 --- a/src/include/algorithm +++ b/src/include/algorithm @@ -78,6 +78,38 @@ namespace std } /** + * Swaps the values of the elements the given iterators are pointing to. + * @param[in] a iterator to the elements to swap + * @param[in] b iterator to the elements to swap + */ + template<class ForwardIterator1, class ForwardIterator2> + inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) + { + swap(*a, *b); + } + + /** + * Swaps the values of the elements the given iterators are pointing to. + * @param[in] first1 iterator of the beginning of first range + * @param[in] last1 iterator of the end of first range + * @param[in] first2 iterator of the beginning of the second range + * @return Iterator to the element past the last element exchanged in the + * range beginning with first2. + */ + + template< class ForwardIterator1, class ForwardIterator2 > + inline ForwardIterator2 swap_ranges(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2) + { + while (first1 != last1) + { + iter_swap(first1++, first2++); + } + return first2; + } + + /** * Exchange values of two objects * @param[in] a reference to an object to be swaped with b * @param[in] b reference to an object to be swaped with a @@ -87,12 +119,24 @@ namespace std inline void swap(T& a, T&b ) { + // @TODO RTC:162287 use std::move() T c(a); a=b; b=c; } /** + * Swaps the arrays a and b. In effect calls std::swap_ranges(a, a+N, b) + * @param[in] a reference to an object to be swaped with b + * @param[in] b reference to an object to be swaped with a + */ + template< class T, size_t N> + inline void swap(T(&a)[N], T(&b)[N]) + { + swap_ranges(a, a+N, b); + } + + /** * Fill a range with value * @param[in] first ForwardIterator to the first position in the source range. * @param[in] last ForwardIterator to the last position +1 in the source range. @@ -874,7 +918,103 @@ namespace std return result; } + /** Returns true if the range [first1, last1) is equal to the range + * [first2, first2 + (last1 - first1)), and false otherwise + * + * The two ranges are considered equal if, for every iterator i in the range + * [first1,last1), *i equals *(first2 + (i - first1)). The overloads use + * operator== to determine if two elements are equal. + * + * @param[in] first1 - The beginning of the first range. + * @param[in] last1 - The end of the first range. + * @param[in] first2 - The beginning of the second range. + * @return - Returns true equal, false otherwise + */ + template < typename InputIterator1, typename InputIterator2 > + bool equal(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2) + { + while(first1 != last1) + { + if (!(*first1 == *first2)) + { + return false; + } + ++first1; ++first2; + } + return true; + } + /** Returns true if the range [first1, last1) is equal, using a predicate, + * to the range [first2, first2 + (last1 - first1)), and false otherwise + * + * The two ranges are considered equal if, for every iterator i in the range + * [first1,last1), *i equals *(first2 + (i - first1)). The overloads use + * operator== to determine if two elements are equal. + * + * @param[in] first1 - The beginning of the first range. + * @param[in] last1 - The end of the first range. + * @param[in] first2 - The beginning of the second range. + * @param[in] comp - Binary predicate which returns true if the elements + * should be treated as equal. + * @return - Returns true equal, false otherwise + */ + template < typename InputIterator1, typename InputIterator2, + typename BinaryPredicate > + bool equal( InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, BinaryPredicate comp ) + { + while(first1 != last1) + { + if (!comp(*first1, *first2)) + { + return false; + } + ++first1; ++first2; + } + return true; + } + + /** Checks if the first range [first1, last1) is lexicographically less than + * the second range [first2, last2). + * + * Elements are compared using operator<. + * Lexicographical comparison is a operation with the following properties: + * - Two ranges are compared element by element. + * - The first mismatching element defines which range is lexicographically + * less or greater than the other. + * - If one range is a prefix of another, the shorter range is + * lexicographically less than the other. + * - If two ranges have equivalent elements and are of the same length, + * then the ranges are lexicographically equal. + * - An empty range is lexicographically less than any non-empty range. + * - Two empty ranges are lexicographically equal. + * + * @param[in] first1 - The beginning of the first range. + * @param[in] last1 - The end of the first range. + * @param[in] first2 - The beginning of the second range. + * @param[in] last2 - The end of the second range. + * @return - true if the first range is lexicographically less than the + * second. + */ + template < typename InputIterator1, typename InputIterator2 > + bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, + InputIterator2 first2, InputIterator2 last2) + { + while( (first1 != last1) && (first2 != last2) ) + { + if (*first1 < *first2) + { + return true; + } + if (*first2 < *first1) + { + return false; + } + first1++; first2++; + } + return (first1 == last1) && (first2 != last2); + } }; #endif diff --git a/src/include/array b/src/include/array new file mode 100644 index 000000000..59c313046 --- /dev/null +++ b/src/include/array @@ -0,0 +1,507 @@ +/* IBM_PROLOG_BEGIN_TAG */ +/* This is an automatically generated prolog. */ +/* */ +/* $Source: src/include/array $ */ +/* */ +/* OpenPOWER HostBoot Project */ +/* */ +/* Contributors Listed Below - COPYRIGHT 2016 */ +/* [+] International Business Machines Corp. */ +/* */ +/* */ +/* 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_array +#define stl_array + +/** + * @file array + * @brief simple stl array template class declaration. + */ + +#include <stddef.h> + +#if !defined( __STDC_LIMIT_MACROS) +#define __STDC_LIMIT_MACROS +#endif +#include <stdint.h> + +namespace std +{ + template <class T, size_t N > + struct array { + // types: + typedef T& reference; + typedef const T& const_reference; + typedef T * iterator; + typedef const T * const_iterator; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef T* pointer; + typedef const T* const_pointer; + +/* Not supporting for now + typedef reverse_iterator<iterator> reverse_iterator; + typedef reverse_iterator<const_iterator> const_reverse_iterator; +*/ + + T elems[N ? N : 1]; // exposition only + + // no explicit construct/copy/destroy for aggregate type + + /** + * Assigns the given value to all elements in the container. + * @param[in] the value to assign to the elements + * @pre None. + * @post None. + */ + void fill(const T& value) + { + fill_n(begin(), N, value); + } + + /** + * Exchanges the contents of the container with those of other. + * @param[in] container to exchange the contents with + * @pre Does not cause iterators and references to associate with the + * other container. + * @post None. + */ + void swap(array<T, N>& other) + { + std::swap(elems, other.elems); + } + + // iterators: + + /** + * Returns an iterator to the first element of the container. + * @return iterator to the first element + * @pre If the container is empty, the returned iterator will be equal + * to end(). + * @post None. + */ + iterator begin() + { + return iterator(&elems[0]); + } + + /** + * Returns a const_iterator to the first element of the container. + * @return const_iterator to the first element + * @pre If the container is empty, the returned iterator will be equal + * to end(). + * @post None. + */ + constexpr const_iterator begin() const + { + return const_iterator(&elems[0]); + } + + /** + * Returns a const_iterator to the first element of the container. + * @return const_iterator to the first element + * @pre If the container is empty, the returned iterator will be equal + * to end(). + * @post None. + */ + constexpr const_iterator cbegin() const + { + return const_iterator(&elems[0]); + } + + /** + * Returns an iterator to the element following the last element of the + * container. + * @return iterator to the element following the last element. + * @pre This element acts as a placeholder; attempting to access it + * results in undefined behavior. + * @post None. + */ + iterator end() + { + return iterator(&elems[N]); + } + + /** + * Returns an const_iterator to the element following the last element + * of the container. + * @return const_iterator to the element following the last element. + * @pre This element acts as a placeholder; attempting to access it + * results in undefined behavior. + * @post None. + */ + constexpr const_iterator end() const + { + return const_iterator(&elems[N]); + } + + /** + * Returns an const_iterator to the element following the last element + * of the container. + * @return const_iterator to the element following the last element. + * @pre This element acts as a placeholder; attempting to access it + * results in undefined behavior. + * @post None. + */ + constexpr const_iterator cend() const + { + return const_iterator(&elems[N]); + } + +/* Not supporting for now + reverse_iterator rbegin(); + const_reverse_iterator rbegin() const; + reverse_iterator rend(); + const_reverse_iterator rend() const; + const_reverse_iterator crbegin() const; + const_reverse_iterator crend() const; +*/ + + // capacity: + + /** + * Returns the number of elements in the container + * @return The number of elements in the container. + * @pre None. + * @post None. + */ + constexpr size_type size() + { + return N; + } + + /** + * Returns the maximum number of elements the container is able to hold + * due to system or library implementation limitations, + * @return Maximum number of elements. + * @pre Because each std::array<T, N> is a fixed-size container, the + * value returned by max_size equals N (which is also the value + * returned by size) + * @post None. + */ + constexpr size_type max_size() + { + return size(); + } + + /** + * Checks if the container has no elements + * @return true if the container is empty, false otherwise + * @pre None. + * @post None. + */ + constexpr bool empty() + { + return (N == 0); + } + + // element access: + + /** + * Returns a reference to the element at specified location pos. + * No bounds checking is performed. + * @param[in] position of the element to return + * @return Reference to the requested element. + * @pre Unlike std::map::operator[], this operator never inserts a new + * element into the container. + * @post None. + */ + reference operator[](size_type n) + { + return elems[n]; + } + + /** + * Returns a const_reference to the element at specified location pos. + * No bounds checking is performed. + * @param[in] position of the element to return + * @return const_reference to the requested element. + * @pre None. + * @post None. + */ + const_reference operator[](size_type n) const + { + return elems[n]; + } + + /** + * Returns a reference to the element at specified location pos, with + * bounds checking. Will assert if pos is not within the range of the + * container + * @param[in] position of the element to return + * @return reference to the requested element. + * @pre None. + * @post None. + */ + reference at(size_type n) + { + assert(n < size()); + return elems[n]; + } + + /** + * Returns a const_reference to the element at specified location pos, + * with bounds checking. Will assert if pos is not within the range of + * the container + * @param[in] position of the element to return + * @return const_reference to the requested element. + * @pre None. + * @post None. + */ + const_reference at(size_type n) const + { + assert(n < size()); + return elems[n]; + } + + /** + * Returns a reference to the first element in the container. Calling + * front on an empty container is undefined. + * @return reference to the first element + * @pre For a container c, the expression c.front() is equivalent to + * *c.begin(). + * @post None. + */ + reference front() + { + return *begin(); + } + + /** + * Returns a const_reference to the first element in the container. + * Calling front on an empty container is undefined. + * @return const_reference to the first element + * @pre For a container c, the expression c.front() is equivalent to + * *c.begin(). + * @post None. + */ + constexpr const_reference front() const + { + return *begin(); + } + + /** + * Returns reference to the last element in the container. + * Calling back on an empty container is undefined. + * @return Reference to the last element. + * @pre For a container c, the expression return c.back(); is equivalent + * to { auto tmp = c.end(); --tmp; return *tmp; } + * @post None. + */ + reference back() + { + return N ? *(end() - 1) : *end(); + } + + /** + * Returns const_reference to the last element in the container. + * Calling back on an empty container is undefined. + * @return const_reference to the last element. + * @pre For a container c, the expression return c.back(); is equivalent + * to { auto tmp = c.end(); --tmp; return *tmp; } + * @post None. + */ + constexpr const_reference back() const + { + return N ? *(end() - 1) : *end(); + } + + /** + * Returns pointer to the underlying array serving as element storage. + * Calling back on an empty container is undefined. + * @return Pointer to the underlying element storage. + * For non-empty containers, returns &front() + * @pre The pointer is such that range [data(); data() + size()) is + * always a valid range, even if the container is empty (data() is + * not dereferenceable in that case). + * @post None. + */ + T * data() + { + return &front(); + } + + /** + * Returns const pointer to the underlying array serving as element + * storage. Calling back on an empty container is undefined. + * @return const_pointer to the underlying element storage. + * For non-empty containers, returns &front() + * @pre The pointer is such that range [data(); data() + size()) is + * always a valid range, even if the container is empty (data() is + * not dereferenceable in that case). + * @post None. + */ + constexpr const T * data() const + { + return &front(); + } + }; + + /** + * Compare the contents of two containers - overload operator== + * @return true if the contents of the containers are equal, false otherwise + * @pre None. + * @post None. + */ + template <class T, size_t N, size_t M=N> + inline bool operator==(const array<T,N>& lhs, const array<T,M>& rhs) + { + static_assert(N==M, "std::arrays must be of the same size when using " + "overloaded compare operators"); + return std::equal(lhs.begin(), lhs.end(), rhs.begin()); + } + + /** + * Compare the contents of two containers - overload operator!= + * @return true if the contents of the containers are not equal, false + * otherwise + * @pre None. + * @post None. + */ + template <class T, size_t N, size_t M=N> + inline bool operator!=(const array<T,N>& lhs, const array<T,M>& rhs) + { + static_assert(N==M, "std::arrays must be of the same size when using " + "overloaded compare operators"); + return !(lhs == rhs); + } + + /** + * Compare the contents of two containers - overload operator< + * @return true if the contents of the lhs are lexicographically less than + * the contents of rhs, false otherwise + * @pre None. + * @post None. + */ + template <class T, size_t N, size_t M=N> + inline bool operator<(const array<T,N>& lhs, const array<T,M>& rhs) + { + static_assert(N==M, "std::arrays must be of the same size when using overloaded compare operators"); + return std::lexicographical_compare(lhs.begin(), lhs.end(), + rhs.begin(), rhs.end()); + } + + /** + * Compare the contents of two containers - overload operator<= + * @return true if the contents of the lhs are lexicographically less than + * or equal the contents of rhs, false otherwise + * @pre None. + * @post None. + */ + template <class T, size_t N, size_t M=N> + inline bool operator<=(const array<T,N>& lhs, const array<T,M>& rhs) + { + static_assert(N==M, "std::arrays must be of the same size when using overloaded compare operators"); + return (lhs < rhs) || (lhs == rhs); + } + + /** + * Compare the contents of two containers - overload operator> + * @return true if the contents of the lhs are lexicographically greater + * than the contents of rhs, false otherwise + * @pre None. + * @post None. + */ + template <class T, size_t N, size_t M=N> + inline bool operator>(const array<T,N>& lhs, const array<T,M>& rhs) + { + static_assert(N==M, "std::arrays must be of the same size when using overloaded compare operators"); + return !(lhs < rhs) && !(lhs == rhs); + } + + /** + * Compare the contents of two containers - overload operator>= + * @return true if the contents of the lhs are lexicographically greater + * than or equal the contents of rhs, false otherwise + * @pre None. + * @post None. + */ + template <class T, size_t N, size_t M=N> + inline bool operator>=(const array<T,N>& lhs, const array<T,M>& rhs) + { + static_assert(N==M, "std::arrays must be of the same size when using overloaded compare operators"); + return !(lhs < rhs); + } + + /** + * Specializes the std::swap algorithm for std::array. Swaps the contents of + * lhs and rhs. Calls lhs.swap(rhs) + * @param[in] container whose contents to swap + * @param[in] container whose contents to swap + * @pre None. + * @post None. + */ + template <class T, size_t N> + inline void swap(array<T,N>& lhs, array<T,N>& rhs) + { + lhs.swap(rhs); + } + + /** + * Extracts the Ith element element from the array. + * @param[in] array whose contents to extract + * @return A reference to the Ith element of a. + * @pre I must be an integer value in range [0, N). This is enforced at + * compile time as opposed to at() or operator[]. + * @post None. + */ + template <size_t I, class T, size_t N> + inline constexpr T& get(array<T, N>& a) + { + static_assert( ( I>=0 && I<N ), "std::get trying to access element out of range"); + return a[I]; + } + + /** + * Extracts the Ith element element from the array. + * @param[in] array whose contents to extract + * @return A const reference to the Ith element of a. + * @pre I must be an integer value in range [0, N). This is enforced at + * compile time as opposed to at() or operator[]. + * @post None. + */ + template <size_t I, class T, size_t N> + inline constexpr const T& get(const array<T, N>& a) + { + static_assert( ( I>=0 && I<N ), "std::get trying to access element out of range"); + return a[I]; + } + + /** + * Extracts the Ith element element from the array. + * @param[in] array whose contents to extract + * @return An rvalue reference to the Ith element of a. + * @pre I must be an integer value in range [0, N). This is enforced at + * compile time as opposed to at() or operator[]. + * @post None. + */ + template <size_t I, class T, size_t N> + inline constexpr T&& get(array<T, N>&& a) + { + static_assert( ( I>=0 && I<N ), "std::get trying to access element out of range"); + return a[I]; + } + +/* Not supporting for now + template <class T> class tuple_size; + template <size_t I, class T> class tuple_element; + template <class T, size_t N> struct tuple_size<array<T, N> >; + template <size_t I, class T, size_t N> struct tuple_element<I, array<T, N> >; +*/ + +} + +#endif
\ No newline at end of file |