From 3e73264261a634935a3dd0c0ce7c890a1a227ff8 Mon Sep 17 00:00:00 2001 From: singler Date: Mon, 17 Sep 2007 12:58:07 +0000 Subject: [PATCH] 2007-09-17 Johannes Singler * include/parallel/for_each.h: Fixed comment/doxygen markup typos. * include/parallel/base.h: Same. * include/parallel/numeric: Same. * include/parallel/quicksort.h: Same. * include/parallel/compiletime_settings.h: Same. * include/parallel/random_shuffle.h: Same. * include/parallel/balanced_quicksort.h: Same. * include/parallel/tree.h: Same. * include/parallel/settings.h: Same. * include/parallel/search.h: Same. * include/parallel/partition.h: Same. * include/parallel/partial_sum.h: Same. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@128545 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 15 ++++++ libstdc++-v3/include/parallel/balanced_quicksort.h | 2 +- libstdc++-v3/include/parallel/base.h | 3 +- .../include/parallel/compiletime_settings.h | 2 +- libstdc++-v3/include/parallel/for_each.h | 2 +- libstdc++-v3/include/parallel/numeric | 2 +- libstdc++-v3/include/parallel/partial_sum.h | 2 +- libstdc++-v3/include/parallel/partition.h | 2 +- libstdc++-v3/include/parallel/quicksort.h | 2 +- libstdc++-v3/include/parallel/random_shuffle.h | 2 +- libstdc++-v3/include/parallel/search.h | 4 +- libstdc++-v3/include/parallel/settings.h | 4 +- libstdc++-v3/include/parallel/tree.h | 60 +++++++++++----------- 13 files changed, 58 insertions(+), 44 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index f84883f969d..a5ac39f13b8 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,18 @@ +2007-09-17 Johannes Singler + + * include/parallel/for_each.h: Fixed comment/doxygen markup typos. + * include/parallel/base.h: Same. + * include/parallel/numeric: Same. + * include/parallel/quicksort.h: Same. + * include/parallel/compiletime_settings.h: Same. + * include/parallel/random_shuffle.h: Same. + * include/parallel/balanced_quicksort.h: Same. + * include/parallel/tree.h: Same. + * include/parallel/settings.h: Same. + * include/parallel/search.h: Same. + * include/parallel/partition.h: Same. + * include/parallel/partial_sum.h: Same. + 2007-09-17 Paolo Carlini * include/tr1_impl/type_traitsfwd.h (aligned_storage): Remove diff --git a/libstdc++-v3/include/parallel/balanced_quicksort.h b/libstdc++-v3/include/parallel/balanced_quicksort.h index 94b0e8cd6c6..881099cb37f 100644 --- a/libstdc++-v3/include/parallel/balanced_quicksort.h +++ b/libstdc++-v3/include/parallel/balanced_quicksort.h @@ -277,7 +277,7 @@ namespace __gnu_parallel || (end - split_pos1) < (n >> 7)) { // Very unequal split, one part smaller than one 128th - // elements not stricly larger than the pivot. + // elements not strictly larger than the pivot. __gnu_parallel::unary_negate<__gnu_parallel::binder1st, value_type> pred(__gnu_parallel::binder1st(comp, *pivot_pos)); // Find other end of pivot-equal range. diff --git a/libstdc++-v3/include/parallel/base.h b/libstdc++-v3/include/parallel/base.h index 3074188e232..12bba0455fc 100644 --- a/libstdc++-v3/include/parallel/base.h +++ b/libstdc++-v3/include/parallel/base.h @@ -49,7 +49,7 @@ namespace __gnu_parallel // XXX remove std::duplicates from here if possible, // XXX but keep minimal dependencies. - /** @brief Calculates the rounded-down logrithm of @c n for base 2. + /** @brief Calculates the rounded-down logarithm of @c n for base 2. * @param n Argument. * @return Returns 0 for argument 0. */ @@ -107,7 +107,6 @@ namespace __gnu_parallel bool operator()(const T1& a, const T2& b) { - // FIXME: wrong in general (T1 != T2) return !comp(a, b) && !comp(b, a); } }; diff --git a/libstdc++-v3/include/parallel/compiletime_settings.h b/libstdc++-v3/include/parallel/compiletime_settings.h index 6278e44837a..717bda56f6f 100644 --- a/libstdc++-v3/include/parallel/compiletime_settings.h +++ b/libstdc++-v3/include/parallel/compiletime_settings.h @@ -69,7 +69,7 @@ #define _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB 0 /** @brief First copy the data, sort it locally, and merge it back - * (0); or copy it back after everyting is done (1). + * (0); or copy it back after everything is done (1). * * Recommendation: 0 */ #define _GLIBCXX_MULTIWAY_MERGESORT_COPY_LAST 0 diff --git a/libstdc++-v3/include/parallel/for_each.h b/libstdc++-v3/include/parallel/for_each.h index eb5e04e84f1..ef950d1f924 100644 --- a/libstdc++-v3/include/parallel/for_each.h +++ b/libstdc++-v3/include/parallel/for_each.h @@ -29,7 +29,7 @@ // Public License. /** @file parallel/for_each.h - * @brief Main interface for embarassingly parallel functions. + * @brief Main interface for embarrassingly parallel functions. * * The explicit implementation are in other header files, like * workstealing.h, par_loop.h, omp_loop.h, and omp_loop_static.h. diff --git a/libstdc++-v3/include/parallel/numeric b/libstdc++-v3/include/parallel/numeric index 3209a58a3e6..4d71b8f1588 100644 --- a/libstdc++-v3/include/parallel/numeric +++ b/libstdc++-v3/include/parallel/numeric @@ -31,7 +31,7 @@ /** * @file parallel/numeric * - * @brief Parallel STL fucntion calls corresponding to stl_numeric.h. + * @brief Parallel STL function calls corresponding to stl_numeric.h. * The functions defined here mainly do case switches and * call the actual parallelized versions in other files. * Inlining policy: Functions that basically only contain one function call, diff --git a/libstdc++-v3/include/parallel/partial_sum.h b/libstdc++-v3/include/parallel/partial_sum.h index c5bc9c955a9..5a1a43e31a4 100644 --- a/libstdc++-v3/include/parallel/partial_sum.h +++ b/libstdc++-v3/include/parallel/partial_sum.h @@ -75,7 +75,7 @@ namespace __gnu_parallel return result; } - /** @brief Parallel partial sum implmenetation, two-phase approach, + /** @brief Parallel partial sum implementation, two-phase approach, no recursion. * @param begin Begin iterator of input sequence. * @param end End iterator of input sequence. diff --git a/libstdc++-v3/include/parallel/partition.h b/libstdc++-v3/include/parallel/partition.h index 3c2917f0e2a..790685bf0a5 100644 --- a/libstdc++-v3/include/parallel/partition.h +++ b/libstdc++-v3/include/parallel/partition.h @@ -102,7 +102,7 @@ namespace __gnu_parallel difference_type thread_left, thread_left_border, thread_right, thread_right_border; thread_left = left + 1; - // Just to satify the condition below. + // Just to satisfy the condition below. thread_left_border = thread_left - 1; thread_right = n - 1; thread_right_border = thread_right + 1; diff --git a/libstdc++-v3/include/parallel/quicksort.h b/libstdc++-v3/include/parallel/quicksort.h index e3df87a66d6..305c8defa74 100644 --- a/libstdc++-v3/include/parallel/quicksort.h +++ b/libstdc++-v3/include/parallel/quicksort.h @@ -48,7 +48,7 @@ namespace __gnu_parallel * @param end End iterator of subsequence. * @param comp Comparator. * @param pivot_rank Desired rank of the pivot. - * @param num_samples Chosse pivot from that many samples. + * @param num_samples Choose pivot from that many samples. * @param num_threads Number of threads that are allowed to work on * this part. */ diff --git a/libstdc++-v3/include/parallel/random_shuffle.h b/libstdc++-v3/include/parallel/random_shuffle.h index f18f7774840..fa546512a40 100644 --- a/libstdc++-v3/include/parallel/random_shuffle.h +++ b/libstdc++-v3/include/parallel/random_shuffle.h @@ -131,7 +131,7 @@ namespace __gnu_parallel } /** @brief Random shuffle code executed by each thread. - * @param pus Arary of thread-local data records. */ + * @param pus Array of thread-local data records. */ template inline void parallel_random_shuffle_drs_pu(DRSSorterPU* pus) { diff --git a/libstdc++-v3/include/parallel/search.h b/libstdc++-v3/include/parallel/search.h index 754150ced9d..af6bd8541f6 100644 --- a/libstdc++-v3/include/parallel/search.h +++ b/libstdc++-v3/include/parallel/search.h @@ -100,7 +100,7 @@ namespace __gnu_parallel // Last point to start search. difference_type input_length = (end1 - begin1) - pattern_length; - // Where is first occurence of pattern? defaults to end. + // Where is first occurrence of pattern? defaults to end. difference_type res = (end1 - begin1); // Pattern too long. @@ -128,7 +128,7 @@ namespace __gnu_parallel { // Get new value of res. #pragma omp flush(res) - // No chance for this thread to find first occurence. + // No chance for this thread to find first occurrence. if (res < start) break; while (pred(begin1[start + pos_in_pattern], begin2[pos_in_pattern])) diff --git a/libstdc++-v3/include/parallel/settings.h b/libstdc++-v3/include/parallel/settings.h index cec9d8225c9..97de007a374 100644 --- a/libstdc++-v3/include/parallel/settings.h +++ b/libstdc++-v3/include/parallel/settings.h @@ -152,7 +152,7 @@ namespace static volatile bool force_sequential; /** @brief Force all algorithms to be executed in parallel. - * This setting can be overriden by __gnu_parallel::sequential_tag + * This setting can be overridden by __gnu_parallel::sequential_tag * (compile-time), and force_sequential (run-time). */ static volatile bool force_parallel; @@ -171,7 +171,7 @@ namespace (quicksort). */ static volatile unsigned int sort_qs_num_samples_preset; - /** @brief Maximal subsequence length to swtich to unbalanced + /** @brief Maximal subsequence length to switch to unbalanced * base case. Applies to std::sort with dynamically * load-balanced quicksort. */ static volatile sequence_index_t sort_qsb_base_case_maximal_n; diff --git a/libstdc++-v3/include/parallel/tree.h b/libstdc++-v3/include/parallel/tree.h index 8aa9269394d..a89dc62cb7b 100644 --- a/libstdc++-v3/include/parallel/tree.h +++ b/libstdc++-v3/include/parallel/tree.h @@ -396,9 +396,9 @@ namespace __gnu_parallel // 1. Convert n to n', where n' will be its rank if the tree // was complete // 2. Calculate neighbours for n' - // 3. Convert the neighbours n1', n2' and n3' to their - // appropiate values n1, n2, n3. Note that it must be - // checked that this neighbours reallly exist. + // 3. Convert the neighbors n1', n2' and n3' to their + // appropriate values n1, n2, n3. Note that it must be + // checked that these neighbors actually exist. calculate_shifts_pos_level(mod_pos, zero, l_s, r_s, p_s); if (l_s > splitting_point) { @@ -534,7 +534,7 @@ namespace __gnu_parallel /** @brief Search for the first 0 bit (growing the weight) using * binary search * - * Binary search can be used instead of a naïve loop using the + * Binary search can be used instead of a naive loop using the * masks in mask array * @param x Binary number (corresponding to a rank in the tree) * whose first 0 bit must be calculated @@ -638,7 +638,7 @@ namespace __gnu_parallel considering valid nodes and gaps * @param pos Rank in the array of nodes considering only valid nodes * @param index Partition which the rank is most likely to - * belong to (ie. the corresponding if there were no gaps) + * belong to (i. e. the corresponding if there were no gaps) * @pre 0 <= @c pos <= number_of_distinct_elements * @return Rank in the array of nodes considering valid nodes and gaps * @post 0 <= @c return <= number_of_elements @@ -746,14 +746,14 @@ namespace __gnu_parallel /** @brief Helper comparator class: Passed as a parameter of list_partition to check that a sequence is sorted * @param _InputIterator Iterator to the elements to compare - * @param _CompIsSorted Comparator to check for sortedness */ + * @param _CompIsSorted Comparator to check for sortednesss */ template class is_sorted_functor { /** @brief Element to compare with (first parameter of comp) */ _InputIterator prev; - /** @brief Comparator to check for sortedness */ + /** @brief Comparator to check for sortednesss */ const _CompIsSorted comp; /** @brief Sum up the history of the operator() of this @@ -767,7 +767,7 @@ namespace __gnu_parallel * Sorted is set to true * @param first Element to compare with the first time the * operator() is called - * @param c Comparator to check for sortednes */ + * @param c Comparator to check for sortedness */ is_sorted_functor(const _InputIterator first, const _CompIsSorted c) : prev(first), comp(c), sorted(true) { } @@ -891,7 +891,7 @@ namespace __gnu_parallel template struct Opposite { - /** @brief Obtain the conceptual left child of a node, inversing + /** @brief Obtain the conceptual left child of a node, inverting the symmetry * @param parent Node whose child must be obtained * @return Reference to the child node */ @@ -899,7 +899,7 @@ namespace __gnu_parallel { return S::right(parent);} /** @brief Obtain the conceptual right child of a node, - inversing the symmetry + inverting the symmetry * @param parent Node whose child must be obtained * @return Reference to the child node */ static _Rb_tree_node_base*& right(_Rb_tree_node_base* parent) @@ -1140,7 +1140,7 @@ namespace __gnu_parallel be inserted into @c t */ size_type pos_beg; - /** @brief Positition of the first node in the array of nodes + /** @brief Position of the first node in the array of nodes that won't be inserted into @c t */ size_type pos_end; @@ -1189,7 +1189,7 @@ namespace __gnu_parallel * The input sequence is preprocessed so that the bulk * construction or insertion can be performed * efficiently. Essentially, the sequence is checked for - * sortedness and iterators to the middle of the structure are + * sortednesss and iterators to the middle of the structure are * saved so that afterwards the sequence can be processed * effectively in parallel. */ template @@ -1249,7 +1249,7 @@ namespace __gnu_parallel * The elements are copied, according to the copy policy, in order * to be sorted. Then the * _M_not_sorted_bulk_insertion_construction() method is called - * appropiately + * appropriately * @param access Array of iterators of size @c num_threads + * 1. Each position contains the first element in each subsequence * to be added into the tree. @@ -1401,7 +1401,7 @@ namespace __gnu_parallel } - /** @brief Allocation of an array of nodes and initilization of + /** @brief Allocation of an array of nodes and initialization of their value fields from an input sequence. Done in parallel. * @param access Array of iterators of size @c num_threads + * 1. Each position contains the first value in the subsequence to @@ -1442,7 +1442,7 @@ namespace __gnu_parallel } - /** @brief Allocation of an array of nodes and initilization of + /** @brief Allocation of an array of nodes and initialization of * their value fields from an input sequence. Done in * parallel. Besides, the sequence is checked for uniqueness while * copying the elements, and if there are repetitions, gaps within @@ -1570,7 +1570,7 @@ namespace __gnu_parallel } - /** @brief Allocation of an array of nodes and initilization of + /** @brief Allocation of an array of nodes and initialization of * their value fields from an input sequence. * * The allocation and initialization is done in parallel. Besides, @@ -1734,7 +1734,7 @@ namespace __gnu_parallel t.tic("bulk allocation and initialization"); - // Link the tree appropiately. + // Link the tree appropriately. // Dealing with repetitions (EFFICIENCY ISSUE). ranker_gaps rank(beg_partition, rank_shift, num_threads); nodes_initializer nodes_init(r, n - rank_shift[num_threads], num_threads, rank); @@ -1772,7 +1772,7 @@ namespace __gnu_parallel } } } - // If the execution reachs this point, there has been no + // If the execution reaches this point, there has been no // exception, and so the structure can be initialized. // Join the tree laid on the array of ptrs with the header node. @@ -1870,7 +1870,7 @@ namespace __gnu_parallel //2. Split the tree according to access in num_threads parts //Initialize upper concat_problems - //Allocate them dinamically because they are afterwards so erased + //Allocate them dynamically because they are afterwards so erased for (int i=0; i < (2*num_threads-1); ++i) { conc[i] = new concat_problem (); @@ -2048,13 +2048,13 @@ namespace __gnu_parallel /** @brief Divide a tree according to the splitter elements of a * given sequence. * - * The tree of the intial recursive call is divided in exactly + * The tree of the initial recursive call is divided in exactly * num_threads partitions, some of which may be empty. Besides, * some nodes may be extracted from it to afterwards concatenate * the subtrees resulting from inserting the elements into it. * This is done sequentially. It could be done in parallel but the * performance is much worse. - * @param t Root of the tree to be splitted + * @param t Root of the tree to be split * @param r Array of nodes to be inserted into the tree (here only * used to look up its elements) * @param access Array of iterators of size @c num_threads + @@ -2184,7 +2184,7 @@ namespace __gnu_parallel * sequentially. * @param r Array of nodes containing the nodes to added into the tree * @param ins_problems Pointer to a queue of insertion - * problems. The calling thread owns this queue, i.e. it is the + * problems. The calling thread owns this queue, i. e. it is the * only one to push elements, but other threads could pop elements * from it in other methods. * @param ip Current insertion problem to be solved @@ -2475,7 +2475,7 @@ namespace __gnu_parallel is_sorted_functor<_InputIterator, _Compare> sorted(__first, base_type::_M_impl._M_key_compare); dist = list_partition(__first, __last, access, (beg_partition+1), num_pieces, sorted, 0); - // Calculate the rank of the begining each partition from the + // Calculate the rank of the beginning each partition from the // sequence sizes (what is stored at this point in beg_partition // array). beg_partition[0] = 0; @@ -2489,7 +2489,7 @@ namespace __gnu_parallel /** @brief Make a full copy of the elements of a sequence * - * The unitialized_copy method from the stl is called in parallel + * The uninitialized_copy method from the STL is called in parallel * using the access array to point to the beginning of each * partition * @param access Array of size @c num_threads + 1 that defines @c @@ -2551,7 +2551,7 @@ namespace __gnu_parallel * @param pos_beg_right Position of the first node in the * resulting right partition (out) * @param existing Number of existing elements before dividing - * (in) and after (out). Specificically, the counter is + * (in) and after (out). Specifically, the counter is * incremented by one for unique containers if the splitting key * was already in the array of nodes. * @param strictly_less_or_less_equal Comparator to deal @@ -2866,10 +2866,10 @@ namespace __gnu_parallel } /** @brief Split a tree according to key in three parts: a left - * child, a right child and an intermediate node. + * child, a right child and an intermediate node. * * Trees are concatenated once the recursive call returns. That - * is, from bottom to top (ie. smaller to larger), so the cost + * is, from bottom to top (i. e. smaller to larger), so the cost * bounds for split hold. * @param t Root of the tree to split. * @param key Key to split according to. @@ -3032,7 +3032,7 @@ namespace __gnu_parallel } /** @brief Split the tree in two parts: the minimum element from a - tree (i.e. leftmost) and the rest (right subtree) + tree (i. e. leftmost) and the rest (right subtree) * @param t Root of the tree * @param root Minimum element (out) * @param r Right subtree: @c t - {@c root} @@ -3080,7 +3080,7 @@ namespace __gnu_parallel /** @brief Split the tree in two parts: the greatest element from - a tree (i.e. rightmost) and the rest (left subtree) + a tree (i. e. rightmost) and the rest (left subtree) * @param t Root of the tree * @param root Maximum element (out) * @param l Left subtree: @c t - {@c root} @@ -3128,7 +3128,7 @@ namespace __gnu_parallel * and a right subtree * * Trees are concatenated once the recursive call returns. That - * is, from bottom to top (ie. smaller to larger), so the cost + * is, from bottom to top (i. e. smaller to larger), so the cost * bounds for split hold. * @param t Root of the tree to split. * @param key Key to split according to. -- 2.11.0