update sources to v12.2.4

[ceph.git] / ceph / src / boost / libs / sort / example / generalizedstruct.cpp

// This example shows how to sort structs using complex multiple part keys using\r
// string_sort.\r
//\r
//  Copyright Steven Ross 2009-2014.\r
//\r
// Distributed under the Boost Software License, Version 1.0.\r
//    (See accompanying file LICENSE_1_0.txt or copy at\r
//          http://www.boost.org/LICENSE_1_0.txt)\r
\r
//  See http://www.boost.org/libs/sort for library home page.\r
\r
#include <boost/sort/spreadsort/string_sort.hpp>\r
#include <boost/sort/spreadsort/float_sort.hpp>\r
#include <time.h>\r
#include <stdio.h>\r
#include <stdlib.h>\r
#include <algorithm>\r
#include <vector>\r
#include <iostream>\r
#include <fstream>\r
#include <string>\r
using std::string;\r
using namespace boost::sort::spreadsort;\r
\r
//[generalized_functors\r
struct DATA_TYPE {\r
  time_t birth;\r
  float net_worth;\r
  string first_name;\r
  string last_name;\r
};\r
\r
static const int birth_size = sizeof(time_t);\r
static const int first_name_offset = birth_size + sizeof(float);\r
static const boost::uint64_t base_mask = 0xff;\r
\r
struct lessthan {\r
  inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const {\r
    if (x.birth != y.birth) {\r
      return x.birth < y.birth;\r
    }\r
    if (x.net_worth != y.net_worth) {\r
      return x.net_worth < y.net_worth;\r
    }\r
    if (x.first_name != y.first_name) {\r
      return x.first_name < y.first_name;\r
    }\r
    return x.last_name < y.last_name;\r
  }\r
};\r
\r
struct bracket {\r
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {\r
    // Sort date as a signed int, returning the appropriate byte.\r
    if (offset < birth_size) {\r
      const int bit_shift = 8 * (birth_size - offset - 1);\r
      unsigned char result = (x.birth & (base_mask << bit_shift)) >> bit_shift;\r
      // Handling the sign bit.  Unnecessary if the data is always positive.\r
      if (offset == 0) {\r
        return result ^ 128;\r
      }\r
\r
      return result;\r
    }\r
\r
    // Sort a signed float.  This requires reversing the order of negatives\r
    // because of the way floats are represented in bits.\r
    if (offset < first_name_offset) {\r
      const int bit_shift = 8 * (first_name_offset - offset - 1);\r
      unsigned key = float_mem_cast<float, unsigned>(x.net_worth);\r
      unsigned char result = (key & (base_mask << bit_shift)) >> bit_shift;\r
      // Handling the sign.\r
      if (x.net_worth < 0) {\r
        return 255 - result;\r
      }\r
      // Increasing positives so they are higher than negatives.\r
      if (offset == birth_size) {\r
        return 128 + result;\r
      }\r
\r
      return result;\r
    }\r
\r
    // Sort a string that is before the end.  This approach supports embedded\r
    // nulls.  If embedded nulls are not required, then just delete the "* 2"\r
    // and the inside of the following if just becomes:\r
    // return x.first_name[offset - first_name_offset];\r
    const unsigned first_name_end_offset =\r
      first_name_offset + x.first_name.size() * 2;\r
    if (offset < first_name_end_offset) {\r
      int char_offset = offset - first_name_offset;\r
      // This signals that the string continues.\r
      if (!(char_offset & 1)) {\r
        return 1;\r
      }\r
      return x.first_name[char_offset >> 1];\r
    }\r
\r
    // This signals that the string has ended, so that shorter strings come\r
    // before longer ones.\r
    if (offset == first_name_end_offset) {\r
      return 0;\r
    }\r
\r
    // The final string needs no special consideration.\r
    return x.last_name[offset - first_name_end_offset - 1];\r
  }\r
};\r
\r
struct getsize {\r
  inline size_t operator()(const DATA_TYPE &x) const {\r
    return first_name_offset + x.first_name.size() * 2 + 1 +\r
      x.last_name.size();\r
  }\r
};\r
//] [/generalized_functors]\r
\r
//Pass in an argument to test std::sort\r
int main(int argc, const char ** argv) {\r
  std::ifstream indata;\r
  std::ofstream outfile;\r
  bool stdSort = false;\r
  unsigned loopCount = 1;\r
  for (int u = 1; u < argc; ++u) {\r
    if (std::string(argv[u]) == "-std")\r
      stdSort = true;\r
    else\r
      loopCount = atoi(argv[u]);\r
  }\r
  double total = 0.0;\r
  //Run multiple loops, if requested\r
  std::vector<DATA_TYPE> array;\r
  for (unsigned u = 0; u < loopCount; ++u) {\r
    indata.open("input.txt", std::ios_base::in | std::ios_base::binary);\r
    if (indata.bad()) {\r
      printf("input.txt could not be opened\n");\r
      return 1;\r
    }\r
\r
    // Read in the data.\r
    DATA_TYPE inval;\r
    while (!indata.eof() ) {\r
      indata >> inval.first_name;\r
      indata >> inval.last_name;\r
      indata.read(reinterpret_cast<char *>(&(inval.birth)), birth_size);\r
      indata.read(reinterpret_cast<char *>(&(inval.net_worth)), sizeof(float));\r
      // Handling nan.\r
      if (inval.net_worth != inval.net_worth) {\r
        inval.net_worth = 0;\r
      }\r
      if (indata.eof())\r
        break;\r
      array.push_back(inval);\r
    }\r
    indata.close();\r
\r
    // Sort the data.\r
    clock_t start, end;\r
    double elapsed;\r
    start = clock();\r
    if (stdSort) {\r
      std::sort(array.begin(), array.end(), lessthan());\r
    } else {\r
//[generalized_functors_call\r
      string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan());\r
//] [/generalized_functors_call]\r
    }\r
    end = clock();\r
    elapsed = static_cast<double>(end - start);\r
    if (stdSort) {\r
      outfile.open("standard_sort_out.txt", std::ios_base::out |\r
                   std::ios_base::binary | std::ios_base::trunc);\r
    } else {\r
      outfile.open("boost_sort_out.txt", std::ios_base::out |\r
                   std::ios_base::binary | std::ios_base::trunc);\r
    }\r
    if (outfile.good()) {\r
      for (unsigned u = 0; u < array.size(); ++u)\r
        outfile << array[u].birth << " " << array[u].net_worth << " "\r
                << array[u].first_name << " " << array[u].last_name << "\n";\r
      outfile.close();\r
    }\r
    total += elapsed;\r
    array.clear();\r
  }\r
  if (stdSort) {\r
    printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC);\r
  } else {\r
    printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC);\r
  }\r
  return 0;\r
}\r