]>
Commit | Line | Data |
---|---|---|
995b27b9 | 1 | /* A splay-tree datatype. |
f1717362 | 2 | Copyright (C) 1998-2016 Free Software Foundation, Inc. |
995b27b9 | 3 | Contributed by Mark Mitchell (mark@markmitchell.com). |
4 | ||
c35c9a62 | 5 | This file is part of the GNU Offloading and Multi Processing Library |
6 | (libgomp). | |
995b27b9 | 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 | |
a9833286 | 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. */ | |
995b27b9 | 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 | ||
a9833286 | 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) | |
81 | # define splay_tree_callback \ | |
82 | splay_tree_name (splay_tree_prefix, splay_tree_callback) | |
83 | #endif | |
84 | ||
85 | #ifndef splay_tree_c | |
86 | /* Header file definitions and prototypes. */ | |
ca4c3545 | 87 | |
995b27b9 | 88 | /* The nodes in the splay tree. */ |
89 | struct splay_tree_node_s { | |
90 | struct splay_tree_key_s key; | |
91 | /* The left and right children, respectively. */ | |
92 | splay_tree_node left; | |
93 | splay_tree_node right; | |
94 | }; | |
95 | ||
96 | /* The splay tree. */ | |
97 | struct splay_tree_s { | |
98 | splay_tree_node root; | |
99 | }; | |
100 | ||
a9833286 | 101 | typedef void (*splay_tree_callback) (splay_tree_key, void *); |
102 | ||
ca4c3545 | 103 | extern splay_tree_key splay_tree_lookup (splay_tree, splay_tree_key); |
104 | extern void splay_tree_insert (splay_tree, splay_tree_node); | |
105 | extern void splay_tree_remove (splay_tree, splay_tree_key); | |
a9833286 | 106 | extern void splay_tree_foreach (splay_tree, splay_tree_callback, void *); |
107 | #else /* splay_tree_c */ | |
108 | # ifdef splay_tree_prefix | |
109 | # include "splay-tree.c" | |
110 | # undef splay_tree_name_1 | |
111 | # undef splay_tree_name | |
112 | # undef splay_tree_node_s | |
113 | # undef splay_tree_s | |
114 | # undef splay_tree_key_s | |
115 | # undef splay_tree_node | |
116 | # undef splay_tree | |
117 | # undef splay_tree_key | |
118 | # undef splay_compare | |
119 | # undef splay_tree_lookup | |
120 | # undef splay_tree_insert | |
121 | # undef splay_tree_remove | |
122 | # undef splay_tree_foreach | |
123 | # undef splay_tree_callback | |
124 | # undef splay_tree_c | |
125 | # endif | |
126 | #endif /* #ifndef splay_tree_c */ | |
995b27b9 | 127 | |
a9833286 | 128 | #ifdef splay_tree_prefix |
129 | # undef splay_tree_prefix | |
130 | #endif |