[LITMUS^RT] Binary heaps for Litmus

[Björn Brandenburg]

On Mar 22, 2012, at 12:29 AM, Glenn Elliott wrote:

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

The attached patches are difficult to comment on. I'll copy and paste some segments.

> 
> 365	        /* NULL data pointers are used internally */
> 366	        if(!data) {
> 367	                WARN();
> 368	                return;
> 369	        }


Should that be a BUG_ON(!data)? It's clearly a misuse of the API, so why only a WARN()? It's not like the user could be expected to do anything about this. A BUG_ON() at least makes sure that it's noticed.

> 422	static inline void __binheap_delete_root(struct binheap_handle *handle,
> 423	                                                                                 struct binheap_node *container)
> 
> 500	static inline void __binheap_delete(
> 501	                                                                struct binheap_node *node_to_delete,
> 502	                                                                struct binheap_node *user_of_node,
> 503	                                                                struct binheap_handle *handle)
> 504	
> 

I don't know what your TAB setting is, but the above code looks very strangely indented to me (same in cgit).

I'm also not quite sure what replacing the  binomial heap in GSN-EDF with a binary heap is buying us.  The new code still relies on dynamic memory allocation and does not look much simpler to me than the existing binomial heap implementation. Is there some pressing need? I'm not really opposed to it, but I'd like to understand the motivation.

Anyway, before this is merged, I think it should be rebased to hide the fixup commits. (Commit bdce67bc2babc2e5b3b2440964e9cf819ac814dc contains unrelated changes, for example).

Thanks,
Björn