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

From: Filip Konvička (filip.konvicka_at_[hidden])
Date: 2007-06-01 18:25:18

>> 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
>   
It gives 3. I've had a bad feeling about simulating 
multi_index_container structure before, and now it finally failed :-) I 
assume that it is because of structure alignment. When I did

 (($T2*)(((char*)&$c)-4))->node_count

it worked well (i.e. assuming that the first member takes 4 bytes and 
casting back to the multi_index_container itself). That "4" can be 
probably calculated automatically, which involves the nasty trick with 
member pointers that I talked about earlier. But that involved a static 
int constant, so I'll stick to hard-coded 4 for now...
> 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.
>   
OK, I looked into buckets.spc.data_, visualized it as an array (I assume 
that buckets.spc.n_ is the number of buckets), and I got some 
hashed_index_node_impl nodes. I see that in some nodes, next_ points 
back to the node (empty bucket?), and with others there seems to be 
something more.

I thought about the algorithm you describe, and I think that this is 
beyond what we can do (there is some #if ... #else ... stuff, but that 
is not recursive...). What I think we could do instead is to visualize 
the hashtable instead - display the buckets and their respective 
contents. A problem here might be that I don't know whether bucket item 
count is known. But let's deal with this later... (it's said that 
there's some anti-loop functionality in visualizer's list iterator, so 
let's see).

> 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.
>   
If you can please tell me some info about the buckets.spc.data_ fields 
(if they really are the buckets, of course). What are the array members? 
hashed_index_node_impl?
> 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.
>   
Sure, I'll look at them and ask.
>> 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.
>   
Thanks for the info, I'll try the "intrusive" approach and see what it 
does to the visualizer (there will be probably a problem with the 
header_holder pattern...). (However....when a user does this, she can 
also adjust the visualizer, right? So I give this a low priority....:-))
Anyway, most of the time using the macros will suffice (that's what I'll 
do in my project).

Cheers,
Filip