[boost] [intrusive] New version uploaded. Review Request.

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2006-12-09 10:10:34

Hi to all,

I've just uploaded a new version of Intrusive, the intrusive container 
library. This is a major rewrite of the library, and includes many 
breaking changes, like class names, headers...

You can find the library in Boost.Vault,

http://boost-consulting.com/vault/index.php?&direction=0&order=&directory=Containers

or Boost.Sandbox CVS

These are some of the changes:

-> Added iset (intrusive set) container.

-> Added constant-time "size()" option to containers. This option adds a 
member to every container that's updated with every insertion/removal. 
This changes some complexity guarantees in the containers. This 
constant-time "size()" is optional and it's not enabled by default.

-> Added support for safe-mode and unsafe-mode hooks. In safe hooks each 
value's constructor puts the hook in a well-known state. Every time a 
value is inserted in the container, that state is checked. Every time a 
value is erased from the container, the hook is put in the well-known 
state. This can detect many programming errors when using intrusive 
containers. On the other hand, unsafe-mode hooks are faster and some 
container operations are have constant-time complexity when using unsafe 
hooks instead of linear-time complexity.

-> Added support for non-raw pointers. It's possible to build shared 
memory intrusive containers using offset_ptr<..> instead of raw pointers.

-> Added many member functions to intrusive containers. These members 
are missing operations that are present in their STL counterparts

-> Removed the additional one pointer size overhead from member hooks. 
Now member and derivation approach have the same size overhead for a value.

-> Added non "auto-unlink" hooks as default hooks. Auto-unlink hooks are 
also provided.

-> Optimized rbtree algorithms for "equal_range" and  "clone". Clone now 
offers support to clone trees using custom cloning functors. This allows 
recycling nodes in non-intrusive containers' operator=().

-> Added support for arbitrary keys in searches and insertion checks for 
associative containers (iset/imultiset). It's possible to use just an 
arbitrary key and a predicate comparing that key and the value inserted 
in the container in many functions: "find", "equal_range", "count", 
"lower_bound", "upper_bound". This allows searches without constructing 
a full value, something that in many cases, is quite expensive.

-> If pointer alignment is power of 2 (nearly always), Intrusive hooks 
offer 3 pointer size overhead instead of the typical 3 pointer + integer 
overhead. This is achieved using the least significant bit of the parent 
pointer as the "red/black" bit of the node.

-> Documentation has been improved and expanded. Added complexity 
guarantees for nearly all functions. Added a full quickbook/doxygen 
reference.

-> More tests. Tested in WinXP-Visual 7.1 and MinGW-gcc 4.1

I think that Intrusive can serve now as a good basis to build 
non-intrusive containers (STL-like, multi-index like...). I've rewritten 
Boost.Interprocess containers using Intrusive containers, and 
performance and size have been improved. I'm also experimenting with a 
new logarithmic allocation time best-fit memory algorithm for 
Interprocess, based on intrusive red-black trees.

I would like to request a review for the library to the review manager. 
While the library waits its review, I'm open to suggestions and 
improvements. If the library is accepted, my plan is to add more 
containers (pseudo-intrusive hash-set, maybe n-ary tress) and more 
functionality to the library.

Comments and suggestions welcome! Regards,

Ion