ceph/src/boost/libs/sort/example/floatfunctorsample.cpp

   1 // spreadsort float functor sorting example.
   2 //
   3 //  Copyright Steven Ross 2009.
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8
   9 //  See http://www.boost.org/libs/sort for library home page.
  10
  11 // Caution: this file contains Quickbook markup as well as code
  12 // and comments, don't change any of the special comment markups!
  13
  14 #include <boost/sort/spreadsort/spreadsort.hpp>
  15 #include <time.h>
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <algorithm>
  19 #include <vector>
  20 #include <string>
  21 #include <fstream>
  22 #include <sstream>
  23 #include <iostream>
  24
  25 using namespace boost::sort::spreadsort;
  26
  27 //[float_functor_types
  28 #define CAST_TYPE int
  29 #define KEY_TYPE float
  30 //] [/float_functor_types]
  31
  32
  33 //[float_functor_datatypes
  34 struct DATA_TYPE {
  35     KEY_TYPE key;
  36     std::string data;
  37 };
  38 //] [/float_functor_datatypes]
  39
  40
  41 //[float_functor_rightshift
  42 // Casting to an integer before bitshifting
  43 struct rightshift {
  44   int operator()(const DATA_TYPE &x, const unsigned offset) const {
  45     return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
  46   }
  47 };
  48 //] [/float_functor_rightshift]
  49
  50 //[float_functor_lessthan
  51 struct lessthan {
  52   bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {
  53     return x.key < y.key;
  54   }
  55 };
  56 //] [/float_functor_lessthan]
  57
  58 // Pass in an argument to test std::sort
  59 // Note that this converts NaNs and -0.0 to 0.0, so that sorting results are
  60 // identical every time
  61 int main(int argc, const char ** argv) {
  62   size_t uCount,uSize=sizeof(DATA_TYPE);
  63   bool stdSort = false;
  64   unsigned loopCount = 1;
  65   for (int u = 1; u < argc; ++u) {
  66     if (std::string(argv[u]) == "-std")
  67       stdSort = true;
  68     else
  69       loopCount = atoi(argv[u]);
  70   }
  71   std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary);
  72   if (input.fail()) {
  73     printf("input.txt could not be opened\n");
  74     return 1;
  75   }
  76   double total = 0.0;
  77   std::vector<DATA_TYPE> array;
  78   input.seekg (0, std::ios_base::end);
  79     size_t length = input.tellg();
  80   uCount = length/uSize;
  81   //Run multiple loops, if requested
  82   for (unsigned u = 0; u < loopCount; ++u) {
  83     input.seekg (0, std::ios_base::beg);
  84     //Conversion to a vector
  85     array.resize(uCount);
  86     unsigned v = 0;
  87     while (input.good() && v < uCount) {
  88       input.read(reinterpret_cast<char *>(&(array[v].key)),
  89                  sizeof(array[v].key));
  90      //Checking for denormalized numbers; float_sort looks too fast on them.
  91      if (!(float_mem_cast<KEY_TYPE, CAST_TYPE>(array[v].key) & 0x7f800000)) {
  92        //Make the top exponent bit high
  93        CAST_TYPE temp = 0x40000000 |
  94          float_mem_cast<KEY_TYPE, CAST_TYPE>(array[v].key);
  95        memcpy(&(array[v].key), &temp, sizeof(KEY_TYPE));
  96      }
  97      //Testcase doesn't sort NaNs; they just cause confusion
  98      if (!(array[v].key < 0.0) && !(0.0 < array[v].key))
  99        array[v].key = 0.0;
 100      //Adding the data, in this case a string
 101      std::stringstream intstr;
 102      intstr << array[v].key;
 103      array[v].data = intstr.str();
 104      ++v;
 105     }
 106     clock_t start, end;
 107     double elapsed;
 108     start = clock();
 109     if (stdSort)
 110       std::sort(array.begin(), array.end(), lessthan());
 111     else
 112       float_sort(array.begin(), array.end(), rightshift(), lessthan());
 113     end = clock();
 114     elapsed = static_cast<double>(end - start) ;
 115     std::ofstream ofile;
 116     if (stdSort)
 117       ofile.open("standard_sort_out.txt", std::ios_base::out |
 118                  std::ios_base::binary | std::ios_base::trunc);
 119     else
 120       ofile.open("boost_sort_out.txt", std::ios_base::out |
 121                  std::ios_base::binary | std::ios_base::trunc);
 122     if (ofile.good()) {
 123       for (unsigned v = 0; v < array.size(); ++v) {
 124         ofile.write(reinterpret_cast<char *>(&(array[v].key)),
 125                     sizeof(array[v].key));
 126         ofile << array[v].data;
 127       }
 128       ofile.close();
 129     }
 130     total += elapsed;
 131     array.clear();
 132   }
 133   if (stdSort)
 134     printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC);
 135   else
 136     printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC);
 137   return 0;
 138 }