Hi all,
I've written a new version of lib/linkm. It's interface is pretty much
the same. Names of functions, variables and the module itself are
subject to revision, as well as the documentation is (my English is
not that good). I've done some testing, the lib works correctly and
outperforms conventional linked list 4 to 12 times. Read the
documentation in linked_list.c for more info.
I'm looking forward to incorporating this into GRASS, since lists are
needed in Vect_get_point_in_poly() and the current library is buggy.
Here is what I've written.
Regards,
Rosen Matev
(attachments)
linked_list.c (4.42 KB)
linked_list.h (1.23 KB)
Hi again,
I really need some help to integrate this one into trunk. The current
module prevents Vect_get_point_in_poly() from working correctly in
some unusual cases.
Regards,
Rosen Matev
On Wed, Sep 24, 2008 at 9:47 PM, Росен Матев <r.matev@gmail.com> wrote:
Hi all,
I've written a new version of lib/linkm. It's interface is pretty much
the same. Names of functions, variables and the module itself are
subject to revision, as well as the documentation is (my English is
not that good). I've done some testing, the lib works correctly and
outperforms conventional linked list 4 to 12 times. Read the
documentation in linked_list.c for more info.
I'm looking forward to incorporating this into GRASS, since lists are
needed in Vect_get_point_in_poly() and the current library is buggy.
Here is what I've written.
Regards,
Rosen Matev
Rosen Matev wrote:
> I've written a new version of lib/linkm. It's interface is pretty much
> the same. Names of functions, variables and the module itself are
> subject to revision, as well as the documentation is (my English is
> not that good). I've done some testing, the lib works correctly and
> outperforms conventional linked list 4 to 12 times. Read the
> documentation in linked_list.c for more info.
> I'm looking forward to incorporating this into GRASS, since lists are
> needed in Vect_get_point_in_poly() and the current library is buggy.
> Here is what I've written.
I really need some help to integrate this one into trunk. The current
module prevents Vect_get_point_in_poly() from working correctly in
some unusual cases.
So are you going to modify your code to match the existing linkm
library, or modify the vector and bitmap libraries to use the new
interface?
--
Glynn Clements <glynn@gclements.plus.com>
I was hoping for more experienced grass developers to suggest the
names of the functions and etc. Then I'll modify what's needed and
give diffs to someone to apply them in trunk.
On Sun, Oct 5, 2008 at 4:16 AM, Glynn Clements <glynn@gclements.plus.com> wrote:
Rosen Matev wrote:
> I've written a new version of lib/linkm. It's interface is pretty much
> the same. Names of functions, variables and the module itself are
> subject to revision, as well as the documentation is (my English is
> not that good). I've done some testing, the lib works correctly and
> outperforms conventional linked list 4 to 12 times. Read the
> documentation in linked_list.c for more info.
> I'm looking forward to incorporating this into GRASS, since lists are
> needed in Vect_get_point_in_poly() and the current library is buggy.
> Here is what I've written.
I really need some help to integrate this one into trunk. The current
module prevents Vect_get_point_in_poly() from working correctly in
some unusual cases.
So are you going to modify your code to match the existing linkm
library, or modify the vector and bitmap libraries to use the new
interface?
--
Glynn Clements <glynn@gclements.plus.com>
Rosen Matev wrote:
>> > I've written a new version of lib/linkm. It's interface is pretty much
>> > the same. Names of functions, variables and the module itself are
>> > subject to revision, as well as the documentation is (my English is
>> > not that good). I've done some testing, the lib works correctly and
>> > outperforms conventional linked list 4 to 12 times. Read the
>> > documentation in linked_list.c for more info.
>> > I'm looking forward to incorporating this into GRASS, since lists are
>> > needed in Vect_get_point_in_poly() and the current library is buggy.
>> > Here is what I've written.
>>
>> I really need some help to integrate this one into trunk. The current
>> module prevents Vect_get_point_in_poly() from working correctly in
>> some unusual cases.
>
> So are you going to modify your code to match the existing linkm
> library, or modify the vector and bitmap libraries to use the new
> interface?
I was hoping for more experienced grass developers to suggest the
names of the functions and etc. Then I'll modify what's needed and
give diffs to someone to apply them in trunk.
The functions used by the bitmap and vector libraries are:
link_cleanup
link_dispose
link_exit_on_error
link_init
link_new
link_set_chunk_size
In spite of the name, its only use purpose appears to be as an
allocator of fixed-sized blocks. In which case, even the proposed
replacement seems too complex.
We probably don't need (or want) to free individual chunks as they
become empty; they can be retained for future allocations. We just
need to free everything in link_dispose().
OTOH, I don't even know if we really need *any* of this. Certainly,
the code in lib/Vlib/poly.c could quite easily just use a realloc()ed
array, with link pointers being replaced by array indices.
The bitmap code probably could as well, although it would need a bit
more work. But then, AFAICT, nothing actually creates sparse bitmaps
(which are the sole reason that the bitmap library uses the link
library).
--
Glynn Clements <glynn@gclements.plus.com>
Hi,
Here is my two-month-delay answer (sorry, very busy at school).
We probably don't need (or want) to free individual chunks as they
become empty; they can be retained for future allocations. We just
need to free everything in link_dispose().
We don't actually free allocated fixed-sized blocks. However, we need
to mark when a block is empty (ready to be "allocated" again).
OTOH, I don't even know if we really need *any* of this. Certainly,
the code in lib/Vlib/poly.c could quite easily just use a realloc()ed
array, with link pointers being replaced by array indices.
Let's assume that every time we call realloc() we double the size of
the array. If we need to allocate N elements, then we will make
log2(N) calls to realloc(). Moreover, in worst case scenario, the
realloc()s would have made a total of 2N element copies. We increase
the constant in the complexity of the algorithm, but my linkm also
increases it (probably even more).
Note: the results worsen if we don't use the "double the size of the
array" rule. For example adding a constant number of elements in every
realloc() is very bad asymptotically.
Having said that, I couldn't agree more to you that we don't need *any* of this.
The bitmap code probably could as well, although it would need a bit
more work. But then, AFAICT, nothing actually creates sparse bitmaps
(which are the sole reason that the bitmap library uses the link
library).
I'm not familiar with bitmap.c yet. I'll have a look
Regards,
Rosen Matev
Rosen Matev wrote:
> We probably don't need (or want) to free individual chunks as they
> become empty; they can be retained for future allocations. We just
> need to free everything in link_dispose().
We don't actually free allocated fixed-sized blocks. However, we need
to mark when a block is empty (ready to be "allocated" again).
In that case, it's probably easier to just keep blocks permanently
allocated. Free nodes live on a global free list, from where new nodes
are allocated. When the free list is empty, a new block is allocated
and its nodes are immediately placed on the free list.
If it wasn't for link_dispose(), you wouldn't even need to keep any
details of the actual blocks.
> OTOH, I don't even know if we really need *any* of this. Certainly,
> the code in lib/Vlib/poly.c could quite easily just use a realloc()ed
> array, with link pointers being replaced by array indices.
Let's assume that every time we call realloc() we double the size of
the array. If we need to allocate N elements, then we will make
log2(N) calls to realloc(). Moreover, in worst case scenario, the
realloc()s would have made a total of 2N element copies. We increase
the constant in the complexity of the algorithm, but my linkm also
increases it (probably even more).
Note: the results worsen if we don't use the "double the size of the
array" rule. For example adding a constant number of elements in every
realloc() is very bad asymptotically.
Ultimately, the time complexity is still only O(n), and anything which
processes the resulting polygon will be at least O(n), and probably
with a much larger constant.
--
Glynn Clements <glynn@gclements.plus.com>