flexarr.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    flexarr.h
// Purpose:     Flexible array / List with index access (Class Template)
// 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 FLEXARR_INCLUDED
#define FLEXARR_INCLUDED

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

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

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

#ifndef ERR_INCLUDED
#include "../base/err.h"
#endif

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

#ifndef PAGE_INCLUDED
#include "../mem/page.h"
#endif

#ifndef MPOOL_INCLUDED
#include "../mem/mpool.h"
#endif


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

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

static const long FLEXARR_MAGIC = 0x464C450AL;  // 'FLE\n'

//-----------------------------------------------------------------------------
// Null Pointers:
//-----------------------------------------------------------------------------

#define FLEXARR_LEAF_NULL (static_cast<T*>(PAGE_NULL))
#define FLEXARR_MID_NULL (static_cast<T**>(PAGE_NULL))
#define FLEXARR_TOP_NULL (static_cast<T***>(PAGE_NULL))


//=============================================================================
//=============================================================================

template<class T> class flexarr_c {
        public:

//-----------------------------------------------------------------------------
// Constructor, Destructor:
//-----------------------------------------------------------------------------

        // Constructor:
        flexarr_c(mpool_t mem_pool)
        {
                // Check parameter:
                CHECK_PAR(mem_pool, "flexarr_c::constructor");

                // Initialize attributes:
                Length        = 0;
                Height        = 0;
                CurrLeafNode  = FLEXARR_LEAF_NULL;
                CurrMidNode   = FLEXARR_MID_NULL;
                CurrTopNode   = FLEXARR_TOP_NULL;
                CurrLeafIndex = 0;
                CurrMidIndex  = 0;
                CurrTopIndex  = 0;
                MemPool       = mem_pool;
                NumPages      = 0;
                UnusedPage1   = PAGE_NULL;
                UnusedPage2   = PAGE_NULL;

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

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

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

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

        private:

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

//=============================================================================
// Auxiliary Methods for Memory Page Management:
//=============================================================================

        private:

        // This handles the following problem:
        // When a memory page allocation fails,
        // we want to restore the state before the operation.
        // However, append might have to allocate three memory pages,
        // and if the last allocation fails, there are two unused memory pages.
        // This is not a real memory leak, because the pages are stored
        // in the memory pool, and the memory pool will free them
        // when it is destroyed.
        //
        // It is also unlikely that a memory page allocation fails,
        // and later it works again (in which case every append might
        // allocate two unused pages in the worst case).
        //
        // However, to be very correct, we remember the unused pages
        // in this object, and use them in the next memory allocation,
        // before we allocate new pages from the memory pool.
        // In this way, there can never be more than two unused pages
        // in this object.
        //
        // Of course, if this object should be destroyed, it is important
        // that the memory pool is destroyed, too.
        // Because this object is used as part of a string table,
        // which has a common memory pool for all its parts, this works
        // (all parts are destroyed together).
        //
        // If one uses the flexible array in other contexts, one must make
        // sure that the memory pool is destroyed whenever this object is
        // destroyed. Otherwise there will be a memory leak.

//-----------------------------------------------------------------------------
// alloc_page: Get a memory page.
//-----------------------------------------------------------------------------

        inline page_t alloc_page() {
                if(UnusedPage1 == PAGE_NULL)
                        return MemPool->alloc_page();
                page_t page = UnusedPage1;
                UnusedPage1 = UnusedPage2;
                UnusedPage2 = PAGE_NULL;
                return page;
        }

//-----------------------------------------------------------------------------
// free_page: De-allocate a memory page.
//-----------------------------------------------------------------------------

        inline void free_page(page_t page) {
                CHECK(page != PAGE_NULL, "flexarr_c::free_page: page is NULL");
                if(UnusedPage1 == PAGE_NULL)
                        UnusedPage1 = page;
                else {
                        CHECK(UnusedPage2 == PAGE_NULL,
                                "flexarr_c::free_page: too many pages");
                        UnusedPage2 = page;
                }
        }

//=============================================================================
// (Object) Methods:
//=============================================================================

        public:

//-----------------------------------------------------------------------------
// append: Append new element to the array (at the end). Returns index.
//-----------------------------------------------------------------------------

        inline int append(T elem) {
                page_t page;

                // Ensure that object is valid:
                CHECK_VALID("flexarr_c::append");

                // Most common case: Add elem to current leaf node:
                if(CurrLeafIndex > 0) {
                        CurrLeafNode[--CurrLeafIndex] = elem;
                        return Length++;
                }

                // Allocate first leaf:
                if(CurrLeafNode == FLEXARR_LEAF_NULL) {  // i.e. Height == 0
                        page = alloc_page();
                        if(page == PAGE_NULL)
                                return -1;
                        NumPages++;
                        CurrLeafNode = reinterpret_cast<T*>(page);
                        CurrLeafIndex = PAGE_SIZE(T) - 1;
                        CHECK(CurrLeafIndex >= 0,
                                "flexarr_c::append: T too large");
                        CurrLeafNode[CurrLeafIndex] = elem;
                        Height = 1;
                        Length = 1;  // Length was 0,
                        return 0;    // could also write Length++ here.
                }

                // There is a leaf node, but it is full:
                CHECK(CurrLeafNode != FLEXARR_LEAF_NULL,
                        "flexarr_c::append: LeafNode is NULL");
                CHECK(CurrLeafIndex == 0,
                        "flexarr_c::append: LeafIndex not 0");

                // Remember old leaf node in case there is no mid node:
                T* old_leaf_node = CurrLeafNode;

                // Allocate new leaf node:
                page = alloc_page();
                if(page == PAGE_NULL)
                        return -1;
                NumPages++;
                CurrLeafNode = reinterpret_cast<T*>(page);
                CurrLeafIndex = PAGE_SIZE(T) - 1;
                CHECK(CurrLeafIndex >= 0,
                        "flexarr_c::append: T too large (2)");
                CurrLeafNode[CurrLeafIndex] = elem;

                // Now we must enter the new leaf node to the mid branch level
                // In case there was no mid branch level before, both nodes,
                // the old leaf node and the new leaf node must be entered
                // to the first mid level branch node.

                // Construct first mid level branch node:
                if(CurrMidNode == FLEXARR_MID_NULL) {
                        page = alloc_page();
                        if(page == PAGE_NULL) {
                                // Restore state before failed append:
                                free_page(CurrLeafNode);
                                CurrLeafNode = old_leaf_node;
                                CurrLeafIndex = 0;
                                return -1;
                        }
                        NumPages++;
                        CurrMidNode = reinterpret_cast<T**>(page);
                        CurrMidIndex = PAGE_SIZE(T*) - 1;
                        CHECK(CurrMidIndex > 0,
                                "flexarr_c::append: T* too large");
                        CurrMidNode[CurrMidIndex] = old_leaf_node;
                        CurrMidNode[--CurrMidIndex] = CurrLeafNode;
                        Height = 2;
                        return Length++;
                }

                // There is a mid level branch node and it is not yet full:
                else if(CurrMidIndex > 0) {
                        CurrMidNode[--CurrMidIndex] = CurrLeafNode;
                        return Length++;
                }

                // There is a mid level branch node, but it is full:
                CHECK(CurrMidNode != FLEXARR_MID_NULL,
                        "flexarr_c::append: MidNode is NULL");
                CHECK(CurrMidIndex == 0,
                        "flexarr_c::append: MidIndex not 0");

                // Construct additional (not first) mid level branch node:
                page = alloc_page();
                if(page == PAGE_NULL) {
                        // Restore state before failed append:
                        free_page(CurrLeafNode);
                        CurrLeafNode = old_leaf_node;
                        CurrLeafIndex = 0;
                        return -1;
                }
                NumPages++;
                T** old_mid_node = CurrMidNode;
                CurrMidNode = reinterpret_cast<T**>(page);
                CurrMidIndex = PAGE_SIZE(T*) - 1;
                CHECK(CurrMidIndex >= 0,
                        "flexarr_c::append: T* too large (2)");
                CurrMidNode[CurrMidIndex] = CurrLeafNode;

                // Now we must enter the new mid node to top level
                // (because it is not the first / only one).
                // Simple case: There is already a top node.
                if(CurrTopNode != FLEXARR_TOP_NULL) {
                        // If it has no space, we would need another level,
                        // which is not implemented:
                        if(CurrTopIndex <= 0) {
                                free_page(CurrLeafNode);
                                CurrLeafNode = old_leaf_node;
                                CurrLeafIndex = 0;
                                free_page(CurrMidNode);
                                CurrMidNode = old_mid_node;
                                CurrMidIndex = 0;
                                err_c::flexarr_capacity_limit(MemPool->name(),
                                                                Length);
                                return -1;
                        }
                        CurrTopNode[--CurrTopIndex] = CurrMidNode;
                        return Length++;
                }

                // Finally handle the case that there is no top level node yet.
                // Construct one (there will always be only one):
                CHECK(CurrTopNode == FLEXARR_TOP_NULL,
                                "flexarr_c::append: CurrTopNode is not null");
                page = alloc_page();
                if(page == PAGE_NULL) {
                        // Restore state before failed append:
                        free_page(CurrLeafNode);
                        CurrLeafNode = old_leaf_node;
                        CurrLeafIndex = 0;
                        free_page(CurrMidNode);
                        CurrMidNode = old_mid_node;
                        CurrMidIndex = 0;
                        return -1;
                }
                NumPages++;
                CurrTopNode = reinterpret_cast<T***>(page);
                CurrTopIndex = PAGE_SIZE(T**) - 1;
                CHECK(CurrTopIndex > 0,
                                "flexarr_c::append: T** too large");
                CurrTopNode[CurrTopIndex] = old_mid_node;
                CurrTopNode[--CurrTopIndex] = CurrMidNode;
                Height = 3;
                return Length++;
        }

//-----------------------------------------------------------------------------
// ptr: Get pointer to element at a given index.
//-----------------------------------------------------------------------------

        inline T* ptr(int i) const {
                // Ensure that object is valid:
                CHECK_VALID("flexarr_c::ptr");

                // Ensure that parameter (index) is valid:
                CHECK(i >= 0, "flexarr_c::ptr: Index is negative");
                CHECK(i < Length, "flexarr_c::ptr: Index is too large");

                // Height 1: There is only a single leaf node:
                if(Height == 1) {
                        // Actual indexes start at end of page:
                        int index = (PAGE_SIZE(T) - 1) - i;

                        // Get data value from leaf node (Root):
                        CHECK(index >= 0, "flexarr_c::ptr: H1 Index<0");
                        CHECK(index >= CurrLeafIndex,
                                        "flexarr_c::ptr: H1 Index too small");
                        CHECK(CurrLeafNode != FLEXARR_LEAF_NULL,
                                        "flexarr_c::ptr: H1 LeafNode is null");
                        return &(CurrLeafNode[index]);
                }

                // Height 2: Mid Level Node is Root
                if(Height == 2) {
                        // Split index into parts for different tree levels:
                        int mid_index = i / PAGE_SIZE(T);
                        int leaf_index = i % PAGE_SIZE(T);

                        // Actual indexes start at end of page:
                        leaf_index = (PAGE_SIZE(T) - 1) - leaf_index;
                        mid_index = (PAGE_SIZE(T*) - 1) - mid_index;

                        // Get leaf node from CurrMidNode (Root):
                        CHECK(mid_index >= 0, "flexarr_c::ptr: H2 Index<0");
                        CHECK(mid_index >= CurrMidIndex,
                                        "flexarr_c::ptr: H2 Index too small");
                        CHECK(CurrMidNode != FLEXARR_MID_NULL,
                                        "flexarr_c::ptr: H2 MidNode is null");
                        T* leaf_node = CurrMidNode[mid_index];

                        // Get data value from leaf node:
                        CHECK(leaf_index >= 0,
                                        "flexarr_c::ptr: H2 LeafIndex<0");
                        CHECK(leaf_node != CurrLeafNode ||
                                        leaf_index >= CurrLeafIndex,
                                        "flexarr_c::ptr: H2 LeafI too small");
                        CHECK(leaf_node != FLEXARR_LEAF_NULL,
                                        "flexarr_c::ptr: H2 leaf_node null");
                        return &(leaf_node[leaf_index]);
                }

                // Height 3:
                if(Height == 3) {
                        // Split index into parts for different tree levels:
                        int mid_index = i / PAGE_SIZE(T);
                        int leaf_index = i % PAGE_SIZE(T);
                        int top_index = mid_index / PAGE_SIZE(T*);
                        mid_index = mid_index % PAGE_SIZE(T*);

                        // Actual indexes start at end of page:
                        leaf_index = (PAGE_SIZE(T) - 1) - leaf_index;
                        mid_index = (PAGE_SIZE(T*) - 1) - mid_index;
                        top_index = (PAGE_SIZE(T**) - 1) - top_index;

                        // Get mid level node from CurrTopNode (Root):
                        CHECK(top_index >= 0, "flexarr_c::ptr: H3 Index<0");
                        CHECK(top_index >= CurrMidIndex,
                                        "flexarr_c::ptr: H3 Index too small");
                        CHECK(CurrTopNode != FLEXARR_TOP_NULL,
                                        "flexarr_c::ptr: H3 TopNode is null");
                        T** mid_node = CurrTopNode[top_index];

                        // Get leaf node from mid level node:
                        CHECK(mid_index >= 0,
                                        "flexarr_c::ptr: H3 MidIndex<0");
                        CHECK(mid_node != CurrMidNode ||
                                        mid_index >= CurrMidIndex,
                                        "flexarr_c::ptr: H3 MidI too small");
                        CHECK(mid_node != FLEXARR_MID_NULL,
                                        "flexarr_c::ptr: H3 mid_node is null");
                        T* leaf_node = mid_node[mid_index];

                        // Get data value from leaf node:
                        CHECK(leaf_index >= 0,
                                        "flexarr_c::ptr: H3 leaf_index<0");
                        CHECK(leaf_node != CurrLeafNode ||
                                        leaf_index >= CurrLeafIndex,
                                        "flexarr_c::ptr: H3 LeafI too small");
                        CHECK(leaf_node != FLEXARR_LEAF_NULL,
                                        "flexarr_c::ptr: H3 leaf_node null");
                        return &(leaf_node[leaf_index]);
                }

                // Greater Heights are not implemented:
                CHECK_IMPOSSIBLE("flexarr_c::ptr: Invalid Height");
                return 0;
        }

//-----------------------------------------------------------------------------
// get: Get element at a given index.
//-----------------------------------------------------------------------------

        inline T get(int i) const {
                // Ensure that object is valid:
                CHECK_VALID("flexarr_c::get");

                // Ensure that parameter (index) is valid:
                CHECK(i >= 0, "flexarr_c::get: Index is negative");
                CHECK(i < Length, "flexarr_c::get: Index is too large");

                // The real work is done in Method ptr:
                return *(ptr(i));
        }


//-----------------------------------------------------------------------------
// length: Get the current length (number of elements) of this array.
//-----------------------------------------------------------------------------

        int length() const {
                return Length;
        }

//-----------------------------------------------------------------------------
// num_pages: Get the number of pages used for this flexible array.
//-----------------------------------------------------------------------------

        int num_pages() const {
                return NumPages;
        }

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

//-----------------------------------------------------------------------------
// 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 != FLEXARR_MAGIC)
                        return "wrong magic number";

                // Check length and indexes:
                if(Length < 0)
                        return "Length is negative";
                if(CurrLeafIndex < 0)
                        return "CurrLeafIndex is negative";
                if(CurrMidIndex < 0)
                        return "CurrMidIndex is negative";
                if(CurrTopIndex < 0)
                        return "CurrTopIndex is negative";
                if(CurrLeafIndex >= PAGE_SIZE(T))
                        return "CurrLeafIndex too large";
                if(CurrMidIndex >= PAGE_SIZE(T*))
                        return "CurrMidIndex too large";
                if(CurrTopIndex >= PAGE_SIZE(T**))
                        return "CurrTopIndex too large";

                // Check by height:
                switch(Height) {
                        case 0:
                                if(Length != 0)
                                        return "Height 0 - Length != 0";
                                if(CurrLeafNode != FLEXARR_LEAF_NULL)
                                        return "Height 0 - Leaf not null";
                                if(CurrMidNode != FLEXARR_MID_NULL)
                                        return "Height 0 - Mid not null";
                                if(CurrTopNode != FLEXARR_TOP_NULL)
                                        return "Height 0 - Top not null";
                                if(CurrLeafIndex != 0)
                                        return "Height 0 - LeafIndex != 0";
                                if(CurrMidIndex != 0)
                                        return "Height 0 - MidIndex != 0";
                                if(CurrTopIndex != 0)
                                        return "Height 0 - TopIndex != 0";
                                break;
                        case 1:
                                if(Length > PAGE_SIZE(T))
                                        return "Height 1 - Length too large";
                                if(CurrLeafNode == FLEXARR_LEAF_NULL)
                                        return "Height 1 - Leaf is null";
                                if(CurrMidNode != FLEXARR_MID_NULL)
                                        return "Height 1 - Mid not null";
                                if(CurrTopNode != FLEXARR_TOP_NULL)
                                        return "Height 1 - Top not null";
                                if(CurrMidIndex != 0)
                                        return "Height 1 - MidIndex != 0";
                                if(CurrTopIndex != 0)
                                        return "Height 1 - TopIndex != 0";
                                break;
                        case 2:
                                if(Length > PAGE_SIZE(T) * PAGE_SIZE(T*))
                                        return "Height 2 - Length too large";
                                if(CurrLeafNode == FLEXARR_LEAF_NULL)
                                        return "Height 2 - Leaf is null";
                                if(CurrMidNode == FLEXARR_MID_NULL)
                                        return "Height 2 - Mid is null";
                                if(CurrTopNode != FLEXARR_TOP_NULL)
                                        return "Height 2 - Top not null";
                                if(CurrTopIndex != 0)
                                        return "Height 2 - TopIndex != 0";
                                break;
                        case 3:
                                if(Length > PAGE_SIZE(T) * PAGE_SIZE(T*)
                                                * PAGE_SIZE(T**))
                                        return "Height 3 - Length too large";
                                if(CurrLeafNode == FLEXARR_LEAF_NULL)
                                        return "Height 3 - Leaf is null";
                                if(CurrMidNode == FLEXARR_MID_NULL)
                                        return "Height 3 - Mid is null";
                                if(CurrTopNode == FLEXARR_TOP_NULL)
                                        return "Height 3 - Top is null";
                                break;
                        default:
                                return "Invalid height";
                }

                // Ok:
                return STR_NULL;
        }

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

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

#if     VER_DUMP

        public:

void dump(str_t headline = STR_NULL) const
{
        // Headline:
        if(headline == STR_NULL)
                headline = "Flexible Array";
        err_c::dump_begin(headline);

        // Basic information:
        err_c::dump_str("MemPool Name: '");
        err_c::dump_str(MemPool->name());
        err_c::dump_str("'");
        err_c::dump_nl();
        err_c::dump_str("Length:        ");
        err_c::dump_int(Length);
        err_c::dump_nl();
        err_c::dump_str("Height:        ");
        err_c::dump_int(Height);
        err_c::dump_nl();
        err_c::dump_str("NumPages: ");
        err_c::dump_int(NumPages);
        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_str("CurrLeafIndex: ");
        err_c::dump_int(CurrLeafIndex);
        err_c::dump_nl();
        err_c::dump_str("CurrMidIndex:  ");
        err_c::dump_int(CurrMidIndex);
        err_c::dump_nl();
        err_c::dump_str("CurrTopIndex:  ");
        err_c::dump_int(CurrTopIndex);
        err_c::dump_nl();
        err_c::dump_str("CurrLeafNode:  ");
        err_c::dump_ptr(CurrLeafNode);
        err_c::dump_nl();
        err_c::dump_str("CurrMidNode:   ");
        err_c::dump_ptr(CurrMidNode);
        err_c::dump_nl();
        err_c::dump_str("CurrTopNode:   ");
        err_c::dump_ptr(CurrTopNode);
        err_c::dump_nl();
        err_c::dump_nl();

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

#endif


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

        private:

        // Length: Number of elements in the array / list.
        int Length;

        // Height: Height of the radix tree implementing the flexible array.
        int Height;     // Can only be 0 (empty tree), 1 (only leaf), 2, 3.

        // Current/Rightmost Leaf Node
        T *CurrLeafNode;        // If Height == 1, this is the root.

        // CurrMid: Current/Rightmost Branch Node One Level Above Leaves.
        T **CurrMidNode;        // If Height == 2, this is the root.

        // CurrTop: Branch node two Levels Above Leaves
        T ***CurrTopNode;       // Root for Height == 3. Otherwise unused.

        // CurrLeafIndex: Last used index in CurrLeafNode
        int CurrLeafIndex;

        // CurrMidIndex: Last used index in CurrMidNode
        int CurrMidIndex;

        // CurrTopIndex: Last used index in CurrTopNode
        int CurrTopIndex;

        // MemPool: Memory pool from which new nodes are allocated.
        mpool_t MemPool;

        // Unused pages left over from a failed append operation:
        page_t UnusedPage1;
        page_t UnusedPage2;

        // Number of memory pages used:
        int NumPages;

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

};


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

#endif