Mercurial > hg > CbC > CbC_gcc
comparison libgomp/splay-tree.h @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* A splay-tree datatype. | |
2 Copyright (C) 1998-2017 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 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 | |
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. */ | |
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 | |
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. */ | |
87 | |
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 | |
101 typedef void (*splay_tree_callback) (splay_tree_key, void *); | |
102 | |
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); | |
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 */ | |
127 | |
128 #ifdef splay_tree_prefix | |
129 # undef splay_tree_prefix | |
130 #endif |