29 #define IGNORE_IN_CLASSLIST 31 #define MapNode CMapNode<K, T> 33 #ifndef DOXYGEN_SHOULD_SKIP_THIS 64 CMap(int32_t size=41, int32_t reserved=128,
bool tracable=
true)
69 use_sg_mallocs=tracable;
72 hash_array=SG_CALLOC(
MapNode*, size);
74 hash_array=(CMapNode<K, T>**) calloc(size,
sizeof(CMapNode<K, T>*));
76 for (int32_t i=0; i<size; i++)
91 virtual const char*
get_name()
const {
return "Map"; }
99 int32_t
add(
const K& key,
const T& data)
101 int32_t index=hash(key);
102 if (chain_search(index, key)==NULL)
105 int32_t added_index=insert_key(index, key, data);
122 int32_t index=hash(key);
123 if (chain_search(index, key)!=NULL)
133 void remove(
const K& key)
135 int32_t index=hash(key);
136 CMapNode<K, T>* result=chain_search(index, key);
141 delete_key(index, result);
154 int32_t index=hash(key);
155 CMapNode<K ,T>* result=chain_search(index, key);
158 return result->index;
171 int32_t index=hash(key);
172 CMapNode<K, T>* result=chain_search(index, key);
178 int32_t added_index=add(key, T());
179 result=get_node_ptr(added_index);
192 int32_t index=hash(key);
193 CMapNode<K, T>* result=chain_search(index, key);
220 return array->get_num_elements();
232 CMapNode<K, T>* result=array->get_element(index);
233 if (result!=NULL && !is_free(result))
234 return &(array->get_element(index)->data);
247 return array->get_element(index);
253 return array->get_array();
261 use_sg_mallocs = orig.use_sg_mallocs;
263 hash_size = orig.hash_size;
266 hash_array = SG_CALLOC(
MapNode*, hash_size);
268 hash_array = (CMapNode<K, T>**) calloc(hash_size,
269 sizeof(CMapNode<K, T>*));
271 for (int32_t i = 0; i<hash_size; i++)
273 hash_array[i] = NULL;
278 for (
int i = 0; i < orig.num_elements; i++)
280 CMapNode<K, T>*
node = orig.array->get_element(i);
281 add(node->key, node->data);
291 int32_t hash(
const K& key)
297 bool is_free(CMapNode<K, T>*
node)
299 if (node->free==
true)
306 CMapNode<K, T>* chain_search(int32_t index,
const K& key)
308 if (hash_array[index]==NULL)
314 CMapNode<K, T>* current=hash_array[index];
318 if (current->key==key)
321 current=current->right;
323 }
while (current!=NULL);
330 int32_t insert_key(int32_t index,
const K& key,
const T& data)
335 if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
339 new_node=SG_CALLOC(
MapNode, 1);
341 new_node=(CMapNode<K, T>*) calloc(1,
sizeof(CMapNode<K, T>));
343 new (&new_node->key) K();
344 new (&new_node->data) T();
346 array->append_element(new_node);
348 new_index=free_index;
353 new_node=array->get_element(free_index);
356 new_index=free_index;
357 free_index=new_node->index;
360 new_node->index=new_index;
361 new_node->free=
false;
365 new_node->right=NULL;
368 if (hash_array[index]==NULL)
375 new_node->right=hash_array[index];
384 void delete_key(int32_t index, CMapNode<K, T>* node)
391 if (node->right!=NULL)
392 node->right->left = node->left;
394 if (node->left!=NULL)
395 node->left->right = node->right;
397 hash_array[index] = node->right;
401 node->index=free_index;
414 for(int32_t i=0; i<array->get_num_elements(); i++)
416 CMapNode<K, T>* element = array->get_element(i);
431 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)
bool contains(const K &key)
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