Hello all
In my GSoC project I need to represent nodes in a linked list. The requirements are:
1. Obtaining an iterator from the value should be a constant time operation 2. Ownership semantics should be similar to boost::ptr_list - that is, objects are owned by only one container and deleted when erased, though there are special functions that allow transfer between containers and releasing an object from a container 3. The list must have a 'closed' flag that determines the behavior of 2 functions that retrieve an iterator to the next and previous node: If it's true, they wrap around, and if it's not they behave like regular ++ and -- on iterators.
Initially I thought about std::list + std::tr1::unordered_map of pointer to node -> iterator, but this is absurd. Then I created my own NodeList class, which worked well enough, but I feel that implementing all the operations is reinventing the wheel. I could use Boost.Intrusive (specifically boost::intrusive::list) to satisfy 1 and 2 out of the box and 3 with a small amount of work. However, I can't find what version of Boost we currently depend on. Boost.Intrusive is a header only library that was released as part of Boost 1.35 in April 2008 (there are no runtime dependencies, so the only possible issue is whether developers run recent enough systems to have it available). It is available in Debian Lenny, as a backport for Etch, and in Ubuntu Hardy LTS. Is it OK to use it?
Regards, Krzysztof Kosiński
I don't see any specific issue with Boost.Intrusive, but I'm curious if GLib's lists can do all of that as GLib is already a dep.
--Ted
On Jul 22, 2009, at 11:20 AM, Krzysztof Kosiński <tweenk.pl@...400...> wrote:
Hello all
In my GSoC project I need to represent nodes in a linked list. The requirements are:
- Obtaining an iterator from the value should be a constant time
operation 2. Ownership semantics should be similar to boost::ptr_list - that is, objects are owned by only one container and deleted when erased, though there are special functions that allow transfer between containers and releasing an object from a container 3. The list must have a 'closed' flag that determines the behavior of 2 functions that retrieve an iterator to the next and previous node: If it's true, they wrap around, and if it's not they behave like regular ++ and -- on iterators.
Initially I thought about std::list + std::tr1::unordered_map of pointer to node -> iterator, but this is absurd. Then I created my own NodeList class, which worked well enough, but I feel that implementing all the operations is reinventing the wheel. I could use Boost.Intrusive (specifically boost::intrusive::list) to satisfy 1 and 2 out of the box and 3 with a small amount of work. However, I can't find what version of Boost we currently depend on. Boost.Intrusive is a header only library that was released as part of Boost 1.35 in April 2008 (there are no runtime dependencies, so the only possible issue is whether developers run recent enough systems to have it available). It is available in Debian Lenny, as a backport for Etch, and in Ubuntu Hardy LTS. Is it OK to use it?
Regards, Krzysztof Kosiński
Inkscape-devel mailing list Inkscape-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/inkscape-devel
Ted Gould wrote:
I don't see any specific issue with Boost.Intrusive, but I'm curious if GLib's lists can do all of that as GLib is already a dep.
After this suggestion I tried it, and it also works, but there are rough edges. Here are the problems: 1. GLists do not store a pointer to the last node, so I have to resort to awful hacks or accept having to walk the entire list just to find the last node. This is a big problem as the most common operations like appending or finding the node adjacent to the first node of a closed path require this. 2. In general, representing lists as a pointer to first node has many shortcomings. Boost.Intrusive, as well as most std::list implementations, use a cyclic list with an empty first node (without any associated value) as a header. This makes it trivially easy to implement iterators, in particular the end iterator, and both begin() and end() are constant time as expected from a doubly-linked list. With GList I have to special case the end iterator. With Boost.Intrusive I don't even have to implement iterators, only the cyclic adjacency operation (next/prev), which is trivial: void next_node(iterator i) { ++i; if (i.pointed_node()->is_header && i.pointed_node()->closed) ++i;) } 3. GLists do not support slicing, only concatenation. I will need slicing or at least splitting into multiple lists to implement break and delete segment.
Regards, Krzysztof Kosiński
I just noticed one more important issue: I need to use GLists as nodes of an intrusive container, but they only support using them as normal containers (e.g. there is no function to append a preexisting GList node, only to append a pointer stored in a newly allocated GList node, which is not what I want). This makes them completely unsuitable for my task.
Regards, Krzysztof Kosiński
OK For now it works with GList and the implementation is a bit simpler than before, but that's because I went for something like the cyclic list approach when doing iterators. I will probably be able to do everything without using Boost.Intrusive. The question still stands: what is the version of Boost we depend on?
On Jul 26, 2009, at 4:02 AM, Krzysztof Kosiński wrote:
OK For now it works with GList and the implementation is a bit simpler than before, but that's because I went for something like the cyclic list approach when doing iterators. I will probably be able to do everything without using Boost.Intrusive. The question still stands: what is the version of Boost we depend on?
I think that's one of the two key questions.
First is to see which versions of boost are available on which distros/OSs. Thankfully the win32 front is fairly up to date, but there are a few distros that delay updating things.
The second is to see what parts of BOOST are where. In the past it had been a collection of things, rather than one large thing itself. It may or may not be a factor for certain distros, so it would need to be checked.
On 27/07/2009, at 1:42 AM, Jon A. Cruz wrote:
First is to see which versions of boost are available on which distros/OSs. Thankfully the win32 front is fairly up to date, but there are a few distros that delay updating things.
FWIW, the latest boost (1.39) is available on Mac OS X.
Michael
Ubuntu Jaunty has 1.37 as the latest, but 1.35 as an alias for 'libboost-dev' (what they call the 'default' version of Boost). Hardy has 1.34 as default. Debian Lenny has 1.34 as default and no later version, Squeeze (testing) and Sid (unstable) have at least 1.38 available. I don't expect many people to run the stable Debian on the desktop, so I think it is safe to assume that at least Boost 1.34 is available on every Debian-based desktop. Could someone familiar with RPM variants tell the situation there?
Regards, Krzysztof
On 27/7/09 00:26, Michael Wybrow wrote:
On 27/07/2009, at 1:42 AM, Jon A. Cruz wrote:
First is to see which versions of boost are available on which distros/OSs. Thankfully the win32 front is fairly up to date, but there are a few distros that delay updating things.
FWIW, the latest boost (1.39) is available on Mac OS X.
I installed boost via MacPorts 'port install boost' as recommended on http://wiki.inkscape.org/wiki/index.php/CompilingMacOsX, without considering any variants or reading the documentation on its homepage. The compilation took a really long time even compared to building inkscape itself and the installed libs have an overall size of 95 MB. Are _all_ of these libraries required to build inkscape?
| LeWitt:mp suv$ port installed |grep boost | boost @1.39.0_2 (active) | boost-jam @3.1.17_0 (active) | LeWitt:mp suv$ ls -1 lib/libboost* | wc -l | 43 | LeWitt:mp suv$ du -sch lib/libboost* <snip> | 95M total | LeWitt:mp suv$
~suv
~suv-2 wrote:
The compilation took a really long time even compared to building inkscape itself and the installed libs have an overall size of 95 MB. Are _all_ of these libraries required to build inkscape?
No, in fact we currently use only Boost libraries that are header-only, so you don't need to compile Boost before compiling Inkscape (though your installation system might disagree). To be precise, we use boost::optional, boost::shared_ptr, boost/concept_check.hpp (used in 2geom) and a few other tidbits; I will probably use boost::ptr_list in the new node tool. On Debian, there are separate packages for the libraries that have runtime dependencies.
Regards, Krzysztof
On 2/8/09 16:30, Krzysztof Kosiński wrote:
~suv-2 wrote:
The compilation took a really long time even compared to building inkscape itself and the installed libs have an overall size of 95 MB. Are _all_ of these libraries required to build inkscape?
No, in fact we currently use only Boost libraries that are header-only, so you don't need to compile Boost before compiling Inkscape (though your installation system might disagree). To be precise, we use boost::optional, boost::shared_ptr, boost/concept_check.hpp (used in 2geom) and a few other tidbits; I will probably use boost::ptr_list in the new node tool. On Debian, there are separate packages for the libraries that have runtime dependencies.
Pardon my naive follow-up question: if I put the required header files into the correct include-dirs, inkscape will build without linking to any libboost_*.a or libboost_*.dylib?
The files installed by MacPorts into ${prefix}include/boost/ aren't few either:
| LeWitt:mp suv$ du -sch include/boost/ | 56M include/boost/ | 56M total | LeWitt:mp suv$ ls -1 include/boost/ | wc -l | 193 | LeWitt:mp suv$
~suv
Pardon my naive follow-up question: if I put the required header files into the correct include-dirs, inkscape will build without linking to any libboost_*.a or libboost_*.dylib?
Yes, it should build fine as long as you have the required headers in $prefix/include/boost.
The files installed by MacPorts into ${prefix}include/boost/ aren't few either:
That's because they contain Doxygen documentation as well as the code. If you are concerned about space, I think you can trade some compilation time by putting the boost directory in a zip archive and then mounting the archive at /usr/include/boost using MacFUSE. On Ubuntu I would use the archive mounter available in Nautilus and symlink the directory created in ~/.gvfs to /usr/include/boost. The size of Inkscape binary won't be affected by the size of Boost headers, because the header-only libraries are templates that do not generate any code if they are not used.
Regards, Krzysztof
On 2/8/09 19:24, Krzysztof Kosiński wrote:
Pardon my naive follow-up question: if I put the required header files into the correct include-dirs, inkscape will build without linking to any libboost_*.a or libboost_*.dylib?
Yes, it should build fine as long as you have the required headers in $prefix/include/boost.
Is there a list of which Boost header only libraries are needed other than grep'ing the source files?
The files installed by MacPorts into ${prefix}include/boost/ aren't few either:
That's because they contain Doxygen documentation as well as the code. If you are concerned about space, I think you can trade some compilation time by putting the boost directory in a zip archive and then mounting the archive at /usr/include/boost using MacFUSE. On Ubuntu I would use the archive mounter available in Nautilus and symlink the directory created in ~/.gvfs to /usr/include/boost.
Reducing the include files to those needed might make a bigger difference regarding disk space. I'm not concerned enough about space to tackle MacFUSE at the moment - I'm already in over my head with handling MacPorts and building Inkscape ;-)
The size of Inkscape binary won't be affected by the size of Boost headers, because the header-only libraries are templates that do not generate any code if they are not used.
Thank you, that's the information I was looking for.
~suv
participants (5)
-
Jon A. Cruz -
Krzysztof Kosiński -
Michael Wybrow -
Ted Gould -
~suv