1/* A splay-tree datatype.
2   Copyright (C) 1998-2015 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#include "splay-tree.h"
41
42extern int splay_compare (splay_tree_key, splay_tree_key);
43
44/* Rotate the edge joining the left child N with its parent P.  PP is the
45   grandparents' pointer to P.  */
46
47static inline void
48rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
49{
50  splay_tree_node tmp;
51  tmp = n->right;
52  n->right = p;
53  p->left = tmp;
54  *pp = n;
55}
56
57/* Rotate the edge joining the right child N with its parent P.  PP is the
58   grandparents' pointer to P.  */
59
60static inline void
61rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
62{
63  splay_tree_node tmp;
64  tmp = n->left;
65  n->left = p;
66  p->right = tmp;
67  *pp = n;
68}
69
70/* Bottom up splay of KEY.  */
71
72static void
73splay_tree_splay (splay_tree sp, splay_tree_key key)
74{
75  if (sp->root == NULL)
76    return;
77
78  do {
79    int cmp1, cmp2;
80    splay_tree_node n, c;
81
82    n = sp->root;
83    cmp1 = splay_compare (key, &n->key);
84
85    /* Found.  */
86    if (cmp1 == 0)
87      return;
88
89    /* Left or right?  If no child, then we're done.  */
90    if (cmp1 < 0)
91      c = n->left;
92    else
93      c = n->right;
94    if (!c)
95      return;
96
97    /* Next one left or right?  If found or no child, we're done
98       after one rotation.  */
99    cmp2 = splay_compare (key, &c->key);
100    if (cmp2 == 0
101	|| (cmp2 < 0 && !c->left)
102	|| (cmp2 > 0 && !c->right))
103      {
104	if (cmp1 < 0)
105	  rotate_left (&sp->root, n, c);
106	else
107	  rotate_right (&sp->root, n, c);
108	return;
109      }
110
111    /* Now we have the four cases of double-rotation.  */
112    if (cmp1 < 0 && cmp2 < 0)
113      {
114	rotate_left (&n->left, c, c->left);
115	rotate_left (&sp->root, n, n->left);
116      }
117    else if (cmp1 > 0 && cmp2 > 0)
118      {
119	rotate_right (&n->right, c, c->right);
120	rotate_right (&sp->root, n, n->right);
121      }
122    else if (cmp1 < 0 && cmp2 > 0)
123      {
124	rotate_right (&n->left, c, c->right);
125	rotate_left (&sp->root, n, n->left);
126      }
127    else if (cmp1 > 0 && cmp2 < 0)
128      {
129	rotate_left (&n->right, c, c->left);
130	rotate_right (&sp->root, n, n->right);
131      }
132  } while (1);
133}
134
135/* Insert a new NODE into SP.  The NODE shouldn't exist in the tree.  */
136
137attribute_hidden void
138splay_tree_insert (splay_tree sp, splay_tree_node node)
139{
140  int comparison = 0;
141
142  splay_tree_splay (sp, &node->key);
143
144  if (sp->root)
145    comparison = splay_compare (&sp->root->key, &node->key);
146
147  if (sp->root && comparison == 0)
148    gomp_fatal ("Duplicate node");
149  else
150    {
151      /* Insert it at the root.  */
152      if (sp->root == NULL)
153	node->left = node->right = NULL;
154      else if (comparison < 0)
155	{
156	  node->left = sp->root;
157	  node->right = node->left->right;
158	  node->left->right = NULL;
159	}
160      else
161	{
162	  node->right = sp->root;
163	  node->left = node->right->left;
164	  node->right->left = NULL;
165	}
166
167      sp->root = node;
168    }
169}
170
171/* Remove node with KEY from SP.  It is not an error if it did not exist.  */
172
173attribute_hidden void
174splay_tree_remove (splay_tree sp, splay_tree_key key)
175{
176  splay_tree_splay (sp, key);
177
178  if (sp->root && splay_compare (&sp->root->key, key) == 0)
179    {
180      splay_tree_node left, right;
181
182      left = sp->root->left;
183      right = sp->root->right;
184
185      /* One of the children is now the root.  Doesn't matter much
186	 which, so long as we preserve the properties of the tree.  */
187      if (left)
188	{
189	  sp->root = left;
190
191	  /* If there was a right child as well, hang it off the
192	     right-most leaf of the left child.  */
193	  if (right)
194	    {
195	      while (left->right)
196		left = left->right;
197	      left->right = right;
198	    }
199	}
200      else
201	sp->root = right;
202    }
203}
204
205/* Lookup KEY in SP, returning NODE if present, and NULL
206   otherwise.  */
207
208attribute_hidden splay_tree_key
209splay_tree_lookup (splay_tree sp, splay_tree_key key)
210{
211  splay_tree_splay (sp, key);
212
213  if (sp->root && splay_compare (&sp->root->key, key) == 0)
214    return &sp->root->key;
215  else
216    return NULL;
217}
218