[LITMUS^RT] Binary heaps for Litmus

[Glenn Elliott]

Hi All,

GSN-EDF and C-EDF use a binomial heap to prioritize CPUs.  This seems to be a little bit overkill since binomial heaps are best at heap merges.  This patch series does the following:

1) Implements a binary heap in the style of Linux's linked lists.
2) Updates GSN-EDF to use the binary heap instead of the binomial heap to order CPUs.
3) Updates C-EDF to use the binary heap instead of the binomial heap to order CPUs.

I need to use this binary heap data structure for other work (priority queues that don't need binomial's fast merges), but I thought it could be applied to other domains.

I've attached the patches.

For those with access to CGIT on rtsrv.cs.unc.edu, here are links (easier to read):
Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=5b73afc4eb1b0303cb92eb29a2ecc59c1db69537
GSN-EDF w/ Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=bdce67bc2babc2e5b3b2440964e9cf819ac814dc
C-EDF w/ Binary Heap: http://rtsrv.cs.unc.edu/cgit/cgit.cgi/litmus-rt.git/commit/?h=wip-binary-heap&id=ee525fe7ba4edf4da2d293629ffdff2caa9ad02b

All of this work is in wip-binary-heap on rtsrv.cs.unc.edu.

I've tested these patches out both in QEMU and Bonham.  Comments and suggestions are welcome.

Thanks,
Glenn

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Binary-heap-implementation.patch
Type: application/octet-stream
Size: 14557 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120321/23e115f0/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-GSN-EDF-Use-binary-heap-instead-of-binomial-heap.patch
Type: application/octet-stream
Size: 5435 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120321/23e115f0/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-C-EDF-Use-binary-heap-instead-of-binomial-heap.patch
Type: application/octet-stream
Size: 3695 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120321/23e115f0/attachment-0002.obj>