set_e.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    set_e.h
// Purpose:     Set of tuples (binding pattern b..b): Using Extendible Hashing
// 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) 2016-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_E_INCLUDED
#define SET_E_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 PAGE_INCLUDED
#include "../mem/page.h"
#endif

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

#ifndef RELSIZE_INCLUDED
#include "../rel/relsize.h"
#endif

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


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

//-----------------------------------------------------------------------------
// SET_E_MAXPAGES: Maximal hash table size in memory pages.
//-----------------------------------------------------------------------------

// static const int SET_E_MAXPAGES = 1024;

        // Since the hash table size is doubled when necessary,
        // SET_E_MAXPAGES should be a power of 2
        // (assuming that a memory page contains a power of 2 of pointers).
        // For 4 KB pages and 64 bit pointers, one page contains 512 pointers,
        // so the total size of the hash table is SET_E_MAXPAGES * 512.

        // The number of memory pages used for buckets is unlimited.
        // If unavoidable, overflow buckets are linked to a bucket.
        // So there is no hard limit on the number of entries in the hash table
        // (but the performance decreases, of course).

//-----------------------------------------------------------------------------
// SET_E_BUCKETSIZE: Number of entries that fit into one bucket.
//-----------------------------------------------------------------------------

static const int SET_E_BUCKETSIZE = 16;

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

static const long SET_E_MAGIC = 0x5354450AL;    // 'STE\n'


//=============================================================================
// Private Class for the Buckets in the Hash Table:
//=============================================================================


template<class T> class set_e_bucket_c {
        public:
                int NumElems;
                int LocalBits;
                set_e_bucket_c<T> *Overflow;
                T Elems[SET_E_BUCKETSIZE];
};

#define SET_E_BUCKET_T          set_e_bucket_c<T>*
#define SET_E_BUCKET_NULL       (static_cast<set_e_bucket_c<T> *>(0))
#define SET_E_BUCKET_L0_NULL    (static_cast<set_e_bucket_c<T> *>(0))
#define SET_E_BUCKET_L1_NULL    (static_cast<set_e_bucket_c<T> **>(0))
#define SET_E_BUCKET_L2_NULL    (static_cast<set_e_bucket_c<T> ***>(0))

// The following page sizes on different levels must be a power of 2.
// With a normal value for VER_PAGESIZE like 4KB or 8KB
// and a normal pointer size like 32 Bit or 64 Bit the following will work.
// In unusual cases, one must explizitly select a page size that is a power
// of 2, such that the pointers fit into a page of VER_PAGESIZE bytes.
// I.e., some memory will be unused in this case.

#define SET_E_PAGESIZE_L0       PAGE_SIZE(set_e_bucket_c<T> *)
#define SET_E_PAGESIZE_L1       PAGE_SIZE(set_e_bucket_c<T> **)
#define SET_E_PAGESIZE_L2       PAGE_SIZE(set_e_bucket_c<T> ***)

//=============================================================================
// Class Template for Sets (for Duplicate Check):
//=============================================================================

template<class T> class set_e_c: public rel_c {
        public:

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

        // Constructor:
        set_e_c(str_t set_e_name);

        // Destructor:
        ~set_e_c();

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

        private:

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


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

        public:

//-----------------------------------------------------------------------------
// insert: Insert an element into the set (returns true if successful).
//-----------------------------------------------------------------------------

        // This method returns true if the element was not already in the set
        // and was successfully inserted (i.e. if it is not a duplicate).
        // It returns false if the element was already in the set (duplicate).
        // It also returns false if it was impossible to insert the element
        // because there was not enough memory.
        // By pretending that it was a duplicate, recursion at least comes
        // to an end and the program terminates.
        // One should check the method mem_err() from time to time
        // (at least at the end) to see whether this problem occurred
        // or the result is reliable.
        // A memory error is also logged in the class err_c.
        // So even if one does not check mem_err() for every set object,
        // one will notice the error if one at least checks the global error
        // log or has enabled output of error messages.

        bool insert(T elem);


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

        bool contains(T elem) const {

                // Check this object:
                CHECK_VALID("set_e_c::contains");

                // Search in hash table. First compute hash function:
                int hash_val = elem.hash();
                CHECK(hash_val >= 0, "set_e_c::contains: hash_val is negative");
                hash_val &= BitMask;

                // Get hash table entry:
                // Note: This is basically the same code as below in function
                // hash_entry(). However, the const qualifier for contains
                // makes it impossible to call this function.

                SET_E_BUCKET_T bucket;
                // The following code sets bucket the the hash table entry:
                switch(Level) {
                case 0:
                        CHECK(hash_val < SET_E_PAGESIZE_L0,
                                "set_e_c::contains: hash_val invalid (L0)");
                        bucket = HashTab.Level0[hash_val];
                        break;

                case 1:
                        CHECK(hash_val < SET_E_PAGESIZE_L1 * SET_E_PAGESIZE_L0,
                                "set_e_c::contains: hash_val invalid (L1)");
                        {
                        SET_E_BUCKET_T *page =
                                HashTab.Level1[hash_val / SET_E_PAGESIZE_L0];
                        bucket = page[hash_val % SET_E_PAGESIZE_L0];
                        }
                        break;

                case 2:
                        CHECK(hash_val < SET_E_PAGESIZE_L2 * SET_E_PAGESIZE_L1 *
                                        SET_E_PAGESIZE_L0,
                                "set_e_c::contains: hash_val invalid (L2)");
                        {
                        int index2 = hash_val /
                                        (SET_E_PAGESIZE_L1 * SET_E_PAGESIZE_L0);
                        int index1 = hash_val %
                                        (SET_E_PAGESIZE_L1 * SET_E_PAGESIZE_L0);
                        int index0 = index1 % SET_E_PAGESIZE_L0;
                        index1 = index1 / SET_E_PAGESIZE_L0;
                        SET_E_BUCKET_T **page_level1 = HashTab.Level2[index2];
                        SET_E_BUCKET_T *page_level0 = page_level1[index1];
                        bucket = page_level0[index0];
                        }
                        break;

                default:
                        CHECK_IMPOSSIBLE("set_e_c::contains: illegal level");
                        return false;
                }

                // Now search the linked list of buckets in that entry:
                for(; bucket != SET_E_BUCKET_NULL; bucket = bucket->Overflow) {
                        T *elem_ptr = bucket->Elems;
                        for(int i = 0; i < bucket->NumElems; i++)
                                if(*elem_ptr++ == elem)
                                        return true;
                }
                return false;
        }

//-----------------------------------------------------------------------------
// hash_size: Size of the hash table.
//-----------------------------------------------------------------------------

        int hash_size() const {
                CHECK_VALID("set_e_c::hash_size");
                return HashSize;
        }

//-----------------------------------------------------------------------------
// num_buckets: Number of distinct buckets that are used (includes overflow).
//-----------------------------------------------------------------------------

        int num_buckets() const {
                CHECK_VALID("set_e_c::num_buckets");
                return NumBuckets;
        }

//-----------------------------------------------------------------------------
// num_overflow: Number of overflow buckets that are used.
//-----------------------------------------------------------------------------

        int num_overflow() const {
                CHECK_VALID("set_e_c::num_overflow");
                return NumOverflow;
        }

//-----------------------------------------------------------------------------
// size_value: Values of data-structure specific size measures.
//-----------------------------------------------------------------------------

        int size_value(relsize_t relsize) const {
                CHECK_VALID("set_e_c::size_value");
                CHECK(relsize_valid(relsize),
                                "set_e_c::size_value: invalid size measure");

                // Return value of selected size measure:
                switch(relsize) {
                        case RELSIZE_OBJ_SIZE:
                                return static_cast<int>(sizeof(set_e_c<T>));
                        case RELSIZE_HASHTAB_SIZE:
                                return HashSize;
                        case RELSIZE_BUCKET_SIZE:
                                return SET_E_BUCKETSIZE;
                        case RELSIZE_BUCKET_BYTES:
                                return static_cast<int>(
                                                sizeof(set_e_bucket_c<T>));
                        case RELSIZE_TOTAL_BUCKETS:
                                return NumBuckets;
                        case RELSIZE_OVERFLOW_BUCKETS:
                                return NumOverflow;
                        default:
                                return -1;
                }
        }

//=============================================================================
// 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_E_MAGIC".
#endif

#if     VER_DUMP
        private:
        // Auxiliary Function to display bucket data in a data structure dump:
        void dump_bucket(int i, SET_E_BUCKET_T bucket) const;

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


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

        private:

        // Hash table size (in number of bits used):
        int GlobalBits;

        // Corresponding bit mask for filtering part of hash value used:
        int BitMask;

        // Hash table size (total number of entries):
        int HashSize;

        // Hash table size (entries in the HashTab array, top level):
        int HashTopSize;

        // Number of distinct buckets in hash table (includes overflow ones):
        int NumBuckets;

        // Number of overflow buckets:
        int NumOverflow;

        // Current Memory Page for Storing Bucket Objects:
        page_t MemPage;

        // Pointer to next free place in current memory page:
        set_e_bucket_c<T> *MemPtr;

        // Number of free places in current page:
        int MemFree;

        // Current indirection level of array HashTab (0, 1, 2):
        int Level;

        // Hash table:
        union {
                SET_E_BUCKET_T    Level0[SET_E_PAGESIZE_L0];
                SET_E_BUCKET_T *  Level1[SET_E_PAGESIZE_L1];
                SET_E_BUCKET_T ** Level2[SET_E_PAGESIZE_L2];
        } HashTab;


//=============================================================================
// Auxiliary Functions:
//=============================================================================

        private:

        //---------------------------------------------------------------------
        // Get new hashtable bucket:
        //---------------------------------------------------------------------

        inline SET_E_BUCKET_T get_new_bucket(int bits)
        {
                // Get new memory page if current page has not enough space:
                if(MemFree <= 0) {
                        // Allocate memory page, handle failure:
                        page_t page = MemPool.alloc_page();
                        if(page == PAGE_NULL) {
                                MemErr = true;
                                return SET_E_BUCKET_NULL;
                        }

                        // Make new page available:
                        MemPage = page;
                        MemPtr  = reinterpret_cast<SET_E_BUCKET_T>(MemPage);
                        MemFree = PAGE_SIZE(set_e_bucket_c<T>);
                }

                // Cut new hashtable bucket from memory page:
                CHECK(MemFree > 0, "set_e_c::get_new_bucket: Page too small");
                SET_E_BUCKET_T bucket = MemPtr++;
                MemFree--;

                // Increase number of buckets used (for statistics):
                NumBuckets++;

                // Initialize and return new bucket:
                bucket->NumElems = 0;
                bucket->LocalBits = bits;
                bucket->Overflow = SET_E_BUCKET_NULL;
                return bucket;
        }


        //---------------------------------------------------------------------
        // Get a pointer to the i-th entry of the hash table.
        //---------------------------------------------------------------------

        //inline SET_E_BUCKET_T const * hashtab_entry(int i) const {
        inline SET_E_BUCKET_T * hashtab_entry(int i) {

                // Check this object:
                CHECK_VALID("set_e_c::hashtab_entry");

                // CHECK parameter:
                CHECK(i >= 0, "set_e_c::hashtab_entry: i is negative");
                CHECK(i < HashSize,
                                "set_e_c::hashtab_entry: i is too large");

                // Get hash table entry:
                switch(Level) {
                case 0:
                        CHECK(i < SET_E_PAGESIZE_L0,
                                "set_e_c::hashtab_entry: i invalid (L0)");
                        return &(HashTab.Level0[i]);
                case 1:
                        CHECK(i < SET_E_PAGESIZE_L1 * SET_E_PAGESIZE_L0,
                                "set_e_c::hashtab_entry: i invalid (L1)");
                        {
                        SET_E_BUCKET_T *page =
                                HashTab.Level1[i / SET_E_PAGESIZE_L0];
                        return page + (i % SET_E_PAGESIZE_L0);
                        }
                case 2:
                        CHECK(i < SET_E_PAGESIZE_L2 * SET_E_PAGESIZE_L1 *
                                        SET_E_PAGESIZE_L0,
                                "set_e_c::hashtab_entry: i invalid (L2)");
                        {
                        int index2 = i / (SET_E_PAGESIZE_L1*SET_E_PAGESIZE_L0);
                        int index1 = i % (SET_E_PAGESIZE_L1*SET_E_PAGESIZE_L0);
                        int index0 = index1 % SET_E_PAGESIZE_L0;
                        index1 = index1 / SET_E_PAGESIZE_L0;
                        SET_E_BUCKET_T **indirect_page = HashTab.Level2[index2];
                        SET_E_BUCKET_T *page = indirect_page[index1];
                        return page + index0;
                        }
                default:
                        CHECK_IMPOSSIBLE(
                                "set_e_c::hashtab_entry: illegal level");
                        return 0;
                }
        }

        //---------------------------------------------------------------------
        // Set a hash table entry:
        //---------------------------------------------------------------------

        inline void set_hashtab_entry(int i, SET_E_BUCKET_T bucket)
        {
                // CHECK parameter:
                CHECK(i >= 0, "set_e_c::set_hashtab_entry: i is negative");
                CHECK(i < HashSize,
                                "set_e_c::set_hashtab_entry: i is too large");

                // Determine pointer:
                SET_E_BUCKET_T *entry = hashtab_entry(i);

                // Set entry:
                *entry = bucket;
        }


        //---------------------------------------------------------------------
        // Copy Level 0 page:
        //---------------------------------------------------------------------

        inline SET_E_BUCKET_T *copy_page0(SET_E_BUCKET_T *input_page);

        //---------------------------------------------------------------------
        // Copy Level 1 page including all linked level 0 pages:
        //---------------------------------------------------------------------

        inline SET_E_BUCKET_T **copy_page1(SET_E_BUCKET_T **input_page);

        //---------------------------------------------------------------------
        // Double Hash Table:
        //---------------------------------------------------------------------

        inline bool double_table();

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

};


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

#endif