SHOGUN  5.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules
Map.h
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2012 Evgeniy Andreev (gsomix)
8  *
9  * Copyright (C) 2012 Evgeniy Andreev (gsomix)
10  */
11 
12 #ifndef _MAP_H_
13 #define _MAP_H_
14 
15 #include <shogun/lib/config.h>
16 
17 #include <shogun/base/SGObject.h>
18 #include <shogun/lib/common.h>
19 #include <shogun/lib/Hash.h>
20 #include <shogun/base/DynArray.h>
21 
22 #include <cstdio>
23 
24 #include <shogun/io/SGIO.h>
25 #include <shogun/lib/Lock.h>
26 
27 
28 namespace shogun
29 {
30 
31 #define IGNORE_IN_CLASSLIST
32 
33 #define MapNode CMapNode<K, T>
34 
35 #ifndef DOXYGEN_SHOULD_SKIP_THIS
36 
37 IGNORE_IN_CLASSLIST template<class K, class T> struct CMapNode
38 {
40  int32_t index;
41 
43  bool free;
44 
46  K key;
47 
49  T data;
50 
52  CMapNode *left;
53 
55  CMapNode *right;
56 };
57 #endif
58 
62 IGNORE_IN_CLASSLIST template<class K, class T> class CMap: public CSGObject
63 {
64 public:
66  CMap(int32_t size=41, int32_t reserved=128, bool tracable=true)
67  {
68  hash_size=size;
69  free_index=0;
70  num_elements=0;
71  use_sg_mallocs=tracable;
72 
73  if (use_sg_mallocs)
74  hash_array=SG_CALLOC(MapNode*, size);
75  else
76  hash_array=(CMapNode<K, T>**) calloc(size, sizeof(CMapNode<K, T>*));
77 
78  for (int32_t i=0; i<size; i++)
79  {
80  hash_array[i]=NULL;
81  }
82 
83  array=new DynArray<CMapNode<K, T>*>(reserved, tracable);
84  }
85 
87  virtual ~CMap()
88  {
89  destroy_map();
90  }
91 
93  virtual const char* get_name() const { return "Map"; }
94 
101  int32_t add(const K& key, const T& data)
102  {
103  int32_t index=hash(key);
104  if (chain_search(index, key)==NULL)
105  {
106  lock.lock();
107  int32_t added_index=insert_key(index, key, data);
108  num_elements++;
109  lock.unlock();
110 
111  return added_index;
112  }
113 
114  return -1;
115  }
116 
122  bool contains(const K& key)
123  {
124  int32_t index=hash(key);
125  if (chain_search(index, key)!=NULL)
126  return true;
127 
128  return false;
129  }
130 
135  void remove(const K& key)
136  {
137  int32_t index=hash(key);
138  CMapNode<K, T>* result=chain_search(index, key);
139 
140  if (result!=NULL)
141  {
142  lock.lock();
143  delete_key(index, result);
144  num_elements--;
145  lock.unlock();
146  }
147  }
148 
154  int32_t index_of(const K& key)
155  {
156  int32_t index=hash(key);
157  CMapNode<K ,T>* result=chain_search(index, key);
158 
159  if (result!=NULL)
160  return result->index;
161 
162  return -1;
163  }
164 
171  T get_element(const K& key)
172  {
173  int32_t index=hash(key);
174  CMapNode<K, T>* result=chain_search(index, key);
175 
176  if (result!=NULL)
177  return result->data;
178  else
179  {
180  int32_t added_index=add(key, T());
181  result=get_node_ptr(added_index);
182 
183  return result->data;
184  }
185  }
186 
192  void set_element(const K& key, const T& data)
193  {
194  int32_t index=hash(key);
195  CMapNode<K, T>* result=chain_search(index, key);
196 
197  lock.lock();
198 
199  if (result!=NULL)
200  result->data=data;
201  else
202  add(key, data);
203 
204  lock.unlock();
205  }
206 
211  int32_t get_num_elements() const
212  {
213  return num_elements;
214  }
215 
220  int32_t get_array_size() const
221  {
222  return array->get_num_elements();
223  }
224 
232  T* get_element_ptr(int32_t index)
233  {
234  CMapNode<K, T>* result=array->get_element(index);
235  if (result!=NULL && !is_free(result))
236  return &(array->get_element(index)->data);
237  return NULL;
238  }
239 
247  CMapNode<K, T>* get_node_ptr(int32_t index)
248  {
249  return array->get_element(index);
250  }
251 
253  CMapNode<K, T>** get_array()
254  {
255  return array->get_array();
256  }
257 
259  CMap& operator =(const CMap& orig)
260  {
261 
262  destroy_map();
263  use_sg_mallocs = orig.use_sg_mallocs;
264 
265  hash_size = orig.hash_size;
266 
267  if (use_sg_mallocs)
268  hash_array = SG_CALLOC(MapNode*, hash_size);
269  else
270  hash_array = (CMapNode<K, T>**) calloc(hash_size,
271  sizeof(CMapNode<K, T>*));
272 
273  for (int32_t i = 0; i<hash_size; i++)
274  {
275  hash_array[i] = NULL;
276  }
277 
279 
280  for (int i = 0; i < orig.num_elements; i++)
281  {
282  CMapNode<K, T>* node = orig.array->get_element(i);
283  add(node->key, node->data);
284  }
285 
286  return *this;
287  }
288 
289 private:
293  int32_t hash(const K& key)
294  {
295  return get_hash_value(key) % hash_size;
296  }
297 
299  bool is_free(CMapNode<K, T>* node)
300  {
301  if (node->free==true)
302  return true;
303 
304  return false;
305  }
306 
308  CMapNode<K, T>* chain_search(int32_t index, const K& key)
309  {
310  if (hash_array[index]==NULL)
311  {
312  return NULL;
313  }
314  else
315  {
316  CMapNode<K, T>* current=hash_array[index];
317  do // iterating all items in the list
318  {
319  if (current->key==key)
320  return current; // it's a search key
321 
322  current=current->right;
323 
324  } while (current!=NULL);
325 
326  return NULL;
327  }
328  }
329 
331  int32_t insert_key(int32_t index, const K& key, const T& data)
332  {
333  int32_t new_index;
334  CMapNode<K, T>* new_node;
335 
337  {
338  // init new node
339  if (use_sg_mallocs)
340  new_node=SG_CALLOC(MapNode, 1);
341  else
342  new_node=(CMapNode<K, T>*) calloc(1, sizeof(CMapNode<K, T>));
343 
344  new (&new_node->key) K();
345  new (&new_node->data) T();
346 
347  array->append_element(new_node);
348 
349  new_index=free_index;
350  free_index++;
351  }
352  else
353  {
354  new_node=array->get_element(free_index);
355  ASSERT(is_free(new_node))
356 
357  new_index=free_index;
358  free_index=new_node->index;
359  }
360 
361  new_node->index=new_index;
362  new_node->free=false;
363  new_node->key=key;
364  new_node->data=data;
365  new_node->left=NULL;
366  new_node->right=NULL;
367 
368  // add new node in start of list
369  if (hash_array[index]==NULL)
370  {
371  hash_array[index]=new_node;
372  }
373  else
374  {
375  hash_array[index]->left=new_node;
376  new_node->right=hash_array[index];
377 
378  hash_array[index]=new_node;
379  }
380 
381  return new_index;
382  }
383 
385  void delete_key(int32_t index, CMapNode<K, T>* node)
386  {
387  int32_t temp=0;
388 
389  if (node==NULL)
390  return;
391 
392  if (node->right!=NULL)
393  node->right->left = node->left;
394 
395  if (node->left!=NULL)
396  node->left->right = node->right;
397  else
398  hash_array[index] = node->right;
399 
400  temp=node->index;
401 
402  node->index=free_index;
403  node->free=true;
404  node->left=NULL;
405  node->right=NULL;
406 
407  free_index=temp;
408  }
409 
410  /*cleans up map*/
411  void destroy_map()
412  {
413  if (array!=NULL)
414  {
415  for(int32_t i=0; i<array->get_num_elements(); i++)
416  {
417  CMapNode<K, T>* element = array->get_element(i);
418  if (element!=NULL)
419  {
420  element->key.~K();
421  element->data.~T();
422 
423  if (use_sg_mallocs)
424  SG_FREE(element);
425  else
426  free(element);
427  }
428  }
429  delete array;
430  }
431 
432  if (hash_array!=NULL)
433  {
434  if (use_sg_mallocs)
435  SG_FREE(hash_array);
436  else
437  free(hash_array);
438  }
439 
440  }
441 
442 protected:
447  virtual uint32_t get_hash_value(const K& key)
448  {
449  return CHash::MurmurHash3((uint8_t*)(&key), sizeof(key), 0xDEADBEEF);
450  }
451 
454 
456  int32_t hash_size;
457 
459  int32_t free_index;
460 
462  int32_t num_elements;
463 
465  CMapNode<K, T>** hash_array;
466 
469 
472 };
473 
474 }
475 
476 #endif /* _MAP_H_ */
T get_element(int32_t index) const
Definition: DynArray.h:142
CMap(int32_t size=41, int32_t reserved=128, bool tracable=true)
Definition: Map.h:66
CMapNode< K, T > ** hash_array
Definition: Map.h:465
int32_t index_of(const K &key)
Definition: Map.h:154
bool append_element(T element)
Definition: DynArray.h:244
node< P > new_node(const P &p)
Definition: JLCoverTree.h:101
virtual const char * get_name() const
Definition: Map.h:93
T get_element(const K &key)
Definition: Map.h:171
int32_t num_elements
Definition: Map.h:462
#define MapNode
Definition: Map.h:33
CMapNode< K, T > ** get_array()
Definition: Map.h:253
void unlock()
Definition: Lock.cpp:64
void set_element(const K &key, const T &data)
Definition: Map.h:192
int32_t get_num_elements() const
Definition: DynArray.h:130
int32_t free_index
Definition: Map.h:459
virtual uint32_t get_hash_value(const K &key)
Definition: Map.h:447
bool contains(const K &key)
Definition: Map.h:122
static uint32_t MurmurHash3(uint8_t *data, int32_t len, uint32_t seed)
Definition: Hash.cpp:366
T * get_element_ptr(int32_t index)
Definition: Map.h:232
CMapNode< K, T > * get_node_ptr(int32_t index)
Definition: Map.h:247
int32_t get_array_size() const
Definition: Map.h:220
int32_t add(const K &key, const T &data)
Definition: Map.h:101
#define ASSERT(x)
Definition: SGIO.h:201
Class Lock used for synchronization in concurrent programs.
Definition: Lock.h:17
Template Dynamic array class that creates an array that can be used like a list or an array...
Definition: DynArray.h:32
CMap & operator=(const CMap &orig)
Definition: Map.h:259
int32_t hash_size
Definition: Map.h:456
#define IGNORE_IN_CLASSLIST
Definition: Map.h:31
CLock lock
Definition: Map.h:471
DynArray< CMapNode< K, T > * > * array
Definition: Map.h:468
bool use_sg_mallocs
Definition: Map.h:453
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
T * get_array() const
Definition: DynArray.h:372
virtual ~CMap()
Definition: Map.h:87
int32_t get_num_elements() const
Definition: Map.h:211
void lock()
Definition: Lock.cpp:57
the class CMap, a map based on the hash-table. w: http://en.wikipedia.org/wiki/Hash_table ...
Definition: SGObject.h:39

SHOGUN Machine Learning Toolbox - Documentation