15 #include <shogun/lib/config.h> 31 #define IGNORE_IN_CLASSLIST 33 #define MapNode CMapNode<K, T> 35 #ifndef DOXYGEN_SHOULD_SKIP_THIS 66 CMap(int32_t size=41, int32_t reserved=128,
bool tracable=
true)
71 use_sg_mallocs=tracable;
74 hash_array=SG_CALLOC(
MapNode*, size);
76 hash_array=(CMapNode<K, T>**) calloc(size,
sizeof(CMapNode<K, T>*));
78 for (int32_t i=0; i<size; i++)
93 virtual const char*
get_name()
const {
return "Map"; }
101 int32_t
add(
const K& key,
const T& data)
103 int32_t index=hash(key);
104 if (chain_search(index, key)==NULL)
107 int32_t added_index=insert_key(index, key, data);
124 int32_t index=hash(key);
125 if (chain_search(index, key)!=NULL)
135 void remove(
const K& key)
137 int32_t index=hash(key);
138 CMapNode<K, T>* result=chain_search(index, key);
143 delete_key(index, result);
156 int32_t index=hash(key);
157 CMapNode<K ,T>* result=chain_search(index, key);
160 return result->index;
173 int32_t index=hash(key);
174 CMapNode<K, T>* result=chain_search(index, key);
180 int32_t added_index=
add(key, T());
181 result=get_node_ptr(added_index);
194 int32_t index=hash(key);
195 CMapNode<K, T>* result=chain_search(index, key);
222 return array->get_num_elements();
234 CMapNode<K, T>* result=array->get_element(index);
235 if (result!=NULL && !is_free(result))
236 return &(array->get_element(index)->data);
249 return array->get_element(index);
255 return array->get_array();
263 use_sg_mallocs = orig.use_sg_mallocs;
265 hash_size = orig.hash_size;
268 hash_array = SG_CALLOC(
MapNode*, hash_size);
270 hash_array = (CMapNode<K, T>**) calloc(hash_size,
271 sizeof(CMapNode<K, T>*));
273 for (int32_t i = 0; i<hash_size; i++)
275 hash_array[i] = NULL;
280 for (
int i = 0; i < orig.num_elements; i++)
282 CMapNode<K, T>*
node = orig.array->get_element(i);
283 add(node->key, node->data);
293 int32_t hash(
const K& key)
295 return get_hash_value(key) % hash_size;
299 bool is_free(CMapNode<K, T>*
node)
301 if (node->free==
true)
308 CMapNode<K, T>* chain_search(int32_t index,
const K& key)
310 if (hash_array[index]==NULL)
316 CMapNode<K, T>* current=hash_array[index];
319 if (current->key==key)
322 current=current->right;
324 }
while (current!=NULL);
331 int32_t insert_key(int32_t index,
const K& key,
const T& data)
336 if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
340 new_node=SG_CALLOC(
MapNode, 1);
342 new_node=(CMapNode<K, T>*) calloc(1,
sizeof(CMapNode<K, T>));
344 new (&new_node->key) K();
345 new (&new_node->data) T();
347 array->append_element(new_node);
349 new_index=free_index;
354 new_node=array->get_element(free_index);
357 new_index=free_index;
358 free_index=new_node->index;
361 new_node->index=new_index;
362 new_node->free=
false;
366 new_node->right=NULL;
369 if (hash_array[index]==NULL)
376 new_node->right=hash_array[index];
385 void delete_key(int32_t index, CMapNode<K, T>* node)
392 if (node->right!=NULL)
393 node->right->left = node->left;
395 if (node->left!=NULL)
396 node->left->right = node->right;
398 hash_array[index] = node->right;
402 node->index=free_index;
415 for(int32_t i=0; i<array->get_num_elements(); i++)
417 CMapNode<K, T>* element = array->get_element(i);
432 if (hash_array!=NULL)
CMapNode< K, T > ** get_array()
int32_t get_array_size() const
node< P > new_node(const P &p)
void set_element(const K &key, const T &data)
CMapNode< K, T > * get_node_ptr(int32_t index)
virtual uint32_t get_hash_value(const K &key)
bool contains(const K &key)
void add(SGVector< T > &a, SGVector< T > &b, SGVector< T > &result, T alpha=1, T beta=1)
DynArray< CMapNode< K, T > * > * array
static uint32_t MurmurHash3(uint8_t *data, int32_t len, uint32_t seed)
virtual const char * get_name() const
T get_element(const K &key)
int32_t get_num_elements() const
Class Lock used for synchronization in concurrent programs.
Template Dynamic array class that creates an array that can be used like a list or an array...
the class CMap, a map based on the hash-table. w: http://en.wikipedia.org/wiki/Hash_table ...
T * get_element_ptr(int32_t index)
#define IGNORE_IN_CLASSLIST
CMap(int32_t size=41, int32_t reserved=128, bool tracable=true)
int32_t index_of(const K &key)
all of classes and functions are contained in the shogun namespace
int32_t add(const K &key, const T &data)
CMapNode< K, T > ** hash_array