/home/palakars/workspace-inprogress/code-in-progress/aitools3/aitools3-aq-invertedindex-cpp/src/core/ExternalMergeSort.hpp

Go to the documentation of this file.

/* Copyright (C) 2010 webis.de
 * All rights reserved.
 */
#ifndef AITOOLS_INVERTEDINDEX_EXTERNAL_MERGE_SORT_HPP
#define AITOOLS_INVERTEDINDEX_EXTERNAL_MERGE_SORT_HPP

#include "InternalIntroSort.hpp"
#include "System.hpp"

namespace aitools {
namespace invertedindex {

class ExternalMergeSort {

private: // nested types

        typedef Configuration::Sorting Sorting;

public: // class data

        static const size_t max_memory = 100 * 1024 * 1024; // 100 MB

private: // disallow instantiation

        ExternalMergeSort();

public: // class methods

        template<typename Value>
        static void
        sort(Postlist<Value>& postlist, Quantile& quantile, Sorting mode);

private: // class methods

        template<typename Value>
        static void
        partition(Postlist<Value>& postlist, Quantile& quantile,
                          std::vector<FILE*>& buckets, Sorting mode);

        template<typename Value>
        static void
        merge(Postlist<Value>& postlist, std::vector<FILE*>& buckets, Sorting mode);

        template<typename Value>
        static FILE*
        swap_out(const std::vector<Value>& entries);

};

// IMPLEMENTATION

template<typename Value>
void ExternalMergeSort::sort
(Postlist<Value>& postlist, Quantile& quantile, Sorting mode)
{
        if (mode == Configuration::DISABLED) return;

        if (postlist.payload() / max_memory == 0)
        {
                return InternalIntroSort::sort(postlist, quantile, mode);
        }

        // Create and write external sorted bucket files
        std::vector<FILE*> buckets;
        partition(postlist, quantile, buckets, mode);

        // Merge bucket files to one sorted postlist
        merge(postlist, buckets, mode);
}

template<typename Value>
void ExternalMergeSort::partition
(Postlist<Value>& postlist, Quantile& quantile, std::vector<FILE*>& buckets,
                Sorting mode)
{
        Value value;
        quantile.clear();
        Quantile subquantile;
        std::vector<Value> entries;
        size_t bucket_count(postlist.payload() / max_memory);
        size_t entries_per_bucket(postlist.length() / bucket_count);
        entries.reserve(entries_per_bucket);
        while (postlist.next(value))
        {
                entries.push_back(value);
                if (entries.size() == entries_per_bucket)
                {
                        InternalIntroSort::sort(entries, subquantile, mode);
                        buckets.push_back(swap_out(entries));
                        quantile += subquantile;
                        entries.clear();
                }
        }
        if (!entries.empty())
        {
                InternalIntroSort::sort(entries, subquantile, mode);
                buckets.push_back(swap_out(entries));
                quantile += subquantile;
                entries.clear();
        }
}

template<typename Value>
void ExternalMergeSort::merge
(Postlist<Value>& postlist, std::vector<FILE*>& buckets, Sorting mode)
{
        ByteBuffer buffer;
//      Iterator::value_size_t value_size;
        uint16_t value_size; // TODO
        std::vector<Value> entries(buckets.size());
        for (unsigned i(0); i != buckets.size(); ++i)
        {
                std::rewind(buckets[i]);
                System::fread(&value_size, sizeof(value_size), 1, buckets[i]);
                buffer.resize(value_size);
                System::fread(buffer.data(), 1, value_size, buckets[i]);
                entries[i].wrap(buffer);
        }
        size_t index;
        PostlistBuilder builder;
        builder.set_checksum(postlist.iterator()->header().checksum);
        typename std::vector<Value>::iterator next_value;
        while (!entries.empty())
        {
                if (mode == Configuration::ASCENDING)
                {
                        next_value = std::min_element(entries.begin(), entries.end());
                }
                else
                {
                        next_value = std::max_element(entries.begin(), entries.end());
                }
                index = next_value - entries.begin();
                next_value->to_bytes(buffer);
                builder.append(buffer);
                try
                {
                        System::fread(&value_size, sizeof(value_size), 1, buckets[index]);
                        buffer.resize(value_size);
                        System::fread(buffer.data(), 1, value_size, buckets[index]);
                        next_value->wrap(buffer);
                }
                catch (const std::runtime_error& error) // end of file reached
                {
                        std::fclose(buckets[index]);
                        entries.erase(next_value);
                        buckets.erase(buckets.begin() + index);
                }
        }
        postlist = builder.build();
}

template<typename Value>
FILE*
ExternalMergeSort::swap_out(const std::vector<Value>& entries)
{
        ByteBuffer buffer;
        FILE* bucket(System::tmpfile());
        Iterator::value_size_t value_size;
        typename std::vector<Value>::const_iterator end(entries.end());
        typename std::vector<Value>::const_iterator it(entries.begin());
        for (; it != end; ++it)
        {
                it->to_bytes(buffer);
                value_size = buffer.size();
                System::fwrite(&value_size, sizeof(value_size), 1, bucket);
                System::fwrite(buffer.data(), 1, value_size, bucket);
        }
        return bucket;
}

} // namespace invertedindex
} // namespace aitools

#endif // AITOOLS_INVERTEDINDEX_EXTERNAL_MERGE_SORT_HPP

---