| James Kuyper <jameskuyper@alumni.caltech.edu>: Oct 19 06:01PM -0400 On 10/18/19 6:20 AM, Frederick Gotham wrote: > auto main(void) -> int > { > vector< uint8_t, MyAllocator<uint8_t> > v; The Allocator template argument of std::vector<> is supposed to meet the allocator requirements listed in 20.5.3.5. MyAllocator<> fails to meet the owverwhelming majority of those requirements. As far as I can see, the only one it actually meets is the one for value_type. It attempts, but fails, to meet the requirements for allocate() and deallocate(), but there should be a flag indicating whether or not buf has currently been allocated; allocate should check that flag, fail if it's set, and otherwise set it. deallocate() should clear the flag. Any one of the unmet requirements might cause your program to fail catastrophically, though that's not guaranteed. It's entirely feasible to meet those requirements with a class that manages a fixed block of memory with static storage duration, and which supports no more than a single allocation from that block - but this isn't how you do it. |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Oct 19 04:37AM +0200 On 18.10.2019 17:21, Paavo Helde wrote: >> "Vector is guaranteed to store all elements in contiguous locations" >> Is this true? > Yes, this has been true formally since 2003. I am surprised that you know that. In 2008 Herb Sutter corrected Andrew Koenig, who had implicitly opined that the contiguous buffer was not part of the vector abstraction, not something that one should rely on; <url: https://herbsutter.com/2008/04/07/cringe-not-vectors-are-guaranteed-to-be-contiguous/> It was a bit ironic since Andrew was secretary of the international C++ standardization committee for C++03, so if he didn't write the new vector requirement letter by letter then at least he copy and pasted it, and noted it in his "unofficial" list of C++03 changes. > For strings a similar guarantee was introduced in C++11. Or marginally less formally, at the Lillehammer meeting in 2005, as I recall. > practice. > Note there is a spatial case of std::vector<bool> which is still > contiguous, but does not have the same memory layout than a bool array[]. s/does not have/does not necessarily have/ or s/does not have/does not guarantee/ or s/does not have/does not in practice have/ - Alf |
| Soviet_Mario <SovietMario@CCCP.MIR>: Oct 19 11:16AM +0200 On 18/10/2019 17:21, Paavo Helde wrote: >> Is this true? > Yes, this has been true formally since 2003. For strings a > similar guarantee was introduced in C++11. but strings means the "descriptors", not the actual text data, right ? I mean, there is a further indirection before accessing the content, comparing to native types, or am I wrong ? If so, even if the array of pointers is monolythic, the true text data of each item should still be "sparse", or not ? -- 1) Resistere, resistere, resistere. 2) Se tutti pagano le tasse, le tasse le pagano tutti Soviet_Mario - (aka Gatto_Vizzato) |
| Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Oct 19 12:40PM +0100 On Sat, 19 Oct 2019 11:16:01 +0200 > wrong ? If so, even if the array of pointers is monolythic, > the true text data of each item should still be "sparse", or > not? Strings don't have "descriptors" so it is not clear (to me at least) what you mean. In any event the requirement for contiguous storage of string data is in §21.4.1/5 of C++11: "The char-like objects in a basic_string object shall be stored contiguously. That is, for any basic_string object s, the identity &*(s.begin() + n) == &*s.begin() + n shall hold for all values of n such that 0 <= n < s.size()." What is meant by "char-like objects" is set out in §21.4/1: "The class template basic_string describes objects that can store a sequence consisting of a varying number of arbitrary char-like objects with the first element of the sequence at position zero. Such a sequence is also called a "string" if the type of the char-like objects that it holds is clear from context. In the rest of this Clause, the type of the char-like objects held in a basic_string object is designated by charT". For std::string the char-like objects are of type char; for std::wstring they are of type wchar_t; and so on for std::u16string and std::u32string ... . |
| Paavo Helde <myfirstname@osa.pri.ee>: Oct 19 06:02PM +0300 On 19.10.2019 12:16, Soviet_Mario wrote: > comparing to native types, or am I wrong ? If so, even if the array of > pointers is monolythic, the true text data of each item should still be > "sparse", or not ? I was comparing std::string to std::vector<char>, not to std::vector<std::string>. The contiguousness guarantee for a std::string formalized in 2005 or 2011 just means that &s[0] + i == &s[i] inside a single string. Regarding std::vector<std::string>, the std::string objects in a std::vector are still contiguous, i.e. you can fetch out a std::string* pointer via data() and just use pointer arithmetic to access other std::string objects in the contiguous buffer. But you are right, this does not mean the character data of all those strings were contiguous or even in order in memory, typically they would be all scattered around. If the string implementation uses small string optimization and all strings are small enough, then the character arrays would reside directly inside the std::string objects, making them to be in order and somewhat "contiguous" in memory, but not quite. Regardless of implementation details it is physically impossible to have the character data of more than one std::string contiguous in memory, because the character array of each string has to be followed by a zero byte (to satisfy the const c_str() member function requirements), but this zero byte is not considered to be a part of the character data of the string. So the character arrays of two different strings cannot be contiguous, there must be at least one zero byte between them. |
| Bonita Montero <Bonita.Montero@gmail.com>: Oct 19 05:20AM +0200 For some other code I needed a special shared mutex that gives writers priority ver readers. With my shared mutex, when a writer wants to get access, all readers since then are allowed to continue and all new readers are deferred. So here's the code: #include <cstdint> #include <cassert> #include "cas.h" #include "semaphore.h" class wprio_shared_mutex { public: wprio_shared_mutex(); ~wprio_shared_mutex(); void lock_shared(); void unlock_shared(); void shared_to_write(); void lock_writer(); void write_to_shared(); void unlock_writer(); private: std::uint64_t m_atomic; // bit 0 - 20: readers // bit 21 - 41: waiting readers // bit 42 - 62: waiting writers // bit 61: writer-flag semaphore m_releaseReadersSem, m_releaseWriterSem; static unsigned const WAITING_READERS_BASE = 21, WAITING_WRITERS_BASE = 42, WRITER_FLAG_BASE = 63; static std::uint64_t const MASK21 = 0x1FFFFFu; static std::uint64_t const READERS_MASK = MASK21, WAITING_READERS_MASK = MASK21 << WAITING_READERS_BASE, WAITING_WRITERS_MASK = MASK21 << WAITING_WRITERS_BASE, WRITER_FLAG_MASK = (std::uint64_t)1 << WRITER_FLAG_BASE; static std::uint64_t const READER_VALUE = (std::uint64_t)1, WAITING_READERS_VALUE = (std::uint64_t)1 << WAITING_READERS_BASE, WAITING_WRITERS_VALUE = (std::uint64_t)1 << WAITING_WRITERS_BASE; static bool check( uint64_t flags ); }; inline bool wprio_shared_mutex::check( std::uint64_t flags ) { unsigned readers = (unsigned)(flags & MASK21), waitingReaders = (unsigned)((flags >> WAITING_READERS_BASE) & MASK21), waitingWriters = (unsigned)((flags >> WAITING_WRITERS_BASE) & MASK21), writerFlag = (unsigned)((flags >> WRITER_FLAG_BASE) & 1); if( readers && (waitingReaders || writerFlag) ) return false; if( waitingReaders && (readers || !writerFlag) ) return false; if( waitingWriters && !(writerFlag || readers) ) return false; if( writerFlag && readers ) return false; return true; } wprio_shared_mutex::wprio_shared_mutex() { m_atomic = 0; } wprio_shared_mutex::~wprio_shared_mutex() { assert(m_atomic == 0); } void wprio_shared_mutex::lock_shared() { using namespace std; for( uint64_t cmp = m_atomic, niu; ; cmp = niu ) { assert(check( cmp )); if( (cmp & WRITER_FLAG_MASK) == 0 ) { assert((cmp & READERS_MASK) != READERS_MASK); if( (niu = CAS( m_atomic, cmp, cmp + READER_VALUE )) == cmp ) return; } else { assert((cmp & WAITING_READERS_MASK) != WAITING_READERS_MASK); if( (niu = CAS( m_atomic, cmp, cmp + WAITING_READERS_VALUE )) == cmp ) { m_releaseReadersSem.forced_wait(); return; } } } } void wprio_shared_mutex::unlock_shared() { using namespace std; for( uint64_t cmp = m_atomic, niu; ; cmp = niu ) { assert(check( cmp )); assert((cmp & READERS_MASK) >= READER_VALUE); if( (cmp & READERS_MASK) != READER_VALUE || (cmp & WAITING_WRITERS_MASK) == 0 ) { if( (niu = CAS( m_atomic, cmp, cmp - READER_VALUE )) == cmp ) return; } else { assert(!(cmp & WRITER_FLAG_MASK)); if( (niu = CAS( m_atomic, cmp, (cmp - READER_VALUE - WAITING_WRITERS_VALUE) | WRITER_FLAG_MASK )) == cmp ) { m_releaseWriterSem.forced_release( 1 ); return; } } } } void wprio_shared_mutex::shared_to_write() { using namespace std; for( uint64_t cmp = m_atomic, niu; ; cmp = niu ) { assert(check( cmp )); assert((cmp & READERS_MASK) >= READER_VALUE); if( (cmp & READERS_MASK) == READER_VALUE ) { assert(!(cmp & WRITER_FLAG_MASK)); if( (niu = CAS( m_atomic, cmp, (cmp - READER_VALUE) | WRITER_FLAG_MASK )) == cmp ) return; } else { assert((cmp & READERS_MASK) > READER_VALUE && (cmp & WAITING_WRITERS_MASK) != WAITING_WRITERS_MASK); if( (niu = CAS( m_atomic, cmp, cmp - READER_VALUE + WAITING_WRITERS_VALUE )) == cmp ) { m_releaseWriterSem.forced_wait(); return; } } } } void wprio_shared_mutex::lock_writer() { using namespace std; for( uint64_t cmp = m_atomic, niu; ; cmp = niu ) { assert(check( cmp )); if( (cmp & (WRITER_FLAG_MASK | READERS_MASK)) == 0 ) { if( (niu = CAS( m_atomic, cmp, cmp | WRITER_FLAG_MASK )) == cmp ) return; } else { assert((cmp & WAITING_WRITERS_MASK) != WAITING_WRITERS_MASK); if( (niu = CAS( m_atomic, cmp, cmp + WAITING_WRITERS_VALUE )) == cmp ) { m_releaseWriterSem.forced_wait(); return; } } } } void wprio_shared_mutex::write_to_shared() { using namespace std; for( uint64_t cmp = m_atomic, niu; ; cmp = niu ) { assert(check( cmp )); if( (cmp & WAITING_WRITERS_MASK) == 0 ) { uint64_t wakeups; if( (niu = CAS( m_atomic, cmp, (cmp & ~WRITER_FLAG_MASK) - (cmp & WAITING_READERS_MASK) + (wakeups = (cmp & WAITING_READERS_MASK) >> WAITING_READERS_BASE) + 1 )) == cmp ) { if( wakeups ) m_releaseReadersSem.forced_release( (unsigned)wakeups ); return; } else continue; } if( (niu = CAS( m_atomic, cmp, cmp - WAITING_WRITERS_VALUE )) == cmp ) { m_releaseWriterSem.forced_release( 1 ); return; } else continue; } } void wprio_shared_mutex::unlock_writer() { using namespace std; for( uint64_t cmp = m_atomic, niu; ; cmp = niu ) { assert(cmp & WRITER_FLAG_MASK && !(cmp & READERS_MASK)); assert(check( cmp )); if( (cmp & WAITING_WRITERS_MASK) != 0 ) { if( (niu = CAS( m_atomic, cmp, cmp - WAITING_WRITERS_VALUE )) == cmp ) { m_releaseWriterSem.forced_release( 1 ); return; } else continue; } if( (cmp & WAITING_READERS_MASK) != 0 ) { uint64_t wakeups; if( (niu = CAS( m_atomic, cmp, (cmp & ~WRITER_FLAG_MASK) - (cmp & WAITING_READERS_MASK) + (wakeups = (cmp & WAITING_READERS_MASK) >> WAITING_READERS_BASE) )) == cmp ) { m_releaseReadersSem.forced_release( (unsigned)wakeups ); return; } else continue; } if( (niu = CAS( m_atomic, cmp, 0 )) == cmp ) return; } } |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 18 11:13PM -0700 On 10/18/2019 8:20 PM, Bonita Montero wrote: > wants to get access, all readers since then are allowed to continue > and all new readers are deferred. > So here's the code: [...] Before I take the time to read it, how close is this to your other read/write primitive, you were partitioning the counter field, right? Keep mine in mind as well for it does not use CAS at all. |
| Bonita Montero <Bonita.Montero@gmail.com>: Oct 19 08:25AM +0200 > [...] > Before I take the time to read it, how close is this to your other > read/write primitive, you were partitioning the counter field, right? Very close. There'S also an atomic value as well as a semaphore and nothin more. > Keep mine in mind as well for it does not use CAS at all. Show it. |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 18 11:28PM -0700 On 10/18/2019 11:25 PM, Bonita Montero wrote: > There'S also an atomic value as well as a semaphore and nothin more. >> Keep mine in mind as well for it does not use CAS at all. > Show it. You already saw it, and commented about it, remember? |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 18 11:30PM -0700 On 10/18/2019 11:28 PM, Chris M. Thomasson wrote: >>> Keep mine in mind as well for it does not use CAS at all. >> Show it. > You already saw it, and commented about it, remember? Wait, are you referencing Joe Seighs semaphore, or my read write mutex that does not use any CAS? I posted them here in this very group. Btw, the semaphore does not use CAS as well... They are called loopless algorithms. As in, no need to loop on a failed CAS... ;^) |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 18 11:35PM -0700 On 10/18/2019 11:30 PM, Chris M. Thomasson wrote: > that does not use any CAS? I posted them here in this very group. Btw, > the semaphore does not use CAS as well... They are called loopless > algorithms. As in, no need to loop on a failed CAS... ;^) My pure standard C++11 code can be found here: https://pastebin.com/raw/1QtPCGhV It should compile right up, and run on any system that has a C++11 compiler. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment