set.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    set.h
// Purpose:     Set of objects/tuples - relation with binding pattern b..b
// 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_INCLUDED
#define SET_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_MAXPAGES: Maximal hash table size in memory pages.
//-----------------------------------------------------------------------------

static const int SET_MAXPAGES = 1024;

        // Since the hash table size is doubled each time more than 75%
        // of the entries are used, SET_MAXPAGES must be a power of 2.

        // Additional pages will be used for entries in the hash table.
        // The number of memory pages used for this purpose is unlimited.

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

static const long SET_MAGIC = 0x5345540AL;      // 'SET\n'


//=============================================================================
// Forward declarations:
//=============================================================================

// Private class for nodes in the hash table chains:
// template<class T> class set_node_c;

//=============================================================================
// Private Class for the Nodes in the Hash Table Chains:
//=============================================================================

template<class T> class set_node_c {
        public:
                T Elem;
                set_node_c<T> *Next;
};

#define SET_NODE_T      set_node_c<T>*
#define SET_NODE_NULL   (static_cast<set_node_c<T> *>(0))


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

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

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

        // Constructor:
        set_c(str_t set_name);

        // Destructor:
        ~set_c();

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

        private:

        set_c(const set_c& obj);                // Not implemented
        set_c& operator=(const set_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_c::contains");

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

                // Get start of linked list:
                SET_NODE_T *hashtab_entry =
                                HashTab[hash_val / PAGE_SIZE(SET_NODE_T)];
                hashtab_entry += (hash_val % PAGE_SIZE(SET_NODE_T));

                // Now search the linked list of atoms in that entry:
                SET_NODE_T node;
                for(node = *hashtab_entry; node != SET_NODE_NULL;
                                                        node = node->Next) {
                        if(node->Elem == elem)
                                return true;
                }
                return false;
        }

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

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

//-----------------------------------------------------------------------------
// entries_used: Number of hash table entries that are used (not NULL).
//-----------------------------------------------------------------------------

        int entries_used() const {
                CHECK_VALID("set_c::entries_used");
                return EntriesUsed;
        }

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

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

                // Return value of selected size measure:
                switch(relsize) {
                        case RELSIZE_OBJ_SIZE:
                                return static_cast<int>(sizeof(set_c<T>));
                        case RELSIZE_HASHTAB_SIZE:
                                return HashSize;
                        case RELSIZE_ENTRIES_USED:
                                return EntriesUsed;
                        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_MAGIC".
#endif

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


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

        private:

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

        // Hash table size (in memory pages):
        int HashPages;

        // Number of used entries in hash table:
        int EntriesUsed;

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

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

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

        // Hash table:
        set_node_c<T> **HashTab[SET_MAXPAGES];

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

};


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

#endif