Re: [Boost-users] [multi_index] MSVS 2005 visualizers?

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2007-06-01 15:34:15

Filip Konvička <filip.konvicka <at> logis.cz> writes:

[...]
> I tried hashed_unique right away, and I have another issue:
> 
> 
boost::multi_index::detail::header_holder<boost::multi_index::detail::hashed_in
dex_node<*>,*>{
>   preview(#("multi_index_container hashed data"))
>   children(
>     #(
>       orig : [$c,!],
>       #list(
>             head : 
> *((hashed_index_node_impl*)(hashed_index_node_trampoline<$T1>*)($c.member)),
>             size : 
> ((multi_index_helper_3<$T2>*)((header_holder<hashed_index_node<$T1>,$T2>*)
(((char*)&$c)+4)))->node_count,
>             next : next_
>       ) : *(multi_index_helper<hashed_index_node<$T1> 
>  >*)(hashed_index_node<$T1>*)(hashed_index_node_trampoline<$T1>*)(&$e)
>     )
>   )
> }
> 
> It seems that accessing node_count using the same technique as with 
> ordered_unique does not work - I'm off by 4 bytes (see the 
> (((char*)&$c)+4) expression). 

I've examined this carefully and I can't see how the offset
should be needed. What's the value the visualizer shows without
the offset, i.e. when using the following expression?

size : ((multi_index_helper_3<$T2>*)&$c)->node_count

> Clicking through the head node's next_ 
> members reveals that I'm cycling between just 2 nodes (there should be 5 
> of them), and the data is garbage. So perhaps I'm missing some 
> additional cast somewhere, but I don't see where.

I'm afraid traversing a hashed index is no easy chore. There are
two popular implementation techniques for TR1 unordered containers
and related data structures (prestandard hash_sets and such):

  a) As a single doubly linked lists of elements.
  b) As several singly linked lists, one for each nonempty bucket.

(for more info on this subject, see section F of
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1443.html )

With a), which is what Dinkumware's stdext::hash_* containers
use, traversing the elements is exactly equivalent to doing
so with an std::list, hence the simple visualizer code for
stdext::hash_map you brought in here yesterday. With b), however,
traversing all elements implies the following:

  1. Going to the beginning of the hashed index's bucket array
 (which is not the header node), whose elements points to the
  corresponding associated element lists.
  2. For each nonempty bucket, traverse the associated list.
  3. When finished with a bucket, hop through the bucket array
  to the next nonempty bucket.

In particular, note that the header here, unlike in ordered
and sequenced indices, cannot be used as the starting point
for the traversal journey.

Do you think the visualizer is powerful enough to run this
algorithm? If so, I can provide you with more details to begin
writing the stuff.

Random access indices are also harder than ordered and sequenced,
but I think it should be far simpler to support them than
hashed indices. Please ping me if you're willing to crack that
one.

> There is one more issue with hashed indices: the type names tend to get 
> so long, that when I use more than one index with hashed_unique, the 
> name gets cut in the half (some fixed string length...) and fails to 
> match the pattern (there're loads of boost::mpl::na or something like 
> this). If there's no compiler flag to set, this will probably be a 
> limitation.

There's some techniques users can apply to reduce symbol name
lengths, as explained at

http://boost.org/libs/multi_index/doc/compiler_specifics.html#symbol_reduction

but there's little else to be done from your side in the case
the user has not applied some of these techniques of her
own accord.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo