Map.h

Go to the documentation of this file.

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2012 Evgeniy Andreev (gsomix)
 *
 * Copyright (C) 2012 Evgeniy Andreev (gsomix)
 */

#ifndef _MAP_H_
#define _MAP_H_

#include <shogun/lib/config.h>

#include <shogun/base/SGObject.h>
#include <shogun/lib/common.h>
#include <shogun/lib/Hash.h>
#include <shogun/base/DynArray.h>

#include <cstdio>

#include <shogun/io/SGIO.h>
#include <shogun/lib/Lock.h>


namespace shogun
{

#define IGNORE_IN_CLASSLIST

#define MapNode CMapNode<K, T>

#ifndef DOXYGEN_SHOULD_SKIP_THIS

IGNORE_IN_CLASSLIST template<class K, class T> struct CMapNode
{
    int32_t index;

    bool free;

    K key;

    T data;

    CMapNode *left;

    CMapNode *right;
};
#endif

IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
{
public:
    CMap(int32_t size=41, int32_t reserved=128, bool tracable=true)
    {
        hash_size=size;
        free_index=0;
        num_elements=0;
        use_sg_mallocs=tracable;

        if (use_sg_mallocs)
            hash_array=SG_CALLOC(MapNode*, size);
        else
            hash_array=(CMapNode<K, T>**) calloc(size, sizeof(CMapNode<K, T>*));

        for (int32_t i=0; i<size; i++)
        {
            hash_array[i]=NULL;
        }

        array=new DynArray<CMapNode<K, T>*>(reserved, tracable);
    }

    virtual ~CMap()
    {
        destroy_map();
    }

    virtual const char* get_name() const { return "Map"; }

    int32_t add(const K& key, const T& data)
    {
        int32_t index=hash(key);
        if (chain_search(index, key)==NULL)
        {
            lock.lock();
            int32_t added_index=insert_key(index, key, data);
            num_elements++;
            lock.unlock();

            return added_index;
        }

        return -1;
    }

    bool contains(const K& key)
    {
        int32_t index=hash(key);
        if (chain_search(index, key)!=NULL)
            return true;

        return false;
    }

    void remove(const K& key)
    {
        int32_t index=hash(key);
        CMapNode<K, T>* result=chain_search(index, key);

        if (result!=NULL)
        {
            lock.lock();
            delete_key(index, result);
            num_elements--;
            lock.unlock();
        }
    }

    int32_t index_of(const K& key)
    {
        int32_t index=hash(key);
        CMapNode<K ,T>* result=chain_search(index, key);

        if (result!=NULL)
            return result->index;

        return -1;
    }

    T get_element(const K& key)
    {
        int32_t index=hash(key);
        CMapNode<K, T>* result=chain_search(index, key);

        if (result!=NULL)
            return result->data;
        else
        {
            int32_t added_index=add(key, T());
            result=get_node_ptr(added_index);

            return result->data;
        }
    }

    void set_element(const K& key, const T& data)
    {
        int32_t index=hash(key);
        CMapNode<K, T>* result=chain_search(index, key);

        lock.lock();

        if (result!=NULL)
            result->data=data;
        else
            add(key, data);

        lock.unlock();
    }

    int32_t get_num_elements() const
    {
        return num_elements;
    }

    int32_t get_array_size() const
    {
        return array->get_num_elements();
    }

    T* get_element_ptr(int32_t index)
    {
        CMapNode<K, T>* result=array->get_element(index);
        if (result!=NULL && !is_free(result))
            return &(array->get_element(index)->data);
        return NULL;
    }

    CMapNode<K, T>* get_node_ptr(int32_t index)
        {
        return array->get_element(index);
        }

    CMapNode<K, T>** get_array()
        {
        return array->get_array();
        }

    CMap& operator =(const CMap& orig)
    {

        destroy_map();
        use_sg_mallocs = orig.use_sg_mallocs;

        hash_size = orig.hash_size;

        if (use_sg_mallocs)
            hash_array = SG_CALLOC(MapNode*, hash_size);
        else
            hash_array = (CMapNode<K, T>**) calloc(hash_size,
                    sizeof(CMapNode<K, T>*));

        for (int32_t i = 0; i<hash_size; i++)
        {
            hash_array[i] = NULL;
        }

        array = new DynArray<CMapNode<K, T>*>(128, use_sg_mallocs);

        for (int i = 0; i < orig.num_elements; i++)
        {
            CMapNode<K, T>* node = orig.array->get_element(i);
            add(node->key, node->data);
        }

        return *this;
    }

private:
    int32_t hash(const K& key)
    {
        return get_hash_value(key) % hash_size;
    }

    bool is_free(CMapNode<K, T>* node)
    {
        if (node->free==true)
            return true;

        return false;
    }

    CMapNode<K, T>* chain_search(int32_t index, const K& key)
        {
        if (hash_array[index]==NULL)
        {
            return NULL;
        }
        else
        {
            CMapNode<K, T>* current=hash_array[index];
            do // iterating all items in the list
            {
                if (current->key==key)
                    return current; // it's a search key

                current=current->right;

            } while (current!=NULL);

            return NULL;
        }
        }

    int32_t insert_key(int32_t index, const K& key, const T& data)
    {
        int32_t new_index;
        CMapNode<K, T>* new_node;

        if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
        {
            // init new node
            if (use_sg_mallocs)
                new_node=SG_CALLOC(MapNode, 1);
            else
                new_node=(CMapNode<K, T>*) calloc(1, sizeof(CMapNode<K, T>));

            new (&new_node->key) K();
            new (&new_node->data) T();

            array->append_element(new_node);

            new_index=free_index;
            free_index++;
        }
        else
        {
            new_node=array->get_element(free_index);
            ASSERT(is_free(new_node))

            new_index=free_index;
            free_index=new_node->index;
        }

        new_node->index=new_index;
        new_node->free=false;
        new_node->key=key;
        new_node->data=data;
        new_node->left=NULL;
        new_node->right=NULL;

        // add new node in start of list
        if (hash_array[index]==NULL)
        {
            hash_array[index]=new_node;
        }
        else
        {
            hash_array[index]->left=new_node;
            new_node->right=hash_array[index];

            hash_array[index]=new_node;
        }

        return new_index;
    }

    void delete_key(int32_t index, CMapNode<K, T>* node)
    {
        int32_t temp=0;

        if (node==NULL)
            return;

        if (node->right!=NULL)
            node->right->left = node->left;

        if (node->left!=NULL)
            node->left->right = node->right;
        else
            hash_array[index] = node->right;

        temp=node->index;

        node->index=free_index;
        node->free=true;
        node->left=NULL;
        node->right=NULL;

        free_index=temp;
    }

    /*cleans up map*/
    void destroy_map()
    {
        if (array!=NULL)
        {
            for(int32_t i=0; i<array->get_num_elements(); i++)
            {
                CMapNode<K, T>* element = array->get_element(i);
                if (element!=NULL)
                {
                    element->key.~K();
                    element->data.~T();

                    if (use_sg_mallocs)
                        SG_FREE(element);
                    else
                        free(element);
                }
            }
            delete array;
        }

        if (hash_array!=NULL)
        {
            if (use_sg_mallocs)
                SG_FREE(hash_array);
            else
                free(hash_array);
        }

    }

protected:
    virtual uint32_t get_hash_value(const K& key)
    {
        return CHash::MurmurHash3((uint8_t*)(&key), sizeof(key), 0xDEADBEEF);
    }

    bool use_sg_mallocs;

    int32_t hash_size;

    int32_t free_index;

    int32_t num_elements;

    CMapNode<K, T>** hash_array;

    DynArray<CMapNode<K, T>*>* array;

    CLock lock;
};

}

#endif /* _MAP_H_ */