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