Added boost::multi_index hashed_unique and hashed_non_unique indexes support

[redboltz]

I implemented printer for hashed indexes.

See https://stackoverflow.com/questions/51549875/how-to-see-boostmulti-index-hashed-indexs-data-using-gdb

Note:

        self.index_offset_for_hash = head_node.type.sizeof - (v.idx + 1) * 0x10

I found the value 0x10 my try and error. I'm not 100% sure it is portable. But this works fine on my environment.

[redboltz]

Now 0x10 is removed. It is replaced with ptr_size * 2. It works well on both 32bit and 64bit environment.

[redboltz]

travis-ci failed. It seems that boost tarball unpacking error. I guess that it is temporary network trouble.

[mbalabin]

Hi! First of all, thank you for contributing!

I restarted the testsuite and it worked. Seems that it was indeed an intermittent error.

I do not see any immediate problems with the code. But I have an additional request concerning your PR. Usually, it is required that any PR is accompanied with unit tests. But in fact, boost multi-index printers are not currently covered by unit tests at all. It would be highly beneficial for the project if you could improve the test coverage by adding a few tests for multi-index containers with various index types. Since you have some hands-on experience with multi-index containers, it probably will not be a big deal for you. If you have any questions about test structure, I would be glad to answer any questions.

[redboltz]

Thank you for the comment! I will add unit tests for multi_index. It will cover not only hashed_index but also sequenced and ordered indexes.

[redboltz]

I implemented tests for multi_index. I noticed that multi_index's internal hashed_index structure is different between the version < 1.56.0 and later. So I skipped older versions test.

[redboltz]

I updated the pull request. I removed as_multi_index() and use C++11 way of type aliasing.

[mbalabin]

Awesome! Now, thanks to you, all the printers are covered by tests. Things tend to break rather often. Again, thanks for the great job.

[joaquintides]

I can't quite follow this code, but I'm afraid it might be failing for a non-unique hashed index when there's three or more elements with the same value: in this case, blindly following the prior_ pointer will loop around the group of equivalent elements (see figure 4 here).

[redboltz]

@joaquintides , I tested the following code.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>

#include <iostream>
#include <string>

namespace mi = boost::multi_index;

struct t_hash{};
struct t_z{};
struct t_seq{};
struct t_y{};

using elems = mi::multi_index_container<
    int,
    mi::indexed_by<
        mi::hashed_non_unique<
            mi::tag<t_hash>,
            mi::identity<int>
        >
    >
>;

int main() {
    elems es;
    for (int i = 0; i != 100; ++i) {
        es.insert(i);
    }
    return 0;
}

And got the following result.

Breakpoint 1, main () at mi_int.cpp:33
33          return 0;
(gdb) p es
$1 = boost::multi_index_container<int, indexed_by<hashed_non_unique<tag<t_hash>, identity<int>>>>[idx=0] = {                                                                                  
  [0x555555771f70] = 99,
  [0x555555771f50] = 98,
  [0x555555771f30] = 97,
  [0x5555557706d0] = 52,
  [0x5555557706b0] = 51,
  [0x555555770690] = 50,
  [0x555555770670] = 49,
  [0x555555770650] = 48,
  [0x555555770630] = 47,
  [0x555555770610] = 46,
  [0x5555557705f0] = 45,
  [0x5555557705d0] = 44,
  [0x5555557705b0] = 43,
  [0x555555770590] = 42,
  [0x555555770570] = 41,
  [0x555555770550] = 40,
  [0x555555770530] = 39,
  [0x555555770510] = 38,
  [0x5555557704f0] = 37,
  [0x5555557704d0] = 36,
  [0x5555557704b0] = 35,
  [0x555555770490] = 34,
  [0x555555770470] = 33,
  [0x555555770450] = 32,
  [0x555555770430] = 31,
  [0x555555770410] = 30,
  [0x5555557703f0] = 29,
  [0x5555557703d0] = 28,
  [0x5555557703b0] = 27,
  [0x555555770390] = 26,
  [0x555555770370] = 25,
  [0x555555770350] = 24,
  [0x555555770330] = 23,
  [0x555555770310] = 22,
  [0x5555557702f0] = 21,
  [0x5555557702d0] = 20,
  [0x5555557702b0] = 19,
  [0x555555770290] = 18,
  [0x555555770270] = 17,
  [0x555555770250] = 16,
  [0x555555770230] = 15,
  [0x555555770210] = 14,
  [0x5555557701f0] = 13,
  [0x5555557701d0] = 12,
  [0x5555557701b0] = 11,
  [0x555555770190] = 10,
  [0x555555770170] = 9,
  [0x555555770150] = 8,
  [0x555555770130] = 7,
  [0x555555770110] = 6,
  [0x5555557700f0] = 5,
  [0x5555557700d0] = 4,
  [0x5555557700b0] = 3,
  [0x555555770090] = 2,
  [0x555555770070] = 1,
  [0x555555770050] = 0,
  [0x555555770d70] = 53,
  [0x555555770d90] = 54,
  [0x555555770db0] = 55,
  [0x555555770dd0] = 56,
  [0x555555770df0] = 57,
  [0x555555770e10] = 58,
  [0x555555770e30] = 59,
  [0x555555770e50] = 60,
  [0x555555770e70] = 61,
  [0x555555770e90] = 62,
  [0x555555770eb0] = 63,
  [0x555555770ed0] = 64,
  [0x555555770ef0] = 65,
  [0x555555770f10] = 66,
  [0x555555770f30] = 67,
  [0x555555770f50] = 68,
  [0x555555770f70] = 69,
  [0x555555770f90] = 70,
  [0x555555770fb0] = 71,
  [0x555555770fd0] = 72,
  [0x555555770ff0] = 73,
  [0x555555771010] = 74,
  [0x555555771030] = 75,
  [0x555555771050] = 76,
  [0x555555771070] = 77,
  [0x555555771090] = 78,
  [0x5555557710b0] = 79,
  [0x5555557710d0] = 80,
  [0x5555557710f0] = 81,
  [0x555555771110] = 82,
  [0x555555771130] = 83,
  [0x555555771150] = 84,
  [0x555555771170] = 85,
  [0x555555771190] = 86,
  [0x5555557711b0] = 87,
  [0x5555557711d0] = 88,
  [0x5555557711f0] = 89,
  [0x555555771210] = 90,
  [0x555555771230] = 91,
  [0x555555771250] = 92,
  [0x555555771270] = 93,
  [0x555555771290] = 94,
  [0x5555557712b0] = 95,
  [0x5555557712d0] = 96
}

It seems that all elements are printed, and no infinity loop happened.

[redboltz]

Sorry, I overlooked the same value. I will check using the same value.

[redboltz]

I've checked with the following code:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>

#include <iostream>
#include <string>

namespace mi = boost::multi_index;

struct elem {
    int x;
    int y;
};

struct t_x{};

using elems = mi::multi_index_container<
    elem,
    mi::indexed_by<
        mi::hashed_non_unique<
            mi::tag<t_x>,
            mi::member<elem, int, &elem::x>
        >
    >
>;

int main() {
    elems es;
    for (int i = 0; i != 10; ++i) {
        es.insert({1, i});
    }
    return 0;
}

Then got infinity loop (gdb automatically stopped) with not all elements.

(gdb) p es
$1 = boost::multi_index_container<elem, indexed_by<hashed_non_unique<tag<t_x>, member<elem, int, &elem::x>>>>[idx=0] = {
  [0x555555770050] = {
  x = 1,
  y = 0
},                    
  [0x555555770070] = {
  x = 1,
  y = 1
},                    
  [0x555555770090] = {
  x = 1,
  y = 2
},                    
  [0x5555557700b0] = {
  x = 1,
  y = 3
},                    
  [0x5555557700d0] = {
  x = 1,
  y = 4
},                    
  [0x5555557700f0] = {
  x = 1,
  y = 5
},                    
  [0x555555770110] = {
  x = 1,
  y = 6
},                    
  [0x555555770130] = {
  x = 1,
  y = 7
},                    
  [0x555555770150] = {
  x = 1,
  y = 8
},                    
  [0x555555770050] = {
  x = 1,
  y = 0
},                    
  [0x555555770070] = {
  x = 1,
  y = 1
},                    
  [0x555555770090] = {
  x = 1,
  y = 2
},                    
  [0x5555557700b0] = {
  x = 1,
  y = 3
},                    
  [0x5555557700d0] = {
  x = 1,
  y = 4
},   
  [0x5555557700f0] = {
  x = 1,
  y = 5                       
},
...

[redboltz]

I sent the #37 to fix it.

[mbalabin]

@joaquintides Could you lend us a hand with #37 review? Frankly speaking, I am not familiar with multi_index container's code at all (and even never used it).

[redboltz]

@joaquintides , plsease see the comment https://github.com/ruediger/Boost-Pretty-Printer/pull/37#issuecomment-409045719 I analyze the internal structure of hashedindex using gdb. (`next` is complicated, I've checked only needed by iteration).

http://1.bp.blogspot.com/-xrTNUJ9Wp00/UsmlHWqEqxI/AAAAAAAAAv4/yv4zr3CLG0E/s1600/boost.multiindex_dup_2.png The element of the picture has 3 attributes as follows:

prior_
next_
value

I noticed that the left most element is different from the actual implementation. In the picture, next_ points to the bottom element, but in the actual implementation, prior_ points to the bottom element.

My algorithm is based on the actual implementation.

[joaquintides]

Hi @redboltz. I've reviewed the code of #37 and taken a look at your slides and everything looks correct to me.

I noticed that the left most element is different from the actual implementation. In the picture, next points to the bottom element, but in the actual implementation, prior points to the bottom element.

Not sure what your understanding of the picture is; the leftmost element (painted pink) has its next pointer pointing to an entry in the bucket array (I guess this is what you call a "bottom element") because it happens to be the last element of its bucket. If this element were also the first in the sequence (which situation is simply not described in the picture, hence the empty prior pointer), its prior pointer would point to the end element. As it happens, your code does not deal with the bucket array at all (nor need it do so). Does this make things clearer to you?

[redboltz]

Hi @joaquintides , thank you for the comment. Now I understand little more.

In http://1.bp.blogspot.com/-xrTNUJ9Wp00/UsmlHWqEqxI/AAAAAAAAAv4/yv4zr3CLG0E/s1600/boost.multiindex_dup_2.png picture, the bottom square is buckets related structure. And the bottom square in my slide is a kind of dummy node in order to implement linked elements structure easier. They are different. At first, I had got confused. But now, I understand the difference.

As it happens, your code does not deal with the bucket array at all (nor need it do so).

As you mentioned, my approach doesn't treat buckets related structure. And in this purpose, printing all elements, I don't need to treat it.

Thank you for your review!