Re: [Kicad-developers] Ratsnest for the GAL
On 11/08/2013 03:24 PM, Dick Hollenbeck wrote: On 10/16/2013 03:19 PM, Dick Hollenbeck wrote: On 10/16/2013 09:32 AM, Maciej Sumiński wrote: On 10/16/2013 02:59 PM, Dick Hollenbeck wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com mailto:d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Thanks for the suggestion - I like the idea. I have briefly read the boost::pool project page and initially it seems to be an easy solution to the problem. That is likely to be a *very* fast solution. But keep in mind that if you are going to delete the pool, since it is anchored in your ratsnest class, then you really don't need element deletion, i.e. operator delete () on the container element. This let's you trancend into *very very* fast, if you use it to your advantage. The problem with supporting pool::free( node ) is that it often requires that a pointer to the big block from which the smaller fixed size block came be saved in the smaller block. There may be other ways, look into this. This additional pointer, if present, is unnecessary if you don't worry about delete node, since the pool is going to be deleted anyways. The pointer is a way to figure out which big block to add the small fixed block back into upon a free. It is overhead you don't need. Just saving that one pointer can be a big deal. If the boost scheme is doing this, or if its allocation function uses more than about 3 lines of code, then it may not be optimal. Also, if your algorithm can work with pointers to the node, where moving nodes from one container to another is really a matter of moving pointers, you will also pick up some speed. What I envision is that when the pool would be inclined to return NULL, meaning the current big block is exhausted, that it allocate another big block and then put that big block onto a linked list of big blocks, singly linked is good enough. After that, it puts each small block within the big block onto another singly linked list, called a freelist. Each of the lists are held in the pool anchor. The anchor destructor frees all the big blocks. operator delete () can be a dummy for the node element, I assume you will need one since the container destructor may be calling it, and this happens before the pool destructor hopefully. Especially that nodes are very likely going to be POD structures with fixed size. I guess it is already included in C++11 as the emplace() function that is available for many std containers. Orson, You reminded me of a couple of things: a) regardless of whether in place new() is used or not, if the objects have std::string or wxString, the objects will need destruction to free up their string internals. The objects very well may need a ~destructor(). I am almost sure that structures that describe nodes and connections are not going to contain strings. It will be rather a small simple POD, so it should perfectly fit memory pool scheme. b) emplace() is a modern way of doing old school memory block management with in place new(). Real time C++ programmers have been using in place new for awhile. emplace() is an opportunity to use a stock container, but has been limited to C++11. But boost, in it effort to bring early functionality even to *C++03*, has emplace() support on boost::container::vector *and* boost::container::deque So for a minimal lines of code implementation of what I was talking about above, a person could simply put a boost::container::deque into your ratsnest class and allocate objects quickly from there, simply by adding them to the deque with emplace(), and returning a pointer to the back(). This is minimal lines of code and I doubt there's a faster way, especically with so few lines of code.
Re: [Kicad-developers] Ratsnest for the GAL
On 10/16/2013 03:19 PM, Dick Hollenbeck wrote: On 10/16/2013 09:32 AM, Maciej Sumiński wrote: On 10/16/2013 02:59 PM, Dick Hollenbeck wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com mailto:d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Thanks for the suggestion - I like the idea. I have briefly read the boost::pool project page and initially it seems to be an easy solution to the problem. That is likely to be a *very* fast solution. But keep in mind that if you are going to delete the pool, since it is anchored in your ratsnest class, then you really don't need element deletion, i.e. operator delete () on the container element. This let's you trancend into *very very* fast, if you use it to your advantage. The problem with supporting pool::free( node ) is that it often requires that a pointer to the big block from which the smaller fixed size block came be saved in the smaller block. There may be other ways, look into this. This additional pointer, if present, is unnecessary if you don't worry about delete node, since the pool is going to be deleted anyways. The pointer is a way to figure out which big block to add the small fixed block back into upon a free. It is overhead you don't need. Just saving that one pointer can be a big deal. If the boost scheme is doing this, or if its allocation function uses more than about 3 lines of code, then it may not be optimal. Also, if your algorithm can work with pointers to the node, where moving nodes from one container to another is really a matter of moving pointers, you will also pick up some speed. What I envision is that when the pool would be inclined to return NULL, meaning the current big block is exhausted, that it allocate another big block and then put that big block onto a linked list of big blocks, singly linked is good enough. After that, it puts each small block within the big block onto another singly linked list, called a freelist. Each of the lists are held in the pool anchor. The anchor destructor frees all the big blocks. operator delete () can be a dummy for the node element, I assume you will need one since the container destructor may be calling it, and this happens before the pool destructor hopefully. Especially that nodes are very likely going to be POD structures with fixed size. I guess it is already included in C++11 as the emplace() function that is available for many std containers. Orson, You reminded me of a couple of things: a) regardless of whether in place new() is used or not, if the objects have std::string or wxString, the objects will need destruction to free up their string internals. The objects very well may need a ~destructor(). b) emplace() is a modern way of doing old school memory block management with in place new(). Real time C++ programmers have been using in place new for awhile. emplace() is an opportunity to use a stock container, but has been limited to C++11. But boost, in it effort to bring early functionality even to *C++03*, has emplace() support on boost::container::vector *and* boost::container::deque So for a minimal lines of code implementation of what I was talking about above, a person could simply put a boost::container::deque into your ratsnest class and allocate objects quickly from there, simply by adding them to the deque with emplace(), and returning a pointer to the back(). This is minimal lines of code and I doubt there's a faster way, especically with so few lines of code. http://www.boost.org/doc/libs/1_48_0/doc/html/container/move_emplace.html#container.move_emplace.emplace ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net
Re: [Kicad-developers] Ratsnest for the GAL
Le 16/10/2013 16:32, Maciej Sumiński a écrit : On 10/16/2013 02:59 PM, Dick Hollenbeck wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com mailto:d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Thanks for the suggestion - I like the idea. I have briefly read the boost::pool project page and initially it seems to be an easy solution to the problem. Especially that nodes are very likely going to be POD structures with fixed size. I guess it is already included in C++11 as the emplace() function that is available for many std containers. Regards, Orson Seems there are some good ideas about ratsnest enhancements. Strangely, I missed the fact some times the ratsnest removed was not the shorter... Here are some info about the current ratsnest and connectivity calculations: - The first minimum spanning tree code to calculate the full basic ratsnest was not very fast, and this is the reason why only the pads were used to build the ratsnest (avoid to calculate it each time a track was changed). - The current minimum spanning tree code is very fast ( 1 to 2 order of magnitude for large boards: more than 5000 pads and 3 tracks) and perhaps could handle the pads + tracks. - to avoid very long calculation time to detect track to pad and track to track connections, there are some limitations: Only track ends are considered: - a track is connected to an other track if the 2 ends are near. (near means here the distance between ends is smaller than the half track width) - a track is connected to a pad if one end is inside the pad. - This allows using fast binary search between tracks and pads, which uses a list of all points candidates sorted by X coordinate value. - But therefore some connections can be missed ( for instance a track crossing an other track or a pad) -currently, most of calculation time (90%) is spent in calculations relative to find tracks and pads connections by copper zone areas. (By the way, www.codeproject.com/Tips/84226/Is-a-Point-inside-a-Polygon is the code used in Kicad to find if a point is inside a polygon) I did not found yet a fast algorithm to really speed up this calculation (because most of times a copper zone covers the full board area). Thanks for all your great work on GAL and now the ratsnest calculations. -- Jean-Pierre CHARRAS ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
[Kicad-developers] Ratsnest for the GAL
Hi all, We need a ratsnest that works with the GAL, therefore I present to you the blueprints for that part: https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal I have seen many great ideas appearing on the mailing list, that's why everyone is welcome to share thoughts. I believe it may lead to a better/faster/more functional implementation in the end. Regards, Orson ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Since you probably want the pool anchored on the container On Oct 16, 2013 4:10 AM, Maciej Sumiński maciej.sumin...@cern.ch wrote: Hi all, We need a ratsnest that works with the GAL, therefore I present to you the blueprints for that part: https://blueprints.launchpad.**net/kicad/+spec/ratsnest-galhttps://blueprints.launchpad.net/kicad/+spec/ratsnest-gal I have seen many great ideas appearing on the mailing list, that's why everyone is welcome to share thoughts. I believe it may lead to a better/faster/more functional implementation in the end. Regards, Orson __**_ Mailing list: https://launchpad.net/~kicad-**developershttps://launchpad.net/~kicad-developers Post to : kicad-developers@lists.**launchpad.netkicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-**developershttps://launchpad.net/~kicad-developers More help : https://help.launchpad.net/**ListHelphttps://help.launchpad.net/ListHelp ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Since you probably want the pool anchored on the container On Oct 16, 2013 4:10 AM, Maciej Sumiński maciej.sumin...@cern.ch wrote: Hi all, We need a ratsnest that works with the GAL, therefore I present to you the blueprints for that part: https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal I have seen many great ideas appearing on the mailing list, that's why everyone is welcome to share thoughts. I believe it may lead to a better/faster/more functional implementation in the end. Regards, Orson ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
On 10/16/2013 04:09 AM, Maciej Sumiński wrote:
Hi all,
We need a ratsnest that works with the GAL, therefore I present to you
the blueprints for that part:
https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal
I have seen many great ideas appearing on the mailing list, that's why
everyone is welcome to share thoughts. I believe it may lead to a
better/faster/more functional implementation in the end.
Regards,
Orson
___
Mailing list: https://launchpad.net/~kicad-developers
Post to : kicad-developers@lists.launchpad.net
Unsubscribe : https://launchpad.net/~kicad-developers
More help : https://help.launchpad.net/ListHelp
.
It requires hashing function to be prepared (eg. using boost::hash), possibly
not very
demanding on CPU cycles.
Sounds good. A hashtable is probably the best bet. Suggest adding it to
hashtables.h
which is where we've put all the hashtables.
Might this work?
/// hash function for RATS_ELEM type
/// taken from:
http://www.boost.org/doc/libs/1_53_0/libs/unordered/examples/fnv1.hpp
struct rats_hash
{
std::size_t operator()( const RATS_ELEM e ) const
{
std::size_t hash = 2166136261u;
hash ^= e.m_x;
hash *= 16777619;
hash ^= e.m_y;
hash *= 16777619;
hash ^= e.m_layer;
hash *= 16777619;
hash ^= e.m_net;
return hash;
}
};
It puts in the members in reverse order of importance, m_net being most
important.
I got this from my const char* hash function for which there is a URL
reference in
hashtables.h
___
Mailing list: https://launchpad.net/~kicad-developers
Post to : kicad-developers@lists.launchpad.net
Unsubscribe : https://launchpad.net/~kicad-developers
More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
FYI, in step 4 of the algorithm, I believe you wanted to refer to step 3: *4. Remove edges with zero weight.* The last step is to remove zero weight edges (as they are already connected). The remaining edges make the ratsnest. This step could be integrated with the step 3, as 0-weight edges could be filtered Carl On Wed, Oct 16, 2013 at 8:59 AM, Dick Hollenbeck d...@softplc.com wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Since you probably want the pool anchored on the container On Oct 16, 2013 4:10 AM, Maciej Sumiński maciej.sumin...@cern.ch wrote: Hi all, We need a ratsnest that works with the GAL, therefore I present to you the blueprints for that part: https://blueprints.launchpad.net/kicad/+spec/ratsnest-gal I have seen many great ideas appearing on the mailing list, that's why everyone is welcome to share thoughts. I believe it may lead to a better/faster/more functional implementation in the end. Regards, Orson ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
On 10/16/2013 03:54 PM, Carl Poirier wrote: FYI, in step 4 of the algorithm, I believe you wanted to refer to step 3: *4. Remove edges with zero weight.* The last step is to remove zero weight edges (as they are already connected). The remaining edges make the ratsnest. This step could be integrated with the step 3, as 0-weight edges could be filtered Carl You are right, thanks for catching this. Good that you can find careful readers here. It's already fixed. Regards, Orson ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
On 10/16/2013 02:59 PM, Dick Hollenbeck wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com mailto:d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Thanks for the suggestion - I like the idea. I have briefly read the boost::pool project page and initially it seems to be an easy solution to the problem. Especially that nodes are very likely going to be POD structures with fixed size. I guess it is already included in C++11 as the emplace() function that is available for many std containers. Regards, Orson ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
On 10/16/2013 09:24 AM, Maciej Sumiński wrote:
On 10/16/2013 03:49 PM, Dick Hollenbeck wrote:
On 10/16/2013 04:09 AM, Maciej Sumiński wrote:
It requires hashing function to be prepared (eg. using boost::hash),
possibly not very
demanding on CPU cycles.
Sounds good. A hashtable is probably the best bet. Suggest adding it to
hashtables.h
which is where we've put all the hashtables.
Might this work?
/// hash function for RATS_ELEM type
/// taken from:
http://www.boost.org/doc/libs/1_53_0/libs/unordered/examples/fnv1.hpp
struct rats_hash
{
std::size_t operator()( const RATS_ELEM e ) const
{
std::size_t hash = 2166136261u;
hash ^= e.m_x;
hash *= 16777619;
hash ^= e.m_y;
hash *= 16777619;
hash ^= e.m_layer;
hash *= 16777619;
hash ^= e.m_net;
return hash;
}
};
It puts in the members in reverse order of importance, m_net being most
important.
I got this from my const char* hash function for which there is a URL
reference in
hashtables.h
Surely, I will give it a try during tests. I was also considering using
netcodes for identification of nodes, but in the end I skipped them. Are
coordinates layer number not enough to unambiguously determine a node?
In space, yes. Good point. No telling when you will get ahold of the BOARD
however,
before or after the DRC. A BOARD with two nets going to the same place (read
point in
space) might get missed or confused. This is a user error, but you need to be
able to
identify all possibilities at that point in space, no?
m_net = was intended to be netcode, but it may not be needed as you suggest.
Regards,
Orson
.
___
Mailing list: https://launchpad.net/~kicad-developers
Post to : kicad-developers@lists.launchpad.net
Unsubscribe : https://launchpad.net/~kicad-developers
More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Ratsnest for the GAL
On 10/16/2013 09:32 AM, Maciej Sumiński wrote: On 10/16/2013 02:59 PM, Dick Hollenbeck wrote: On Oct 16, 2013 7:53 AM, Dick Hollenbeck d...@softplc.com mailto:d...@softplc.com wrote: Looks promising, and super job on the presentation. Once you have it working, give some thought to using a special purpose allocator for the elements of your container. A memory pool scheme, anchored on the container, might pay dividends if it removes the size test for element allocations. If you want the pool anchored on the container, then overloading operator new is not best, but rather have a container function do the allocations of its elements (from a pool it owns.) Invariably this means having an in place new operator for the element, not a normal new operator overload. Such anchoring of pool in container is a separate decision from deciding to use a fixed block allocator at all. The fixed block allocator will be worth it regardless of where the pool lives. If you have to move elements from one container to another, then anchoring the pool on the container is not appropriate. But you could then have a class that held all your containers and a pool common to those containers. I bring this up because when instantiating hundreds of thousands of elements, memory heap calls can be the bottleneck. Thanks for the suggestion - I like the idea. I have briefly read the boost::pool project page and initially it seems to be an easy solution to the problem. That is likely to be a *very* fast solution. But keep in mind that if you are going to delete the pool, since it is anchored in your ratsnest class, then you really don't need element deletion, i.e. operator delete () on the container element. This let's you trancend into *very very* fast, if you use it to your advantage. The problem with supporting pool::free( node ) is that it often requires that a pointer to the big block from which the smaller fixed size block came be saved in the smaller block. There may be other ways, look into this. This additional pointer, if present, is unnecessary if you don't worry about delete node, since the pool is going to be deleted anyways. The pointer is a way to figure out which big block to add the small fixed block back into upon a free. It is overhead you don't need. Just saving that one pointer can be a big deal. If the boost scheme is doing this, or if its allocation function uses more than about 3 lines of code, then it may not be optimal. Also, if your algorithm can work with pointers to the node, where moving nodes from one container to another is really a matter of moving pointers, you will also pick up some speed. What I envision is that when the pool would be inclined to return NULL, meaning the current big block is exhausted, that it allocate another big block and then put that big block onto a linked list of big blocks, singly linked is good enough. After that, it puts each small block within the big block onto another singly linked list, called a freelist. Each of the lists are held in the pool anchor. The anchor destructor frees all the big blocks. operator delete () can be a dummy for the node element, I assume you will need one since the container destructor may be calling it, and this happens before the pool destructor hopefully. Especially that nodes are very likely going to be POD structures with fixed size. I guess it is already included in C++11 as the emplace() function that is available for many std containers. Regards, Orson ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
