On 10/15/2015 12:56 AM, Jakub Jelinek wrote:
On Sun, Oct 11, 2015 at 12:47:19PM -0700, Aldy Hernandez wrote:
I'm investigating balanced binary tree options for the multiple priorities
variant of the task scheduler. In looking at the splay tree adaption in
libgomp, I noticed that it requires preexisting typedefs and other
definitions before including splay-tree.h. This makes it impossible to
reuse for another key within the library because splay-tree.c must know
about the node contents, and other files throughout libgomp all share the
aforementioned typedefs (because they all include libgomp.h).
I also can't use libiberty's version because there are name conflicts with
libgomp's adaptation.
I see no reason why the splay tree implementation itself (splay-tree.c)
needs to know about the content of the nodes. With a little rearranging of
the data structures and some casts, we can reuse the splay trees at will.
With the following patch we achieve the above, with the only penalty of an
indirection for a compare callback.
Tested with make check-target-libgomp on x86-64 Linux.
What about the following patch instead?
Untested, other than compile time testing.
I would ideally like to look at sp->root from within header files
(priority_queue.h) to quickly determine if we have an empty queue, and
the contents of the splay tree are not available in the header file
(task.c, or priority_queue.c as you describe). I'd hate to have to call
a splay-tree.c function to do so.
I could do pointer magic from the header file (yuck).
I could take sp == NULL to mean empty, but then we need to allocate the
splay tree which is silly cause it's just one pointer.
Up to you, it's your baby. ;-)
Aldy
