00001
00002
00003
00004
00005
00006
00007
00008
00009
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/base/Parallel.h>
00024
00025 #ifdef HAVE_PTHREAD
00026 #include <pthread.h>
00027 #endif
00028
00029 namespace shogun
00030 {
00031
00032 #define IGNORE_IN_CLASSLIST
00033
00034 #define MapNode CMapNode<K, T>
00035
00036 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00037
00038 IGNORE_IN_CLASSLIST template<class K, class T> struct CMapNode
00039 {
00041 int32_t index;
00042
00044 bool free;
00045
00047 K key;
00048
00050 T data;
00051
00053 CMapNode *left;
00054
00056 CMapNode *right;
00057 };
00058 #endif
00059
00063 IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
00064 {
00065 public:
00067 CMap(int32_t size=41, int32_t reserved=128, bool tracable=true)
00068 {
00069 hash_size=size;
00070 free_index=0;
00071 num_elements=0;
00072 use_sg_mallocs=tracable;
00073
00074 if (use_sg_mallocs)
00075 hash_array=SG_CALLOC(MapNode*, size);
00076 else
00077 hash_array=(CMapNode<K, T>**) calloc(size, sizeof(CMapNode<K, T>*));
00078
00079 for (int32_t i=0; i<size; i++)
00080 {
00081 hash_array[i]=NULL;
00082 }
00083
00084 array=new DynArray<CMapNode<K, T>*>(reserved, tracable);
00085
00086 #ifdef HAVE_PTHREAD
00087 PTHREAD_LOCK_INIT(&lock);
00088 #endif
00089 }
00090
00092 virtual ~CMap()
00093 {
00094 #ifdef HAVE_PTHREAD
00095 PTHREAD_LOCK_DESTROY(&lock);
00096 #endif
00097 destroy_map();
00098 }
00099
00101 virtual const char* get_name() const { return "Map"; }
00102
00109 int32_t add(const K& key, const T& data)
00110 {
00111 int32_t index=hash(key);
00112 if (chain_search(index, key)==NULL)
00113 {
00114 #ifdef HAVE_PTHREAD
00115 PTHREAD_LOCK(&lock);
00116 #endif
00117 int32_t added_index=insert_key(index, key, data);
00118 num_elements++;
00119 #ifdef HAVE_PTHREAD
00120 PTHREAD_UNLOCK(&lock);
00121 #endif
00122
00123 return added_index;
00124 }
00125
00126 return -1;
00127 }
00128
00134 bool contains(const K& key)
00135 {
00136 int32_t index=hash(key);
00137 if (chain_search(index, key)!=NULL)
00138 return true;
00139
00140 return false;
00141 }
00142
00147 void remove(const K& key)
00148 {
00149 int32_t index=hash(key);
00150 CMapNode<K, T>* result=chain_search(index, key);
00151
00152 if (result!=NULL)
00153 {
00154 #ifdef HAVE_PTHREAD
00155 PTHREAD_LOCK(&lock);
00156 #endif
00157 delete_key(index, result);
00158 num_elements--;
00159 #ifdef HAVE_PTHREAD
00160 PTHREAD_UNLOCK(&lock);
00161 #endif
00162 }
00163 }
00164
00170 int32_t index_of(const K& key)
00171 {
00172 int32_t index=hash(key);
00173 CMapNode<K ,T>* result=chain_search(index, key);
00174
00175 if (result!=NULL)
00176 return result->index;
00177
00178 return -1;
00179 }
00180
00187 T get_element(const K& key)
00188 {
00189 int32_t index=hash(key);
00190 CMapNode<K, T>* result=chain_search(index, key);
00191
00192 if (result!=NULL)
00193 return result->data;
00194 else
00195 {
00196 int32_t added_index=add(key, T());
00197 result=get_node_ptr(added_index);
00198
00199 return result->data;
00200 }
00201 }
00202
00208 void set_element(const K& key, const T& data)
00209 {
00210 int32_t index=hash(key);
00211 CMapNode<K, T>* result=chain_search(index, key);
00212
00213 #ifdef HAVE_PTHREAD
00214 PTHREAD_LOCK(&lock);
00215 #endif
00216 if (result!=NULL)
00217 result->data=data;
00218 else
00219 {
00220 add(key, data);
00221 }
00222
00223 #ifdef HAVE_PTHREAD
00224 PTHREAD_UNLOCK(&lock);
00225 #endif
00226 }
00227
00232 int32_t get_num_elements() const
00233 {
00234 return num_elements;
00235 }
00236
00241 int32_t get_array_size() const
00242 {
00243 return array->get_num_elements();
00244 }
00245
00253 T* get_element_ptr(int32_t index)
00254 {
00255 CMapNode<K, T>* result=array->get_element(index);
00256 if (result!=NULL && !is_free(result))
00257 return &(array->get_element(index)->data);
00258 return NULL;
00259 }
00260
00268 CMapNode<K, T>* get_node_ptr(int32_t index)
00269 {
00270 return array->get_element(index);
00271 }
00272
00274 CMapNode<K, T>** get_array()
00275 {
00276 return array->get_array();
00277 }
00278
00280 CMap& operator =(const CMap& orig)
00281 {
00282
00283 destroy_map();
00284 use_sg_mallocs = orig.use_sg_mallocs;
00285
00286 hash_size = orig.hash_size;
00287
00288 if (use_sg_mallocs)
00289 hash_array = SG_CALLOC(MapNode*, hash_size);
00290 else
00291 hash_array = (CMapNode<K, T>**) calloc(hash_size,
00292 sizeof(CMapNode<K, T>*));
00293
00294 for (int32_t i = 0; i<hash_size; i++)
00295 {
00296 hash_array[i] = NULL;
00297 }
00298
00299 array = new DynArray<CMapNode<K, T>*>(128, use_sg_mallocs);
00300
00301 for (int i = 0; i < orig.num_elements; i++)
00302 {
00303 CMapNode<K, T>* node = orig.array->get_element(i);
00304 add(node->key, node->data);
00305 }
00306
00307 return *this;
00308 }
00309
00310 private:
00314 int32_t hash(const K& key)
00315 {
00316 return CHash::MurmurHash3((uint8_t*)(&key), sizeof(key), 0xDEADBEEF) % hash_size;
00317 }
00318
00320 bool is_free(CMapNode<K, T>* node)
00321 {
00322 if (node->free==true)
00323 return true;
00324
00325 return false;
00326 }
00327
00329 CMapNode<K, T>* chain_search(int32_t index, const K& key)
00330 {
00331 if (hash_array[index]==NULL)
00332 {
00333 return NULL;
00334 }
00335 else
00336 {
00337 CMapNode<K, T>* current=hash_array[index];
00338
00339 do
00340 {
00341 if (current->key==key)
00342 return current;
00343
00344 current=current->right;
00345
00346 } while (current!=NULL);
00347
00348 return NULL;
00349 }
00350 }
00351
00353 int32_t insert_key(int32_t index, const K& key, const T& data)
00354 {
00355 int32_t new_index;
00356 CMapNode<K, T>* new_node;
00357
00358 if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
00359 {
00360
00361 if (use_sg_mallocs)
00362 new_node=SG_CALLOC(MapNode, 1);
00363 else
00364 new_node=(CMapNode<K, T>*) calloc(1, sizeof(CMapNode<K, T>));
00365
00366 new (&new_node->key) K();
00367 new (&new_node->data) T();
00368
00369 array->append_element(new_node);
00370
00371 new_index=free_index;
00372 free_index++;
00373 }
00374 else
00375 {
00376 new_node=array->get_element(free_index);
00377 ASSERT(is_free(new_node));
00378
00379 new_index=free_index;
00380 free_index=new_node->index;
00381 }
00382
00383 new_node->index=new_index;
00384 new_node->free=false;
00385 new_node->key=key;
00386 new_node->data=data;
00387 new_node->left=NULL;
00388 new_node->right=NULL;
00389
00390
00391 if (hash_array[index]==NULL)
00392 {
00393 hash_array[index]=new_node;
00394 }
00395 else
00396 {
00397 hash_array[index]->left=new_node;
00398 new_node->right=hash_array[index];
00399
00400 hash_array[index]=new_node;
00401 }
00402
00403 return new_index;
00404 }
00405
00407 void delete_key(int32_t index, CMapNode<K, T>* node)
00408 {
00409 int32_t temp=0;
00410
00411 if (node==NULL)
00412 return;
00413
00414 if (node->right!=NULL)
00415 node->right->left = node->left;
00416
00417 if (node->left!=NULL)
00418 node->left->right = node->right;
00419 else
00420 hash_array[index] = node->right;
00421
00422 temp=node->index;
00423
00424 node->index=free_index;
00425 node->free=true;
00426 node->left=NULL;
00427 node->right=NULL;
00428
00429 free_index=temp;
00430 }
00431
00432
00433 void destroy_map()
00434 {
00435 if (array!=NULL)
00436 {
00437 for(int32_t i=0; i<array->get_num_elements(); i++)
00438 {
00439 CMapNode<K, T>* element = array->get_element(i);
00440 if (element!=NULL)
00441 {
00442 element->key.~K();
00443 element->data.~T();
00444
00445 if (use_sg_mallocs)
00446 SG_FREE(element);
00447 else
00448 free(element);
00449 }
00450 }
00451 delete array;
00452 }
00453
00454 if (hash_array!=NULL)
00455 {
00456 if (use_sg_mallocs)
00457 SG_FREE(hash_array);
00458 else
00459 free(hash_array);
00460 }
00461
00462 }
00463
00464 protected:
00466 bool use_sg_mallocs;
00467
00469 int32_t hash_size;
00470
00472 int32_t free_index;
00473
00475 int32_t num_elements;
00476
00478 CMapNode<K, T>** hash_array;
00479
00481 DynArray<CMapNode<K, T>*>* array;
00482
00483 #ifdef HAVE_PTHREAD
00484
00485 PTHREAD_LOCK_T lock;
00486 #endif
00487 };
00488
00489 }
00490
00491 #endif