ExternalSort.h

Go to the documentation of this file.

#ifndef SORT_EXTERNALSORT_H
#define SORT_EXTERNALSORT_H
 
#include "tdb.h"
 
#include <functional>
 
#include "extsort/ItemIterator.h"
#include "storage/VarlenDataPage.h"
#include "storage/FileManager.h"
 
namespace taco {
 
typedef std::function<int(const char *item1, const char *item2)>
        SortCompareFunction;
 
 
class ExternalSort {
public:
    static std::unique_ptr<ExternalSort>
    Create(const SortCompareFunction& comp, size_t merge_ways);
 
    ~ExternalSort();
 
    std::unique_ptr<ItemIterator> Sort(ItemIterator *input_iter);
 
private:
 
    class OutputIterator : public ItemIterator {
    public:
        OutputIterator(const File* tmpfile,
                       PageNumber final_num_pages);
 
        ~OutputIterator() override;
 
        bool Next() override;
 
        const char* GetCurrentItem(FieldOffset& p_reclen) override;
 
        bool SupportsRewind() const override { return true; }
 
        uint64_t SavePosition() const override {
            RecordId rid = {m_pid, m_sid};
            return *reinterpret_cast<uint64_t*>(&rid);
        }
 
        void Rewind(uint64_t pos) override;
 
        /*
         * Clean up state.
         */
        void EndScan() override;
    private:
 
        const File* m_file;
 
        PageNumber m_pid;
        PageNumber m_final_num_pages;
        SlotId m_sid;
        char* m_buf;
        VarlenDataPage m_pg;
    };
 
    ExternalSort(const SortCompareFunction& comp, size_t merge_ways);
 
    void SortInitialRuns(ItemIterator* item_iter);
 
    void GenerateNewPass(std::vector<PageNumber>& new_run_boundaries);
 
    PageNumber MergeInternalRuns(size_t low_run, size_t high_run);
 
    void WriteOutInitialPass(std::vector<Record>& pass);
    void WriteOutRecord(Record& rec);
 
    uint8_t m_current_pass;
    std::unique_ptr<File> m_file[2];
    size_t m_merge_ways;
    SortCompareFunction m_cmp;
    std::vector<PageNumber> m_run_boundaries;
 
    char* m_inputbuf;
    char* m_outbuf;
    VarlenDataPage m_outpg;
    PageNumber m_output_pos;
};
 
}   // namespace taco
 
#endif      // SORT_EXTERNALSORT_H