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.
--- 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
Jakub
