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