strtab.h

Go to the documentation of this file.

// ============================================================================
// Project:     Deductive Database
// Filename:    strtab.h
// Purpose:     String Table
// 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 STRTAB_INCLUDED
#define STRTAB_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 FLEXARR_INCLUDED
#include "../bds/flexarr.h"
#endif

#ifndef STRMEM_INCLUDED
#include "../dom/strmem.h"
#endif


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

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

static const long STRTAB_MAGIC = 0x5354420AL;   // 'STB\n'


//=============================================================================
// Private Types:
//=============================================================================

//-----------------------------------------------------------------------------
// strtab_node_c: Superclass of Nodes.
//-----------------------------------------------------------------------------

class strtab_node_c;

//-----------------------------------------------------------------------------
// strtab_leaf_c: Leaf node.
//-----------------------------------------------------------------------------

class strtab_leaf_c;

//-----------------------------------------------------------------------------
// strtab_small_c: Small branch node.
//-----------------------------------------------------------------------------

class strtab_small_c;

//-----------------------------------------------------------------------------
// strtab_full_s: Full branch node.
//-----------------------------------------------------------------------------

class strtab_full_c;

//=============================================================================
// Class for String Table (Saves Strings Without Duplicates, Assigns ID):
//=============================================================================

class strtab_c {
        public:


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

        // Constructor:
        strtab_c(str_t tab_name);

        // Destructor:
        ~strtab_c();

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

        // put: Insert a string into this string memory pool, return ID.
        int put(str_t start, str_t end);

        // put: As above, but with '\0'-terminated string:
        int put(str_t str) {
                CHECK_VALID("strtab_c::put(str_t)");
                CHECK(str != STR_NULL, "strtab_c::put(str_t): str is null");
                return put(str, str + str_len(str));
        }

        // get: Get a string for a given ID.
        str_t get(int id) const {
                return StrArr.get(id);
        }

        // Return name of this string table:
        str_t name() const {
                return MemPool.name();
        }

        // Return number of strings in this table:
        int num_strings() const {
                return StrMem.num_strings();
        }

        // Return number of leaf nodes:
        int num_leaf_nodes() const {
                return NumLeafNodes;
        }

        // Return number of small nodes:
        int num_small_nodes() const {
                return NumSmallNodes;
        }

        // Return number of full nodes:
        int num_full_nodes() const {
                return NumFullNodes;
        }

        // Return number of memory pages used for storing nodes:
        int num_node_pages() const {
                return NumPages;
        }

        // Return number of memory pages used for storing strings:
        int num_str_pages() const {
                return StrMem.num_pages();
        }

        // Return number of memory pages used for the id->str array:
        int num_array_pages() const {
                return StrArr.num_pages();
        }

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

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

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

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

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

        private:

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

//-----------------------------------------------------------------------------
// Auxiliary Methods:
//-----------------------------------------------------------------------------

        private:

        // make_leaf: Construct new leaf node.
        strtab_leaf_c *make_leaf(str_t str, int id);

        // make_small: Construct small node with a single entry.
        strtab_small_c* make_small(char c);

        // make_full: Construct full node with data of small node (upgrade).
        strtab_full_c* make_full(strtab_small_c* small);

        // dump_node: Recursive method to show search tree data structure.
#if     VER_DUMP
        int dump_node(int depth, int ch, strtab_node_c *node,
                                        int parent_no, int node_no) const;
#endif

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

        private:

        // Memory Pool for Allocating Storage Pages:
        mpool_c MemPool;

        // String Memory (for saving/copying strings to own memory):
        strmem_c StrMem;

        // Flexible Array of Pointers to Strings in StrMem:
        flexarr_c<str_t> StrArr;

        // Current Page for Storing Index Tree Nodes:
        page_t MemPage;

        // Pointer to next free position in current page:
        page_u_t FreePtr;

        // Number of free memory units in current page:
        int FreeUnits;

        // Free list for small nodes (which have been upgraded to full nodes):
        strtab_small_c *FreeSmallNodes;

        // Number of memory pages used for storing tree nodes:
        int NumPages;

        // Root of the radix tree for string search:
        strtab_node_c *Root;

        // Node numbers of different types:
        int NumLeafNodes;
        int NumSmallNodes;
        int NumFullNodes;

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

};

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

typedef strtab_c *strtab_t;

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

#define STRTAB_NULL (static_cast<strtab_t>(0))

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

#endif