Re: [boost] [ boost ] [ Trie ]

On 8 March 2015 at 11:27, Antony Polukhin wrote:

2015-03-07 20:10 GMT+03:00 Cosmin Boaca :

Yep, methods create_node/destroy_node are required I am thinking at creating a new class something like node_factory that would handle this. I think it's more like the OOP way.

That's a bad idea: iterators must know nothing about erasure. Convert those __erase_self_value_node() methods into a free functions in detail namespace. Those functions will be accepting allocator and will be overloaded by node pointers.

Ok. I will change this one. Many optimizations may be applied there:

* key_ends_here is a boolean value, that actually could be hidden in one of the pointers. In all cases our nodes are at least 2 bytes aligned, so all the parent, pred_node, next_node guaranteed to have first bit set to 0. so we can hide that `key_ends_here` bit in pointer just like this: pointer | (key_ends_here ? 1u : 0u). This will probably require addition of set_parent(). parent(), <...> functions to all the trie_nodes.

Can you give me some further explanations about this ? Why are the nodes at least 2 bytes aligned and why does this imply that the first bit of the pointers is set to 0 ? When you're saying the first bit you mean the least significant one (index 0) don't you ?

* children_type is not good. We get problems (like having additional child_iter_of_parent in node), because the key is not stored in node. So the plan is following: make trie_node to be usable in intrusive set, and use the nodes directly in children. Here are some steps: use boost::intrusive::set for children_type, derive trie_node from set_base_hook and make it intrusive-set compatible, remove child_iter_of_parent and store key in trie_node directly. This will significally reduce memory usage by nodes and memory allocations (unlike intrusive set, std::map allocates memory for nodes).

I think I will start with this. The idea of intrusive containers seems pretty interesting to me. I have never heard of something like this until now. Thank you, Cosmin