interest in a stateful pointer library?

newer
Boost Serialization: Serializing...

Hans Dembinski

2 Oct 2017 2 Oct '17

8:46 a.m.

Hi everyone, I wrote a variant of std::unique_ptr, called tagged_ptr, which allows safe read/write access to a customisable number of bits in the pointer variable. You can find the library on github: https://github.com/HDembinski/stateful_pointer You can use those bits to store extra state in the pointer variable at no extra space cost. I did some benchmarks to show that the computational overhead required for the bit manipulation is also negligible. One needs little imagination to find good use for those bits. As a proof of principle, I wrote an STL compatible string class which has the size of const char*, but can store up to 7 ASCII characters (on a 64 bit system) without allocating any memory on the heap (aka small string optimisation). The string class is also included in the library. To make this work, I use one of the bits in the pointer variable to recognise whether the variable should be interpreted as a pointer or as a char array. The Stateful Pointer library is C++11, header-only, and AFAIK platform-independent (in theory, this has not been tested so far). To create pointers which allow one to use a certain number of bits for other purposes, I rely on Boost.Align to allocate aligned memory. How does it work? Aligned memory, as the name implies, does not point to any address in memory, only certain addresses are allowed. For example, a two-byte aligned memory block can only have an even address. Therefore the lowest bit in the address is always zero. Since the bit is guaranteed to be zero, we can use it to store something else and mask it to zero whenever we need to dereference the pointer. I think this is a generally useful class to have in Boost, so is there some interest in polishing it up in a review process? Best regards, Hans

Show replies by date

Christof Donat

2 Oct 2 Oct

10:37 a.m.

Hi, Am 02.10.2017 10:46, schrieb Hans Dembinski via Boost:

...

I wrote a variant of std::unique_ptr, called tagged_ptr, which allows safe read/write access to a customisable number of bits in the pointer variable. You can find the library on github:

https://github.com/HDembinski/stateful_pointer

I don't have a current use, but I think, it might be very useful in memory constraint environments.

...

One needs little imagination to find good use for those bits. As a proof of principle, I wrote an STL compatible string class which has the size of const char*, but can store up to 7 ASCII characters (on a 64 bit system) without allocating any memory on the heap (aka small string optimisation).

I understand, that this is only an example, but... I have not yet written a STL compatible string class, nor have I taken my time to look at existing implementations. Therefore I might be completely wrong. In my understanding, it would contain a size_t together with the const char*, so it will always be 16 bytes on a 64 Bit system and you can have up to 14 chars plus one null byte without heap allocation. Christof

Hans Dembinski

9 Oct 9 Oct

9:32 a.m.

Hi Christof, thank you for your reply and sorry for the late answer. In the meantime I had some interesting discussion on Reddit about this library.

...

On 2. Oct 2017, at 12:37, Christof Donat via Boost wrote:

Am 02.10.2017 10:46, schrieb Hans Dembinski via Boost:

...
I wrote a variant of std::unique_ptr, called tagged_ptr, which allows safe read/write access to a customisable number of bits in the pointer variable. You can find the library on github: https://github.com/HDembinski/stateful_pointer

I don't have a current use, but I think, it might be very useful in memory constraint environments.

Please have a look at the updated README on Github. tagged_ptr uses Boost.Align to get pointers with a special bit pattern which allows to perfectly predict these bits and therefore use them to hold state. I thought that this trick was platform-independent, since Boost.Align seems platform-independent, but smart people on Reddit showed me that I am relying on undefined behaviour here. It turns out that the conversion between memory address and integers may not be as trivial as it is on a x86 machine, and then this trick would fail. This is kinda sad, because the library is much less useful if tagged_ptr is not guaranteed to work on all platforms now and in the future. Just assume you use this in a large project and rely on it, and then a new processor generation comes out where tagged_ptr does not work anymore. That being said it is probably still useful for special projects, but not something to put in Boost. :(

...

...
One needs little imagination to find good use for those bits. As a proof of principle, I wrote an STL compatible string class which has the size of const char*, but can store up to 7 ASCII characters (on a 64 bit system) without allocating any memory on the heap (aka small string optimisation).

I understand, that this is only an example, but...

I have not yet written a STL compatible string class, nor have I taken my time to look at existing implementations. Therefore I might be completely wrong. In my understanding, it would contain a size_t together with the const char*, so it will always be 16 bytes on a 64 Bit system and you can have up to 14 chars plus one null byte without heap allocation.

On my system (gcc stdlib), std::string has the size of 32 bytes = 256 bits. That's 64 bits for a const char* pointer, 64 bits to hold the size_t, 64 bits to hold the allocator instance, and another 64 bits that I don't know what they are good for. I haven't looked into the gcc implementation, so I don't know whether it uses small string optimisation. The boost::container::string has a size of 24 bytes, which is enough to hold pointer, size, and allocator. The boost::container::string does small string optimisation. It almost has the size you expected, you just forgot the space required for the allocator instance. I did not look into the implementation closely, but I guess it can use up to 15 bytes to store a small string without doing a heap allocation. The string I wrote is only 8 bytes = 64 bits. In small string mode, it holds the (small) size in the lowest bits and uses the rest of the bits to hold up to 7 chars. In normal mode, the size is stored at the beginning in the allocated memory, so that I do not need to store it inside the string class. I do not support allocators with state, thus I can get away without holding an instance of the allocator. std::allocator is an example of a stateless allocator which would work with this class. Anyway, since tagged_ptr is not really portable, neither is this string. That's a bummer, because it would be great to have a portable tiny string class. It just does the optimisation a bit differently than other string classes, more focused on minimal size. Being able to chose between different optimisations by replacing the string class in a project is nice. Best regards, Hans

Peter Dimov

9:37 a.m.

Hans Dembinski wrote:

...

This is kinda sad, because the library is much less useful if tagged_ptr is not guaranteed to work on all platforms now and in the future. Just assume you use this in a large project and rely on it, and then a new processor generation comes out where tagged_ptr does not work anymore. That being said it is probably still useful for special projects, but not something to put in Boost. :(

On the contrary, this is exactly why it needs to be put in Boost - to isolate the platform-specific differences behind a portable interface.

...

but smart people on Reddit showed me that I am relying on undefined behaviour here.

Out of curiosity, what's the specific problem that was pointed out? What behavior is undefined?

Arvid Norberg

10:59 a.m.

On Mon, Oct 9, 2017 at 11:37 AM, Peter Dimov via Boost < boost@lists.boost.org> wrote:

...

Hans Dembinski wrote:

This is kinda sad, because the library is much less useful if tagged_ptr

...
is not guaranteed to work on all platforms now and in the future. Just assume you use this in a large project and rely on it, and then a new processor generation comes out where tagged_ptr does not work anymore. That being said it is probably still useful for special projects, but not something to put in Boost. :(

On the contrary, this is exactly why it needs to be put in Boost - to isolate the platform-specific differences behind a portable interface.

but smart people on Reddit showed me that I am relying on undefined

...
behaviour here.

Out of curiosity, what's the specific problem that was pointed out? What behavior is undefined?

Without having read the reddit thread, I would expect this library to only depend on *implementation defined* behavior. Namely the mapping of pointer to integer conversions [1]. A pointer can be explicitly converted to any integral type large enough to

...

hold it. The mapping function is implementation-defined.

[ Note: It is intended to be unsurprising to those who know the addressing

...

structure of the underlying machine. — end note]

That note seem to indicate that only in the case of exotic hardware would the assumptions about what aligned addresses look like be invalid. -- Arvid Norberg [1] http://eel.is/c++draft/expr#reinterpret.cast-4

Hans Dembinski

3:12 p.m.

Hi Arvid,

...

On 9. Oct 2017, at 12:59, Arvid Norberg via Boost wrote:

Without having read the reddit thread, I would expect this library to only depend on *implementation defined* behavior. Namely the mapping of pointer to integer conversions [1].

A pointer can be explicitly converted to any integral type large enough to

...
hold it. The mapping function is implementation-defined.

[ Note: It is intended to be unsurprising to those who know the addressing

...
structure of the underlying machine. — end note]

That note seem to indicate that only in the case of exotic hardware would the assumptions about what aligned addresses look like be invalid.

yes, that was also the conclusion in the Reddit thread, thank you for clarifying this. We cannot know whether the library might be used on exotic hardware, right? Then we would need a fallback solution which relies only on standard behavior for such a platform. The question is what kind of fallback solution one could offer. If the library does not guarantee that tagged_ptr always has the size of void*, then one could fall back to something like this template struct tagged_ptr_fallback { T* ptr; [smallest integral type that can hold Nbits] bits; }; There is already a hidden tagged_ptr in Boost, see lockfree/detail/tagged_ptr.hpp, which uses this kind of fallback. The bit-harvesting there follows a different approach, btw. which is relies on details of the x86_64 hardware and only works there. I am not an expert, but I think it exploits that some part of the address space is reserved for the kernel. This actually has advantages over my approach of using aligned memory; the number of harvested bits is quite large and it works with any allocator. I just thought that the trick of using aligned memory would work on more platforms. Best regards, Hans

Hans Dembinski

12:34 p.m.

Hi Peter,

...

On 9. Oct 2017, at 11:37, Peter Dimov via Boost wrote:

...
This is kinda sad, because the library is much less useful if tagged_ptr is not guaranteed to work on all platforms now and in the future. Just assume you use this in a large project and rely on it, and then a new processor generation comes out where tagged_ptr does not work anymore. That being said it is probably still useful for special projects, but not something to put in Boost. :(

On the contrary, this is exactly why it needs to be put in Boost - to isolate the platform-specific differences behind a portable interface.

ok, if you put it that way, I will not disagree. :) It would be nice to have a portable interface for a tagged_ptr. I am not sure, what kind of guarantees this pointer could offer for a new platform that is not supported yet. Boost.Align has a nice fallback solution for not-yet-supported systems. I thought I could ride piggy-back on that feature with this library, but as the Redditors pointed out, it is not that simple.

...

...
but smart people on Reddit showed me that I am relying on undefined behaviour here.

Out of curiosity, what's the specific problem that was pointed out? What behavior is undefined?

I was pointed to this answer on SO: https://stackoverflow.com/questions/34737737/relation-between-numeric-repres... I am relying on two things: - memory addresses map trivially to consecutive integers - the address of aligned memory allocated by Boost.Align always converts into an integer that is a multiple of the alignment value Neither seems to be guaranteed by the standard. The conversion from memory address to integer is an implementation detail, the SO answer gives examples of "exotic" mappings which are conceivable (not that there is any machine out there which actually does it this way). Concerning the second point, there is no guarantee that the integer is an exact multiple of the alignment value, there could be an offset, too. The offset could depend on the platform, which would be a minor problem for predictability, or even on the memory segment from which the memory was allocated… then it would be impossible to predict and tagged_ptr falls flat. Best regards, Hans

Peter Dimov

2:42 p.m.

Hans Dembinski wrote:

...

...
Out of curiosity, what's the specific problem that was pointed out? What behavior is undefined?

I was pointed to this answer on SO: https://stackoverflow.com/questions/34737737/relation-between-numeric-repres...

I am relying on two things: - memory addresses map trivially to consecutive integers - the address of aligned memory allocated by Boost.Align always converts into an integer that is a multiple of the alignment value

Neither seems to be guaranteed by the standard. The conversion from memory address to integer is an implementation detail, the SO answer gives examples of "exotic" mappings which are conceivable (not that there is any machine out there which actually does it this way).

As far as I can see, you're storing an uintptr_t. This is not undefined. The only thing you're missing is an ASSERT that the tag_mask part is 0 after the reinterpret_cast. Yes, this is not guaranteed to work in principle, but if it does, it's not undefined. Your converting constructor seems broken though. Even if we put aside the problem that destroying U* is not the same as destroying T*, you have to convert to T* first, then to U*, then back to uintptr_t. (And assert here as well, as the new value is no longer guaranteed to have a tag_mask of 0.) Stepping back a bit, I would have expected a tagged_ptr to be a low-level component that just adds tag bits to a pointer, rather than being responsible for allocating and destroying objects and arrays. Perhaps the way you've implemented it makes it more useful for certain scenarios though, I'm not sure.

Hans Dembinski

3:50 p.m.

...

On 9. Oct 2017, at 16:42, Peter Dimov via Boost wrote:

Hans Dembinski wrote:

...
...
Out of curiosity, what's the specific problem that was pointed out? What > behavior is undefined?

I was pointed to this answer on SO: https://stackoverflow.com/questions/34737737/relation-between-numeric-repres...

I am relying on two things: - memory addresses map trivially to consecutive integers - the address of aligned memory allocated by Boost.Align always converts into an integer that is a multiple of the alignment value

Neither seems to be guaranteed by the standard. The conversion from memory address to integer is an implementation detail, the SO answer gives examples of "exotic" mappings which are conceivable (not that there is any machine out there which actually does it this way).

As far as I can see, you're storing an uintptr_t. This is not undefined. The only thing you're missing is an ASSERT that the tag_mask part is 0 after the reinterpret_cast. Yes, this is not guaranteed to work in principle, but if it does, it's not undefined.

Ok, yes, but tripping an assert (or raising a compile-time error) on an unsupported platform is not a nice solution, I think. Wouldn't it be better to provide a fallback that at least works somehow without crashing build or runtime? I talked a bit about that in my reply to Arvid.

...

Your converting constructor seems broken though. Even if we put aside the problem that destroying U* is not the same as destroying T*, you have to convert to T* first, then to U*, then back to uintptr_t. (And assert here as well, as the new value is no longer guaranteed to have a tag_mask of 0.)

Maybe you are right, I am not sure. I copied the declaration from std::unique_ptr. This should only compile if U* and T* are convertible, e.g. if T is the base of U. AFAIU this is supposed to mimic what one can do with raw pointers: auto d = new Derived(); // inherits from Base with virtual dtor auto b = static_cast(d); // still the same physical address, so should map to the same integer, no? delete b; // correctly deletes Derived using vtable

...

Stepping back a bit, I would have expected a tagged_ptr to be a low-level component that just adds tag bits to a pointer, rather than being responsible for allocating and destroying objects and arrays. Perhaps the way you've implemented it makes it more useful for certain scenarios though, I'm not sure.

I made tagged_ptr mimic std::unique_ptr, because I rely on having full control over (de)allocation to harvest the low bits of the pointer. I wanted to have an interface which makes sure that I cannot pass a pointer that has been wrongly allocated. I thought the easiest way to do that is to make a smart pointer which can only be created via a "make_tagged" factory. Since std::unique_ptr supports objects and arrays, I also tried to support both. Best regards, Hans

Peter Dimov

3:54 p.m.

Hans Dembinski wrote:

...

Ok, yes, but tripping an assert (or raising a compile-time error) on an unsupported platform is not a nice solution, I think. Wouldn't it be better to provide a fallback that at least works somehow without crashing build or runtime?

Once you encounter the platform where it doesn't work, you'll have to provide a fallback, yes. Before that, not.

...

auto d = new Derived(); // inherits from Base with virtual dtor auto b = static_cast(d); // still the same physical address, so should map to the same integer, no?

No. It's neither the same physical address in general, nor is it required to map to the same integer even if it were.

...

delete b; // correctly deletes Derived using vtable

If Base has a vtable, yes. You're not asserting that though.

...

I made tagged_ptr mimic std::unique_ptr, because I rely on having full control over (de)allocation to harvest the low bits of the pointer.

tagged_unique_ptr then perhaps?

Glen Fernandes

11:42 a.m.

On Mon, Oct 9, 2017 at 5:32 AM, Hans Dembinski wrote:

...

Please have a look at the updated README on Github. tagged_ptr uses Boost.Align to get pointers with a special bit pattern which allows to perfectly predict these bits and therefore use them to hold state. I thought that this trick was platform-independent, since Boost.Align seems platform- independent, but smart people on Reddit showed me that I am relying on undefined behaviour here. It turns out that the conversion between memory address and integers may not be as trivial as it is on a x86 machine, and then this trick would fail.

If you're referring to the implementation of boost::alignment::align, it is platform-dependent. i.e. That is one of the reasons we wanted it in a Boost library: So that if there is a C++ implementation which requires a different platform-dependent solution, then boost::alignment::align will be updated to support that too. Glen

Hans Dembinski

12:06 p.m.

Hi Glen,

...

On 9. Oct 2017, at 13:42, Glen Fernandes via Boost wrote:

On Mon, Oct 9, 2017 at 5:32 AM, Hans Dembinski wrote:

...
Please have a look at the updated README on Github. tagged_ptr uses Boost.Align to get pointers with a special bit pattern which allows to perfectly predict these bits and therefore use them to hold state. I thought that this trick was platform-independent, since Boost.Align seems platform- independent, but smart people on Reddit showed me that I am relying on undefined behaviour here. It turns out that the conversion between memory address and integers may not be as trivial as it is on a x86 machine, and then this trick would fail.

If you're referring to the implementation of boost::alignment::align, it is platform-dependent. i.e. That is one of the reasons we wanted it in a Boost library: So that if there is a C++ implementation which requires a different platform-dependent solution, then boost::alignment::align will be updated to support that too.

ok, thanks for clarifying this. I understood that, but I was not very clear in my statement. AFAIU, Boost.Align also has a fall-back solution for unsupported systems, where more memory is allocated than necessary to assure the alignment. In that sense the library is "platform-independent" in that it would always do what it is supposed to do, although perhaps not as efficiently as possible. Best regards, Hans

Glen Fernandes

11:50 a.m.

On Mon, Oct 9, 2017 at 5:32 AM, Hans Dembinski wrote:

...

Please have a look at the updated README on Github. tagged_ptr uses Boost.Align to get pointers with a special bit pattern which allows to perfectly predict these bits and therefore use them to hold state. I thought that this trick was platform-independent, since Boost.Align seems platform- independent,

Note that the specific functions that you are using from Boost.Align (boost::alignment::aligned_alloc and boost::alignment::aligned_free) are portable and well-defined on every C++ implementation that has either a function for those, or every C++11 and above implementation which provides std::align (since boost::alignment::align will use a conforming std::align if one exists). On C++ implementations which have neither, then it falls back to the custom (platform-dependent) implementation in boost::alignment::align. Glen

Olaf van der Spek

10 Oct 10 Oct

12:49 p.m.

On Mon, Oct 9, 2017 at 11:32 AM, Hans Dembinski via Boost wrote:

...

On my system (gcc stdlib), std::string has the size of 32 bytes = 256 bits. That's 64 bits for a const char* pointer, 64 bits to hold the size_t, 64 bits to hold the allocator instance, and another 64 bits that I don't know what they are good for.

Capacity? -- Olaf

Ion Gaztañaga

9 Oct 9 Oct

10:17 p.m.

On 02/10/2017 10:46, Hans Dembinski via Boost wrote:

...

Hi everyone,

I wrote a variant of std::unique_ptr, called tagged_ptr, which allows safe read/write access to a customisable number of bits in the pointer variable. You can find the library on github:

https://github.com/HDembinski/stateful_pointer

You can use those bits to store extra state in the pointer variable at no extra space cost. I did some benchmarks to show that the computational overhead required for the bit manipulation is also negligible.

One needs little imagination to find good use for those bits. As a proof of principle, I wrote an STL compatible string class which has the size of const char*, but can store up to 7 ASCII characters (on a 64 bit system) without allocating any memory on the heap (aka small string optimisation). The string class is also included in the library. To make this work, I use one of the bits in the pointer variable to recognise whether the variable should be interpreted as a pointer or as a char array.

The Stateful Pointer library is C++11, header-only, and AFAIK platform-independent (in theory, this has not been tested so far). To create pointers which allow one to use a certain number of bits for other purposes, I rely on Boost.Align to allocate aligned memory.

How does it work? Aligned memory, as the name implies, does not point to any address in memory, only certain addresses are allowed. For example, a two-byte aligned memory block can only have an even address. Therefore the lowest bit in the address is always zero. Since the bit is guaranteed to be zero, we can use it to store something else and mask it to zero whenever we need to dereference the pointer.

I think this is a generally useful class to have in Boost, so is there some interest in polishing it up in a review process?

There is a related (not a replacement) utility in Boost.Intrusive, used to store additional bits in red-black and AVL trees: http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp It assumes the conversion between pointers and integers preserves the alignment in the lower bits of the integer. There are some esoteric platforms where this might not be true, but Boost.Intrusive does not support them. Best, Ion

Hans Dembinski

10 Oct 10 Oct

8:02 a.m.

Hi Ion,

...

On 10. Oct 2017, at 00:17, Ion Gaztañaga via Boost wrote:

There is a related (not a replacement) utility in Boost.Intrusive, used to store additional bits in red-black and AVL trees:

http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp

It assumes the conversion between pointers and integers preserves the alignment in the lower bits of the integer. There are some esoteric platforms where this might not be true, but Boost.Intrusive does not support them.

ah, thanks, I didn't know that one. I thought Boost.Intrusive was about containers only, so I would never have looked there. Seeing how pointer_plus_bits is used in Boost.Intrusive, it seems that it is not really intended for users, and serves more as an utility for the library. It is not advertised in the documentation either. Best regards, Hans

Ion Gaztañaga

11 Oct 11 Oct

8:21 a.m.

On 10/10/2017 10:02, Hans Dembinski via Boost wrote:

...

Hi Ion,

...
On 10. Oct 2017, at 00:17, Ion Gaztañaga via Boost wrote:

There is a related (not a replacement) utility in Boost.Intrusive, used to store additional bits in red-black and AVL trees:

http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp

It assumes the conversion between pointers and integers preserves the alignment in the lower bits of the integer. There are some esoteric platforms where this might not be true, but Boost.Intrusive does not support them.

ah, thanks, I didn't know that one. I thought Boost.Intrusive was about containers only, so I would never have looked there. Seeing how pointer_plus_bits is used in Boost.Intrusive, it seems that it is not really intended for users, and serves more as an utility for the library. It is not advertised in the documentation either.

Right now it's used internally and shared with Boost.Interprocess. But obviously we could make them public. The main point is that an utility to embed bits in pointers could consider also fancy pointers. Best, Ion

Hans Dembinski

9:11 a.m.

Hi Ion,

...

On 11. Oct 2017, at 10:21, Ion Gaztañaga via Boost wrote:

On 10/10/2017 10:02, Hans Dembinski via Boost wrote:

...
Hi Ion,

...
On 10. Oct 2017, at 00:17, Ion Gaztañaga via Boost wrote:

There is a related (not a replacement) utility in Boost.Intrusive, used to store additional bits in red-black and AVL trees:

http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp

It assumes the conversion between pointers and integers preserves the alignment in the lower bits of the integer. There are some esoteric platforms where this might not be true, but Boost.Intrusive does not support them. ah, thanks, I didn't know that one. I thought Boost.Intrusive was about containers only, so I would never have looked there. Seeing how pointer_plus_bits is used in Boost.Intrusive, it seems that it is not really intended for users, and serves more as an utility for the library. It is not advertised in the documentation either.

Right now it's used internally and shared with Boost.Interprocess. But obviously we could make them public. The main point is that an utility to embed bits in pointers could consider also fancy pointers.

Yes, you are right. I think that's the way to go. I am still a bit puzzled how pointer_plus_bits is used in Boost.Intrusive. As far as I can see by reading the code, in boost/intrusive/detail/rbtree_node.hpp and boost/intrusive/detail/avltree_node.hpp it is simply assumed that one or two bits from the pointer can be harvested. There is no platform-check and no general fallback solution. If I used this code on a platform where the assumptions related to bit harvesting are violated, I would trip a BOOST_INTRUSIVE_INVARIANT_ASSERT at runtime instead of crashing, but I could not run the software on such a system. Which platforms are supported by Boost.Intrusive? Does it work on an ARM processor? The documentation does not say anything about that. That is a bit scary, to be honest. I always assumed that Boost libraries are platform-independent unless explicitly stated otherwise. Best regards, Hans

Ion Gaztañaga

6:50 p.m.

On 11/10/2017 11:11, Hans Dembinski via Boost wrote:

...

Hi Ion,

...
On 11. Oct 2017, at 10:21, Ion Gaztañaga via Boost wrote:

On 10/10/2017 10:02, Hans Dembinski via Boost wrote:

...
Hi Ion,

...
On 10. Oct 2017, at 00:17, Ion Gaztañaga via Boost wrote:

There is a related (not a replacement) utility in Boost.Intrusive, used to store additional bits in red-black and AVL trees:

http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp http://www.boost.org/doc/libs/1_65_1/boost/intrusive/pointer_plus_bits.hpp

It assumes the conversion between pointers and integers preserves the alignment in the lower bits of the integer. There are some esoteric platforms where this might not be true, but Boost.Intrusive does not support them. ah, thanks, I didn't know that one. I thought Boost.Intrusive was about containers only, so I would never have looked there. Seeing how pointer_plus_bits is used in Boost.Intrusive, it seems that it is not really intended for users, and serves more as an utility for the library. It is not advertised in the documentation either.

Right now it's used internally and shared with Boost.Interprocess. But obviously we could make them public. The main point is that an utility to embed bits in pointers could consider also fancy pointers.

Yes, you are right. I think that's the way to go.

I am still a bit puzzled how pointer_plus_bits is used in Boost.Intrusive. As far as I can see by reading the code, in boost/intrusive/detail/rbtree_node.hpp and boost/intrusive/detail/avltree_node.hpp it is simply assumed that one or two bits from the pointer can be harvested. There is no platform-check and no general fallback solution. If I used this code on a platform where the assumptions related to bit harvesting are violated, I would trip a BOOST_INTRUSIVE_INVARIANT_ASSERT at runtime instead of crashing, but I could not run the software on such a system.

Which platforms are supported by Boost.Intrusive? Does it work on an ARM processor? The documentation does not say anything about that. That is a bit scary, to be honest. I always assumed that Boost libraries are platform-independent unless explicitly stated otherwise.

Nodes use the trait "max_pointer_plus_bits". If N bits are needed and node type's alignment is at least 2^N bytes, then pointer_plus_bits is used, otherwise, normal pointers are used. An static assert could and maybe should go in pointer_traits, but the check is done at compile time before being used. Best, Ion

2603

Age (days ago)

2612

Last active (days ago)

List overview

Download

18 comments

7 participants

participants (7)

Arvid Norberg
Christof Donat
Glen Fernandes
Hans Dembinski
Ion Gaztañaga
Olaf van der Spek
Peter Dimov