SHOGUN  v3.2.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Map.h
Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 2012 Evgeniy Andreev (gsomix)
00008  *
00009  * Copyright (C) 2012 Evgeniy Andreev (gsomix)
00010  */
00011 
00012 #ifndef _MAP_H_
00013 #define _MAP_H_
00014 
00015 #include <shogun/base/SGObject.h>
00016 #include <shogun/lib/common.h>
00017 #include <shogun/lib/Hash.h>
00018 #include <shogun/base/DynArray.h>
00019 
00020 #include <cstdio>
00021 
00022 #include <shogun/io/SGIO.h>
00023 #include <shogun/lib/Lock.h>
00024 
00025 
00026 namespace shogun
00027 {
00028 
00029 #define IGNORE_IN_CLASSLIST
00030 
00031 #define MapNode CMapNode<K, T>
00032 
00033 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00034 
00035 IGNORE_IN_CLASSLIST template<class K, class T> struct CMapNode
00036 {
00038     int32_t index;
00039 
00041     bool free;
00042 
00044     K key;
00045 
00047     T data;
00048 
00050     CMapNode *left;
00051 
00053     CMapNode *right;
00054 };
00055 #endif
00056 
00060 IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
00061 {
00062 public:
00064     CMap(int32_t size=41, int32_t reserved=128, bool tracable=true)
00065     {
00066         hash_size=size;
00067         free_index=0;
00068         num_elements=0;
00069         use_sg_mallocs=tracable;
00070 
00071         if (use_sg_mallocs)
00072             hash_array=SG_CALLOC(MapNode*, size);
00073         else
00074             hash_array=(CMapNode<K, T>**) calloc(size, sizeof(CMapNode<K, T>*));
00075 
00076         for (int32_t i=0; i<size; i++)
00077         {
00078             hash_array[i]=NULL;
00079         }
00080 
00081         array=new DynArray<CMapNode<K, T>*>(reserved, tracable);
00082     }
00083 
00085     virtual ~CMap()
00086     {
00087         destroy_map();
00088     }
00089 
00091     virtual const char* get_name() const { return "Map"; }
00092 
00099     int32_t add(const K& key, const T& data)
00100     {
00101         int32_t index=hash(key);
00102         if (chain_search(index, key)==NULL)
00103         {
00104             lock.lock();
00105             int32_t added_index=insert_key(index, key, data);
00106             num_elements++;
00107             lock.unlock();
00108 
00109             return added_index;
00110         }
00111 
00112         return -1;
00113     }
00114 
00120     bool contains(const K& key)
00121     {
00122         int32_t index=hash(key);
00123         if (chain_search(index, key)!=NULL)
00124             return true;
00125 
00126         return false;
00127     }
00128 
00133     void remove(const K& key)
00134     {
00135         int32_t index=hash(key);
00136         CMapNode<K, T>* result=chain_search(index, key);
00137 
00138         if (result!=NULL)
00139         {
00140             lock.lock();
00141             delete_key(index, result);
00142             num_elements--;
00143             lock.unlock();
00144         }
00145     }
00146 
00152     int32_t index_of(const K& key)
00153     {
00154         int32_t index=hash(key);
00155         CMapNode<K ,T>* result=chain_search(index, key);
00156 
00157         if (result!=NULL)
00158             return result->index;
00159 
00160         return -1;
00161     }
00162 
00169     T get_element(const K& key)
00170     {
00171         int32_t index=hash(key);
00172         CMapNode<K, T>* result=chain_search(index, key);
00173 
00174         if (result!=NULL)
00175             return result->data;
00176         else
00177         {
00178             int32_t added_index=add(key, T());
00179             result=get_node_ptr(added_index);
00180 
00181             return result->data;
00182         }
00183     }
00184 
00190     void set_element(const K& key, const T& data)
00191     {
00192         int32_t index=hash(key);
00193         CMapNode<K, T>* result=chain_search(index, key);
00194 
00195         lock.lock();
00196 
00197         if (result!=NULL)
00198             result->data=data;
00199         else
00200             add(key, data);
00201 
00202         lock.unlock();
00203     }
00204 
00209     int32_t get_num_elements() const
00210     {
00211         return num_elements;
00212     }
00213 
00218     int32_t get_array_size() const
00219     {
00220         return array->get_num_elements();
00221     }
00222 
00230     T* get_element_ptr(int32_t index)
00231     {
00232         CMapNode<K, T>* result=array->get_element(index);
00233         if (result!=NULL && !is_free(result))
00234             return &(array->get_element(index)->data);
00235         return NULL;
00236     }
00237 
00245     CMapNode<K, T>* get_node_ptr(int32_t index)
00246         {
00247         return array->get_element(index);
00248         }
00249 
00251     CMapNode<K, T>** get_array()
00252         {
00253         return array->get_array();
00254         }
00255 
00257     CMap& operator =(const CMap& orig)
00258     {
00259 
00260         destroy_map();
00261         use_sg_mallocs = orig.use_sg_mallocs;
00262 
00263         hash_size = orig.hash_size;
00264 
00265         if (use_sg_mallocs)
00266             hash_array = SG_CALLOC(MapNode*, hash_size);
00267         else
00268             hash_array = (CMapNode<K, T>**) calloc(hash_size,
00269                     sizeof(CMapNode<K, T>*));
00270 
00271         for (int32_t i = 0; i<hash_size; i++)
00272         {
00273             hash_array[i] = NULL;
00274         }
00275 
00276         array = new DynArray<CMapNode<K, T>*>(128, use_sg_mallocs);
00277 
00278         for (int i = 0; i < orig.num_elements; i++)
00279         {
00280             CMapNode<K, T>* node = orig.array->get_element(i);
00281             add(node->key, node->data);
00282         }
00283 
00284         return *this;
00285     }
00286 
00287 private:
00291     int32_t hash(const K& key)
00292     {
00293         return CHash::MurmurHash3((uint8_t*)(&key), sizeof(key), 0xDEADBEEF) % hash_size;
00294     }
00295 
00297     bool is_free(CMapNode<K, T>* node)
00298     {
00299         if (node->free==true)
00300             return true;
00301 
00302         return false;
00303     }
00304 
00306     CMapNode<K, T>* chain_search(int32_t index, const K& key)
00307         {
00308         if (hash_array[index]==NULL)
00309         {
00310             return NULL;
00311         }
00312         else
00313         {
00314             CMapNode<K, T>* current=hash_array[index];
00315 
00316             do // iterating all items in the list
00317             {
00318                 if (current->key==key)
00319                     return current; // it's a search key
00320 
00321                 current=current->right;
00322 
00323             } while (current!=NULL);
00324 
00325             return NULL;
00326         }
00327         }
00328 
00330     int32_t insert_key(int32_t index, const K& key, const T& data)
00331     {
00332         int32_t new_index;
00333         CMapNode<K, T>* new_node;
00334 
00335         if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
00336         {
00337             // init new node
00338             if (use_sg_mallocs)
00339                 new_node=SG_CALLOC(MapNode, 1);
00340             else
00341                 new_node=(CMapNode<K, T>*) calloc(1, sizeof(CMapNode<K, T>));
00342 
00343             new (&new_node->key) K();
00344             new (&new_node->data) T();
00345 
00346             array->append_element(new_node);
00347 
00348             new_index=free_index;
00349             free_index++;
00350         }
00351         else
00352         {
00353             new_node=array->get_element(free_index);
00354             ASSERT(is_free(new_node))
00355 
00356             new_index=free_index;
00357             free_index=new_node->index;
00358         }
00359 
00360         new_node->index=new_index;
00361         new_node->free=false;
00362         new_node->key=key;
00363         new_node->data=data;
00364         new_node->left=NULL;
00365         new_node->right=NULL;
00366 
00367         // add new node in start of list
00368         if (hash_array[index]==NULL)
00369         {
00370             hash_array[index]=new_node;
00371         }
00372         else
00373         {
00374             hash_array[index]->left=new_node;
00375             new_node->right=hash_array[index];
00376 
00377             hash_array[index]=new_node;
00378         }
00379 
00380         return new_index;
00381     }
00382 
00384     void delete_key(int32_t index, CMapNode<K, T>* node)
00385     {
00386         int32_t temp=0;
00387 
00388         if (node==NULL)
00389             return;
00390 
00391         if (node->right!=NULL)
00392             node->right->left = node->left;
00393 
00394         if (node->left!=NULL)
00395             node->left->right = node->right;
00396         else
00397             hash_array[index] = node->right;
00398 
00399         temp=node->index;
00400 
00401         node->index=free_index;
00402         node->free=true;
00403         node->left=NULL;
00404         node->right=NULL;
00405 
00406         free_index=temp;
00407     }
00408 
00409     /*cleans up map*/
00410     void destroy_map()
00411     {
00412         if (array!=NULL)
00413         {
00414             for(int32_t i=0; i<array->get_num_elements(); i++)
00415             {
00416                 CMapNode<K, T>* element = array->get_element(i);
00417                 if (element!=NULL)
00418                 {
00419                     element->key.~K();
00420                     element->data.~T();
00421 
00422                     if (use_sg_mallocs)
00423                         SG_FREE(element);
00424                     else
00425                         free(element);
00426                 }
00427             }
00428             delete array;
00429         }
00430 
00431         if (hash_array!=NULL)
00432         {
00433             if (use_sg_mallocs)
00434                 SG_FREE(hash_array);
00435             else
00436                 free(hash_array);
00437         }
00438 
00439     }
00440 
00441 protected:
00443     bool use_sg_mallocs;
00444 
00446     int32_t hash_size;
00447 
00449     int32_t free_index;
00450 
00452     int32_t num_elements;
00453 
00455     CMapNode<K, T>** hash_array;
00456 
00458     DynArray<CMapNode<K, T>*>* array;
00459 
00461     CLock lock;
00462 };
00463 
00464 }
00465 
00466 #endif /* _MAP_H_ */
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation