[LITMUS^RT] Binary heaps for Litmus

[Glenn Elliott]

I realized that binheap_delete() was more complicated than necessary.  Cleaned that up and then added binheap_decrease().  Sorry for the explosion of patches.

-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/b0793a66/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/b0793a66/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/b0793a66/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-Simplify-binheap_delete-and-add-binheap_decrease.patch
Type: application/octet-stream
Size: 5043 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120321/b0793a66/attachment-0003.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0005-Make-GSN-EDF-work-with-simlified-binheap_delete.patch
Type: application/octet-stream
Size: 1349 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120321/b0793a66/attachment-0004.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0006-Make-C-EDF-work-with-simplified-binheap_delete.patch
Type: application/octet-stream
Size: 811 bytes
Desc: not available
URL: <http://lists.litmus-rt.org/pipermail/litmus-dev/attachments/20120321/b0793a66/attachment-0005.obj>
-------------- next part --------------


On Mar 21, 2012, at 5:02 PM, Glenn Elliott wrote:

> 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
> 
> <0001-Binary-heap-implementation.patch><0002-GSN-EDF-Use-binary-heap-instead-of-binomial-heap.patch><0003-C-EDF-Use-binary-heap-instead-of-binomial-heap.patch>