===================================================================
@@ -0,0 +1,227 @@
+/* A splay-tree datatype.
+ Copyright 1998-2013
+ Free Software Foundation, Inc.
+ Contributed by Mark Mitchell (mark@markmitchell.com).
+
+ This file is part of the GNU OpenMP Library (libgomp).
+
+ Libgomp is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ more details.
+
+ Under Section 7 of GPL version 3, you are granted additional
+ permissions described in the GCC Runtime Library Exception, version
+ 3.1, as published by the Free Software Foundation.
+
+ You should have received a copy of the GNU General Public License and
+ a copy of the GCC Runtime Library Exception along with this program;
+ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+ <http://www.gnu.org/licenses/>. */
+
+/* The splay tree code copied from include/splay-tree.h and adjusted,
+ so that all the data lives directly in splay_tree_node_s structure
+ and no extra allocations are needed.
+
+ Files including this header should before including it add:
+typedef struct splay_tree_node_s *splay_tree_node;
+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. */
+
+/* For an easily readable description of splay-trees, see:
+
+ Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
+ Algorithms. Harper-Collins, Inc. 1991.
+
+ The major feature of splay trees is that all basic tree operations
+ are amortized O(log n) time for a tree with n nodes. */
+
+/* Forward declaration for a node in the tree. */
+typedef struct splay_tree_node_s *splay_tree_node;
+typedef struct splay_tree_s *splay_tree;
+typedef struct splay_tree_key_s *splay_tree_key;
+
+#include "libgomp.h"
+#include "splay-tree.h"
+
+/* Rotate the edge joining the left child N with its parent P. PP is the
+ grandparents' pointer to P. */
+
+static inline void
+rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
+{
+ splay_tree_node tmp;
+ tmp = n->right;
+ n->right = p;
+ p->left = tmp;
+ *pp = n;
+}
+
+/* Rotate the edge joining the right child N with its parent P. PP is the
+ grandparents' pointer to P. */
+
+static inline void
+rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
+{
+ splay_tree_node tmp;
+ tmp = n->left;
+ n->left = p;
+ p->right = tmp;
+ *pp = n;
+}
+
+/* Bottom up splay of KEY. */
+
+static void
+splay_tree_splay (splay_tree sp, splay_tree_key key)
+{
+ if (sp->root == NULL)
+ return;
+
+ do {
+ int cmp1, cmp2;
+ splay_tree_node n, c;
+
+ n = sp->root;
+ cmp1 = splay_compare (key, &n->key);
+
+ /* Found. */
+ if (cmp1 == 0)
+ return;
+
+ /* Left or right? If no child, then we're done. */
+ if (cmp1 < 0)
+ c = n->left;
+ else
+ c = n->right;
+ if (!c)
+ return;
+
+ /* Next one left or right? If found or no child, we're done
+ after one rotation. */
+ cmp2 = splay_compare (key, &c->key);
+ if (cmp2 == 0
+ || (cmp2 < 0 && !c->left)
+ || (cmp2 > 0 && !c->right))
+ {
+ if (cmp1 < 0)
+ rotate_left (&sp->root, n, c);
+ else
+ rotate_right (&sp->root, n, c);
+ return;
+ }
+
+ /* Now we have the four cases of double-rotation. */
+ if (cmp1 < 0 && cmp2 < 0)
+ {
+ rotate_left (&n->left, c, c->left);
+ rotate_left (&sp->root, n, n->left);
+ }
+ else if (cmp1 > 0 && cmp2 > 0)
+ {
+ rotate_right (&n->right, c, c->right);
+ rotate_right (&sp->root, n, n->right);
+ }
+ else if (cmp1 < 0 && cmp2 > 0)
+ {
+ rotate_right (&n->left, c, c->right);
+ rotate_left (&sp->root, n, n->left);
+ }
+ else if (cmp1 > 0 && cmp2 < 0)
+ {
+ rotate_left (&n->right, c, c->left);
+ rotate_right (&sp->root, n, n->right);
+ }
+ } while (1);
+}
+
+/* Insert a new NODE into SP. The NODE shouldn't exist in the tree. */
+
+attribute_hidden void
+splay_tree_insert (splay_tree sp, splay_tree_node node)
+{
+ int comparison = 0;
+
+ splay_tree_splay (sp, &node->key);
+
+ if (sp->root)
+ comparison = splay_compare (&sp->root->key, &node->key);
+
+ if (sp->root && comparison == 0)
+ abort ();
+ else
+ {
+ /* Insert it at the root. */
+ if (sp->root == NULL)
+ node->left = node->right = NULL;
+ else if (comparison < 0)
+ {
+ node->left = sp->root;
+ node->right = node->left->right;
+ node->left->right = NULL;
+ }
+ else
+ {
+ node->right = sp->root;
+ node->left = node->right->left;
+ node->right->left = NULL;
+ }
+
+ sp->root = node;
+ }
+}
+
+/* Remove node with KEY from SP. It is not an error if it did not exist. */
+
+attribute_hidden void
+splay_tree_remove (splay_tree sp, splay_tree_key key)
+{
+ splay_tree_splay (sp, key);
+
+ if (sp->root && splay_compare (&sp->root->key, key) == 0)
+ {
+ splay_tree_node left, right;
+
+ left = sp->root->left;
+ right = sp->root->right;
+
+ /* One of the children is now the root. Doesn't matter much
+ which, so long as we preserve the properties of the tree. */
+ if (left)
+ {
+ sp->root = left;
+
+ /* If there was a right child as well, hang it off the
+ right-most leaf of the left child. */
+ if (right)
+ {
+ while (left->right)
+ left = left->right;
+ left->right = right;
+ }
+ }
+ else
+ sp->root = right;
+ }
+}
+
+/* Lookup KEY in SP, returning NODE if present, and NULL
+ otherwise. */
+
+attribute_hidden splay_tree_key
+splay_tree_lookup (splay_tree sp, splay_tree_key key)
+{
+ splay_tree_splay (sp, key);
+
+ if (sp->root && splay_compare (&sp->root->key, key) == 0)
+ return &sp->root->key;
+ else
+ return NULL;
+}
===================================================================
@@ -43,6 +43,11 @@
The major feature of splay trees is that all basic tree operations
are amortized O(log n) time for a tree with n nodes. */
+#include "target.h"
+
+#ifndef _SPLAY_TREE_H
+#define _SPLAY_TREE_H
+
/* The nodes in the splay tree. */
struct splay_tree_node_s {
struct splay_tree_key_s key;
@@ -56,177 +61,9 @@
splay_tree_node root;
};
-/* Rotate the edge joining the left child N with its parent P. PP is the
- grandparents' pointer to P. */
+attribute_hidden splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key);
+attribute_hidden void splay_tree_insert (splay_tree, splay_tree_node);
+attribute_hidden void splay_tree_remove (splay_tree, splay_tree_key);
+attribute_hidden int splay_compare (splay_tree_key, splay_tree_key);
-static inline void
-rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
-{
- splay_tree_node tmp;
- tmp = n->right;
- n->right = p;
- p->left = tmp;
- *pp = n;
-}
-
-/* Rotate the edge joining the right child N with its parent P. PP is the
- grandparents' pointer to P. */
-
-static inline void
-rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
-{
- splay_tree_node tmp;
- tmp = n->left;
- n->left = p;
- p->right = tmp;
- *pp = n;
-}
-
-/* Bottom up splay of KEY. */
-
-static void
-splay_tree_splay (splay_tree sp, splay_tree_key key)
-{
- if (sp->root == NULL)
- return;
-
- do {
- int cmp1, cmp2;
- splay_tree_node n, c;
-
- n = sp->root;
- cmp1 = splay_compare (key, &n->key);
-
- /* Found. */
- if (cmp1 == 0)
- return;
-
- /* Left or right? If no child, then we're done. */
- if (cmp1 < 0)
- c = n->left;
- else
- c = n->right;
- if (!c)
- return;
-
- /* Next one left or right? If found or no child, we're done
- after one rotation. */
- cmp2 = splay_compare (key, &c->key);
- if (cmp2 == 0
- || (cmp2 < 0 && !c->left)
- || (cmp2 > 0 && !c->right))
- {
- if (cmp1 < 0)
- rotate_left (&sp->root, n, c);
- else
- rotate_right (&sp->root, n, c);
- return;
- }
-
- /* Now we have the four cases of double-rotation. */
- if (cmp1 < 0 && cmp2 < 0)
- {
- rotate_left (&n->left, c, c->left);
- rotate_left (&sp->root, n, n->left);
- }
- else if (cmp1 > 0 && cmp2 > 0)
- {
- rotate_right (&n->right, c, c->right);
- rotate_right (&sp->root, n, n->right);
- }
- else if (cmp1 < 0 && cmp2 > 0)
- {
- rotate_right (&n->left, c, c->right);
- rotate_left (&sp->root, n, n->left);
- }
- else if (cmp1 > 0 && cmp2 < 0)
- {
- rotate_left (&n->right, c, c->left);
- rotate_right (&sp->root, n, n->right);
- }
- } while (1);
-}
-
-/* Insert a new NODE into SP. The NODE shouldn't exist in the tree. */
-
-static void
-splay_tree_insert (splay_tree sp, splay_tree_node node)
-{
- int comparison = 0;
-
- splay_tree_splay (sp, &node->key);
-
- if (sp->root)
- comparison = splay_compare (&sp->root->key, &node->key);
-
- if (sp->root && comparison == 0)
- abort ();
- else
- {
- /* Insert it at the root. */
- if (sp->root == NULL)
- node->left = node->right = NULL;
- else if (comparison < 0)
- {
- node->left = sp->root;
- node->right = node->left->right;
- node->left->right = NULL;
- }
- else
- {
- node->right = sp->root;
- node->left = node->right->left;
- node->right->left = NULL;
- }
-
- sp->root = node;
- }
-}
-
-/* Remove node with KEY from SP. It is not an error if it did not exist. */
-
-static void
-splay_tree_remove (splay_tree sp, splay_tree_key key)
-{
- splay_tree_splay (sp, key);
-
- if (sp->root && splay_compare (&sp->root->key, key) == 0)
- {
- splay_tree_node left, right;
-
- left = sp->root->left;
- right = sp->root->right;
-
- /* One of the children is now the root. Doesn't matter much
- which, so long as we preserve the properties of the tree. */
- if (left)
- {
- sp->root = left;
-
- /* If there was a right child as well, hang it off the
- right-most leaf of the left child. */
- if (right)
- {
- while (left->right)
- left = left->right;
- left->right = right;
- }
- }
- else
- sp->root = right;
- }
-}
-
-/* Lookup KEY in SP, returning NODE if present, and NULL
- otherwise. */
-
-static splay_tree_key
-splay_tree_lookup (splay_tree sp, splay_tree_key key)
-{
- splay_tree_splay (sp, key);
-
- if (sp->root && splay_compare (&sp->root->key, key) == 0)
- return &sp->root->key;
- else
- return NULL;
-}
+#endif /* _SPLAY_TREE_H */
===================================================================
@@ -69,20 +69,7 @@
splay_tree_key list[];
};
-struct splay_tree_key_s {
- /* Address of the host object. */
- uintptr_t host_start;
- /* Address immediately after the host object. */
- uintptr_t host_end;
- /* Descriptor of the target memory. */
- struct target_mem_desc *tgt;
- /* Offset from tgt->tgt_start to the start of the target object. */
- uintptr_t tgt_offset;
- /* Reference count. */
- uintptr_t refcount;
- /* True if data should be copied from device to host at the end. */
- bool copy_from;
-};
+#include "target.h"
/* Array of descriptors of all available devices. */
static struct gomp_device_descr *devices;
@@ -92,7 +79,7 @@
/* The comparison function. */
-static int
+attribute_hidden int
splay_compare (splay_tree_key x, splay_tree_key y)
{
if (x->host_start == x->host_end
===================================================================
@@ -0,0 +1,46 @@
+/* Copyright (C) 2013 Free Software Foundation, Inc.
+ Contributed by Jakub Jelinek <jakub@redhat.com>.
+
+ This file is part of the GNU OpenMP Library (libgomp).
+
+ Libgomp is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ FOR A PARTICULAR PURPOSE. See the GNU General Public License for
+ more details.
+
+ Under Section 7 of GPL version 3, you are granted additional
+ permissions described in the GCC Runtime Library Exception, version
+ 3.1, as published by the Free Software Foundation.
+
+ You should have received a copy of the GNU General Public License and
+ a copy of the GCC Runtime Library Exception along with this program;
+ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+ <http://www.gnu.org/licenses/>. */
+
+/* This file handles the maintainence of threads in response to team
+ creation and termination. */
+
+#ifndef _TARGET_H
+#define _TARGET_H
+
+struct splay_tree_key_s {
+ /* Address of the host object. */
+ uintptr_t host_start;
+ /* Address immediately after the host object. */
+ uintptr_t host_end;
+ /* Descriptor of the target memory. */
+ struct target_mem_desc *tgt;
+ /* Offset from tgt->tgt_start to the start of the target object. */
+ uintptr_t tgt_offset;
+ /* Reference count. */
+ uintptr_t refcount;
+ /* True if data should be copied from device to host at the end. */
+ bool copy_from;
+};
+
+#endif /* _TARGET_H */
===================================================================
@@ -60,7 +60,7 @@
libgomp_la_SOURCES = alloc.c barrier.c critical.c env.c error.c iter.c \
iter_ull.c loop.c loop_ull.c ordered.c parallel.c sections.c single.c \
task.c team.c work.c lock.c mutex.c proc.c sem.c bar.c ptrlock.c \
- time.c fortran.c affinity.c target.c oacc-parallel.c
+ time.c fortran.c affinity.c target.c oacc-parallel.c splay-tree.c
nodist_noinst_HEADERS = libgomp_f.h
nodist_libsubinclude_HEADERS = omp.h openacc.h
===================================================================
@@ -96,7 +96,8 @@
error.lo iter.lo iter_ull.lo loop.lo loop_ull.lo ordered.lo \
parallel.lo sections.lo single.lo task.lo team.lo work.lo \
lock.lo mutex.lo proc.lo sem.lo bar.lo ptrlock.lo time.lo \
- fortran.lo affinity.lo target.lo oacc-parallel.lo
+ fortran.lo affinity.lo target.lo oacc-parallel.lo \
+ splay-tree.lo
libgomp_la_OBJECTS = $(am_libgomp_la_OBJECTS)
DEFAULT_INCLUDES = -I.@am__isrc@
depcomp = $(SHELL) $(top_srcdir)/../depcomp
@@ -317,7 +318,7 @@
libgomp_la_SOURCES = alloc.c barrier.c critical.c env.c error.c iter.c \
iter_ull.c loop.c loop_ull.c ordered.c parallel.c sections.c single.c \
task.c team.c work.c lock.c mutex.c proc.c sem.c bar.c ptrlock.c \
- time.c fortran.c affinity.c target.c oacc-parallel.c
+ time.c fortran.c affinity.c target.c oacc-parallel.c splay-tree.c
nodist_noinst_HEADERS = libgomp_f.h
nodist_libsubinclude_HEADERS = omp.h openacc.h
@@ -477,6 +478,7 @@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/sections.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/sem.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/single.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/splay-tree.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/target.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/task.Plo@am__quote@
@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/team.Plo@am__quote@