[Re-devel] Using a heap (not a linked list) for timers

Rob Day rkd at rkd.me.uk
Sun Apr 24 13:53:34 CEST 2016

On 17/04/16 12:49, Alfred E. Heggestad wrote:

> Hey Rob,
> the current code has a linked-list element (struct le) in the
> timer struct, thus avoiding memory allocations. Would it be possible
> to do something similar with the heap structure ? 

Unfortunately I don't think it is - the data store underlying a heap
needs to support O(1) random access, so it needs to be a C array rather
than a linked list. Note that the heap doesn't allocate memory on every
timer addition - it starts with a 13-element array then doubles its size
when it needs to grow, so it should quickly 'figure out' what the right
size is for an application and then not do any more allocating.

> we are maintaining a test-program for libre/librem that is
> called "retest". This program mainly tests that the code is correct.
> can you try to run this program against your code? the latest
> version is here:
>     http://www.creytiv.com/pub/retest-0.4.4.tar.gz

Thanks! this was a useful test to run - it flushed out a couple of bugs
around the case when the heap became empty. I had to fix up retest to
expect a heap structure, but it's still testing the same properties
(timers all pop, timers are ordered) - that patch is attached.

> I tried to apply your patch locally and compile, but a source file
> "tmr_heap.c" was missing. Would it be possible to get a complete
> patch ?

Sorry about that - just unfamiliarity with SVN. I've attached an updated
patch including tmr_heap.c and some other fixes (e.g. the ones coming
out of retest).

> /alfred

-------------- next part --------------
A non-text attachment was scrubbed...
Name: timer_heap.patch
Type: text/x-patch
Size: 18917 bytes
Desc: not available
URL: <http://lists.creytiv.com/pipermail/re-devel/attachments/20160424/52acd541/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: retest_tmr.patch
Type: text/x-patch
Size: 2462 bytes
Desc: not available
URL: <http://lists.creytiv.com/pipermail/re-devel/attachments/20160424/52acd541/attachment-0001.bin>
-------------- next part --------------
Re-devel mailing list
Re-devel at lists.creytiv.com

More information about the Re-devel mailing list