SHOGUN
v3.2.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/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_ */