1/* A splay-tree datatype.
2   Copyright (C) 1998-2020 Free Software Foundation, Inc.
3   Contributed by Mark Mitchell (mark@markmitchell.com).
4
5   This file is part of the GNU Offloading and Multi Processing Library
6   (libgomp).
7
8   Libgomp is free software; you can redistribute it and/or modify it
9   under the terms of the GNU General Public License as published by
10   the Free Software Foundation; either version 3, or (at your option)
11   any later version.
12
13   Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
14   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15   FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
16   more details.
17
18   Under Section 7 of GPL version 3, you are granted additional
19   permissions described in the GCC Runtime Library Exception, version
20   3.1, as published by the Free Software Foundation.
21
22   You should have received a copy of the GNU General Public License and
23   a copy of the GCC Runtime Library Exception along with this program;
24   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
25   <http://www.gnu.org/licenses/>.  */
26
27/* The splay tree code copied from include/splay-tree.h and adjusted,
28   so that all the data lives directly in splay_tree_node_s structure
29   and no extra allocations are needed.  */
30
31/* For an easily readable description of splay-trees, see:
32
33     Lewis, Harry R. and Denenberg, Larry.  Data Structures and Their
34     Algorithms.  Harper-Collins, Inc.  1991.
35
36   The major feature of splay trees is that all basic tree operations
37   are amortized O(log n) time for a tree with n nodes.  */
38
39#include "libgomp.h"
40
41/* Rotate the edge joining the left child N with its parent P.  PP is the
42   grandparents' pointer to P.  */
43
44static inline void
45rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
46{
47  splay_tree_node tmp;
48  tmp = n->right;
49  n->right = p;
50  p->left = tmp;
51  *pp = n;
52}
53
54/* Rotate the edge joining the right child N with its parent P.  PP is the
55   grandparents' pointer to P.  */
56
57static inline void
58rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
59{
60  splay_tree_node tmp;
61  tmp = n->left;
62  n->left = p;
63  p->right = tmp;
64  *pp = n;
65}
66
67/* Bottom up splay of KEY.  */
68
69static void
70splay_tree_splay (splay_tree sp, splay_tree_key key)
71{
72  if (sp->root == NULL)
73    return;
74
75  do {
76    int cmp1, cmp2;
77    splay_tree_node n, c;
78
79    n = sp->root;
80    cmp1 = splay_compare (key, &n->key);
81
82    /* Found.  */
83    if (cmp1 == 0)
84      return;
85
86    /* Left or right?  If no child, then we're done.  */
87    if (cmp1 < 0)
88      c = n->left;
89    else
90      c = n->right;
91    if (!c)
92      return;
93
94    /* Next one left or right?  If found or no child, we're done
95       after one rotation.  */
96    cmp2 = splay_compare (key, &c->key);
97    if (cmp2 == 0
98	|| (cmp2 < 0 && !c->left)
99	|| (cmp2 > 0 && !c->right))
100      {
101	if (cmp1 < 0)
102	  rotate_left (&sp->root, n, c);
103	else
104	  rotate_right (&sp->root, n, c);
105	return;
106      }
107
108    /* Now we have the four cases of double-rotation.  */
109    if (cmp1 < 0 && cmp2 < 0)
110      {
111	rotate_left (&n->left, c, c->left);
112	rotate_left (&sp->root, n, n->left);
113      }
114    else if (cmp1 > 0 && cmp2 > 0)
115      {
116	rotate_right (&n->right, c, c->right);
117	rotate_right (&sp->root, n, n->right);
118      }
119    else if (cmp1 < 0 && cmp2 > 0)
120      {
121	rotate_right (&n->left, c, c->right);
122	rotate_left (&sp->root, n, n->left);
123      }
124    else if (cmp1 > 0 && cmp2 < 0)
125      {
126	rotate_left (&n->right, c, c->left);
127	rotate_right (&sp->root, n, n->right);
128      }
129  } while (1);
130}
131
132/* Insert a new NODE into SP.  The NODE shouldn't exist in the tree.  */
133
134attribute_hidden void
135splay_tree_insert (splay_tree sp, splay_tree_node node)
136{
137  int comparison = 0;
138
139  splay_tree_splay (sp, &node->key);
140
141  if (sp->root)
142    comparison = splay_compare (&sp->root->key, &node->key);
143
144  if (sp->root && comparison == 0)
145    gomp_fatal ("Duplicate node");
146  else
147    {
148      /* Insert it at the root.  */
149      if (sp->root == NULL)
150	node->left = node->right = NULL;
151      else if (comparison < 0)
152	{
153	  node->left = sp->root;
154	  node->right = node->left->right;
155	  node->left->right = NULL;
156	}
157      else
158	{
159	  node->right = sp->root;
160	  node->left = node->right->left;
161	  node->right->left = NULL;
162	}
163
164      sp->root = node;
165    }
166}
167
168/* Remove node with KEY from SP.  It is not an error if it did not exist.  */
169
170attribute_hidden void
171splay_tree_remove (splay_tree sp, splay_tree_key key)
172{
173  splay_tree_splay (sp, key);
174
175  if (sp->root && splay_compare (&sp->root->key, key) == 0)
176    {
177      splay_tree_node left, right;
178
179      left = sp->root->left;
180      right = sp->root->right;
181
182      /* One of the children is now the root.  Doesn't matter much
183	 which, so long as we preserve the properties of the tree.  */
184      if (left)
185	{
186	  sp->root = left;
187
188	  /* If there was a right child as well, hang it off the
189	     right-most leaf of the left child.  */
190	  if (right)
191	    {
192	      while (left->right)
193		left = left->right;
194	      left->right = right;
195	    }
196	}
197      else
198	sp->root = right;
199    }
200}
201
202/* Lookup KEY in SP, returning NODE if present, and NULL
203   otherwise.  */
204
205attribute_hidden splay_tree_key
206splay_tree_lookup (splay_tree sp, splay_tree_key key)
207{
208  splay_tree_splay (sp, key);
209
210  if (sp->root && splay_compare (&sp->root->key, key) == 0)
211    return &sp->root->key;
212  else
213    return NULL;
214}
215
216/* Helper function for splay_tree_foreach.
217
218   Run FUNC on every node in KEY.  */
219
220static void
221splay_tree_foreach_internal (splay_tree_node node, splay_tree_callback func,
222			     void *data)
223{
224  if (!node)
225    return;
226  func (&node->key, data);
227  splay_tree_foreach_internal (node->left, func, data);
228  /* Yeah, whatever.  GCC can fix my tail recursion.  */
229  splay_tree_foreach_internal (node->right, func, data);
230}
231
232/* Run FUNC on each of the nodes in SP.  */
233
234attribute_hidden void
235splay_tree_foreach (splay_tree sp, splay_tree_callback func, void *data)
236{
237  splay_tree_foreach_internal (sp->root, func, data);
238}
239