SHOGUN
v2.0.0
|
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/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 // iterating all items in the list 00340 { 00341 if (current->key==key) 00342 return current; // it's a search key 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 // init new node 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 // add new node in start of list 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 /*cleans up map*/ 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 /* _MAP_H_ */