SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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();
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 CHash::MurmurHash3((uint8_t*)(&key), sizeof(key), 0xDEADBEEF) % 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 
318  do // iterating all items in the list
319  {
320  if (current->key==key)
321  return current; // it's a search key
322 
323  current=current->right;
324 
325  } while (current!=NULL);
326 
327  return NULL;
328  }
329  }
330 
332  int32_t insert_key(int32_t index, const K& key, const T& data)
333  {
334  int32_t new_index;
335  CMapNode<K, T>* new_node;
336 
338  {
339  // init new node
340  if (use_sg_mallocs)
341  new_node=SG_CALLOC(MapNode, 1);
342  else
343  new_node=(CMapNode<K, T>*) calloc(1, sizeof(CMapNode<K, T>));
344 
345  new (&new_node->key) K();
346  new (&new_node->data) T();
347 
348  array->append_element(new_node);
349 
350  new_index=free_index;
351  free_index++;
352  }
353  else
354  {
355  new_node=array->get_element(free_index);
356  ASSERT(is_free(new_node))
357 
358  new_index=free_index;
359  free_index=new_node->index;
360  }
361 
362  new_node->index=new_index;
363  new_node->free=false;
364  new_node->key=key;
365  new_node->data=data;
366  new_node->left=NULL;
367  new_node->right=NULL;
368 
369  // add new node in start of list
370  if (hash_array[index]==NULL)
371  {
372  hash_array[index]=new_node;
373  }
374  else
375  {
376  hash_array[index]->left=new_node;
377  new_node->right=hash_array[index];
378 
379  hash_array[index]=new_node;
380  }
381 
382  return new_index;
383  }
384 
386  void delete_key(int32_t index, CMapNode<K, T>* node)
387  {
388  int32_t temp=0;
389 
390  if (node==NULL)
391  return;
392 
393  if (node->right!=NULL)
394  node->right->left = node->left;
395 
396  if (node->left!=NULL)
397  node->left->right = node->right;
398  else
399  hash_array[index] = node->right;
400 
401  temp=node->index;
402 
403  node->index=free_index;
404  node->free=true;
405  node->left=NULL;
406  node->right=NULL;
407 
408  free_index=temp;
409  }
410 
411  /*cleans up map*/
412  void destroy_map()
413  {
414  if (array!=NULL)
415  {
416  for(int32_t i=0; i<array->get_num_elements(); i++)
417  {
418  CMapNode<K, T>* element = array->get_element(i);
419  if (element!=NULL)
420  {
421  element->key.~K();
422  element->data.~T();
423 
424  if (use_sg_mallocs)
425  SG_FREE(element);
426  else
427  free(element);
428  }
429  }
430  delete array;
431  }
432 
433  if (hash_array!=NULL)
434  {
435  if (use_sg_mallocs)
436  SG_FREE(hash_array);
437  else
438  free(hash_array);
439  }
440 
441  }
442 
443 protected:
446 
448  int32_t hash_size;
449 
451  int32_t free_index;
452 
454  int32_t num_elements;
455 
457  CMapNode<K, T>** hash_array;
458 
461 
464 };
465 
466 }
467 
468 #endif /* _MAP_H_ */

SHOGUN Machine Learning Toolbox - Documentation