|
|
Boost : |
From: Jan Gaspar (jga_at_[hidden])
Date: 2003-07-21 06:23:14
Nazdar Pavel!
Pavel Vozenilek wrote:
> "Jan Gaspar" <jga_at_[hidden]> wrote in message
> news:3F17F1B1.47E66E6_at_whitestein.com...
> > The implementation can be found at
> > http://groups.yahoo.com/group/boost/files/circular_buffer.zip
> >
> Hello Jan,
>
> I took look on the library and have few comments.
> These could be voiced already - I didn't follow older
> threads.
>
> 1. Namespace boost::detail should be changed
> to boost::circular_buffer or something similar.
> The "detail" may be used by other libraries
> and cause name collisions.
OK
>
>
> 2. "NonconstSelf" type name uses different naming convention than
> all other names. Maybe it should be changed to "nonconst_self".
>
OK
>
> 3. cb_iterator: is the m_end value needed?
>
> It can be computed using 'm_it == m_buff->m_last' in
> those few (~2) places it is needed and if eliminated,
> iterator will get smaller (by 30%) and simpler.
Yes, the m_end member is needed. Suppose the circular_buffer is full. Then
m_buff->m_first == m_buff->m_last. If there is no m_end variable how would you
recognize that the iterator points to the beginning or end?
>
>
> 4. Last cb_iterator constuctor: wouldn't it be more efficient
> to pass the 'it' by value instead of reference?
Yes! You're right.
>
>
> 5. In cb_iterator::operator-(): result of the expression
> ' it < *this' can be saved and not computed second time.
But it is not used second time.
>
>
> 6. cb_iterator::operator==(): is the check 'm_end == it.m_end'
> really needed?
Yes, it is. See the item 3.
>
>
> 7. cb_iterator::operator!=(): it may be more efficient to code
> it as 'm_it != it.m_it ...' instead of !operator==().
> I do not know if compilers are allowed to change logical
> expression and if, how good they are in it.
Maybe. But everyone uses it like this.
>
>
> 8. cb_iterator::operator<(): the ASSERTS here are useless.
> Function compare() doesn't return anything else
> than -1/0/1 - I see it.
Yes, they are useless. But
1) omitting them doesn't speed up the execution (in general)
2) suppose if someone changes the compare() method implementation ... !!!!
3) this code is clean, you should always provide the default option
>
>
> In addition, e.g. MSVC may pessimize result code if default
> switch branch simply exists.
>
> 9. OTOH there are places where ASSERT can be inserted:
> - ensuring two iterators come from the same buffer
> - checking iterators are within valid range
> - checking type of iterators is the same (reverse / normal)
circular_buffer is a STL compliant container - no STL container is doing this.
>
>
> STLport has similar facility in debug mode.
>
> I can imagine circular_buffer invalidating iterators
> (by setting flag 'invalid').
I'm lazy for this, but you can add it.
>
>
> 10. cb_iterator::compare() should be private.
OK
>
>
> 11. circular_buffer<>: is the m_capacity member needed?
> It can be calculated in capacity(). (The performance
> impact is however rather small.)
In contrary the m_capacity member doesn't occupy a lot of memory.
>
>
> 12. circular_buffer<>: front(), back(), first(), last()
> can be implemented more efficiently without using
> rather complex operator[]. Compiler here has
> no chance to optimize it away.
I agree, I forgot about this.
>
>
> 13. circular_buffer<>: set_capacity() should check
> for ' new_capacity == capacity()'.
OK
>
>
> 14. circular_buffer<>: set_capacity() is not exception safe:
> if uninitialized_copy() throws it will leak.
> This problem happens IMHO in many functions (e.g.
> in constructors).
>
> Scope guard can be used to get basic exception safety.
OK, I will try to fix it.
>
>
> 15: circular_buffer<>: function destroy() shoudl set m_buff to 0
> to avoid chance for double delete. I am not sure it can
> happen here but it feels more safe.
Agree!
>
>
> 16. circular_buffer<> constructor taking iterators seems to be
> buggy:
>
> if (diff > capacity) {
> std::advance(first, diff - capacity);
> m_size = capacity;
> m_last = m_buff;
> } else {
> m_size = diff;
> m_last = m_buff + size();
> }
>
> should be:
>
> if (diff > capacity) {
> std::advance(first, diff - capacity);
> m_size = capacity;
> m_last = m_buff;
> } else {
> m_size = diff;
> if (diff == capacity) { <<<-----
> m_last = m_buff; <<<-----
> } else {
> m_last = m_buff + size();
> }
> }
You are right! It is BUG!
>
>
> 17. circular_buffer<>::operator=(): possible executable
> size improvement:
>
> if (full()) {
> m_last = m_buff;
> std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
> } else {
> m_last = std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
> }
> can be
>
> m_last = std::uninitialized_copy(cb.begin(), cb.end(), m_buff);
> if (full()) {
> m_last = m_buff;
> }
>
OK
>
> (I didn't test it.)
>
> 18. both circular_buffer<>::assign():
>
> m_buff = m_alloc.allocate(capacity(), 0);
> should be
> m_buff = allocate(n);
>
No, it is OK. capacity() will be always at least 1.
>
> 19. circular_buffer<>: both assign() can share common code.
You are right. I'll improve it.
>
>
> 20. circular_buffer<>::swap(): shouldn't m_alloc be swapped
> as well? (I do not know what is current opinion about
> this.)
>
Maybe yes, but it is not probable to have different allocators because allocators
don't have state.
>
> If yes, it should be put at the beginning for exception
> safety.
>
> 21. circular_buffer<>: there are few public sections one
> following other. Is there any reason for this?
The reason is just I wanted to split the circular_buffer into logical groups of
methods.
>
>
> 22. circular_buffer<>::push_back() and other functions
> may benefit from passing some types by value rather
> than by reference. Boost.call_traits<> can be used here.
>
> When this trick was applied to STLport, these functions
> got sped up by ~30%.
>
> The same trick may be likely used for passed iterators.
OK
>
>
> 23. It may be wortwile to check whether A. Alexandrescu's
> Mojo technique cannot be used within circular_buffer<>.
> (I have no idea about concrete applicaility here.)
I have no idea what the Mojo technique is. Try to explore it.
>
>
> 24: circular_buffer<>::push_back() and others:
>
> void push_back(const value_type& item) {
> if (full()) {
> ...
> return;
> }
> ...
> }
>
> should be rather
>
> void push_back(const value_type& item) {
> if (full()) {
> ...
> } else
> ...
> }
> }
>
> for aestethic reasons.
It is the way how do I code. It is shorter and I don't like indentation if not
necessary.
>
>
> 25. circular_buffer<>::pop_back() and pop_front():
>
> Shouldn't therse functions be protected against
> empty buffer?
>
> E.g. push_back/front are protected against zero size
> buffer.
>
> The cost of this check is rather small.
No. Standard containers don't do that. The check
if (empty())
return;
in the push_back() is the check if the zero capacity.
>
>
> 26. circular_buffer<>:: first insert(): some code from here
> can be shared throughout the library.
I don't know exactly what you mean.
>
>
> 27. circular_buffer<>: first insert(): POD types
> can be memmove()d instead of object copying one by one.
> Dtto for insert_n/rinsert_n.
>
> I am not sure if this solution wouldn't get too complex,
> though.
I'm lazy for that.
>
>
> 28. circular_buffer<>: insert(pos, n, item): I get compile error.
>
> Test:
> -----
> circular_buffer<int> a(5);
> a.push_back(1);
> a.push_back(2);
> a.push_back(3);
> a.push_back(4);
> circular_buffer<int>::iterator it1 = a.begin() + 2;
> int new_value = 99;
> a.insert(it1, 5, new_value);
>
>
> Output on Intel C++ 7 plugged in MSVC6 IDE:
> -------------------------------------------
> Compiling...
> test.cpp
> C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\utility(102): error:
> no instance of overloaded function "std::_Iter_cat"
>
> matches the argument list
> argument types are: (int)
> _Distance(_F, _L, _N, _Iter_cat(_F));
> ^
> detected during:
> instantiation of "ptrdiff_t={int} __cdecl std::distance(_II,
> _II) [with _II=int]" at line 868 of
>
> "C:\Temp\temp\circular_buffer\test\../include/circular_buffer.hpp"
> instantiation of "void boost::circular_buffer<T,
> Alloc>::insert(boost::circular_buffer<T, Alloc>::iterator,
>
> InputIterator, InputIterator) [with T=int, Alloc=std::vector<int,
> std::allocator<int>>::allocator_type, InputIterator=int]"
> C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\iterator(227): error:
> no instance of overloaded function
>
> "std::_Iter_cat" matches the argument list
> argument types are: (int)
> {_Advance(_I, _N, _Iter_cat(_I)); }
> ^
> detected during:
> instantiation of "void std::advance(_II &, _D) [with _II=int,
> _D=int]" at line 871 of
>
> "C:\Temp\temp\circular_buffer\test\../include/circular_buffer.hpp"
> instantiation of "void boost::circular_buffer<T,
> Alloc>::insert(boost::circular_buffer<T, Alloc>::iterator,
>
> InputIterator, InputIterator) [with T=int, Alloc=std::vector<int,
> std::allocator<int>>::allocator_type, InputIterator=int]"
> C:\Temp\temp\circular_buffer\test\../include/circular_buffer.hpp(782):
> error: operand of "*" must be a pointer
> operator const value_type& () const { return *m_it++; }
> ^
> detected during:
> instantiation of "boost::circular_buffer<T,
> Alloc>::Item<InputIterator>::operator const boost::circular_buffer<T,
>
> Alloc>::value_type &() const [with T=int, Alloc=std::vector<int,
> std::allocator<int>>::allocator_type, InputIterator=int]"
> at line 1051
> instantiation of "void boost::circular_buffer<T,
> Alloc>::insert_n(boost::circular_buffer<T, Alloc>::iterator,
>
> boost::circular_buffer<T, Alloc>::size_type, const Item &) [with T=int,
> Alloc=std::vector<int,
>
> std::allocator<int>>::allocator_
> type, Item=boost::circular_buffer<int, std::vector<int,
> std::allocator<int>>::allocator_type>::Item<int>]" at line 874
> instantiation of "void boost::circular_buffer<T,
> Alloc>::insert(boost::circular_buffer<T, Alloc>::iterator,
>
> InputIterator, InputIterator) [with T=int, Alloc=std::vector<int,
> std::allocator<int>>::allocator_type, InputIterator=int]"
> compilation aborted for C:\Temp\temp\circular_buffer\test\test.cpp (code 2)
> Error executing cl.exe.
>
> test.exe - 3 error(s), 0 warning(s)
>
> Output on BC++B 6.4:
> --------------------
> Build
> [C++ Warning] _debug.h(377): W8058 Cannot create pre-compiled header: code
> in header
> [C++ Error] _iterator_base.h(94): E2406 Dependent type qualifier 'int' is
> not a class or struct type
> [C++ Error] _iterator_base.h(95): E2406 Dependent type qualifier 'int' is
> not a class or struct type
> [C++ Error] _iterator_base.h(96): E2406 Dependent type qualifier 'int' is
> not a class or struct type
> [C++ Error] _iterator_base.h(97): E2406 Dependent type qualifier 'int' is
> not a class or struct type
> [C++ Error] _iterator_base.h(98): E2406 Dependent type qualifier 'int' is
> not a class or struct type
> [C++ Error] circular_buffer.hpp(782): E2062 Invalid indirection
> [C++ Error] _iterator_base.h(367): E2285 Could not find a match for
> '__distance<_RandomAccessIterator,_Distance>(const
>
> int,const int,undefined)'
> [C++ Error] _iterator_base.h(367): E2109 Not an allowed type
> [C++ Error] _iterator_base.h(447): E2285 Could not find a match for
> '__advance<_InputIter,_Distance>(int,int,undefined)'
>
> To cast second parameter to size_t helps but IMHO this should work.
I've got the same problem, but I don't know how to fix it (except the type cast).
>
>
> 29. circular_buffer<>: all insert(): special case when
> n/copy == 0 can be handled just here
> (and not in insert_n()).
>
> This would avoid possible long costly advance().
OK
>
>
> 30. circular_buffer<>: insert(Iterator, Iterator):
> the last parameters can be safely passed as:
> call_traits<InputIterator>::value_type.
OK
>
>
> 31. circular_buffer<>::erase(pos): maybe there should
> be protection against erase(buffer.end()) situation.
STL containers just don't do such checks (but you can create an adaptor).
>
>
> 32. circular_buffer<>::erase(Iter, Iter) may try to use
> memcpy() for POD. Again, if it isn't too complex
> to implement.
>
Lazy :-(
>
> 33. circular_buffer<>::insert(Iter, Iter) may contain
> STATIC_ASSERT check that Iter iterator value is
> convertible to buffer main data type.
> Some other functions as well.
>
> Iterator traits may be checked as well.
I think, if the value won't be convertible the compilation fails anyway.
>
>
> 34. This fragment produces invalid iterator value:
>
> circular_buffer<int> a(0);
> circular_buffer<int>::iterator it1 = a.begin();
> ++it1;
>
> I mention it only because every other capacity
> leaves such iterator valid (and equal end()).
The iterator was not designed to be circular. It was designed for iterating from
begin to end. The result of the operation ++ at the iterator pointing to the end
is unspecified.
>
>
> 35. circular_buffer<>: functions add() and sub()
> could return changed pointer instead of using in/out.
> It is nicer and with call_traits<> maybe even
> faster.
OK
>
>
> 36. circular_buffer<>::allocate() should check
> against m_alloc.max_size() and
> throw out_of_range if fails.
>
> Now it (on old Dinkumware) likely throws bad_alloc.
Probably yes.
>
>
> 37. Documentation: it would be nice to have documented
> precondition, postconditions, exceptions
> thrown etc. Maybe this info can be embedded into
> Doxygened text.
What do you mean by precondition and postconditions. Give an example.
>
>
> 38. Documentation: can standard algorithms be used on
> circular buffer?
Yes, they can and it is explicitly mentioned in the documentation.
>
>
> 39. Can ostream<<() or dump() be added into
> the library (conditionally by macro)?
Yes, someone can do this.
>
>
> 40. Can circular_buffer<std::auto_ptr<...> > be made
> uncompilable like standard containers are?
IMHO standart containers don't do it. std::vector< std::auto_ptr<char> > v; can be
compiled.
>
>
> 41. Documentation: can the documentation describe if
> and possibly how hypotetical full featured policy based
> circular buffer can be based on this one?
>
> For example if one would like to add MT safety.
I don't know. I'm lazy for that.
>
>
> S pozdravom,
> /Pavel
>
Vdaka za review.
Jano
-- Jan Gaspar | jga_at_[hidden] Whitestein Technologies | www.whitestein.com Panenska 28 | SK-81103 Bratislava | Slovak Republic Tel +421(2)5930-0735 | Fax +421(2)5443-5512
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk