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)
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());
192 int32_t index=hash(key);
193 CMapNode<K, T>* result=chain_search(index, key);
233 if (result!=NULL && !is_free(result))
269 sizeof(CMapNode<K, T>*));
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)
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)
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();
357 free_index=new_node->index;
360 new_node->index=new_index;
361 new_node->free=false;
365 new_node->right=NULL;
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;
CMapNode< K, T > ** get_array()
T get_element(int32_t index) const
bool append_element(T element)
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
virtual const char * get_name() const
int32_t get_num_elements() const
int32_t get_num_elements() const
static uint32_t MurmurHash3(uint8_t *data, int32_t len, uint32_t seed)
T get_element(const K &key)
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)
int32_t add(const K &key, const T &data)
CMap & operator=(const CMap &orig)
CMapNode< K, T > ** hash_array
int32_t get_array_size() const