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