diff mbox

[gomp4.1] make libgomp's splay tree implementation key agnostic

Message ID 20151015075612.GC478@tucnak.redhat.com
State New
Headers show

Commit Message

Jakub Jelinek Oct. 15, 2015, 7:56 a.m. UTC 
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.

If one includes splay-tree.h (as already included from splay-tree.h) without
special macros, you get what we have right now, but you can instantiate it
again (though, in that case only for use within a single source file).
The typedefs and type definitions could be moved into libgomp.h if you need
them there, where you put the task_splay_compare inline doesn't matter
either (either libgomp.h or task.c if you only use it in there),
and it is just a matter of including splay-tree.h again in task.c
after defining splay_tree_prefix task.  You then use
task_splay_tree_{lookup,insert,remove} for the task instantiations.



	Jakub

Comments

Aldy Hernandez Oct. 15, 2015, 2:56 p.m. UTC | #1 
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
diff mbox

Patch

--- libgomp/splay-tree.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/splay-tree.c	2015-10-15 08:58:17.301398630 +0200
@@ -37,9 +37,6 @@ 
    are amortized O(log n) time for a tree with n nodes.  */
 
 #include "libgomp.h"
-#include "splay-tree.h"
-
-extern int splay_compare (splay_tree_key, splay_tree_key);
 
 /* Rotate the edge joining the left child N with its parent P.  PP is the
    grandparents' pointer to P.  */
--- libgomp/target.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/target.c	2015-10-15 08:56:45.040779485 +0200
@@ -92,23 +92,6 @@  gomp_realloc_unlock (void *old, size_t s
   return ret;
 }
 
-/* The comparison function.  */
-
-attribute_hidden int
-splay_compare (splay_tree_key x, splay_tree_key y)
-{
-  if (x->host_start == x->host_end
-      && y->host_start == y->host_end)
-    return 0;
-  if (x->host_end <= y->host_start)
-    return -1;
-  if (x->host_start >= y->host_end)
-    return 1;
-  return 0;
-}
-
-#include "splay-tree.h"
-
 attribute_hidden void
 gomp_init_targets_once (void)
 {
--- libgomp/oacc-mem.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/oacc-mem.c	2015-10-15 08:58:45.351978800 +0200
@@ -31,7 +31,6 @@ 
 #include "libgomp.h"
 #include "gomp-constants.h"
 #include "oacc-int.h"
-#include "splay-tree.h"
 #include <stdint.h>
 #include <assert.h>
 
--- libgomp/libgomp.h.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/libgomp.h	2015-10-15 08:57:40.708946305 +0200
@@ -800,6 +800,21 @@  struct splay_tree_key_s {
   uintptr_t async_refcount;
 };
 
+/* The comparison function.  */
+
+static inline int
+splay_compare (splay_tree_key x, splay_tree_key y)
+{
+  if (x->host_start == x->host_end
+      && y->host_start == y->host_end)
+    return 0;
+  if (x->host_end <= y->host_start)
+    return -1;
+  if (x->host_start >= y->host_end)
+    return 1;
+  return 0;
+}
+
 #include "splay-tree.h"
 
 typedef struct acc_dispatch_t
--- libgomp/splay-tree.h.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/splay-tree.h	2015-10-15 09:45:55.073722692 +0200
@@ -33,7 +33,12 @@  typedef struct splay_tree_node_s *splay_
 typedef struct splay_tree_s *splay_tree;
 typedef struct splay_tree_key_s *splay_tree_key;
    define splay_tree_key_s structure, and define
-   splay_compare inline function.  */
+   splay_compare inline function.
+
+   Or, they can define splay_tree_prefix macro before including this
+   header and then all the above types, the splay_compare function
+   and the splay_tree_{lookup,insert_remove} function will be prefixed
+   by that prefix.  */
 
 /* For an easily readable description of splay-trees, see:
 
@@ -43,6 +48,32 @@  typedef struct splay_tree_key_s *splay_t
    The major feature of splay trees is that all basic tree operations
    are amortized O(log n) time for a tree with n nodes.  */
 
+#ifdef splay_tree_prefix
+# define splay_tree_name_1(prefix, name) prefix ## _ ## name
+# define splay_tree_name(prefix, name) splay_tree_name_1 (prefix, name)
+# define splay_tree_node_s	\
+    splay_tree_name (splay_tree_prefix, splay_tree_node_s)
+# define splay_tree_s		\
+    splay_tree_name (splay_tree_prefix, splay_tree_s)
+# define splay_tree_key_s	\
+    splay_tree_name (splay_tree_prefix, splay_tree_key_s)
+# define splay_tree_node	\
+    splay_tree_name (splay_tree_prefix, splay_tree_node)
+# define splay_tree		\
+    splay_tree_name (splay_tree_prefix, splay_tree)
+# define splay_tree_key		\
+    splay_tree_name (splay_tree_prefix, splay_tree_key)
+# define splay_compare		\
+    splay_tree_name (splay_tree_prefix, splay_compare)
+# define splay_tree_lookup	\
+    splay_tree_name (splay_tree_prefix, splay_tree_lookup)
+# define splay_tree_insert	\
+    splay_tree_name (splay_tree_prefix, splay_tree_insert)
+# define splay_tree_remove	\
+    splay_tree_name (splay_tree_prefix, splay_tree_remove)
+# undef _SPLAY_TREE_H
+#endif
+
 #ifndef _SPLAY_TREE_H
 #define _SPLAY_TREE_H 1
 
@@ -63,4 +94,21 @@  extern splay_tree_key splay_tree_lookup
 extern void splay_tree_insert (splay_tree, splay_tree_node);
 extern void splay_tree_remove (splay_tree, splay_tree_key);
 
+#ifdef splay_tree_prefix
+# include "splay-tree.c"
+# undef splay_tree_prefix
+# undef splay_tree_name_1
+# undef splay_tree_name
+# undef splay_tree_node_s
+# undef splay_tree_s
+# undef splay_tree_key_s
+# undef splay_tree_node
+# undef splay_tree
+# undef splay_tree_key
+# undef splay_compare
+# undef splay_tree_lookup
+# undef splay_tree_insert
+# undef splay_tree_remove
+#endif
+
 #endif /* _SPLAY_TREE_H */
--- libgomp/task.c.jj	2015-10-14 10:24:10.000000000 +0200
+++ libgomp/task.c	2015-10-15 09:42:57.513362943 +0200
@@ -59,6 +59,31 @@  htab_eq (hash_entry_type x, hash_entry_t
   return x->addr == y->addr;
 }
 
+/* Define another splay tree instantiation, for task.c priorities.  */
+
+typedef struct task_splay_tree_node_s *task_splay_tree_node;
+typedef struct task_splay_tree_s *task_splay_tree;
+typedef struct task_splay_tree_key_s *task_splay_tree_key;
+
+struct task_splay_tree_key_s {
+  int priority;
+};
+
+/* The comparison function.  */
+
+static inline int
+task_splay_compare (task_splay_tree_key x, task_splay_tree_key y)
+{
+  if (x->priority < y->priority)
+    return -1;
+  if (x->priority > y->priority)
+    return 1;
+  return 0;
+}
+
+#define splay_tree_prefix task
+#include "splay-tree.h"
+
 /* Create a new task data structure.  */
 
 void