cur_list.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    cur_list.h
// Purpose:     Cursor for list of objects/tuples
// Last Change: 04.08.2017
// Language:    C++
// EMail:       brass@informatik.uni-halle.de
// WWW:         http://www.informatik.uni-halle.de/~brass/
// Address:     Feldschloesschen 15, D-06120 Halle (Saale), GERMANY
// Copyright:   (c) 2015-2017 by Stefan Brass
// License:     See file "LICENSE" for copying conditions.
// Note:        There is no warranty at all - this code may contain bugs.
// ============================================================================


//=============================================================================
// Include File Frame:
//=============================================================================

#ifndef CUR_LIST_INCLUDED
#define CUR_LIST_INCLUDED

//=============================================================================
// Used Types and Macros:
//=============================================================================

#ifndef VER_INCLUDED
#include "../base/ver.h"
#endif

#ifndef STR_INCLUDED
#include "../base/str.h"
#endif

#ifndef CHECK_INCLUDED
#include "../base/check.h"
#endif

#ifndef STACK_INCLUDED
#include "../bds/stack.h"
#endif

#ifndef LIST_INCLUDED
#include "../rel/list.h"
#endif


//=============================================================================
// Private Constants:
//=============================================================================

//-----------------------------------------------------------------------------
// CUR_LIST_MAGIC: Magic number (identifies objects of this class).
//-----------------------------------------------------------------------------

static const long CUR_LIST_MAGIC = 0x434C540AL; // 'CLT\n'

//=============================================================================
// Class Template for Flexible Arrays (Lists with Index Access):
//=============================================================================

template<class T> class cur_list_c {
        public:

//-----------------------------------------------------------------------------
// Constructor:
//-----------------------------------------------------------------------------

        cur_list_c(const list_c<T> *list) {

                // Check parameter:
                CHECK(list != static_cast<list_c<T>*>(0),
                                "cur_list_c::constructor: list is NULL");
                CHECK_PAR(list, "cur_list_c::constructor");

                // Initialize attributes:
                List        = list;
                StartPos    = 0;
                EndPos      = 0;
                TotalRest   = 0;
                LeafPtr     = LIST_LEAF_NULL;
                MidPtr      = LIST_MID_NULL;
                TopPtr      = LIST_TOP_NULL;
                LeafRest    = 0;
                MidRest     = 0;
                TopRest     = 0;

                // Set Magic number:
                CHECK_CODE(Magic = CUR_LIST_MAGIC);
        }

//-----------------------------------------------------------------------------
// Destructor:
//-----------------------------------------------------------------------------

        ~cur_list_c()
        {
                // Check this object:
                CHECK_VALID("cur_list_c::destructor");

                // Make this object invalid:
                CHECK_CODE(Magic = 0);
        }

//-----------------------------------------------------------------------------
// Open cursor over entire list (to current end):
//-----------------------------------------------------------------------------

        inline void open() {

                // Check this object:
                CHECK_VALID("cur_list_c::open()");

                // The real work is done in method init(start_pos, end_pos):
                init(0, List->NumRows);
        }

//-----------------------------------------------------------------------------
// Open cursor for looping through a sublist (start pos to current end):
//-----------------------------------------------------------------------------

        inline void open(int start_pos) {

                // Check this object:
                CHECK_VALID("cur_list_c::open(start_pos)");

                // Check Parameter:
                CHECK(start_pos >= 0, "cur_list_c::open: start_pos < 0");
                CHECK(start_pos <= List->NumRows,
                                "cur_list_c::open: start_pos too big");

                // Set the index range and the number of remaining tuples:
                StartPos    = start_pos;
                EndPos      = List->NumRows;
                TotalRest   = EndPos - StartPos;

                // No tuples in each node forces initialization in fetch:
                LeafRest    = 0;
                MidRest     = 0;
                TopRest     = 0;

                // Not really necessary, but maybe safer:
                LeafPtr     = LIST_LEAF_NULL;
                MidPtr      = LIST_MID_NULL;
                TopPtr      = LIST_TOP_NULL;
        }

//-----------------------------------------------------------------------------
// fetch: Get next tuple, returns false if there is no further tuple.
//-----------------------------------------------------------------------------

        inline bool fetch() {

                // Check whether there are still tuples left:
                if(TotalRest-- <= 0)
                        return false;

                // Now we must make LeafPtr point to the current tuple.
                // Most common case: Simply increment it:
                if(LeafRest-- > 0) {
                        LeafPtr++;
                        return true;
                }

                // Switch to next leaf:
                if(MidRest-- > 0) {
                        MidPtr++;
                        LeafPtr = *MidPtr;
                        LeafRest = PAGE_SIZE(T) - 1;
                        return true;
                }

                // Switch to next mid level branch node:
                if(TopRest-- > 0) {
                        TopPtr++;
                        MidPtr   = *TopPtr;
                        MidRest  = PAGE_SIZE(T*) - 1;
                        LeafPtr  = *MidPtr;
                        LeafRest = PAGE_SIZE(T) - 1;
                        return true;
                }

                // Nothing worked. Must initialize everything for first tuple:
                int leaf_offset = StartPos % PAGE_SIZE(T);
                int mid_offset  = StartPos / PAGE_SIZE(T);
                int top_offset  = mid_offset / PAGE_SIZE(T*);
                mid_offset  = mid_offset % PAGE_SIZE(T*);
                CHECK(leaf_offset >= 0, "cur_list_c::fetch: leaf_offset < 0");
                CHECK(mid_offset  >= 0, "cur_list_c::fetch: mid_offset  < 0");
                CHECK(top_offset  >= 0, "cur_list_c::fetch: top_offset  < 0");
                CHECK(leaf_offset < PAGE_SIZE(T),
                                "cur_list_c::fetch: leaf_offset too big");
                CHECK(mid_offset < PAGE_SIZE(T*),
                                "cur_list_c::fetch: mid_offset too big");
                CHECK(top_offset < PAGE_SIZE(T**),
                                "cur_list_c::fetch: top_offset too big");
                switch(List->Height) {
                case 0:
                        CHECK_IMPOSSIBLE(
                            "cur_list_c::fetch: TotalRest>0 but list empty");
                        return false;
                case 1:
                        TopRest  = 0;
                        MidRest  = 0;
                        LeafPtr  = List->LeafNode + leaf_offset;
                        LeafRest = PAGE_SIZE(T) - 1 - leaf_offset;
                        break;
                case 2:
                        TopRest  = 0;
                        MidPtr   = List->MidNode + mid_offset;
                        MidRest  = PAGE_SIZE(T*) - 1 - mid_offset;
                        LeafPtr  = *MidPtr + leaf_offset;
                        LeafRest = PAGE_SIZE(T) - 1 - leaf_offset;
                        break;
                case 3:
                        TopPtr   = List->TopNode + top_offset;
                        TopRest  = PAGE_SIZE(T**) - 1 - top_offset;
                        MidPtr   = *TopPtr + mid_offset;
                        MidRest  = PAGE_SIZE(T*) - 1 - mid_offset;
                        LeafPtr  = *MidPtr + leaf_offset;
                        LeafRest = PAGE_SIZE(T) - 1 - leaf_offset;
                        break;
                default:
                        CHECK_IMPOSSIBLE(
                                "cur_list_c::fetch: Invalid height");
                        return false;
                }
                return true;
        }

//-----------------------------------------------------------------------------
// row: Get current row/tuple:
//-----------------------------------------------------------------------------

        inline T* row() {
                // Check this object:
                CHECK_VALID("cur_list_c::row");

                // Check state:
                CHECK(LeafPtr != LIST_LEAF_NULL,
                                "cur_list_c::row: No current tuple");

                // Return pointer to current tuple:
                return LeafPtr;
        }



//-----------------------------------------------------------------------------
// push: Save the cursor state on a stack.
//-----------------------------------------------------------------------------

        bool push(stack_c<int> *stack) {

                // Check this object:
                CHECK_VALID("cur_list_c::push");

                // Save new start position:
                int start_pos = EndPos - TotalRest;
                CHECK(start_pos >= 0, "cur_list_c::push: start_pos < 0");
                CHECK(start_pos <= EndPos,
                                "cur_list_c::push: start_pos too big");
                if(!stack->push(start_pos))
                        return false;

                // The end position must also be saved
                // because new rows might be inserted into the list:
                if(!stack->push(EndPos))
                        return false;

                // Ok:
                return true;
        }

//-----------------------------------------------------------------------------
// pop: Restore the cursor state from a stack.
//-----------------------------------------------------------------------------

        void pop(stack_c<int> *stack) {

                // Check this object:
                CHECK_VALID("cur_list_c::pop");

                // Reopen this cursor at the saved start position:
                int end_pos   = stack->pop();
                int start_pos = stack->pop();
                CHECK(start_pos >= 0, "cur_list_c::pop: start_pos < 0");
                CHECK(end_pos >= 0, "cur_list_c::pop: end_pos < 0");
                CHECK(start_pos <= end_pos,
                                "cur_list_c::pop: start_pos too big");
                CHECK(end_pos <= List->NumRows,
                                "cur_list_c::pop: end_pos too big");
                init(start_pos, end_pos);
        }

//-----------------------------------------------------------------------------
// Close cursor:
//-----------------------------------------------------------------------------

        inline void close() {
                // Check this object:
                CHECK_VALID("cur_list_c::close");
        }


//=============================================================================
// Auxiliary Methods:
//=============================================================================

        private:

//-----------------------------------------------------------------------------
// Set up a cursor for a given sublist (used in open and pop):
//-----------------------------------------------------------------------------

        inline void init(int start_pos, int end_pos) {

                // Check this object:
                CHECK_VALID("cur_list_c::init");

                // Check Parameters:
                CHECK(start_pos >= 0, "cur_list_c::init: start_pos < 0");
                CHECK(start_pos <= List->NumRows,
                                "cur_list_c::init: start_pos too big");
                CHECK(end_pos >= 0, "cur_list_c::init: end_pos < 0");
                CHECK(end_pos <= List->NumRows,
                                "cur_list_c::init: end_pos too big");

                // Set the index range and the number of remaining tuples:
                StartPos    = start_pos;
                EndPos      = end_pos;
                TotalRest   = EndPos - StartPos;

                // No tuples in each node forces initialization in fetch:
                LeafRest    = 0;
                MidRest     = 0;
                TopRest     = 0;

                // Not really necessary, but maybe safer:
                LeafPtr     = LIST_LEAF_NULL;
                MidPtr      = LIST_MID_NULL;
                TopPtr      = LIST_TOP_NULL;
        }

//=============================================================================
// Debugging Support:
//=============================================================================

//-----------------------------------------------------------------------------
// Copy-constructor and assignment operator are not supported for this class:
//-----------------------------------------------------------------------------

        private:

        cur_list_c(const cur_list_c& obj);              // Not implemented
        cur_list_c& operator=(const cur_list_c& obj);   // Not implemented


//-----------------------------------------------------------------------------
// check: Check the integrity of this object, return error message or NULL.
//-----------------------------------------------------------------------------

#if     VER_DEBUG
        // Integrity check:
        public:
        str_t   check() const {

                // Check magic number:
                if(Magic != CUR_LIST_MAGIC)
                        return "wrong magic number";

                // Check that list is defined:
                if(!List)
                        CHECK_ERR("list is null");

                // Check global positions:
                if(StartPos < 0)
                        CHECK_ERR("StartPos is negative");
                if(StartPos > List->NumRows)
                        CHECK_ERR("StartPos is bigger than list length");
                if(EndPos < 0)
                        CHECK_ERR("EndPos is negative");
                if(EndPos > List->NumRows)
                        CHECK_ERR("EndPos is bigger than list length");
                if(StartPos > EndPos + 1)
                        CHECK_ERR("StartPos > EndPos + 1");
                if(TotalRest > EndPos - StartPos)
                        CHECK_ERR("TotalRest too big");

                // Check remaining number of entries in pages:
                if(LeafRest < 0)
                        CHECK_ERR("LeafRest is negative");
                if(MidRest < 0)
                        CHECK_ERR("MidRest is negative");
                if(TopRest < 0)
                        CHECK_ERR("TopRest is negative");
                if(LeafRest >= PAGE_SIZE(T))
                        CHECK_ERR("LeafRest too big");
                if(MidRest >= PAGE_SIZE(T*))
                        CHECK_ERR("MidRest too big");
                if(TopRest >= PAGE_SIZE(T**))
                        CHECK_ERR("TopRest too big");

                // Check that pointers are defined:
                if(LeafRest > 0 && LeafPtr == LIST_LEAF_NULL)
                        CHECK_ERR("LeafRest is positive, but pointer is null");
                if(MidRest > 0 && MidPtr == LIST_MID_NULL)
                        CHECK_ERR("MidRest is positive, but pointer is null");
                if(TopRest > 0 && TopPtr == LIST_TOP_NULL)
                        CHECK_ERR("TopRest is positive, but pointer is null");

                // Check consistency of pointers:
                if(MidPtr != LIST_MID_NULL &&
                                LeafPtr != *MidPtr +
                                                (PAGE_SIZE(T) - LeafRest - 1))
                        CHECK_ERR("LeafPtr inconsistent with MidPtr+Rest");
                if(TopPtr != LIST_TOP_NULL &&
                                MidPtr != *TopPtr +
                                                (PAGE_SIZE(T*) - MidRest - 1))
                        CHECK_ERR("MidPtr inconsistent with TopPtr+Rest");

                // At least, the root pointer must be within the list page:
                switch(List->Height) {
                case 0:
                        break;
                case 1:
                        if(LeafRest > 0) {
                                if(LeafPtr < List->LeafNode)
                                        CHECK_ERR("Invalid LeafPtr (<)");
                                if(LeafPtr >= List->LeafNode + PAGE_SIZE(T))
                                        CHECK_ERR("Invalid LeafPtr (>=)");
                                if(LeafPtr != List->LeafNode +
                                                (PAGE_SIZE(T)-LeafRest-1))
                                        CHECK_ERR("Invalid LeafPtr (!=)");
                        }
                        break;
                case 2:
                        if(MidRest > 0) {
                                if(MidPtr < List->MidNode)
                                        CHECK_ERR("Invalid MidPtr (<)");
                                if(MidPtr >= List->MidNode + PAGE_SIZE(T*))
                                        CHECK_ERR("Invalid MidPtr (>=)");
                                if(MidPtr != List->MidNode +
                                                (PAGE_SIZE(T*)-MidRest-1))
                                        CHECK_ERR("Invalid MidPtr (!=)");
                        }
                        break;
                case 3:
                        if(TopRest > 0) {
                                if(TopPtr < List->TopNode)
                                        CHECK_ERR("Invalid TopPtr (<)");
                                if(TopPtr >= List->TopNode + PAGE_SIZE(T**))
                                        CHECK_ERR("Invalid TopPtr (>=)");
                                if(TopPtr != List->TopNode +
                                                (PAGE_SIZE(T**)-TopRest-1))
                                        CHECK_ERR("Invalid TopPtr (!=)");
                        }
                        break;
                default:
                        CHECK_ERR("Invalid height");
                }

                // Ok:
                return STR_NULL;
        }

        // Magic number (identifies objects of this class for debugging).
        private:
        long    Magic;          // Must be "CUR_LIST_MAGIC".
#endif

//-----------------------------------------------------------------------------
// dump: Show data structure.
//-----------------------------------------------------------------------------

#if     VER_DUMP

        public:

void dump(str_t headline = STR_NULL) const
{
        // Headline:
        if(headline == STR_NULL)
                headline = "Cursor for List";
        err_c::dump_begin(headline);

        // Basic information:
        err_c::dump_str("List Name:     '");
        err_c::dump_str(List->Name);
        err_c::dump_str("'");
        err_c::dump_nl();
        err_c::dump_str("Start Pos.:     ");
        err_c::dump_int(StartPos);
        err_c::dump_nl();
        err_c::dump_str("End Pos.:       ");
        err_c::dump_int(EndPos);
        err_c::dump_nl();
        err_c::dump_str("Current Pos.:   ");
        err_c::dump_int(EndPos - TotalRest);
        err_c::dump_nl();
        err_c::dump_str("TotalRest:      ");
        err_c::dump_int(TotalRest);
        err_c::dump_nl();
        err_c::dump_str("TopRest:        ");
        err_c::dump_int(TopRest);
        err_c::dump_nl();
        err_c::dump_str("MidRest:        ");
        err_c::dump_int(MidRest);
        err_c::dump_nl();
        err_c::dump_str("LeafRest:       ");
        err_c::dump_int(LeafRest);
        err_c::dump_nl();
        err_c::dump_str("TopPtr:         ");
        err_c::dump_ptr(TopPtr);
        err_c::dump_nl();
        err_c::dump_str("MidPtr:         ");
        err_c::dump_ptr(MidPtr);
        err_c::dump_nl();
        err_c::dump_str("LeafPtr:        ");
        err_c::dump_ptr(LeafPtr);
        err_c::dump_nl();
        err_c::dump_str("Height:         ");
        err_c::dump_int(List->Height);
        err_c::dump_nl();
        err_c::dump_str("Curr. TopNode:  ");
        err_c::dump_ptr(List->TopNode);
        err_c::dump_nl();
        err_c::dump_str("Curr. MidNode:  ");
        err_c::dump_ptr(List->MidNode);
        err_c::dump_nl();
        err_c::dump_str("Curr. LeafNode: ");
        err_c::dump_ptr(List->LeafNode);
        err_c::dump_nl();
        err_c::dump_str("Page Size:      ");
        err_c::dump_int(VER_PAGESIZE);
        err_c::dump_str(" Bytes");
        err_c::dump_nl();
        err_c::dump_str("PAGE_SIZE(T):   ");
        err_c::dump_int(PAGE_SIZE(T));
        err_c::dump_nl();
        err_c::dump_str("PAGE_SIZE(T*):  ");
        err_c::dump_int(PAGE_SIZE(T*));
        err_c::dump_nl();
        err_c::dump_nl();

        // Done:
        err_c::dump_end();
}

#endif


//=============================================================================
// Private Object Members:
//=============================================================================

        private:

        // List: List to which this cursor belongs:
        const list_c<T> *List;

        // StartPos: Index/Position in the list where cursor starts
        // (if cursor is pushed and popped again, this is the popped value):
        int StartPos;

        // EndPos: Current length of the list when the cursor was opened
        // (so that values inserted into the list after the open are not
        // returned by the cursor):
        int EndPos;

        // TotalRest: Number of entries the cursor still has to return
        // (note that this can become negative, if one fetches several times
        // at the end of the scan, but this means the same as 0):
        int TotalRest;

        // LeafRest: Number of entries still remaining in the current leaf node
        // (not counting the current entry, to which LeafPtr points).
        // Note: It is not guaranteed that this number of entries in the node
        // are actually filled, so it is necessary to check TotalRest first.
        int LeafRest;

        // MidRest: Number of slots still remaining in the current mid level
        // node (not counting the current entry to which MidPtr points).
        int MidRest;

        // TopRest: Number of slots still remaining in the top level node
        // (not counting the current entry to which TopPtr points):
        int TopRest;

        // LeafPtr: Pointer to the current value (tuple) in the scan
        // (this is only usable if LeafRest > 0):
        T* LeafPtr;

        // MidPtr: Pointer to the current entry in the mid level node
        // (i.e. this points to the current leaf, if it is not null,
        // so there is a mid level node. This is only usable if MidRest > 0):
        T** MidPtr;

        // TopPtr: Pointer to the current entry in the top level node
        // (i.e. this points to the current mid level node, if it is not null,
        // i.e. there is a top node. This is only usable if TopRest > 0):
        T*** TopPtr;

//=============================================================================
// End of Class Template:
//=============================================================================

};


//=============================================================================
// End of Include File:
//=============================================================================

#endif