HPCToolkit
splay-macros.h
Go to the documentation of this file.
1 // -*-Mode: C++;-*- // technically C99
2 
3 // * BeginRiceCopyright *****************************************************
4 //
5 // $HeadURL$
6 // $Id$
7 //
8 // --------------------------------------------------------------------------
9 // Part of HPCToolkit (hpctoolkit.org)
10 //
11 // Information about sources of support for research and development of
12 // HPCToolkit is at 'hpctoolkit.org' and in 'README.Acknowledgments'.
13 // --------------------------------------------------------------------------
14 //
15 // Copyright ((c)) 2002-2019, Rice University
16 // All rights reserved.
17 //
18 // Redistribution and use in source and binary forms, with or without
19 // modification, are permitted provided that the following conditions are
20 // met:
21 //
22 // * Redistributions of source code must retain the above copyright
23 // notice, this list of conditions and the following disclaimer.
24 //
25 // * Redistributions in binary form must reproduce the above copyright
26 // notice, this list of conditions and the following disclaimer in the
27 // documentation and/or other materials provided with the distribution.
28 //
29 // * Neither the name of Rice University (RICE) nor the names of its
30 // contributors may be used to endorse or promote products derived from
31 // this software without specific prior written permission.
32 //
33 // This software is provided by RICE and contributors "as is" and any
34 // express or implied warranties, including, but not limited to, the
35 // implied warranties of merchantability and fitness for a particular
36 // purpose are disclaimed. In no event shall RICE or contributors be
37 // liable for any direct, indirect, incidental, special, exemplary, or
38 // consequential damages (including, but not limited to, procurement of
39 // substitute goods or services; loss of use, data, or profits; or
40 // business interruption) however caused and on any theory of liability,
41 // whether in contract, strict liability, or tort (including negligence
42 // or otherwise) arising in any way out of the use of this software, even
43 // if advised of the possibility of such damage.
44 //
45 // ******************************************************* EndRiceCopyright *
46 
47 /*
48  * Splay Tree Macros for regular and interval trees.
49  *
50  * Copyright (c) 2002-2019, Rice University.
51  * All rights reserved.
52  *
53  * Redistribution and use in source and binary forms, with or without
54  * modification, are permitted provided that the following conditions are
55  * met:
56  *
57  * * Redistributions of source code must retain the above copyright
58  * notice, this list of conditions and the following disclaimer.
59  *
60  * * Redistributions in binary form must reproduce the above copyright
61  * notice, this list of conditions and the following disclaimer in the
62  * documentation and/or other materials provided with the distribution.
63  *
64  * * Neither the name of Rice University (RICE) nor the names of its
65  * contributors may be used to endorse or promote products derived from
66  * this software without specific prior written permission.
67  *
68  * This software is provided by RICE and contributors "as is" and any
69  * express or implied warranties, including, but not limited to, the
70  * implied warranties of merchantability and fitness for a particular
71  * purpose are disclaimed. In no event shall RICE or contributors be
72  * liable for any direct, indirect, incidental, special, exemplary, or
73  * consequential damages (including, but not limited to, procurement of
74  * substitute goods or services; loss of use, data, or profits; or
75  * business interruption) however caused and on any theory of liability,
76  * whether in contract, strict liability, or tort (including negligence
77  * or otherwise) arising in any way out of the use of this software, even
78  * if advised of the possibility of such damage.
79  *
80  * $Id$
81  */
82 
83 #ifndef _SPLAY_TREE_MACROS_
84 #define _SPLAY_TREE_MACROS_
85 
86 #include <stdlib.h>
87 
88 /*
89  * The Sleator-Tarjan top-down splay algorithm for regular,
90  * single-key trees.
91  *
92  * This macro is the body of the splay function. It rotates the node
93  * containing "key" to the root, if there is one, else the new root
94  * will be an adjacent node (left or right).
95  *
96  * The general macro takes 2 comparisons as arguments
97  * [ Frequently, only 1 is necessary, but occasionally, when the keys are
98  * not a primitive data type, the lt and gt operations may not show the
99  * same symmetry as the purely mathematical operations.
100  *
101  * lt(a, b) // defines the "less than" comparison
102  * gt(a, b) // defines the "greater than" comparison
103  *
104  * Nodes in the tree should be a struct with name "type" containing
105  * at least these field names with these types:
106  *
107  * lt_field: the field of the key used with "less than" comparisons
108  * gt_field: the field of the key used with "greater than" comparisons
109  *
110  * left : struct type *,
111  * right : struct type *.
112  *
113  * NB: lt_field and gt_field are frequently the same field, but, in general,
114  * they can be different
115  *
116  * "root" is a struct type * and is reset to the new root.
117  *
118  */
119 
120 #define GENERAL_SPLAY_TREE(type, root, key, lt_field, gt_field, left, right, lt, gt) \
121  struct type dummy_node; \
122  struct type *ltree_max, *rtree_min, *yy; \
123  if ((root) != NULL) { \
124  ltree_max = rtree_min = &dummy_node; \
125  for (;;) { \
126  if (lt((key), (root)->lt_field)) { \
127  if ((yy = (root)->left) == NULL) \
128  break; \
129  if (lt((key), yy->lt_field)) { \
130  (root)->left = yy->right; \
131  yy->right = (root); \
132  (root) = yy; \
133  if ((yy = (root)->left) == NULL) \
134  break; \
135  } \
136  rtree_min->left = (root); \
137  rtree_min = (root); \
138  } else if (gt((key), (root)->gt_field)) { \
139  if ((yy = (root)->right) == NULL) \
140  break; \
141  if (gt((key), yy->gt_field)) { \
142  (root)->right = yy->left; \
143  yy->left = (root); \
144  (root) = yy; \
145  if ((yy = (root)->right) == NULL) \
146  break; \
147  } \
148  ltree_max->right = (root); \
149  ltree_max = (root); \
150  } else \
151  break; \
152  (root) = yy; \
153  } \
154  ltree_max->right = (root)->left; \
155  rtree_min->left = (root)->right; \
156  (root)->left = dummy_node.right; \
157  (root)->right = dummy_node.left; \
158  }
159 
160 
161 /*
162  * The Sleator-Tarjan top-down splay algorithm for regular,
163  * single-key trees. This kind of splay tree uses the
164  * builtin < and > as comparison operations, and the lt_field
165  * and gt_field are the same (called 'value' in the derived macro)
166  *
167  */
168 
169 #define lcl_builtin_lt(a, b) ((a) < (b))
170 #define lcl_builtin_gt(a, b) ((a) > (b))
171 
172 #define REGULAR_SPLAY_TREE(type, root, key, value, left, right) \
173  GENERAL_SPLAY_TREE(type, root, key, value, value, left, right, lcl_builtin_lt, lcl_builtin_gt)
174 
175 /*
176  * The Sleator-Tarjan top-down splay algorithm for interval trees.
177  *
178  * This macro is the body of the splay function. It rotates the
179  * interval containing "key" to the root, if there is one, else the
180  * new root will be an adjacent interval (left or right).
181  *
182  * Nodes in the tree should be a struct with name "type" containing
183  * at least these four field names with these types:
184  *
185  * start : same type as key,
186  * end : same type as key,
187  * left : struct type *,
188  * right : struct type *.
189  *
190  * "root" is a struct type * and is reset to the new root.
191  *
192  * Intervals are semi-inclusive: [start, end).
193  */
194 
195 #define lcl_intvl_lt(a, b) ((a) < (b))
196 #define lcl_intvl_gt(a, b) ((a) >= (b))
197 
198 #define INTERVAL_SPLAY_TREE(type, root, key, start, end, left, right) \
199  GENERAL_SPLAY_TREE(type, root, key, start, end, left, right, lcl_intvl_lt, lcl_intvl_gt)
200 
201 #endif /* ! _SPLAY_TREE_MACROS_ */