set_tt.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    set_tt.h
// Purpose:     Set with two columns with range [0..1023] (ten bits)
// 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 SET_TT_INCLUDED
#define SET_TT_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 MPOOL_INCLUDED
#include "../mem/mpool.h"
#endif

#ifndef REL_INCLUDED
#include "../rel/rel.h"
#endif


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

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

static const long SET_TT_MAGIC = 0x5354540AL;   // 'STT\n'

//-----------------------------------------------------------------------------
// SET_TT_C1_SIZE: Number of possible values in column 1 (array size):
//-----------------------------------------------------------------------------

static const int SET_TT_C1_SIZE = 1024;

//-----------------------------------------------------------------------------
// SET_TT_C2_SIZE: Number of possible values in column 2 (bitmap size):
//-----------------------------------------------------------------------------

static const int SET_TT_C2_SIZE = 1024;


//=============================================================================
// Local Types:
//=============================================================================

//-----------------------------------------------------------------------------
// SET_TT_BITMAP_SIZE: Size of a bitmap for column 2 in "unsigned int" units:
//-----------------------------------------------------------------------------

#define SET_TT_BITMAP_SIZE \
        ((SET_TT_C2_SIZE + (VER_UINT_BITS-1)) / VER_UINT_BITS)

//-----------------------------------------------------------------------------
// Bitmap used for second column:
//-----------------------------------------------------------------------------

class set_tt_bitmap_c {
        private:
                unsigned int BitMap[SET_TT_BITMAP_SIZE];
        friend class set_tt_c;
};

//-----------------------------------------------------------------------------
// Pointer type for bitmaps:
//-----------------------------------------------------------------------------

typedef set_tt_bitmap_c *set_tt_bitmap_t;

//-----------------------------------------------------------------------------
// Null pointer for bitmaps:
//-----------------------------------------------------------------------------

#define SET_TT_BITMAP_NULL (static_cast<set_tt_bitmap_t>(0))


//=============================================================================
// Class for Set with two Integer Columns with Range [0..1023] (ten bits):
//=============================================================================

// Non-negative integers are used as ID for strings and for atoms.
// This version has an index on the first column.
// It is assumed that the first column is dense, so we can basically use
// an array as index. However, it is also assumed that a fixed-size array
// is not sufficient, so the relation can be quite big or of an unknown size.

class set_tt_c : public rel_c {
        public:

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

        // Constructor:
        set_tt_c(str_t rel_name);

        // Destructor:
        ~set_tt_c();

//-----------------------------------------------------------------------------
// (Object) Methods:
//-----------------------------------------------------------------------------

        // insert: Insert tuple into relation.
        bool insert(int c1, int c2);

//-----------------------------------------------------------------------------
// contains: Check whether an element is contained in the set.
//-----------------------------------------------------------------------------

        inline bool contains(int c1, int c2) const {
                // Check this object:
                CHECK_VALID("set_tt_c::contains");

                // Check parameters:
                CHECK(c1 >= 0, "set_tt_c::contains: c1 is negative");
                CHECK(c2 >= 0, "set_tt_c::contains: c2 is negative");
                CHECK(c1 < SET_TT_C1_SIZE,
                                "set_tt_c::contains: c1 is too large");
                CHECK(c2 < SET_TT_C2_SIZE,
                                "set_tt_c::contains: c2 is too large");

                // Check whether bitmap for c1 exists.
                // If not, there is no such row:
                set_tt_bitmap_t bitmap = Arr[c1];
                if(bitmap == SET_TT_BITMAP_NULL)
                        return false;

                // Search bit for c2 in bitmap:
                int index  = c2 / VER_UINT_BITS;
                int bit_no = c2 % VER_UINT_BITS;
                unsigned int *ptr = bitmap->BitMap + index;
                unsigned int  mask = 1 << bit_no;
                return (*ptr & mask) != 0;
        }

//-----------------------------------------------------------------------------
// Debugging Support:
//-----------------------------------------------------------------------------

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

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

#if     VER_DUMP
        public:
        // Display data structure:
        void dump(str_t headline = STR_NULL) const;
#endif

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

        private:

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

//-----------------------------------------------------------------------------
// Private Object Members:
//-----------------------------------------------------------------------------

        private:

        // Array of pointers to bitmaps:
        set_tt_bitmap_t Arr[SET_TT_C1_SIZE];

        // Current Memory Page for Storing Bitmaps:
        page_t MemPage;

        // Pointer to next free place in current memory page:
        set_tt_bitmap_t MemPtr;

        // Number of free places in current page (in set_tt_bitmap_c units):
        int MemFree;


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

};

//-----------------------------------------------------------------------------
// Define pointer type:
//-----------------------------------------------------------------------------

typedef set_tt_c *set_tt_t;

//-----------------------------------------------------------------------------
// Define null pointer:
//-----------------------------------------------------------------------------

#define SET_TT_NULL (static_cast<set_tt_t>(0))

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

#endif