1 /* A splay-tree datatype.
2 Copyright (C) 1998-2015 Free Software Foundation, Inc.
3 Contributed by Mark Mitchell (mark@markmitchell.com).
5 This file is part of the GNU OpenMP Library (libgomp).
7 Libgomp is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
17 Under Section 7 of GPL version 3, you are granted additional
18 permissions described in the GCC Runtime Library Exception, version
19 3.1, as published by the Free Software Foundation.
21 You should have received a copy of the GNU General Public License and
22 a copy of the GCC Runtime Library Exception along with this program;
23 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 <http://www.gnu.org/licenses/>. */
26 /* The splay tree code copied from include/splay-tree.h and adjusted,
27 so that all the data lives directly in splay_tree_node_s structure
28 and no extra allocations are needed.
30 Files including this header should before including it add:
31 typedef struct splay_tree_node_s *splay_tree_node;
32 typedef struct splay_tree_s *splay_tree;
33 typedef struct splay_tree_key_s *splay_tree_key;
34 define splay_tree_key_s structure, and define
35 splay_compare inline function. */
37 /* For an easily readable description of splay-trees, see:
39 Lewis, Harry R. and Denenberg, Larry. Data Structures and Their
40 Algorithms. Harper-Collins, Inc. 1991.
42 The major feature of splay trees is that all basic tree operations
43 are amortized O(log n) time for a tree with n nodes. */
45 /* The nodes in the splay tree. */
46 struct splay_tree_node_s
{
47 struct splay_tree_key_s key
;
48 /* The left and right children, respectively. */
50 splay_tree_node right
;
58 /* Rotate the edge joining the left child N with its parent P. PP is the
59 grandparents' pointer to P. */
62 rotate_left (splay_tree_node
*pp
, splay_tree_node p
, splay_tree_node n
)
71 /* Rotate the edge joining the right child N with its parent P. PP is the
72 grandparents' pointer to P. */
75 rotate_right (splay_tree_node
*pp
, splay_tree_node p
, splay_tree_node n
)
84 /* Bottom up splay of KEY. */
87 splay_tree_splay (splay_tree sp
, splay_tree_key key
)
97 cmp1
= splay_compare (key
, &n
->key
);
103 /* Left or right? If no child, then we're done. */
111 /* Next one left or right? If found or no child, we're done
112 after one rotation. */
113 cmp2
= splay_compare (key
, &c
->key
);
115 || (cmp2
< 0 && !c
->left
)
116 || (cmp2
> 0 && !c
->right
))
119 rotate_left (&sp
->root
, n
, c
);
121 rotate_right (&sp
->root
, n
, c
);
125 /* Now we have the four cases of double-rotation. */
126 if (cmp1
< 0 && cmp2
< 0)
128 rotate_left (&n
->left
, c
, c
->left
);
129 rotate_left (&sp
->root
, n
, n
->left
);
131 else if (cmp1
> 0 && cmp2
> 0)
133 rotate_right (&n
->right
, c
, c
->right
);
134 rotate_right (&sp
->root
, n
, n
->right
);
136 else if (cmp1
< 0 && cmp2
> 0)
138 rotate_right (&n
->left
, c
, c
->right
);
139 rotate_left (&sp
->root
, n
, n
->left
);
141 else if (cmp1
> 0 && cmp2
< 0)
143 rotate_left (&n
->right
, c
, c
->left
);
144 rotate_right (&sp
->root
, n
, n
->right
);
149 /* Insert a new NODE into SP. The NODE shouldn't exist in the tree. */
152 splay_tree_insert (splay_tree sp
, splay_tree_node node
)
156 splay_tree_splay (sp
, &node
->key
);
159 comparison
= splay_compare (&sp
->root
->key
, &node
->key
);
161 if (sp
->root
&& comparison
== 0)
165 /* Insert it at the root. */
166 if (sp
->root
== NULL
)
167 node
->left
= node
->right
= NULL
;
168 else if (comparison
< 0)
170 node
->left
= sp
->root
;
171 node
->right
= node
->left
->right
;
172 node
->left
->right
= NULL
;
176 node
->right
= sp
->root
;
177 node
->left
= node
->right
->left
;
178 node
->right
->left
= NULL
;
185 /* Remove node with KEY from SP. It is not an error if it did not exist. */
188 splay_tree_remove (splay_tree sp
, splay_tree_key key
)
190 splay_tree_splay (sp
, key
);
192 if (sp
->root
&& splay_compare (&sp
->root
->key
, key
) == 0)
194 splay_tree_node left
, right
;
196 left
= sp
->root
->left
;
197 right
= sp
->root
->right
;
199 /* One of the children is now the root. Doesn't matter much
200 which, so long as we preserve the properties of the tree. */
205 /* If there was a right child as well, hang it off the
206 right-most leaf of the left child. */
219 /* Lookup KEY in SP, returning NODE if present, and NULL
222 static splay_tree_key
223 splay_tree_lookup (splay_tree sp
, splay_tree_key key
)
225 splay_tree_splay (sp
, key
);
227 if (sp
->root
&& splay_compare (&sp
->root
->key
, key
) == 0)
228 return &sp
->root
->key
;