]>
Commit | Line | Data |
---|---|---|
1df3f842 | 1 | /* A splay-tree datatype. |
a945c346 | 2 | Copyright (C) 1998-2024 Free Software Foundation, Inc. |
1df3f842 JJ |
3 | Contributed by Mark Mitchell (mark@markmitchell.com). |
4 | ||
f1f3453e TS |
5 | This file is part of the GNU Offloading and Multi Processing Library |
6 | (libgomp). | |
1df3f842 JJ |
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 | Files including this header should before including it add: | |
32 | typedef struct splay_tree_node_s *splay_tree_node; | |
33 | typedef struct splay_tree_s *splay_tree; | |
34 | typedef struct splay_tree_key_s *splay_tree_key; | |
35 | define splay_tree_key_s structure, and define | |
e4606348 JJ |
36 | splay_compare inline function. |
37 | ||
d4b6d147 TB |
38 | Define splay_tree_static to mark all functions as static. |
39 | ||
e4606348 JJ |
40 | Alternatively, they can define splay_tree_prefix macro before |
41 | including this header and then all the above types, the | |
42 | splay_compare function and the splay_tree_{lookup,insert_remove} | |
43 | function will be prefixed by that prefix. If splay_tree_prefix | |
44 | macro is defined, this header must be included twice: once where | |
45 | you need the header file definitions, and once where you need the | |
46 | .c implementation routines. In the latter case, you must also | |
47 | define the macro splay_tree_c. See the include of splay-tree.h in | |
48 | priority_queue.[hc] for an example. */ | |
1df3f842 JJ |
49 | |
50 | /* For an easily readable description of splay-trees, see: | |
51 | ||
52 | Lewis, Harry R. and Denenberg, Larry. Data Structures and Their | |
53 | Algorithms. Harper-Collins, Inc. 1991. | |
54 | ||
55 | The major feature of splay trees is that all basic tree operations | |
56 | are amortized O(log n) time for a tree with n nodes. */ | |
57 | ||
e4606348 JJ |
58 | #ifdef splay_tree_prefix |
59 | # define splay_tree_name_1(prefix, name) prefix ## _ ## name | |
60 | # define splay_tree_name(prefix, name) splay_tree_name_1 (prefix, name) | |
61 | # define splay_tree_node_s \ | |
62 | splay_tree_name (splay_tree_prefix, splay_tree_node_s) | |
63 | # define splay_tree_s \ | |
64 | splay_tree_name (splay_tree_prefix, splay_tree_s) | |
65 | # define splay_tree_key_s \ | |
66 | splay_tree_name (splay_tree_prefix, splay_tree_key_s) | |
67 | # define splay_tree_node \ | |
68 | splay_tree_name (splay_tree_prefix, splay_tree_node) | |
69 | # define splay_tree \ | |
70 | splay_tree_name (splay_tree_prefix, splay_tree) | |
71 | # define splay_tree_key \ | |
72 | splay_tree_name (splay_tree_prefix, splay_tree_key) | |
73 | # define splay_compare \ | |
74 | splay_tree_name (splay_tree_prefix, splay_compare) | |
75 | # define splay_tree_lookup \ | |
76 | splay_tree_name (splay_tree_prefix, splay_tree_lookup) | |
d4b6d147 TB |
77 | # define splay_tree_lookup_node \ |
78 | splay_tree_name (splay_tree_prefix, splay_tree_lookup_node) | |
e4606348 JJ |
79 | # define splay_tree_insert \ |
80 | splay_tree_name (splay_tree_prefix, splay_tree_insert) | |
81 | # define splay_tree_remove \ | |
82 | splay_tree_name (splay_tree_prefix, splay_tree_remove) | |
83 | # define splay_tree_foreach \ | |
84 | splay_tree_name (splay_tree_prefix, splay_tree_foreach) | |
ea4b23d9 TB |
85 | # define splay_tree_foreach_lazy \ |
86 | splay_tree_name (splay_tree_prefix, splay_tree_foreach_lazy) | |
e4606348 JJ |
87 | # define splay_tree_callback \ |
88 | splay_tree_name (splay_tree_prefix, splay_tree_callback) | |
ea4b23d9 TB |
89 | # define splay_tree_callback_stop \ |
90 | splay_tree_name (splay_tree_prefix, splay_tree_callback_stop) | |
e4606348 JJ |
91 | #endif |
92 | ||
93 | #ifndef splay_tree_c | |
94 | /* Header file definitions and prototypes. */ | |
41dbbb37 | 95 | |
1df3f842 JJ |
96 | /* The nodes in the splay tree. */ |
97 | struct splay_tree_node_s { | |
98 | struct splay_tree_key_s key; | |
99 | /* The left and right children, respectively. */ | |
100 | splay_tree_node left; | |
101 | splay_tree_node right; | |
102 | }; | |
103 | ||
104 | /* The splay tree. */ | |
105 | struct splay_tree_s { | |
106 | splay_tree_node root; | |
107 | }; | |
108 | ||
e4606348 | 109 | typedef void (*splay_tree_callback) (splay_tree_key, void *); |
ea4b23d9 | 110 | typedef int (*splay_tree_callback_stop) (splay_tree_key, void *); |
e4606348 | 111 | |
d4b6d147 | 112 | #ifndef splay_tree_static |
41dbbb37 | 113 | extern splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key); |
d4b6d147 | 114 | extern splay_tree_node splay_tree_lookup_node (splay_tree, splay_tree_key); |
41dbbb37 TS |
115 | extern void splay_tree_insert (splay_tree, splay_tree_node); |
116 | extern void splay_tree_remove (splay_tree, splay_tree_key); | |
e4606348 | 117 | extern void splay_tree_foreach (splay_tree, splay_tree_callback, void *); |
ea4b23d9 | 118 | extern void splay_tree_foreach_lazy (splay_tree, splay_tree_callback_stop, void *); |
d4b6d147 TB |
119 | #endif |
120 | ||
121 | #ifdef splay_tree_static_unused_attr | |
122 | # undef splay_tree_static_unused_attr | |
123 | #endif | |
124 | ||
e4606348 JJ |
125 | #else /* splay_tree_c */ |
126 | # ifdef splay_tree_prefix | |
127 | # include "splay-tree.c" | |
e4606348 | 128 | # endif |
6b4e49fd | 129 | # undef splay_tree_c |
e4606348 | 130 | #endif /* #ifndef splay_tree_c */ |
1df3f842 | 131 | |
d4b6d147 TB |
132 | #ifdef splay_tree_static |
133 | # undef splay_tree_static | |
134 | #endif | |
135 | ||
e4606348 | 136 | #ifdef splay_tree_prefix |
6b4e49fd TB |
137 | # undef splay_tree_name_1 |
138 | # undef splay_tree_name | |
139 | # undef splay_tree_node_s | |
140 | # undef splay_tree_s | |
141 | # undef splay_tree_key_s | |
142 | # undef splay_tree_node | |
143 | # undef splay_tree | |
144 | # undef splay_tree_key | |
145 | # undef splay_compare | |
146 | # undef splay_tree_lookup | |
d4b6d147 | 147 | # undef splay_tree_lookup_node |
6b4e49fd TB |
148 | # undef splay_tree_insert |
149 | # undef splay_tree_remove | |
150 | # undef splay_tree_foreach | |
ea4b23d9 | 151 | # undef splay_tree_foreach_lazy |
6b4e49fd | 152 | # undef splay_tree_callback |
ea4b23d9 | 153 | # undef splay_tree_callback_stop |
e4606348 JJ |
154 | # undef splay_tree_prefix |
155 | #endif |