ExternalSortMerger.h

Go to the documentation of this file.

/*
// $Id: //open/dev/fennel/sorter/ExternalSortMerger.h#2 $
// Fennel is a library of data storage and processing components.
// Copyright (C) 2005-2009 The Eigenbase Project
// Copyright (C) 2009-2009 SQLstream, Inc.
// Copyright (C) 2004-2009 LucidEra, Inc.
// Portions Copyright (C) 2004-2009 John V. Sichi
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 of the License, or (at your option)
// any later version approved by The Eigenbase Project.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef Fennel_ExternalSortMerger_Included
#define Fennel_ExternalSortMerger_Included

#include "fennel/sorter/ExternalSortSubStream.h"
#include "fennel/tuple/TupleAccessor.h"
#include "fennel/tuple/TupleData.h"
#include "fennel/tuple/TupleProjectionAccessor.h"

#include <boost/scoped_ptr.hpp>
#include <boost/scoped_array.hpp>

#include <vector>

FENNEL_BEGIN_NAMESPACE

struct ExternalSortMergeInfo
{
    PBuffer val;
    uint runOrd;

    explicit ExternalSortMergeInfo()
    {
        val = NULL;
        runOrd = 0;
    }
};

class ExternalSortInfo;
class ExternalSortRunAccessor;

typedef boost::shared_ptr<ExternalSortRunAccessor>
SharedExternalSortRunAccessor;

class FENNEL_SORTER_EXPORT ExternalSortMerger
    : public ExternalSortSubStream
{
    ExternalSortInfo &sortInfo;

    boost::scoped_array<SharedExternalSortRunAccessor> ppRunAccessors;

    boost::scoped_array<ExternalSortFetchArray *> ppFetchArrays;

    boost::scoped_array<uint> pOrds;

    uint nMergeMemPages;

    uint nRuns;

    boost::scoped_array<ExternalSortMergeInfo> mergeInfo;

    ExternalSortFetchArray fetchArray;

    PBuffer ppTupleBuffers[EXTSORT_FETCH_ARRAY_SIZE];

    // TODO:  comment or replace
    TupleAccessor tupleAccessor;
    TupleAccessor tupleAccessor2;
    TupleProjectionAccessor keyAccessor;
    TupleProjectionAccessor keyAccessor2;
    TupleData keyData;
    TupleData keyData2;

// ----------------------------------------------------------------------
// private methods
// ----------------------------------------------------------------------

    inline uint heapParent(uint i);
    inline uint heapLeft(uint i);
    inline uint heapRight(uint i);
    inline void heapExchange(uint i,uint j);
    void heapify(uint i);
    void heapBuild();

    // TODO:  doc
    ExternalSortRC checkFetch();
    inline ExternalSortMergeInfo &getMergeHigh();

public:
    explicit ExternalSortMerger(ExternalSortInfo &info);
    virtual ~ExternalSortMerger();

    void initRunAccess();

    void startMerge(
        std::vector<SharedSegStreamAllocation>::iterator pStoredRun,
        uint nRunsToMerge);

    void releaseResources();

    // implement ExternalSortSubStream
    virtual ExternalSortFetchArray &bindFetchArray();
    virtual ExternalSortRC fetch(uint nTuplesRequested);
};

FENNEL_END_NAMESPACE

#endif

// End ExternalSortMerger.h

---