- Boost - lists.boost.org

[Boost-bugs] [ boost-Patches-1434821 ] rational::operator< fails for unsigned value types
by SourceForge.net 02 Nov '06

02 Nov '06

Patches item #1434821, was opened at 2006-02-19 16:24 Message generated for change (Comment added) made by dlwalker You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1434821&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None >Status: Closed >Resolution: Fixed Priority: 5 Private: No Submitted By: David Benbennick (dbenbenn) Assigned to: Jonathan Turkanis (turkanis) Summary: rational::operator< fails for unsigned value types Initial Comment: There's a minor bug in rational.hpp when using unsigned values. Consider the following simple program: int main(void) { boost::rational<unsigned int> x = 0; assert(x.operator<(1)); } The assertion fails. The reason is that in rational.hpp::rational<IntType>::operator< (param_type i) are the lines if (num > zero) return (num/den) < i; else return -i < (-num/den); The last line is bogus for unsigned types if num == 0 and i > 0. The problem can be fixed by changing (num > zero) to (num >= zero). Another issue with the same section of code is that it uses up to 5 comparisons of IntType values. Attached is a patch that fixes the bug described, and also makes the function only perform up to 3 comparisons. That can make a difference, of course, if IntType is a complicated type with a slow comparison operator. ---------------------------------------------------------------------- >Comment By: Daryle L. Walker (dlwalker) Date: 2006-11-02 11:03 Message: Logged In: YES user_id=551024 An extra change while fixing bug #798357 fixes this issue, without using this patch. The current solution performs a floor-rounding division and modulus, followed by a comparison. The floor division involves either one or two extra comparisons, for possibly converting from a truncating division. (The assert currently there uses another comparison.) ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1434821&group_… ------------------------------------------------------------------------- Using Tomcat but need to do more? Need to support web services, security? Get stuff done quickly with pre-integrated technology to make your job easier Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642 _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Re: [boost] [proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)
by Martin Knoblauch Revuelta 02 Nov '06

02 Nov '06

Rene Rivera wrote: > Martin Knoblauch Revuelta wrote: > > How about a sequence container [..]. > > I was wondering how long it would take this to make it from the usenet > groups to here :-) > > I've mentioned this type of container here in the past, under the name > of "rank_tree". Very soon now I will have the version I wrote, and use, > ported to the framework that Bernhard produced for the SoC tree project. > You can look at the draft TR > <https://boost-consulting.com:8443/trac/soc/browser/boost/soc/2006/tree/trun…> > that mentions it, and other trees. > > I don't have time to look at your implementation right now. But perhaps > you could comment on how you think your implementation might fit within > the above. And of course if there's something we haven't thought about. Well, maybe the most important thing is the experimental feature NPSV that I added in version 1.1. I described it briefly in my message, but there's a detailed description in the notes for version 1.1 of stlavlarray.h. The example program in npsvexample.cpp shows it's behaviour. Example where NPSV would be useful: a simple avl_array (or rank_tree) would waste a lot of memory when used for small contained types. This can be solved with NPSV, by storing more than one contained type element in every tree node. The 'width' of the node would be the number of occupied elements in the node, which would contain a circular buffer. Additionally, avl_array has the next characteristics (use it as a check list): * On iterators, ++ and -- are O(1) * begin(), end(), rbegin() and rend() are all O(1) * Copy constructor, assignment operator and destructor are O(n) * Other constructors, where the number of elements is known, are O(n) * Comparison operators are all O(n) * reverse(), merge(), and unique are O(n) * avl_array swap is O(1) * element swap is O(1) unless when NPSV is used _and_ the elements' widths don't match (then it is O(log n)) * element swap also works between two different avl_arrays * resize, range-insert and range-erase take O(m log n) when m is small, but O(n) when m is reasonably significant compared to n. (m: number of elements to insert/erase; n: size of the array) * move() is O(log n) unless it is a single-position move, in which case it is done with a swap * both sort() and stable_sort() are provided with O(n log n) * search tree methods are provided * insert_anywhere() inserts without rotations favouring balance (though still O(log n)) * Iterators follow their referenced elements, even when theese are moved from an avl_array to another one Can all this be done with generic trees while keeping them simple, efficient and usable for other purposes where the hierarchy is visible to the user? Regards, Martin Knoblauch Revuelta

9 27

[proposal] Sequence container with O(log n) random access _and_ O(log n) insertion/removal (wherever)
by Martin Knoblauch Revuelta 02 Nov '06

02 Nov '06

- How about a sequence container (like a vector) with the advantage of logarithmic time insertion/removal at any point of the sequence? The disadvantage is that random access takes logarithmic time too (instead of the usual constant time random access of a vector). Here it is: http://sourceforge.net/projects/avl-array It is implemented with a tree, but it is _not_ a map. The 'position' of elements in avl_array are always natural numbers (0, 1, 2... up to size()-1). When an element is inserted/removed, it changes automatically the position of all elements after it in the sequence (in logarithmic time!). A simple experiment realized consisted in populating a container by inserting random numbers in random positions, and then removing numbers from random positions, showing the value of the last one for checking. In this test AVL Arrays completely outperform list, vector and deque. The test code and the results are in sourceforge too. Version 1.1 includes a new experimental feature that I call "Non-Proportional Sequence View". In the normal sequence, every element occupies a position of size 1. Additionally, elements can be viewed as a sequence where the 'width' of every element can be changed (in O(log n) time), being the position of every element the sum of the widths of all previous elements in the sequence. Negative widths are forbidden, but zero widths are valid. The type used for the width is a template parameter, so any class supporting some operators can be used, not only unsigned or double. I've tried to adapt it to the boost requirements, but I'm sure there's still a lot of things to change. If you are interested, please take a look at it, and tell me your opinion. Regards, Martin Knoblauch Revuelta Universidad de Alcala

4 11

[config] patch for config/compiler/hp_acc.hpp
by Boris Gubenko 02 Nov '06

02 Nov '06

Attached a small patch for hp_acc.hpp configuration header. It fixes all but one failure in parameter library (the remaining failure is python_test which is, most likely, some configuration problem with python). The tests would not compile with the old header because it defines BOOST_NO_TEMPLATE_TEMPLATES macro which is inappropriate for aCC6 compiler. The patch also fixes test failures in statechart library, this library now has zero failures. I also verified, that the patch does not introduce any regressions. I think, the changes are obvious, but I can comment, if necessary. The only question I can envision is: why inclusion of "common_edg.hpp" is conditionalized with '#if (__HP_aCC >= 61200)' and not with, say, '> 60000' ? After all, aCC6 is EDG-based compiler since day one. The reason is that before A.06.12, the compiler does not predefine __EDG__ and __EDG_VERSION__ macros. It was corrected in A.06.12. Since "common_edg.hpp" checks if __EDG_VERSION__ is defined, it cannot be included if a pre-A.06.12 compiler is used. Of course, I could use '#ifdef __EDG_VERSION__' condition, but I thought, that a specific compiler version in hp_acc.hpp header is more appropriate. Can the patch below be applied to both the HEAD and the RC 1.34 branch? Thanks, Boris Index: hp_acc.hpp =================================================================== RCS file: /cvsroot/boost/boost/boost/config/compiler/hp_acc.hpp,v retrieving revision 1.20 diff -r1.20 hp_acc.hpp 5a6 > // (C) Copyright Boris Gubenko 2006. 13a15,18 > #if (__HP_aCC >= 61200) > #include "boost/config/compiler/common_edg.hpp" > #endif > 30,31c35 < // This version check is way to high, but we don't know the right one to use: < #if (__HP_aCC < 60700) --- > #if (__HP_aCC < 60000) 62c66 < #if (__HP_aCC > 53800) --- > #if (__HP_aCC > 61300)

2 1

[program_options] Potential bug in options_description.cpp
by Stas Khirman 02 Nov '06

02 Nov '06

While reviewing diff of options_description.cpp rev 1.14 and 1.17 , I came across of potential bug in line 417: 417 : (line_length - indent) / 2) However, line_length already had been decrease by "indent" in line 332 ( introduced in rev 1.15) I assume that correction is: 417 : (line_length) / 2) Regards Stas Khirman

1 0

Boost regression notification (2006-10-31 [RC_1_34_0])
by Douglas Gregor 02 Nov '06

02 Nov '06

Boost Regression test failures Report time: 2006-10-31T11:56:09Z This report lists all regression test failures on release platforms. Detailed report: http://engineering.meta-comm.com/boost-regression/CVS-RC_1_34_0/developer/i… 36 failures in 7 libraries date_time (1) iostreams (10) mpl (4) program_options (7) random (1) serialization (12) utility (1) |date_time| testgreg_serialize_xml: msvc-8.0 |iostreams| bzip2_test: msvc-7.1 msvc-8.0 example_test: vc-6_5-stlport file_descriptor_test: cw-9.4 finite_state_filter_test: cw-9.4 gzip_test: msvc-7.1 msvc-8.0 mapped_file_test: cw-9.4 zlib_test: msvc-7.1 msvc-8.0 |mpl| multiset: gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 gcc-4.1.1_sunos_i86pc |program_options| cmdline_test_dll: cw-9.4 options_description_test_dll: cw-9.4 parsers_test_dll: cw-9.4 positional_options_test_dll: cw-9.4 unicode_test_dll: cw-9.4 variable_map_test_dll: cw-9.4 winmain_dll: cw-9.4 |random| random_test: intel-linux-9.0 |serialization| test_class_info_load_text_warchive: vc-6_5 test_reset_object_address: vc-7_0 test_reset_object_address_dll: vc-7_0 test_simple_class_binary_archive_dll: vc-6_5 test_simple_class_text_archive_dll: vc-6_5 test_simple_class_text_warchive_dll: vc-6_5 test_simple_class_xml_archive_dll: vc-6_5 test_simple_class_xml_warchive_dll: vc-6_5 test_variant_xml_archive: borland-5_8_2 test_variant_xml_archive_dll: borland-5_8_2 test_variant_xml_warchive: borland-5_8_2 test_variant_xml_warchive_dll: borland-5_8_2 |utility| operators_test: gcc-3.4.5_linux_x86_64

3 2

[thread] Question about MT API C++0X N2094
by Roland Schwarz 01 Nov '06

01 Nov '06

I'd like to know the rationale behind mutex concept requiring explicit locking signatures. Are users of the library "allowed" to access them directly? If yes why? Isn't this redundant to locks? Not requiring them, but letting them be implementation defined will allow the implementor more freedom. The only required concept should be: being able to take the address of the mutex. (Because this makes it unique.) E.g. the requirement for these N2094 mutex concepts would make implementation of my proposed POD mutex variant impossible. E.g. the current boost mutex also does not need to make these explicit functions. Sorry if I misunderstood the document. I would be glad if someone (H. Hinnant?) could explain to me. Thank you. Roland

5 21

Boost regression notification (2006-11-01 [RC_1_34_0])
by Douglas Gregor 01 Nov '06

01 Nov '06

Boost Regression test failures Report time: 2006-11-01T10:24:34Z This report lists all regression test failures on release platforms. Detailed report: http://engineering.meta-comm.com/boost-regression/CVS-RC_1_34_0/developer/i… 31 failures in 7 libraries iostreams (10) mpl (4) program_options (7) random (1) serialization (7) spirit (1) utility (1) |iostreams| bzip2_test: msvc-7.1 msvc-8.0 example_test: vc-6_5-stlport file_descriptor_test: cw-9.4 finite_state_filter_test: cw-9.4 gzip_test: msvc-7.1 msvc-8.0 mapped_file_test: cw-9.4 zlib_test: msvc-7.1 msvc-8.0 |mpl| multiset: gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 gcc-4.1.1_sunos_i86pc |program_options| cmdline_test_dll: cw-9.4 options_description_test_dll: cw-9.4 parsers_test_dll: cw-9.4 positional_options_test_dll: cw-9.4 unicode_test_dll: cw-9.4 variable_map_test_dll: cw-9.4 winmain_dll: cw-9.4 |random| random_test: intel-linux-9.0 |serialization| test_class_info_load_text_warchive: vc-6_5 test_reset_object_address: vc-7_0 test_reset_object_address_dll: vc-7_0 test_variant_xml_archive: borland-5_8_2 test_variant_xml_archive_dll: borland-5_8_2 test_variant_xml_warchive: borland-5_8_2 test_variant_xml_warchive_dll: borland-5_8_2 |spirit| scanner_value_type_tests: gcc-4.1.0_linux |utility| operators_test: gcc-3.4.5_linux_x86_64

3 2

Re: [boost] Quicktime v210 format support (Re: GIL Review)
by Lubomir Bourdev 01 Nov '06

01 Nov '06

Lubomir Bourdev wrote: > 2. Now that we have writing out of the way, we can create a > model of an r-value channel reference (ChannelConcept, but > not MutableChannelConcept) that takes two channels and > returns a value half-way in between (or if generalization is > important, an arbitrary interpolation). Lets call it > InterpolatingChannel Of course, the moment I submitted the post I came up with a much simpler alternative. We don't need any InterpolatingChannel. We simply need to create a subbyte channel value. Synopsis: // Represents a channel *value* whose size is not byte-divisible // Models ChannelValueConcept template <typename UnpackedChannelValue, int NumBits> class packed_channel_value { public: typedef ChannelValue value_type; packed_channel_value(const value_type& data) : _data(data) {} packed_channel_value(const packed_channel_value& c) : _data(c._data) {} operator value_type() const { return _data&MAX_VALUE; } packed_channel_value& operator=(const value_type& data) { // warning: using this method may indicate a bug in your code! _data=data; return *this; } ... private: value_type _data; static const value_type MAX_VALUE = (1<<NumBits)-1; }; The difference between this and the packed_channel_reference class is that this one holds a copy of the data, whereas the packed channel reference holds a reference to the data which is located remotely. Now our channel type is simply: typedef packed_channel_value<uint16_t,10> v210_channel_t; Our pixel model is simply: typedef pixel<v210_channel_t, ycbcr_t> v210_pixel_t; We keep the same model of pixel iterator I outlined earlier. But we simply instantiate it with the correct values: reference v120_pixel_ptr::dereference() const { switch (index) { ... case 3: return reference( v120_channel_t(Y3), v120_channel_t((CB1+CB2)/2), v120_channel_t((CR1+CR2)/2)); } } Where "reference" is the same type as "value_type" (since this is an immutable view) Y3,CB1,CB2,CR1 and CR2 are the values of the corresponding 10-bit channels (some shift and mask math necessary) In short, dropping the requirement to write pixel-by-pixel into v210 (which is not a well defined operation anyway) results in a simpler and faster implementation. Lubomir

1 0

[xml] XML Reader Interface
by Sebastian Redl 01 Nov '06

01 Nov '06

Hi, Once again I'm turning to the list for discussion about a design issue in the XML library. This time I hope to avoid any discussion about the implementation on the library and focus on interface only. The interface in question is the reader interface, also known as pull interface. Like SAX, the pull interface is an event-based interface. There are a few event types (roughly, StartElement, EndElement, Characters, and a few more for other XML features), all of which provide come with some additional data: the element name, the character data, etc. There are two types of reader interfaces currently in use that I've found. I've come up with a third. I wonder which the people on this list would prefer, where they see their weaknesses and strengths. The names that I've given them are my own creation. 1) The Monolithic Interface Examples: .Net XMLReader, libxml2 XMLReader (modeled after the .Net one), Java Common API for XML Pull Parsing (XmlPull) (don't confuse with JSR 173 "StAX") In the monolithic interface, the XML parser acts as a cursor over the event stream. You call next() and it points to the next event in the stream. From there, you can query its type (usually some integral constants) and call some methods to retrieve the data. All methods are always available on the object; calling one that is not appropriate for the current event (e.g. getTagName() for a Characters event) returns a null value or signals an error. Pro: Event objects do not need to be allocated. The parser itself contains the entire state and can, for example, be passed down a recursive function group. Contra: You cannot store raw events: calling next() overwrites the current data. The parser contains a lot of state. This interface does not protect you in any way from calling inappropriate methods. 2) The Inheritance Interface Examples: JSR 173 "StAX" In the inheritance interface, the event types are modeled as a group of classes that all inherit from an Event base class. The parser acts as an iterator, Java style; calling next() returns a reference/pointer to the event object for this event. You use RTTI or a similar mechanism to find the type of the event, then cast the reference to the appropriate subclass. The subclasses then provide access to the data that is actually available for this event type. Pro: Cannot call methods that are inappropriate for the event. Event objects are independent of the parser and can be stored as they are. This is especially interesting if you have an event-based output system that uses the same event type: in this case, you can store the events, shuffle them, edit them, then pass them on to the writer. A proper analog to the stateful parser is harder to design. The parser contains less state, as it does not need to store the data that is currently queried. Contra: Event objects need to be allocated on the heap. In a non-GC language like C++, this is even more of a problem than in Java, as you have to use either a smart pointer or have the user responsible for deleting the object. The scenario of a group of functions as mentioned above is limited insofar as that if some functions want to process the same event, they need to be passed the current event along with the parser. 3) The Variant Interface Examples: None. I believe I came up with this entirely on my own. The variant interface seeks to combine the strengths of the other two interfaces. It uses a non-monolithic interface, that is, the parser acts like an iterator and the data is not stored within it. It does not return a reference to the event object, though, but instead a boost::variant of all possible events. This way, heap allocation of the event object is avoided, together with all the trouble coming with that. The event type can be determined either by calling variant::which, or with a variant visitor (type-safe!), or with a special get_base() function that works like get() but can retrieve a reference to a common base of all the variant types. (This is possible, although an implementation does not exist in Boost.) Pro: Cannot call methods that are inappropriate. The visitor system allows type-safe usage. (Of course, it also loses you part of the advantage of a pull interface over a push interface.) Does not need heap allocation if the event classes are properly designed (i.e. not trigger the case where the variant allocates heap memory.) Events can be stored, copied (another advantage over the inheritance interface, which would require a clone() method for that), and manipulated at will. They can be pre-allocated, a reference passed to next(), to save even the stack allocation. Contra: The issue about a group of function still applies. Independently of the type of interface chosen, another issue is important: the scope of the interface. Should it report all XML events, including those coming from DTD parsing? Should this be a user choice, or should there perhaps be two interfaces, one "high-level" and one "low-level"? Should errors be reported as error events, or as exceptions? Should this, too, be a user choice? How about warnings: exceptions are inappropriate for them. Should it be possible to disable them completely? All comments are welcome. Sebastian Redl

8 19