[v3] pb_ds fixes for debug mode, valgrind

[v3] pb_ds fixes for debug mode, valgrind

[Benjamin Kosnik]

[-- Attachment #1: Type: text/plain, Size: 1516 bytes --]


This aims to fix several longstanding memory issues in ext/pb_ds, and
the rest of the -D_GLIBCXX_DEBUG fails. I believe PR libstdc++/37144
and PR libstdc++/28457 apply. 

In a nutshell, these fixes were

1) ov_tree_map/join, remove debug join, adjust dtor
2) trie/rec_split, move to opportunistic interator usage
3) binary_heap/pop, adjust pop_heap usage, be caseful
about make_heap.

Anyway. This extension code is the last part of the docs not expressed
in doxygen and docbook. The docbook parts are in motion but the
conversion is not yet complete. Here's the doxygen part and some
refactoring based on it. There are several transformations and
reductions (null_type consolidation, template parameter reductions in
pat_trie, etc, etc, etc.) Perhaps I went too far with some
of the reductions and replacements in pat_trie_base, where I stripped
out the _Alloc parameter in a fit of pique. Enough with the rebinding!!!
It can be re-added, but it seems like the smarter ploy is to integrate
this with the trie traits class as a base in a more streamlined manner
with conscious attention being paid to minimizing the rebinds....

I'll be curious to see/do this as part of C++0x allocator work. 

There is a known issue WRT doxygen and figuring out
template-metaprogrammed base types, discussed here:
https://svn.boost.org/trac/boost/wiki/Guidelines/DoxygenGuidelines

Unfortunately this exists in abundance with this design.

tested x86_64/linux
make check
make check-debug
make check-performance
valgrind

-benjamin

[-- Attachment #2: 20110523-4.patch.bz2 --]
[-- Type: application/x-bzip, Size: 107610 bytes --]