STXXL

http://stxxl.org/tags/1.4.1/
Admin
STXXL is a C++ template library for external memory computations that enables algorithms and...
Tokens:624,768
Snippets:5,071
Trust Score:6.2
Update:1 month ago
Show doc for...
Tokens:
Raw
### Build example programs

Source: http://stxxl.org/tags/1.4.1/install_build_options.html

Use this command to build the many small example programs included with STXXL.

```bash
$ cmake -DBUILD_EXAMPLES=ON ...
```

--------------------------------

### Minimal STXXL Priority Queue Example

Source: http://stxxl.org/tags/1.4.1/tutorial_pqueue.html

Demonstrates the setup of a priority queue using STXXL_PRIORITY_QUEUE_GENERATOR, including a custom comparator and read-write pool configuration.

```cpp
#include <stxxl/priority_queue>
#include <iostream>
#include <limits>
// comparison struct for priority queue where top() returns the smallest contained value:
struct ComparatorGreater
{
bool operator () (const int& a, const int& b) const
{ return (a > b); }
int min_value() const
{ return std::numeric_limits<int>::max(); }
};
int main()
{
typedef stxxl::PRIORITY_QUEUE_GENERATOR<int, ComparatorGreater, 128*1024*1024, 1024*1024>::result pqueue_type;
typedef pqueue_type::block_type block_type;
// block_type::raw_size = 262144 bytes
// use 64 block read and write pools each to enable overlapping between I/O and computation
const unsigned int mem_for_pools = 32 * 1024 * 1024;
stxxl::read_write_pool<block_type> pool((mem_for_pools / 2) / block_type::raw_size, (mem_for_pools / 2) / block_type::raw_size);
pqueue_type my_pqueue(pool); // creates stxxl priority queue instance with read-write-pool
my_pqueue.push(5);
my_pqueue.push(4);
my_pqueue.push(19);
my_pqueue.push(1);
assert(my_pqueue.size() == 4);
assert(my_pqueue.top() == 1);
STXXL_MSG("Smallest inserted value in my: " << my_pqueue.top());
my_pqueue.pop(); // pop the 1 on top
assert(my_pqueue.top() == 4);
STXXL_MSG("Smallest value after 1 pop(): " << my_pqueue.top());
return 0;
}
```

--------------------------------

### Example disk configuration with syscall and unlink

Source: http://stxxl.org/tags/1.4.1/install_config.html

Example configuration for two disks using the syscall file I/O method with the unlink option. This is a typical setup for Unix-like systems.

```text
disk=/data01/stxxl,500G,syscall unlink
disk=/data02/stxxl,300G,syscall unlink

```

--------------------------------

### Install library and headers to a prefix

Source: http://stxxl.org/tags/1.4.1/install_build_options.html

Use these commands to install the library and all public headers into a specified prefix.

```bash
$ cmake -DCMAKE_INSTALL_PREFIX=/some/dir ...
```

```bash
$ make install
```

--------------------------------

### Run example program test1 in local/

Source: http://stxxl.org/tags/1.4.1/install_unix.html

Runs the example program 'test1' from the local directory inside the build directory.

```bash
(inside my-project/build/)
$ cd local
$ ./test1
<lots of output>

```

--------------------------------

### stxxl::grow_shrink_stack2 Usage Example

Source: http://stxxl.org/tags/1.4.1/design_stack.html

Example demonstrating the use of grow_shrink_stack2 with prefetch and write pools.

```cpp
typedef STACK_GENERATOR<int,external,grow_shrink2>::result stack_type;
typedef stack_type::block_type block_type;
stxxl::prefetch_pool p_pool(10); // 10 read buffers
stxxl::write_pool w_pool(6); // 6 write buffers
stack_type S(p_pool,w_pool,0); // no read buffers used
for(long long i = 0; i < max_value; ++i)
S.push(i);
S.set_prefetch_aggressiveness(5);
/* give a hint that we are going to shrink the stack from now on,
always prefetch 5 buffers beforehand */
for(long long i = 0; i < max_value; ++i)
S.pop();
S.set_prefetch_aggressiveness(0);
// stop prefetching
```

--------------------------------

### Example disk configuration with linuxaio and unlink

Source: http://stxxl.org/tags/1.4.1/install_config.html

Example configuration for Linux using the linuxaio file I/O method with the unlink option. This setup takes advantage of NCQ and Kernel AIO queues.

```text
disk=/data01/stxxl,500G,linuxaio unlink
disk=/data02/stxxl,300G,linuxaio unlink

```

--------------------------------

### Clone STXXL example project

Source: http://stxxl.org/tags/1.4.1/install_unix.html

Clone the example project from GitHub to see a working STXXL example.

```bash
git clone http://github.com/stxxl/myproject.git
```

--------------------------------

### Minimal working example of STXXL stack

Source: http://stxxl.org/tags/1.4.1/tutorial_stack.html

A complete example demonstrating stack creation, pushing, popping, and assertion checks.

```cpp
#include <stxxl/stack>
int main()
{
typedef stxxl::STACK_GENERATOR<int>::result stack_type;
stack_type my_stack;
my_stack.push(8);
my_stack.push(7);
my_stack.push(4);
assert(my_stack.size() == 3);
assert(my_stack.top() == 4);
my_stack.pop();
assert(my_stack.top() == 7);
my_stack.pop();
assert(my_stack.top() == 8);
my_stack.pop();
assert(my_stack.empty());
return 0;
}
```

--------------------------------

### stxxl::timer::start()

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1timer.html

Starts the timer.

```APIDOC
## Method: stxxl::timer::start()

### Description
Starts the timer.

### Returns
- **void** - No return value.

### Definition
Defined at line 84 of file timer.h.
```

--------------------------------

### Specify installation subdirectories

Source: http://stxxl.org/tags/1.4.1/install_build_options.html

Use these options to specify the installation subdirectories for binaries, libraries, headers, pkgconfig, and CMake files.

```bash
INSTALL_BIN_DIR=bin
INSTALL_LIB_DIR=lib
INSTALL_INCLUDE_DIR=include
INSTALL_PKGCONFIG_DIR=lib/pkgconfig
INSTALL_CMAKE_DIR=lib/cmake/stxxl
```

--------------------------------

### Example disk configuration for Windows with wincall and delete

Source: http://stxxl.org/tags/1.4.1/install_config.html

Example configuration for Windows using the wincall file I/O method with the delete option. Uses different disk drives as specified.

```text
disk=c:\stxxl.tmp,700G,wincall delete
disk=d:\stxxl.tmp,200G,wincall delete

```

--------------------------------

### Minimal STXXL deque example

Source: http://stxxl.org/tags/1.4.1/tutorial_deque.html

A complete example demonstrating creation, insertion, access, and iteration of a stxxl::deque.

```cpp
#include <stxxl/deque>
#include <iostream>
int main()
{
typedef stxxl::deque<int> deque;
deque my_deque;
my_deque.push_front(2);
my_deque.push_front(11);
my_deque.push_back(5);
my_deque.push_back(8);
// deque now stores: |11|2|5|8|
std::cout << "return 'first' element: " << my_deque.front() << std::endl; // prints 11
std::cout << "return 'last' element: " << my_deque.back() << std::endl; // prints 8
std::cout << "random access: " << my_deque[2] << std::endl; // prints 5
// generate forward iterator
stxxl::deque_iterator<deque> deque_iterator = my_deque.begin();
// iterate over my_deque, access values and delete them afterwards
while (!my_deque.empty())
{
std::cout << *deque_iterator << " ";
++deque_iterator;
my_deque.pop_front();
}
return 0;
}
```

--------------------------------

### STXXL Stream Package Example (examples/stream/stream1.cpp)

Source: http://stxxl.org/tags/1.4.1/examples_2stream_2stream1_8cpp-example.html

This example demonstrates how to create custom stream objects, a transformer stream, and how to use the iterator2stream adapter.

```cpp
/***************************************************************************
* examples/stream/stream1.cpp
*
* This file contains the example snippets from the stream tutorial.
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2012-2013 Timo Bingmann <tb@panthema.net>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#include <stxxl/stream>
#include <stxxl/vector>
#include <stxxl/sorter>
#include <vector>
#include <climits>
struct counter_object
{
// This stream produces a sequence of integers.
typedef int value_type;
private:
// A class attribute to save the current value.
int m_current_value;
public:
// A constructor to set the initial value to 1.
counter_object()
: m_current_value(1)
{ }
// The retrieve operator returning the current value.
const value_type& operator * () const
{
return m_current_value;
}
// Increment operator advancing to the next integer.
counter_object& operator ++ ()
{
++m_current_value;
return *this;
}
// Empty indicator, which in this case can check the current value.
bool empty() const
{
return (m_current_value > 1000);
}
};
template <typename InputStream>
struct squaring_object
{
// This stream produces a sequence of integers.
typedef int value_type;
private:
// A reference to another stream of integers, which are our input.
InputStream& m_input_stream;
// A temporary value buffer to hold the current square in for retrieval.
value_type m_current_value;
public:
// A constructor taking another stream of integers as input.
squaring_object(InputStream& input_stream)
: m_input_stream(input_stream)
{
if (!m_input_stream.empty())
{
m_current_value = *m_input_stream;
m_current_value = m_current_value * m_current_value;
}
}
// The retrieve operator returning the square of the input stream.
const value_type& operator * () const
{
return m_current_value;
}
// Increment operator: handled by incrementing the input stream.
squaring_object& operator ++ ()
{
++m_input_stream;
if (!m_input_stream.empty())
{
m_current_value = *m_input_stream;
m_current_value = m_current_value * m_current_value;
}
return *this;
}
// Empty indicator: this stream is empty when the input stream is.
bool empty() const
{
return m_input_stream.empty();
}
};
// define comparator class: compare right-most decimal and then absolute value
struct CompareMod10
{
// comparison operator() returning true if (a < b)
inline bool operator () (int a, int b) const
{
if ((a % 10) == (b % 10))
return a < b;
else
return (a % 10) < (b % 10);
}
// smallest possible integer value
int min_value() const { return INT_MIN; }
// largest possible integer value
int max_value() const { return INT_MAX; }
};
int main()
{
{
counter_object counter;
while (!counter.empty())
{
std::cout << *counter << " ";
++counter;
}
std::cout << std::endl;
}
{
for (counter_object cnt; !cnt.empty(); ++cnt)
{
std::cout << *cnt << " ";
}
std::cout << std::endl;
}
{
counter_object counter;
squaring_object<counter_object> squares(counter);
while (!squares.empty())
{
std::cout << *squares << " ";
++squares;
}
std::cout << std::endl;
}
{
std::vector<int> intvector;
// (fill intvector)
// define stream class iterating over an integer vector
typedef stxxl::stream::iterator2stream<std::vector<int>::const_iterator> intstream_type;
// instantiate the stream object, iterate from begin to end of intvector.
intstream_type intstream(intvector.begin(), intvector.end());
```

--------------------------------

### stxxl_tool benchmark_disks example run

Source: http://stxxl.org/tags/1.4.1/stxxl_tool.html

Benchmarks disk bandwidth by reading the .stxxl configuration, opening all parallel disk files, and writing/reading the specified amount of data. The example uses 10 GiB with batch size 4 and shows the output including parameter settings, disk allocation messages, and per-offset transfer speeds.

```bash
$ stxxl_tool benchmark_disks 10gib -b 4
Parameter size set to 10737418240.
Option -b, --batch set to 4.
[STXXL-MSG] STXXL v1.4.0 (prerelease)
[STXXL-MSG] Disk '/data01/stxxl' is allocated, space: 228881 MiB, I/O implementation: syscall
[STXXL-MSG] Disk '/data02/stxxl' is allocated, space: 228881 MiB, I/O implementation: syscall
[STXXL-MSG] In total 2 disks are allocated, space: 457763 MiB
# Batch size: 33554432 (32.000 MiB)  (4 blocks of 8388608 (8.000 MiB) ) using randomized cycling striping
Offset          0 MiB: 170.6 MiB/s write, 108.9 MiB/s read
Offset         32 MiB: 164.6 MiB/s write, 108.4 MiB/s read
Offset         64 MiB: 158.6 MiB/s write, 102.0 MiB/s read
Offset         96 MiB: 143.8 MiB/s write, 116.3 MiB/s read
Offset        128 MiB: 156.3 MiB/s write, 130.7 MiB/s read
Offset        160 MiB: 168.3 MiB/s write,  99.3 MiB/s read
Offset        192 MiB: 156.6 MiB/s write, 109.2 MiB/s read
Offset        224 MiB: 159.9 MiB/s write, 107.7 MiB/s read
Offset        256 MiB: 156.0 MiB/s write,  88.7 MiB/s read
Offset        288 MiB: 149.6 MiB/s write, 109.7 MiB/s read
Offset        320 MiB: 138.3 MiB/s write, 113.2 MiB/s read
[...]

```

--------------------------------

### Copy and Sort File Example

Source: http://stxxl.org/tags/1.4.1/examples_2algo_2copy_and_sort_file_8cpp-example.html

This example imports a file into an stxxl::vector without copying its content and then sorts it using stxxl::stream::sort while writing the sorted output to a different file.

```cpp
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <stxxl/io>
#include <stxxl/vector>
#include <stxxl/stream>
struct my_type
{
typedef unsigned key_type;
key_type m_key;
char m_data[128 - sizeof(key_type)];
my_type() { }
my_type(key_type k) : m_key(k) { }
static my_type min_value()
{
return my_type(std::numeric_limits<key_type>::min());
}
static my_type max_value()
{
return my_type(std::numeric_limits<key_type>::max());
}
};
inline bool operator < (const my_type& a, const my_type& b)
{
return a.m_key < b.m_key;
}
inline bool operator == (const my_type& a, const my_type& b)
{
return a.m_key == b.m_key;
}
struct Cmp
{
typedef my_type first_argument_type;
typedef my_type second_argument_type;
typedef bool result_type;
bool operator () (const my_type& a, const my_type& b) const
{
return a < b;
}
static my_type min_value()
{
return my_type::min_value();
}
static my_type max_value()
{
return my_type::max_value();
}
};
std::ostream& operator << (std::ostream& o, const my_type& obj)
{
o << obj.m_key;
return o;
}
int main(int argc, char** argv)
{
if (argc < 3)
{
std::cout << "Usage: " << argv[0] << " infile outfile" << std::endl;
return -1;
}
const stxxl::internal_size_type memory_to_use = 512 * 1024 * 1024;
const stxxl::internal_size_type block_size = sizeof(my_type) * 4096;
typedef stxxl::vector<my_type, 1, stxxl::lru_pager<2>, block_size> vector_type;
stxxl::syscall_file in_file(argv[1], stxxl::file::DIRECT | stxxl::file::RDONLY);
stxxl::syscall_file out_file(argv[2], stxxl::file::DIRECT | stxxl::file::RDWR | stxxl::file::CREAT);
vector_type input(&in_file);
vector_type output(&out_file);
output.resize(input.size());
typedef stxxl::stream::streamify_traits<vector_type::iterator>::stream_type input_stream_type;
input_stream_type input_stream = stxxl::stream::streamify(input.begin(), input.end());
typedef Cmp comparator_type;
typedef stxxl::stream::sort<input_stream_type, comparator_type, block_size> sort_stream_type;
sort_stream_type sort_stream(input_stream, comparator_type(), memory_to_use);
vector_type::iterator o = stxxl::stream::materialize(sort_stream, output.begin(), output.end());
STXXL_ASSERT(o == output.end());
if (1) {
STXXL_MSG("Checking order...");
STXXL_MSG((stxxl::is_sorted(output.begin(), output.end(), comparator_type()) ? "OK" : "WRONG"));
}
return 0;
}
```

--------------------------------

### STXXL unordered_map Example

Source: http://stxxl.org/tags/1.4.1/examples_2containers_2unordered_map1_8cpp-example.html

A complete example demonstrating the definition of custom hash and comparison functors, construction of an unordered_map, and basic operations like insertion, deletion, and iteration.

```cpp
/***************************************************************************
* examples/containers/unordered_map1.cpp
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2013 Daniel Feist <daniel.feist@student.kit.edu>
* Copyright (C) 2014 Timo Bingmann <tb@panthema.net>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
//! [example]
#include <stxxl/unordered_map>
#include <iostream>
//! [hash]
struct HashFunctor
{
size_t operator () (int key) const
{
// a simple integer hash function
return (size_t)(key * 2654435761u);
}
};
//! [hash]
//! [comparator]
struct CompareLess
{
bool operator () (const int& a, const int& b) const
{ return a < b; }
static int min_value() { return std::numeric_limits<int>::min(); }
static int max_value() { return std::numeric_limits<int>::max(); }
};
//! [comparator]
int main()
{
//! [construction]
#define SUB_BLOCK_SIZE 8192
#define SUB_BLOCKS_PER_BLOCK 256
// template parameter <KeyType, MappedType, HashType, CompareType, SubBlockSize, SubBlocksPerBlock>
typedef stxxl::unordered_map<
int, char, HashFunctor, CompareLess, SUB_BLOCK_SIZE, SUB_BLOCKS_PER_BLOCK
> unordered_map_type;
// constructor: use defaults for all parameters
unordered_map_type my_map;
//! [construction]
// insert some items and delete one
my_map.insert(std::make_pair(1, 'a'));
my_map.insert(std::make_pair(2, 'b'));
my_map.insert(std::make_pair(3, 'c'));
my_map.insert(std::make_pair(4, 'd'));
my_map.erase(3);
// iterate over all items in the unordered_map
unordered_map_type::iterator iter;
std::cout << "my_map contains:\n";
for (iter = my_map.begin(); iter != my_map.end(); ++iter)
{
std::cout << iter->first << " => " << iter->second << std::endl;
}
// direct operator[] access to items
std::cout << "my_map[2] = " << my_map[2] << std::endl;
// efficient bulk-insert into hash map by sorting by hash keys
std::vector<unordered_map_type::value_type> value_array;
for (int i = 0; i < 128; ++i)
value_array.push_back(std::make_pair(i, (char)i));
my_map.insert(value_array.begin(), value_array.end(), 8 * 1024 * 1024);
// check results of insertion
std::cout << "my_map[42] = " << my_map[42] << std::endl;
std::cout << "my_map.size() = " << my_map.size() << std::endl;
return 0;
}
//! [example]
```

--------------------------------

### STXXL Matrix multiplication and transpose example

Source: http://stxxl.org/tags/1.4.1/tutorial_matrix.html

Minimal working example of STXXL's Matrix. Creates three 3x3 matrices with 64 MB internal memory, fills A and B with arithmetic sequences, multiplies them, transposes the result, and prints C. Requires small_block_order to be a multiple of the matrix value type's bit size.

```cpp
#include <stxxl/bits/containers/matrix.h>
#include <iostream>

int main()
{
    // Matrix dimensions
    int height = 3;
    int width = 3;
    int internal_memory = 64 * 1024 * 1024;
    const int small_block_order = 32; // must be multiple of matrix valueType in bits

    typedef stxxl::block_scheduler<stxxl::matrix_swappable_block<int, small_block_order> > block_schedular_type;
    typedef stxxl::matrix<int, small_block_order> matrix_type;

    block_schedular_type my_bs(internal_memory);

    // Create 3 matrices with given dimensions
    matrix_type A(my_bs, height, width);
    matrix_type B(my_bs, height, width);
    matrix_type C(my_bs, height, width);

    typedef matrix_type::row_major_iterator row_iterator;

    int i = 0;
    // Fill matrix A with values 0,1,2,3,...
    for (row_iterator it_A = A.begin(); it_A != A.end(); ++it_A, ++i)
    {
        *it_A = i;
    }

    i = 0;
    // Fill matrix B with values 0,2,4,8,...
    for (row_iterator it_B = B.begin(); it_B != B.end(); ++it_B, ++i)
    {
        *it_B = i * 2;
    }

    // Multiply matrix A and B and store result in matrix C
    C = A * B;
    C.transpose();

    // Print out matrix C
    for (row_iterator it_C = C.begin(); it_C != C.end(); ++it_C)
    {
        std::cout << *it_C << " ";
    }

    return 0;
}
```

--------------------------------

### Experimental performance results

Source: http://stxxl.org/tags/1.4.1/tutorial_vector_buf.html

Example output from running the vector_buf benchmark on a machine with four disks.

```text
$ vector_buf 64
[STXXL-MSG] STXXL v1.4.0 (prerelease)
[STXXL-MSG] Disk '/data01/stxxl' is allocated, space: 162124 MiB, I/O implementation: syscall_unlink
[STXXL-MSG] Disk '/data02/stxxl' is allocated, space: 228881 MiB, I/O implementation: syscall_unlink
[STXXL-MSG] Disk '/data03/stxxl' is allocated, space: 228881 MiB, I/O implementation: syscall_unlink
[STXXL-MSG] Disk '/data04/stxxl' is allocated, space: 228881 MiB, I/O implementation: syscall_unlink
[STXXL-MSG] In total 4 disks are allocated, space: 848770 MiB
[STXXL-MSG] Starting vector element access
sum: 4393751543808
[STXXL-MSG] Finished vector element access after 848.695 seconds. Processed 128.000 GiB @ 154.439 MiB/s
[STXXL-MSG] Starting vector iterator access
sum: 4393751543808
[STXXL-MSG] Finished vector iterator access after 540.938 seconds. Processed 128.000 GiB @ 242.305 MiB/s
[STXXL-MSG] Starting vector buffered access
sum: 4393751543808
[STXXL-MSG] Finished vector buffered access after 441.26 seconds. Processed 128.000 GiB @ 297.040 MiB/s
[STXXL-MSG] Starting vector C++11 loop access
sum: 4393751543808
[STXXL-MSG] Finished vector C++11 loop access after 440.977 seconds. Processed 128.000 GiB @ 297.231 MiB/s
```

--------------------------------

### C++ example using stxxl::cmdline_parser

Source: http://stxxl.org/tags/1.4.1/common_cmdline.html

Shows how to create a command line parser, add options (uint, bytes, string parameter), process arguments, and print results. Requires including <stxxl/cmdline>. If processing fails, it returns -1 and prints help.

```cpp
#include <stxxl/cmdline>

int main(int argc, char* argv[])
{
    stxxl::cmdline_parser cp;

    // add description and author
    cp.set_description("This may some day be a useful program, which solves "
                        "many serious problems of the real world and achives "
                        "global peace.");
    cp.set_author("Timo Bingmann <tb@panthema.net>");

    // add an unsigned integer option --rounds <N>
    unsigned int rounds = 0;
    cp.add_uint('r', "rounds", "N", "Run N rounds of the experiment.", rounds);

    // add a byte size argument which the user can enter like '1gi'
    stxxl::uint64 a_size = 0;
    cp.add_bytes('s', "size", "Number of bytes to process.", a_size);

    // add a required parameter
    std::string a_filename;
    cp.add_param_string("filename", "A filename to process", a_filename);

    // process command line
    if (!cp.process(argc, argv))
        return -1; // some error occurred and help was always written to user.

    std::cout << "Command line parsed okay." << std::endl;

    // output for debugging
    cp.print_result();

    // do something useful
}
```

--------------------------------

### skew3.cpp: External memory suffix array construction (DC3)

Source: http://stxxl.org/tags/1.4.1/examples_2applications_2skew3_8cpp-example.html

Full source of the STXXL example skew3.cpp implementing the DC3 (skew3) external memory suffix array algorithm. Includes the sacheck() correctness checker and the start of the main pipeline. Uses STXXL data structures and streams.

```cpp
/***************************************************************************
* examples/applications/skew3.cpp
*
* Implementation of the external memory suffix sorting algorithm DC3 aka
* skew3 as described in Roman Dementiev, Juha Kaerkkaeinen, Jens Mehnert and
* Peter Sanders. "Better External Memory Suffix Array Construction". Journal
* of Experimental Algorithmics (JEA), volume 12, 2008.
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2004 Jens Mehnert <jmehnert@mpi-sb.mpg.de>
* Copyright (C) 2012-2013 Timo Bingmann <tb@panthema.net>
* Copyright (C) 2012-2013 Daniel Feist <daniel.feist@student.kit.edu>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
#include <stxxl/algorithm>
#include <stxxl/cmdline>
#include <stxxl/io>
#include <stxxl/random>
#include <stxxl/sorter>
#include <stxxl/stats>
#include <stxxl/stream>
#include <stxxl/vector>
#include <stxxl/bits/common/uint_types.h>
using stxxl::uint64;
using stxxl::internal_size_type;
using stxxl::external_size_type;
namespace stream = stxxl::stream;
// 1 GiB ram used by external data structures / 1 MiB block size
internal_size_type ram_use = 1024 * 1024 * 1024;
// alphabet data type
typedef unsigned char alphabet_type;
// calculation data type
typedef external_size_type size_type;
/// Suffix Array checker for correctness verification
/**
* Algorithm to check whether the suffix array is correct. Loosely based on the
* ideas of Kaerkkaeinen und Burghardt, originally implemented in STXXL by Jens
* Mehnert (2004), reimplemented using triples by Timo Bingmann (2012).
*
* @param InputT is the original text, from which the suffix array was build
* @param InputSA is the suffix array from InputT
*
* Note: ISA := The inverse of SA
*/
template <typename InputT, typename InputSA>
bool sacheck(InputT& inputT, InputSA& inputSA)
{
typedef typename InputSA::value_type offset_type;
typedef stxxl::tuple<offset_type, offset_type> pair_type;
typedef stxxl::tuple<offset_type, offset_type, offset_type> triple_type;
// *** Pipeline Declaration ***
// Build tuples with index: (SA[i]) -> (i, SA[i])
typedef stxxl::stream::counter<offset_type> index_counter_type;
index_counter_type index_counter;
typedef stream::make_tuple<index_counter_type, InputSA> tuple_index_sa_type;
tuple_index_sa_type tuple_index_sa(index_counter, inputSA);
// take (i, SA[i]) and sort to (ISA[i], i)
typedef stxxl::tuple_less2nd<pair_type> pair_less_type;
typedef typename stream::sort<tuple_index_sa_type, pair_less_type> build_isa_type;
build_isa_type build_isa(tuple_index_sa, pair_less_type(), ram_use / 3);
// build (ISA[i], T[i], ISA[i+1]) and sort to (i, T[SA[i]], ISA[SA[i]+1])
typedef stxxl::tuple_less1st<triple_type> triple_less_type; // comparison relation
typedef typename stream::use_push<triple_type> triple_push_type; // indicator use push()
typedef typename stream::runs_creator<triple_push_type, triple_less_type> triple_rc_type;
typedef typename stream::runs_merger<typename triple_rc_type::sorted_runs_type, triple_less_type> triple_rm_type;
triple_rc_type triple_rc(triple_less_type(), ram_use / 3);
// ************************* Process ******************************
// loop 1: read ISA and check for a permutation. Simultaneously create runs
// of triples by iterating ISA and T.

```

--------------------------------

### Create my-project directory and clone STXXL inside it

Source: http://stxxl.org/tags/1.4.1/install_unix.html

Creates an empty directory 'my-project' and clones the STXXL repository inside it.

```bash
$ mkdir my-project
$ cd my-project
$ git clone http://github.com/stxxl/stxxl.git

```

--------------------------------

### external_shared_ptr get method

Source: http://stxxl.org/tags/1.4.1/external__shared__ptr_8h_source.html

Returns the wrapped pointer. Calling get() after unwrap() results in undefined behavior.

```cpp
P get() const
{
  P* p = reinterpret_cast<P*>((void*)data);
  return *p;
}
```

--------------------------------

### scoped_print_timer::scoped_print_timer

Source: http://stxxl.org/tags/1.4.1/timer_8h_source.html

Constructs a scoped print timer, saving the message and starting the timer. It prints a start message.

```APIDOC
## scoped_print_timer::scoped_print_timer

### Description
Constructs a scoped print timer, saving the message and starting the timer. It prints a start message.

### Method
Constructor

### Parameters
- **message** (const std::string&) - Required - The message to display.
- **bytes** (const uint64) - Optional - The number of bytes processed. Default is 0.

### Request Example
```cpp
scoped_print_timer t("Processing", 1024);
```

```

--------------------------------

### Using stxxl::queue in examples/containers/queue2.cpp

Source: http://stxxl.org/tags/1.4.1/examples_2containers_2queue2_8cpp-example.html

This example demonstrates how to instantiate an stxxl::queue, populate it with random 32-bit integers, and iterate through the elements to find a value smaller than the last inserted element.

```cpp
/***************************************************************************
* examples/containers/queue2.cpp
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2013 Daniel Feist <daniel.feist@student.kit.edu>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
#include <stxxl/queue>
#include <iostream>
int main()
{
// template parameter <value_type, block_size, allocation_strategy, size_type>
typedef stxxl::queue<unsigned int> a_queue;
// construct queue with default parameters
a_queue my_queue;
unsigned int random;
stxxl::random_number32 rand32; // define random number generator
stxxl::uint64 number_of_elements = 64 * 1024 * 1024;
// push random values in the queue
for (stxxl::uint64 i = 0; i < number_of_elements; i++)
{
random = rand32(); // generate random integers from interval [0,2^32)
my_queue.push(random);
}
unsigned int last_inserted = my_queue.back();
STXXL_MSG("last element inserted: " << last_inserted);
// identify smaller element than first_inserted, search in growth-direction (front->back)
while (!my_queue.empty())
{
if (last_inserted > my_queue.front())
{
STXXL_MSG("found smaller element: " << my_queue.front() << " than last inserted element");
break;
}
std::cout << my_queue.front() << " " << std::endl;
my_queue.pop();
}
return 0;
}
```

--------------------------------

### init()

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1sequence.html

Initializes an empty sequence with optional prefetch configuration.

```APIDOC
## init()

### Description
Initialize empty sequence.

### Method
init

### Signature
`void init(int _blocks2prefetch_ = -1)`

### Parameters
- **_blocks2prefetch_** (int) - Optional - Number of blocks to prefetch. Defaults to -1.

### Returns
- **void** - No return value.

### Definition
Line 195 of sequence.h.
```

--------------------------------

### stxxl::for_each Usage Example

Source: http://stxxl.org/tags/1.4.1/design_algo_foreach.html

An example demonstrating the use of stxxl::for_each with a custom print functor to iterate over an STXXL vector.

```cpp
template<class T>
struct print : public unary_function<T, void>
{
print(ostream& out) : os(out), count(0) {}
void operator() (T x) { os << x << ' '; ++count; }
ostream& os;
int count;
};
typedef stxxl::VECTOR_GENERATOR<int>::result vector_type;
int main()
{
vector_type A(N);
// fill A with some values
// ...
print<int> P = stxxl::for_each(A.begin(), A.end(), print<int>(cout));
cout << endl << P.count << " objects printed." << endl;
}
```

--------------------------------

### Insert elements at start and end with push_front/push_back

Source: http://stxxl.org/tags/1.4.1/tutorial_sequence.html

Inserts elements at the start and end of the sequence using push_front() and push_back(), resulting in |11|2|5|8|.

```cpp
my_sequence.push_front(2);
my_sequence.push_front(11);
my_sequence.push_back(5);
my_sequence.push_back(8);
// sequence now stores: |11|2|5|8|
```

--------------------------------

### Build and run unit tests

Source: http://stxxl.org/tags/1.4.1/install_build_options.html

Use these commands to build and run the test suite. Defining BUILD_TESTS also builds everything in examples/.

```bash
$ cmake -DBUILD_TESTS=ON ...
```

```bash
$ make test
```

--------------------------------

### Comparison Type Example: CmpIntLess

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1map.html

An example of a comparison struct for stxxl::map that implements a less-than ordering and provides the required max_value method.

```cpp
struct CmpIntLess
{
  bool operator () (const int & a, const int & b) const { return a<b; }
  static int max_value() const  { return std::numeric_limits<int>::max(); }
};
```

--------------------------------

### Initialize Write-Back Through-Log File

Source: http://stxxl.org/tags/1.4.1/create__file_8cpp_source.html

Instantiates a wbtl_file with a syscall_file backend.

```cpp
else if (cfg.io_impl == "wbtl")
{
ufs_file_base* backend =
new syscall_file(cfg.path, mode, -1, -1); // FIXME: ID
wbtl_file* result =
new stxxl::wbtl_file(backend, 16 * 1024 * 1024, 2, cfg.queue,
disk_allocator_id);
result->lock();

if (cfg.unlink_on_open)
backend->unlink();

return result;
}
```

--------------------------------

### STXXL queue push/pop/front/back example

Source: http://stxxl.org/tags/1.4.1/examples_2containers_2queue1_8cpp-example.html

Demonstrates the STXXL queue container. Creates a queue of unsigned ints, pushes four values, then prints and asserts the back (last inserted) and front (first inserted) elements. After popping the front, it prints and asserts the new front. Requires the stxxl/queue header.

```cpp
#include <stxxl/queue>
#include <iostream>
int main()
{
typedef stxxl::queue<unsigned int> queue;
queue my_queue;
my_queue.push(5);
my_queue.push(11);
my_queue.push(3);
my_queue.push(7);
// my_queue now stores: |7|3|11|5|
assert(my_queue.size() == 4);
std::cout << "back element " << my_queue.back() << std::endl; // prints out 7 (last inserted element)
assert(my_queue.back() == 7);
std::cout << "front element " << my_queue.front() << std::endl; // prints out 5 (first inserted element)
assert(my_queue.front() == 5);
my_queue.pop(); // deletes element 5, queue now stores: |7|3|11|
std::cout << "front element " << my_queue.front() << std::endl; // prints out 11
assert(my_queue.front() == 11);
return 0;
}
```

--------------------------------

### Comparison Type Example: CmpIntGreater

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1map.html

An example of a comparison struct for stxxl::map that implements a greater-than ordering and provides the required max_value method.

```cpp
struct CmpIntGreater
{
  bool operator () (const int & a, const int & b) const { return a>b; }
  static int max_value() { return std::numeric_limits<int>::min(); }
};
```

--------------------------------

### stxxl::for_each_m example: AddX functor and usage

Source: http://stxxl.org/tags/1.4.1/design_algo_foreachm.html

Example showing how to use stxxl::for_each_m to add a constant value to each element of a stxxl::VECTOR_GENERATOR vector. The functor AddX modifies its argument in place, demonstrating the mutating capability. The example includes the functor definition, vector type declaration, and the call to stxxl::for_each_m.

```cpp
struct AddX
{
int x;
AddX(int x_): x(x_) {}
void operator() (int & val)
{ val += x; }
};
typedef stxxl::VECTOR_GENERATOR<int>::result vector_type;
int main()
{
vector_type A(N);
// fill A with some values ...
// Add 5 to each value in the vector
stxxl::for_each_m(A.begin(), A.end(), AddX(5));
}
```

--------------------------------

### C++ code configuring STXXL disks with stxxl::config and stxxl::disk_config

Source: http://stxxl.org/tags/1.4.1/install_config.html

Shows how to configure STXXL disks from a user application using the stxxl::config singleton, stxxl::disk_config objects, and the add_disk method. This must be done before any other STXXL calls, before allocating external memory blocks. The example forces O_DIRECT via disk1.direct and adds disks from a directory and a string.

```cpp
int main()
{
// get uninitialized config singleton
stxxl::config * cfg = stxxl::config::get_instance();
// create a disk_config structure.
stxxl::disk_config disk1("/tmp/stxxl.tmp", 100 * 1024 * 1024, "syscall unlink");
disk1.direct = stxxl::disk_config::DIRECT_ON; // force O_DIRECT
// add disk to config
cfg->add_disk(disk1);
// add another disk
cfg->add_disk( disk_config("disk=/tmp/stxxl-2.tmp, 10 GiB, syscall unlink") );
// ... add more disks
// use STXXL library as usual ...
}

```

--------------------------------

### void scoped_read_write_timer::start(size_type size)

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1stats_1_1scoped__read__write__timer.html

Starts the timer for a read or write operation with the given size. This method is used to manually start timing if the timer was stopped.

```APIDOC
## Method: void start(size_type size)

### Description
Starts the timer for a read or write operation with the given size. This method is used to manually start timing if the timer was stopped.

### Parameters
- **size** (size_type) - Required - The size of the operation.

### Example
```cpp
stxxl::stats::scoped_read_write_timer timer(1024);
timer.stop();
timer.start(2048);
```
```

--------------------------------

### normal_leaf size, my_bid, save, load, prefetch, init

Source: http://stxxl.org/tags/1.4.1/leaf_8h_source.html

Utility methods: returns current size, returns the leaf's bid, writes block to disk, reads block from disk, prefetches block, and initializes the leaf with a bid.

```cpp
unsigned size() const
{
    return m_block->info.cur_size;
}

const bid_type & my_bid() const
{
    return m_block->info.me;
}

void save()
{
    request_ptr req = m_block->write(my_bid());
    req->wait();
}

request_ptr load(const bid_type& bid)
{
    request_ptr req = m_block->read(bid);
    req->wait();
    assert(bid == my_bid());
    return req;
}

request_ptr prefetch(const bid_type& bid)
{
    return m_block->read(bid);
}

void init(const bid_type& my_bid_)
{
    m_block->info.me = my_bid_;
    m_block->info.succ = bid_type();
    m_block->info.pred = bid_type();
}
```

--------------------------------

### begin()

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1vector__bufreader.html

Returns an iterator for C++11 range-based for loops.

```APIDOC
## bufreader_iterator begin()

### Description
Return vector_bufreader_iterator for C++11 range-based for loop.

### Returns
- **bufreader_iterator** - iterator for range-based for loop

### Definition
Line 2079 of file vector.h.
```

--------------------------------

### B-tree lower_bound() start

Source: http://stxxl.org/tags/1.4.1/btree_8h_source.html

Starts the lower_bound search by finding the first element not less than the key in the root node. The code is truncated in the source; the full implementation is not shown.

```cpp
iterator lower_bound(const key_type& k)
{
root_node_iterator_type it = m_root_node.lower_bound(k);
assert(it != m_root_node.end());
```

--------------------------------

### Basic stxxl::vector usage

Source: http://stxxl.org/tags/1.4.1/design_vector.html

Demonstrates initializing an stxxl::vector, adding an element with push_back, and verifying the state with assertions.

```cpp
stxxl::vector<int> V;
V.push_back(3);
assert(V.size() == 1 && V.capacity() >= 1 && V[0] == 3);
```

--------------------------------

### disk_config(const std::string &path, uint64 size, const std::string &fileio)

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1disk__config.html

Initializes disk configuration with path, size, and fileio string, parsing the fileio parameter.

```APIDOC
## `disk_config(const std::string &path, uint64 size, const std::string &fileio)`

### Description
Initializing constructor that sets the disk path, size, and file I/O parameters. It also parses the fileio parameter for optional configuration.

### Parameters
- **path** (const std::string&) - The disk path.
- **size** (uint64) - The disk size.
- **fileio** (const std::string&) - The fileio implementation and optional parameters.

### Return Value
None.

```

--------------------------------

### get

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1const__counting__ptr.html

Returns the enclosed pointer.

```APIDOC
## `template<class Type> const Type* stxxl::const_counting_ptr<Type>::get() const`

### Description
Returns the enclosed pointer.

### Method
`get`

### Parameters
None.

### Return Value
`const Type*` - The enclosed pointer.
```

--------------------------------

### begin()

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1unordered__map.html

Returns an iterator pointing to the beginning of the hash-map.

```APIDOC
## iterator begin()

### Description
Returns an iterator pointing to the beginning of the hash-map.

### Returns
- **iterator** - Iterator to the first element.
```

--------------------------------

### get_internal_block (non-const)

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1swappable__block.html

Get a reference to the data-block. Has to be acquired.

```APIDOC
## get_internal_block (non-const)

### Description
Get a reference to the data-block. Has to be acquired.

### Method
get_internal_block

### Signature
`template<typename ValueType, unsigned BlockSize> internal_block_type& stxxl::swappable_block<ValueType, BlockSize>::get_internal_block()`

### Parameters
None

### Returns
internal_block_type& - reference to the internal block

```

--------------------------------

### Build STXXL project with CMake

Source: http://stxxl.org/tags/1.4.1/install_unix.html

Commands to copy a test file, create a build directory, configure with CMake, and compile the project. The output is omitted but indicated by placeholders.

```bash
$ cp stxxl/local/test1.cpp main.cpp
$ mkdir build
$ cd build
$ cmake ..
<lots of output by cmake>
$ make
<lots of compilation messages>
```

--------------------------------

### get_internal_block (const)

Source: http://stxxl.org/tags/1.4.1/classstxxl_1_1swappable__block.html

Get a reference to the data-block. Has to be acquired.

```APIDOC
## get_internal_block (const)

### Description
Get a reference to the data-block. Has to be acquired.

### Method
get_internal_block

### Signature
`template<typename ValueType, unsigned BlockSize> const internal_block_type& stxxl::swappable_block<ValueType, BlockSize>::get_internal_block() const`

### Parameters
None

### Returns
const internal_block_type& - reference to the internal block

```

--------------------------------

### Deprecated get method

Source: http://stxxl.org/tags/1.4.1/write__pool_8h_source.html

A deprecated alias for the steal() method.

```cpp
STXXL_DEPRECATED(block_type * get())
{
	return steal();
}
```

--------------------------------

### init method

Source: http://stxxl.org/tags/1.4.1/block__scheduler_8h_source.html

Initializes the scheduler by copying the prediction sequence from an old algorithm and populating evictable blocks.

```cpp
void init(block_scheduler_algorithm_type* old_algo)
{
if (old_algo)
// copy prediction sequence
prediction_sequence = old_algo->get_prediction_sequence();
next_op_to_schedule = prediction_sequence.begin();
if (get_algorithm_from_block_scheduler())
while (! get_algorithm_from_block_scheduler()->evictable_blocks_empty())
free_evictable_blocks.insert(get_algorithm_from_block_scheduler()->evictable_blocks_pop());
schedule_next_operations();
}
```
Tokens:
Raw