From 4c52b65595fb795a3615b1fb6626410cfa355df4 Mon Sep 17 00:00:00 2001 From: bangerth Date: Wed, 28 Mar 2007 20:05:29 +0000 Subject: [PATCH] Move a helper function into a namespace of its own and mark it static there. This is necessary since on x86_64, gcc3.3.x complains because it apparently forgets that inline functions have internal linkage, and consequently the function shows up as 'T' in two object files. This then leads to linker errors. git-svn-id: https://svn.dealii.org/trunk@14603 0785d39b-7218-0410-832d-ea1e28bc413d --- .../lac/include/lac/sparse_matrix.templates.h | 12 +- deal.II/lac/include/lac/sparsity_pattern.h | 231 +++++++++--------- deal.II/lac/source/sparsity_pattern.cc | 9 +- 3 files changed, 126 insertions(+), 126 deletions(-) diff --git a/deal.II/lac/include/lac/sparse_matrix.templates.h b/deal.II/lac/include/lac/sparse_matrix.templates.h index d739627109..5d2e597ca6 100644 --- a/deal.II/lac/include/lac/sparse_matrix.templates.h +++ b/deal.II/lac/include/lac/sparse_matrix.templates.h @@ -991,9 +991,9 @@ SparseMatrix::precondition_SSOR (Vector &dst, // line denotes the diagonal element, // which we need not check. const unsigned int first_right_of_diagonal_index - = (SparsityPattern::optimized_lower_bound (&cols->colnums[*rowstart_ptr+1], - &cols->colnums[*(rowstart_ptr+1)], - row) + = (internals::SparsityPatternTools::optimized_lower_bound (&cols->colnums[*rowstart_ptr+1], + &cols->colnums[*(rowstart_ptr+1)], + row) - &cols->colnums[0]); @@ -1015,9 +1015,9 @@ SparseMatrix::precondition_SSOR (Vector &dst, for (int row=n-1; row>=0; --row, --rowstart_ptr, --dst_ptr) { const unsigned int first_right_of_diagonal_index - = (SparsityPattern::optimized_lower_bound (&cols->colnums[*rowstart_ptr+1], - &cols->colnums[*(rowstart_ptr+1)], - static_cast(row)) - + = (internals::SparsityPatternTools::optimized_lower_bound (&cols->colnums[*rowstart_ptr+1], + &cols->colnums[*(rowstart_ptr+1)], + static_cast(row)) - &cols->colnums[0]); for (unsigned int j=first_right_of_diagonal_index; j<*(rowstart_ptr+1); ++j) if (cols->colnums[j] > static_cast(row)) diff --git a/deal.II/lac/include/lac/sparsity_pattern.h b/deal.II/lac/include/lac/sparsity_pattern.h index 8b36a7be7c..0c15457dcf 100644 --- a/deal.II/lac/include/lac/sparsity_pattern.h +++ b/deal.II/lac/include/lac/sparsity_pattern.h @@ -2,7 +2,7 @@ // $Id$ // Version: $Name$ // -// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006 by the deal.II authors +// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 by the deal.II authors // // This file is subject to QPL and may not be distributed // without copyright and license information. Please refer @@ -38,6 +38,120 @@ class CompressedSparsityPattern; namespace internals { + namespace SparsityPatternTools + { + /** + * Optimized replacement for + * std::lower_bound for + * searching within the range of + * column indices. Slashes + * execution time by + * approximately one half for the + * present application, partly + * because we have eliminated + * templates and the compiler + * seems to be able to optimize + * better, and partly because the + * binary search is replaced by a + * linear search for small loop + * lengths. + */ + static + inline + const unsigned int * + optimized_lower_bound (const unsigned int *first, + const unsigned int *last, + const unsigned int &val) + { + // this function is mostly copied + // over from the STL __lower_bound + // function, but with template args + // replaced by the actual data + // types needed here, and above all + // with a rolled out search on the + // last four elements + unsigned int len = last-first; + + if (len==0) + return first; + + while (true) + { + // if length equals 8 or less, + // then do a rolled out + // search. use a switch without + // breaks for that and roll-out + // the loop somehow + if (len < 8) + { + switch (len) + { + case 7: + if (*first >= val) + return first; + ++first; + case 6: + if (*first >= val) + return first; + ++first; + case 5: + if (*first >= val) + return first; + ++first; + case 4: + if (*first >= val) + return first; + ++first; + case 3: + if (*first >= val) + return first; + ++first; + case 2: + if (*first >= val) + return first; + ++first; + case 1: + if (*first >= val) + return first; + return first+1; + default: + // indices seem + // to not be + // sorted + // correctly!? or + // did len + // become==0 + // somehow? that + // shouln't have + // happened + Assert (false, ExcInternalError()); + } + } + + + + const unsigned int half = len >> 1; + const unsigned int * const middle = first + half; + + // if the value is larger than + // that pointed to by the + // middle pointer, then the + // insertion point must be + // right of it + if (*middle < val) + { + first = middle + 1; + len -= half + 1; + } + else + len = half; + } + } + + } + + + namespace SparsityPatternIterators { // forward declaration @@ -1505,28 +1619,6 @@ class SparsityPattern : public Subscriptor */ bool diagonal_optimized; - /** - * Optimized replacement for - * std::lower_bound for - * searching within the range of - * column indices. Slashes - * execution time by - * approximately one half for the - * present application, partly - * because we have eliminated - * templates and the compiler - * seems to be able to optimize - * better, and partly because the - * binary search is replaced by a - * linear search for small loop - * lengths. - */ - static - const unsigned int * - optimized_lower_bound (const unsigned int *first, - const unsigned int *last, - const unsigned int &val); - /** * Helper function to get the * column index from a @@ -1835,99 +1927,6 @@ SparsityPattern::end (const unsigned int r) const -inline -const unsigned int * -SparsityPattern::optimized_lower_bound (const unsigned int *first, - const unsigned int *last, - const unsigned int &val) -{ - // this function is mostly copied - // over from the STL __lower_bound - // function, but with template args - // replaced by the actual data - // types needed here, and above all - // with a rolled out search on the - // last four elements - unsigned int len = last-first; - - if (len==0) - return first; - - while (true) - { - // if length equals 8 or less, - // then do a rolled out - // search. use a switch without - // breaks for that and roll-out - // the loop somehow - if (len < 8) - { - switch (len) - { - case 7: - if (*first >= val) - return first; - ++first; - case 6: - if (*first >= val) - return first; - ++first; - case 5: - if (*first >= val) - return first; - ++first; - case 4: - if (*first >= val) - return first; - ++first; - case 3: - if (*first >= val) - return first; - ++first; - case 2: - if (*first >= val) - return first; - ++first; - case 1: - if (*first >= val) - return first; - return first+1; - default: - // indices seem - // to not be - // sorted - // correctly!? or - // did len - // become==0 - // somehow? that - // shouln't have - // happened - Assert (false, ExcInternalError()); - }; - }; - - - - const unsigned int half = len >> 1; - const unsigned int * const middle = first + half; - - // if the value is larger than - // that pointed to by the - // middle pointer, then the - // insertion point must be - // right of it - if (*middle < val) - { - first = middle + 1; - len -= half + 1; - } - else - len = half; - } -} - - - inline unsigned int SparsityPattern::n_rows () const diff --git a/deal.II/lac/source/sparsity_pattern.cc b/deal.II/lac/source/sparsity_pattern.cc index e815591672..ca058b9dea 100644 --- a/deal.II/lac/source/sparsity_pattern.cc +++ b/deal.II/lac/source/sparsity_pattern.cc @@ -2,7 +2,7 @@ // $Id$ // Version: $Name$ // -// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006 by the deal.II authors +// Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 by the deal.II authors // // This file is subject to QPL and may not be distributed // without copyright and license information. Please refer @@ -718,9 +718,10 @@ SparsityPattern::operator () (const unsigned int i, const unsigned int * const sorted_region_start = (diagonal_optimized ? &colnums[rowstart[i]+1] : &colnums[rowstart[i]]); - const unsigned int * const p = optimized_lower_bound (sorted_region_start, - &colnums[rowstart[i+1]], - j); + const unsigned int * const p + = internals::SparsityPatternTools::optimized_lower_bound (sorted_region_start, + &colnums[rowstart[i+1]], + j); if ((p != &colnums[rowstart[i+1]]) && (*p == j)) return (p - &colnums[0]); else -- 2.39.5