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>*));
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;