- Boost-users - lists.boost.org

[serialization] problems with using wide-char archives
by Hilal Shaath 06 May '06

06 May '06

Hello All: The serialization library is one of the best libraries I have used. I used to to serialize a number of files with various sizes, and it works like a charm. However, when I am using the wide-char archives, I get a linking error. Here are the problem specifications: When including : #include "boost/archive/binary_woarchive.hpp" #include "boost/archive/binary_wiarchive.hpp" Or #include "boost/archive/text_woarchive.hpp" #include "boost/archive/text_wiarchive.hpp" And attempt to use them (i.e.) std::map<wstring,size_t> htable; wstring root = L"c:"; findDFF(&htable,&root); std::wofstream ofs("someFile",std::wios::binary); boost::archive::binary_woarchive o(ofs); I get the following linking errors: [ DB3 error LNK2019: unresolved external symbol "public: __thiscall boost::archive::basic_binary_oprimitive<class boost::archive::binary_woarchive,class std::basic_ostream<unsigned short,struct std::char_traits<unsigned short> > >::~basic_binary_oprimitive<class boost::archive::binary_woarchive,class std::basic_ostream<unsigned short,struct std::char_traits<unsigned short> > >(void)" (??1?$basic_binary_oprimitive@Vbinary_woarchive@archive@boost@@V?$basic_ostream@GU?$char_traits@G@std@@@std@@@archive@boost@@QAE@XZ) referenced in function "public: __thiscall boost::archive::binary_woarchive_impl<class boost::archive::binary_woarchive>::~binary_woarchive_impl<class boost::archive::binary_woarchive>(void)" (??1?$ ] If I use the regular archives (binary_oarchive) I don't get any errors, and it runs as a charm! The compiler I am using is VC++ version 7.1/ I would be grateful if some could point me to the reason for this error. Thanks for your help Hilal

1 0

[multi_index] const mem_fun serialization bug.
by Julien Pervillé 06 May '06

06 May '06

Hello boost-users. I am writing to report an annoying serialization bug encountered while developing a project with Boost.multi_index, which is a wonderfully useful data structure. Thank you Joaquín! First a fast overview of my project: I am developing a virtual file system for my internship. In this file system, I have to store user paths which I call "entries". "entries" are associated with another "internal entry" which is the path to the physical target inside the file system. "entries" are also contained in a concept of "directory". To ease up things I store entries in a boost::multi_index with at least 3 indexes: - an unique index to look up user entries. - a non-unique index to do reverse look up (by internal targets). - a non-unique index to do directory listings. The latter is the one that interests us. The "entry" class splits the entry into the "dirname" and "file" parts. A getter function returns a const-reference to "dirname", let's call it "entry::dirname()". To do directory listings efficiently, I define an ordered-non-unique index pointinh to the const-reference returned by the entry.dirname() thanks to a wrapper "mem_fun" named getdirname(). Now comes the bug. To test my file system, I import some existing directories into my file system. When I unload it, I expect that the internal boost::multi_index is serialized and restored properly when I reload the file system program. When working on huge batches of small files, like untaring a linux kernel or copying the thousands of files from /usr/share/doc, I noticed that the import works but reloading the serialized mappings fails with a (for now unexplained but reproducable) boost::serialization::other_exception. After hunting through the headers, I located the triggered exception to line 1080 of boost/multi_index/ordered_index.hpp (line number from boost 1.33) Here is the context from the "rearranger" method where the exception is thrown: > 1080 if(position!=x){ > 1081 /* check the rearrangement is consistent */ > 1082 if(!in_place(x->value,position,Category())){ > 1083 throw_exception( > 1084 archive::archive_exception( > 1085 archive::archive_exception::other_exception)); > 1086 } Since my multi_index works perfectly until I save, I checked that my data is properly serialized. Since I saw no obvious errors, I modified the header to swallow the exception and see what happens. > 1080 if(position!=x){ > 1081 /* check the rearrangement is consistent */ > 1082 if(!in_place(x->value,position,Category())){ > 1083 return; throw_exception( > 1084 archive::archive_exception( > 1085 archive::archive_exception::other_exception)); > 1086 } After this small hack, everything "seems" to work fine but if I do a "find" on my file system some entries appear "missing". They are actually not missing but they were attributed to the wrong directory! And in the wrong parent directory, a lookup says "file not found" when find tries to access it. However, I can still access the entries by naming them explicitely (using the main index, not the dirname one). I investigated and found out that the "dirname" ordered_index (const mem_fun) is not restored properly, even through it is saved correctly. The "entry" and the "target" ordered indexes (member) are restored as intended. However look what happens to the mem_fun "dirname" index: its values are restored in positions that are not a valid binary tree. Actually it is "almost" a binary tree, just some values are wrongly restored. Like a dozen out of 1000 entries, but always the same ones. As a consequence even if my entry::operator<() predicate is proved correct, lookups through the "dirname" index give byzantine results. I tracked down the problem and found a small set of "entries" that are not restored properly and wrote a small example file. Please have a look at the attached source "seri-bug.cpp". The example dumps the contents of a 5 entries multi_index, first by entry and then by "dirname". The displaying is done before serializing to disk and after reloading the mappings. The corruption can then be see by checking the different position inside the dirname index for the "/doc/binutils-doc" entry before and after. Sample run: Original structure dump by dirname, pre serialization. > entry `/' with dirname `'. > entry `/doc' with dirname `'. > entry `/doc/binutils-doc' with dirname `/doc'. > entry `/doc/binutils-doc/ld' with dirname `/doc/binutils-doc'. > entry `/doc/binutils-doc/gas' with dirname `/doc/binutils-doc'. Post serialized loading dump. Notice that the "/doc/binutils-doc" entry was not restored at the correct position. Since the dirnames are not properly sorted in memory, doing a find() by dirname obtains byzantine results (doing a find of "/doc" dirname returns the `/doc/binutils-doc/ld' result instead of the expected `/doc/binutils-doc' entry). > entry `/' with dirname `'. > entry `/doc' with dirname `'. > entry `/doc/binutils-doc/ld' with dirname `/doc/binutils-doc'. > entry `/doc/binutils-doc' with dirname `/doc'. > entry `/doc/binutils-doc/gas' with dirname `/doc/binutils-doc'. Even if this sample triggers the restore anomaly, to see a boost::archive::other_exception one needs more data inside the multi_index, like a few thousand entries. I would really love to see a this bug fixed since it stalls my projects. My c++ template metaprogramming skills aren't very sharp but I think that this bug is a good opportunity to learn some about this subject. I am looking forward to test patches and offer my help testing, so that this little quirk gets solved. Sincerely, Julien Perville Intern, Global Core, Amadeus IT Group.

1 0

adjacency_list and UndirectedGraph in BGL
by sean yang 06 May '06

06 May '06

I am a newbie using BGL and only read a couple of example source code. I have a question about class representing a graph. It seems adjacency_list represent a graph, but it seems there is a class hierarchy (as shown in (2) ) to represent a graph. What is their relationship? (1) adjacency_list can represent a graph, e.g., typedef adjacency_list<vecS, vecS, bidirectionalS, no_property, property<edge_weight_t, float> > Graph; (2) And the online manual give a list of Graph representation. I guess it's a hierarchical class representation. i.e., Graph <--Incidence Graph <--Bidirectional Graph. Am I right? But if so, I did not find the constructor of these classes. Furthermore, this class hierarchy has give a full classification of graph, why is there a adjacency_list representation? Chapter 11. The Boost Graph Interface 1. Graph 2. Incidence Graph 3. Bidirectional Graph 4. Adjacency Graph 5. Vertex List Graph 6. Edge List Graph 7. Vertex and Edge List Graph 8. Mutable Graph 9. Property Graph 10. Mutable Property Graph (3) There is an exmple of UndirectedGraph in the book of "User guide and reference manual" { ... V=3; UndirectedGraph undigraph(V); add_edge(0, undigraph); ..... } is there a way not specifying vertice number when defining an object and dynamically adding vertex when according to user input? i.e, something like UndirectedGraph undigraph( ); while (getline(in, line)){ add_edge(line, undigraph); } _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today - it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/

1 0

[MULTI_INDEX] intersection algorithm?
by Guillaume Lazzara 06 May '06

06 May '06

Hello, I am currently using multi_index as "set" container and I wanted to know how to use intersection algorithm. I tried with the STL interction algorithm but it crashed. How can I do? Thanks in advance, -- Guillaume Lazzara Epita Promo 2008 http://guillaume.lazzara.fr

1 0

Re: [Boost-users] boost::multi_index_container different search key type
by JOAQUIN LOPEZ MU?Z 06 May '06

06 May '06

----- Mensaje original ----- De: bert hubert <bert.hubert(a)netherlabs.nl> Fecha: Miércoles, Mayo 3, 2006 8:15 pm Asunto: [Boost-users] boost::multi_index_container different search key type > Joaquin, list, > > In one of the last issues of the C/C++ User's Journal, Andrei > Alexandrescu described the need for something better than std::map > when using expensive > keys: > [...] > > More on http://www.ddj.com/dept/cpp/184402065 - might this be > something boost::multi_index_container could be made to do? > Hello Bert, I'm glad you asked, because multi_index_container already provides this, and I would dare say in a more powerful fashion. Ordered and hashed indices lookup member functions (find, equal_range, etc.) are overloaded to accept *compatible keys*, which can be used to pass alternate representations of keys in exactly the same manner as described in Andrei's article. Compatible keys are introduced at http://tinyurl.com/rouet and formally described at http://tinyurl.com/hp9j4 (ordered indices) http://tinyurl.com/ze5od (hashed indices) But there is more: in the case of ordered indices, compatible keys need not be in a 1-to-1 relation with the original keys, but can be "coarser", in a sense. An example can help clarify this: Suppose we've got an index ordered by a date, with millisecond precision, then the index is certainly ordered by year; compatible key support can be thus used to perform lookup by year if only we provide the appropriate comparison semantics between full dates and years, so that "year" is a compatible key of "date". Although it might not be apparent, composite keys take full advantage of all of this: * When you pass a tuple to lookup on some composite_key- enabled index, the tuple is *not* the index key_type, but merely a more convenient representation. * Compatible key support (in the "coarser key" sense) is used when you do "partial searches" in which only the first tuple values are specified: see http://tinyurl.com/hdf3q. When Andrei's article first came out, I contacted him to discuss these concepts and the similarities between his ÜberContainers and compatible key support as provided by B.MI: IMHO it is not unusual that these sort of ideas come up recurrently. Thanks for your active interest in Boost.MultiIndex! Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

Re: [Boost-users] Thread-safe smart pointers, hashtables
by Gottlob Frege 06 May '06

06 May '06

> Date: Fri, 5 May 2006 14:09:33 -0600 > From: Ray Whitmer <ray(a)personallegal.net> > Subject: Re: [Boost-users] Thread-safe smart pointers, hashtables > without locking > To: boost-users(a)lists.boost.org > Message-ID: <0D5E3BD4-9A5D-4CE2-9040-35500773C190(a)personallegal.net> > Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed > > > The algorithm makes sense, and if all these claims hold then it > > should work, I think. I'm still concerned about step (2), however, > > if only because of the assumption that what you write as a load/ > > store in C++ maps to a load/store in ML. Will it? Always? I ask as > > a non-rhetorical question: does the C++ standard *guarantee* it? > > Because if it doesn't then it seems like a potential problem, but > > maybe I'm being too careful. I'd also say the idea of moving a pointer out of the way, and then using the flip-gate-count-thing to wait for any 'potentially-using' readers to finish, definitely has 'potential'. You would need to show detailed code to really be sure. And not to us - to the guys on comp.programming.threads. If I could answer in the affirmative, I could prove it works and not > have to talk to anyone. I can make a bunch of lesser claims, that of > course fail to add up to the strong claim but make me feel better: > > 3. I have looked at the output of many C compilers and have never > seen a pointer assignment take multiple instructions. The exception > might be if someone used a poorly-written memcpy-like operations to > transfer the contents of a structure byte by byte. A well-written > one takes the respective alignments into account and transfers > aligned 32-bit quantities one-by-one. We are talking about code in a > controlled Hashtable class, it would have to be the "C" compiler > choosing to transfer a class consisting of a single address field > using something other than a single instruction. It doesn't sound > logical to me, but it wouldn't surprise me completely to see it > happen, but I would report it as a compiler bug and expect it to be > addressed even though it is not in the standard. As long as the address of the pointer is properly aligned, it will be atomic. The language doesn't guarantee that (the language doesn't talk about atomic or threads at all - at least not yet), but the processors + compilers tend to guarantee it. HOWEVER! *even if it is atomic*, on a multi-cpu machine each cpu might see memory differently - you need memory barriers to ensure the other cpus see your new pointer value correctly. Think of cpus and memory like harddrive controllers that reorder reads and writes to lessen seeks - the cpu does the same sort of thing with memory - and in doing so, it may reorder the write of your pointer to 'happen' before you expected (because it was near other memory it was writing) and/or read the pointer later than expected (because it optimized other reads into a 'bundle' before the read of your pointer). Anyhow, if you haven't already, take a look at memory barriers, and, as a canonical example, the broken 'double checked locking pattern'. You can't do lock free without understanding this stuff. 4. These issues have to be addressed with the multi-processor cores > becoming more prevalent because they are basic to lock-free > processing, or can C++ accept significant inferiority to Java with > respect to lock-free multiprocessing? see above. Much of it doesn't come for free. For what it is worth, if anyone else thinks the solution is worth a > generic contribution, or is of the opposite opinion that it would not > be generic enough, I would be interested in hearing. I suppose this > sort of question should go to the developers list. I think it would > be much more difficult to implement a table of shared_ptr than it is > for intrusive_ptr, because assigning a shared_ptr is much less likely > to be uninterrupted, leaving other threads with a broken visible > state. There is clearly more detail to discuss as well. > Ray Whitmer Your wording of 'much less likely' is scary, and I think similar wording made James apprehensive as well. There is no grey - it is black or white, thread safe or not. And you are correct, you can't make { reading the location of a shared_ptr + incrementing its ref-count } atomic, it least not on most processors. I'm not sure of the exact implementation of intrusive_ptr, but assuming it is like most, you can make ip1 = ip2; atomic IF ip2 is 'stable', ie guaranteed to not be changing during the assignment. ie ip1 can be read and/or written by other threads "while" the assignment is happening, and you will either get the before state of ip1, or the after state. I don't think the boost implementation of intrusive_ptr's operator=() is atomic, but it could be made to be. Tony

1 0

[BGL] adjacency_list property map selection
by Daniel Mitchell 06 May '06

06 May '06

Are there any plans to replace the property map selection code with a mechanism based on partial specialization? I'm implementing interior property maps for my own graph classes and must decide which approach to use. Partial specialization is elegant, but there's also value in consistency with BGL. D.

1 0

Re: [Boost-users] [multi-array] [C++ ] multi array dimensions
by Sohail Somani 05 May '06

05 May '06

> -----Original Message----- > From: boost-users-bounces(a)lists.boost.org > [mailto:boost-users-bounces@lists.boost.org] On Behalf Of > Bruno Martínez > Sent: Friday, May 05, 2006 4:52 PM > To: boost-users(a)lists.boost.org > Subject: Re: [Boost-users] [multi-array] [C++ ] multi array dimensions > > On Tue, 02 May 2006 16:04:04 -0300, Karim Bakir > <rimbak(a)yahoo.fr> wrote: > > > Ok so , And is it possible to retrieve the size of the dimension? > > Yes. That's the shape() member function. I've been thinking, it would be nice if shape() returned a const boost::array & whose indexing has nice asserts at debug time :) Anyone else feels the same?

1 0

[multi-array] [C++ ] multi array dimensions
by Karim Bakir 05 May '06

05 May '06

Hi , I want to known if exists method which give us the dimension of a multi array ...I see the documentation and i 'will say no , if no, does it exist a method to determine the dimension of a multi array ? Thanks.

2 5

Possible bug in program_options when disabling _SECURE_SCL on VS8
by Roger Dahl 05 May '06

05 May '06

I think I've found a bug in program_options. #define _SECURE_SCL 0 on Visual Studio 2005 causes program_options to crash in store(). I used boost from CVS. Below is an example. Thanks for an awesome library! Roger -- #define _SECURE_SCL 0 #include <boost/program_options.hpp> namespace po = boost::program_options; int main(int argc, char* argv[]) { po::options_description desc("Allowed Options"); desc.add_options() ("help", "produce help message") ; po::variables_map vm; po::store(po::parse_command_line(argc, argv, desc), vm); po::notify(vm); return 0; }

1 0