1/* { dg-do run } */
2/* { dg-set-target-env-var OMP_CANCELLATION "true" } */
3
4#include <stdlib.h>
5#include <omp.h>
6
7struct T { struct T *children[2]; int val; };
8
9struct T *
10search (struct T *tree, int val, int lvl)
11{
12  if (tree == NULL || tree->val == val)
13    return tree;
14  struct T *ret = NULL;
15  int i;
16  for (i = 0; i < 2; i++)
17    #pragma omp task shared(ret) if(lvl < 10)
18    {
19      struct T *r = search (tree->children[i], val, lvl + 1);
20      if (r)
21	{
22	  #pragma omp atomic write
23	  ret = r;
24	  #pragma omp cancel taskgroup
25	}
26    }
27  #pragma omp taskwait
28  return ret;
29}
30
31struct T *
32searchp (struct T *tree, int val)
33{
34  struct T *ret;
35  #pragma omp parallel shared(ret) firstprivate (tree, val)
36  #pragma omp single
37  #pragma omp taskgroup
38  ret = search (tree, val, 0);
39  return ret;
40}
41
42int
43main ()
44{
45  /* Must be power of two minus 1.  */
46  int size = 0x7ffff;
47  struct T *trees = (struct T *) malloc (size * sizeof (struct T));
48  if (trees == NULL)
49    return 0;
50  int i, l = 1, b = 0;
51  for (i = 0; i < size; i++)
52    {
53      if (i == l)
54	{
55	  b = l;
56	  l = l * 2 + 1;
57	}
58      trees[i].val = i;
59      trees[i].children[0] = l == size ? NULL : &trees[l + (i - b) * 2];
60      trees[i].children[1] = l == size ? NULL : &trees[l + (i - b) * 2 + 1];
61    }
62  for (i = 0; i < 50; i++)
63    {
64      int v = random () & size;
65      if (searchp (&trees[0], v) != &trees[v])
66	abort ();
67    }
68  free (trees);
69  return 0;
70}
71