diff options
author | Patrick Williams <iawillia@us.ibm.com> | 2012-05-14 12:29:39 -0500 |
---|---|---|
committer | A. Patrick Williams III <iawillia@us.ibm.com> | 2012-05-21 09:47:27 -0500 |
commit | 2a98222faf80705d4de4ed5703166802cdacc491 (patch) | |
tree | a43eea98e02cb1ff6138ead516dad88dba67c516 /src/include/util | |
parent | 7fd3b786f79d8e9a5b0ab25593d81cb45c8cc1d7 (diff) | |
download | talos-hostboot-2a98222faf80705d4de4ed5703166802cdacc491.tar.gz talos-hostboot-2a98222faf80705d4de4ed5703166802cdacc491.zip |
Enhanced STL capabilities.
- max_element
- for_each
- remove / remove_if
- unique
- sort
- mem_fun / mem_fun_ref
- bind1st / bind2nd
RTC: 41636
Change-Id: Icf15ef90562ed20097306a15f4a314e05511b199
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/1068
Tested-by: Jenkins Server
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Bradley W. Bishop <bradleyb@us.ibm.com>
Reviewed-by: Terry J. Opie <opiet@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>
Diffstat (limited to 'src/include/util')
-rw-r--r-- | src/include/util/impl/qsort.H | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/src/include/util/impl/qsort.H b/src/include/util/impl/qsort.H new file mode 100644 index 000000000..3146d7d73 --- /dev/null +++ b/src/include/util/impl/qsort.H @@ -0,0 +1,189 @@ +// IBM_PROLOG_BEGIN_TAG +// This is an automatically generated prolog. +// +// $Source: src/include/util/impl/qsort.H $ +// +// IBM CONFIDENTIAL +// +// COPYRIGHT International Business Machines Corp. 2012 +// +// p1 +// +// Object Code Only (OCO) source materials +// Licensed Internal Code Source Materials +// IBM HostBoot Licensed Internal Code +// +// The source code for this program is not published or other- +// wise divested of its trade secrets, irrespective of what has +// been deposited with the U.S. Copyright Office. +// +// Origin: 30 +// +// IBM_PROLOG_END + +#ifndef __UTIL_IMPL_QSORT_H +#define __UTIL_IMPL_QSORT_H + +/** @file qsort.H + * + * Contains the internal implementation details of std::sort implemented as + * quick-sort. + */ + +#include <iterator> + +// Forward declaration due to 'swap' being defined in <algorithm> which is +// including this file itself. +namespace std +{ + template <typename T> void swap(T& a, T& b); +}; + +namespace Util +{ + namespace __Util_QSort_Impl + { + template <typename RandomAccessIterator> + void sort(RandomAccessIterator first, RandomAccessIterator last) + { + size_t length = std::distance(first, last); + + // A range of length 0 or 1 is already sort. + if ((length == 0) || (length == 1)) + { + return; + } + + // A range of length 2 has a trivial sort. + if (length == 2) + { + RandomAccessIterator next = first; + std::advance(next, 1); + + if (*next < *first) + { + std::swap(*first, *next); + } + return; + } + + // Choose pivot as middle and move pivot to end. + // This is done to eliminate the O(n^2) behavior when the + // range is already sorted. + RandomAccessIterator pivot = first; + std::advance(pivot,length - 1); + RandomAccessIterator middle = first; + std::advance(middle, length / 2); + std::swap(*pivot, *middle); + + // Perform partitioning... + + // Division points to the first element greater than the pivot or + // else the farthest point partitioned if no elements greater than + // the pivot have been found yet. + RandomAccessIterator division = first; + RandomAccessIterator pos = first; + while(pos != pivot) + { + // Element less than the pivot is found, so move it to the + // "less than" side of the division line. + if (*pos < *pivot) + { + if (pos != division) + { + std::swap(*pos, *division); + } + ++division; + } + + ++pos; + } + + // Move the pivot down to the division line, which is its sorted + // position in the range. + if (pivot != division) + { + std::swap(*pivot,*division); + } + + // Sort each partition. + sort(first,division); + std::advance(division, 1); + sort(division, last); + }; + + + template <typename RandomAccessIterator, typename StrictWeakOrdering> + void sort(RandomAccessIterator first, RandomAccessIterator last, + StrictWeakOrdering pred) + { + size_t length = std::distance(first, last); + + // A range of length 0 or 1 is already sort. + if ((length == 0) || (length == 1)) + { + return; + } + + // A range of length 2 has a trivial sort. + if (length == 2) + { + RandomAccessIterator next = first; + std::advance(next, 1); + + if (pred(*next,*first)) + { + std::swap(*first, *next); + } + return; + } + + // Choose pivot as middle and move pivot to end. + // This is done to eliminate the O(n^2) behavior when the + // range is already sorted. + RandomAccessIterator pivot = first; + std::advance(pivot,length - 1); + RandomAccessIterator middle = first; + std::advance(middle, length / 2); + std::swap(*pivot, *middle); + + // Perform partitioning... + + // Division points to the first element greater than the pivot or + // else the farthest point partitioned if no elements greater than + // the pivot have been found yet. + RandomAccessIterator division = first; + RandomAccessIterator pos = first; + while(pos != pivot) + { + // Element less than the pivot is found, so move it to the + // "less than" side of the division line. + if (pred(*pos,*pivot)) + { + if (pos != division) + { + std::swap(*pos, *division); + } + ++division; + } + + ++pos; + } + + // Move the pivot down to the division line, which is its sorted + // position in the range. + if (pivot != division) + { + std::swap(*pivot,*division); + } + + // Sort each partition. + sort(first,division); + std::advance(division, 1); + sort(division, last); + }; + + }; +}; + +#endif |