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