blob: d52b08e4357cdbade308448cac669b594b3c5034 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
|
include "trs.h"
#* HISTORY *
#* B.Simon 02-Jan-98 original
# This tree traversal code assumes the tree has links to the left and right
# subtrees, as well as a link to the parent node. The parent node of the root
# node is NULL. Leaf nodes contain pointers to other information. To
# distinguish these pointers from tree links, the pointers are negative
# numbers. All procedures are non-recursive as SPP does not support recursion.
# The tree contains information parsed from the row selection expression.
# It is used as an intermediate data structure for optimization before
# the information is converted to pseudocode instructions.
# TRS_COL_TREE -- Retrieve column pointer from range node above it in the tree
pointer procedure trs_col_tree (current)
pointer current # i: current node in tree
#--
pointer col, node
begin
col = NULL
node = current
while (node != NULL) {
if (TREE_OPER(node) == YRANGE) {
col = - TREE_RIGHT(node)
break
}
node = TREE_UP(node)
}
return (col)
end
# TRS_FIRST_TREE -- Get first (deepest leftmost) node in binary tree
pointer procedure trs_first_tree (root)
pointer root # i: root of binary tree
#--
pointer node
begin
node = root
repeat {
while (TREE_LEFT(node) > 0)
node = TREE_LEFT(node)
if (TREE_RIGHT(node) <= 0)
break
node = TREE_RIGHT(node)
}
return (node)
end
# TRS_NEXT_TREE -- Get next node in binary tree in postfix order
# After looking at the left subtree, look at the leftmost node of the right
# subtree. After looking at the right subtree, look at its immediate parent
# The root node has an UP node of NULL, which signals an end to the traverse
pointer procedure trs_next_tree (current)
pointer current # i: currently visited node
#--
pointer node
begin
node = TREE_UP(current)
if (node > 0) {
# right nodes only need to back up one
# left nodes need to get right subtree
if (current == TREE_LEFT(node)) {
if (TREE_RIGHT(node) > 0) {
# Get right node of parent
node = TREE_RIGHT(node)
# Get deepest leftmost subtree
repeat {
while (TREE_LEFT(node) > 0)
node = TREE_LEFT(node)
if (TREE_RIGHT(node) <= 0)
break
node = TREE_RIGHT(node)
}
}
}
}
return (node)
end
# TRS_OVER_TREE -- Determine if current node is over a row range node
bool procedure trs_over_tree (current)
pointer current # i: node to be checked
#--
bool over
pointer node
pointer trs_first_tree(), trs_next_tree()
begin
over = false
node = trs_first_tree (current)
while (node != TREE_UP(current)) {
if (TREE_OPER(node) == YRANGE && TREE_RIGHT(node) == NULL) {
over = true
break
}
node = trs_next_tree (node)
}
return (over)
end
# TRS_SNIP_TREE -- Remove node and its children from the binary tree
procedure trs_snip_tree (current)
pointer current # i: currently visited node
#--
pointer node
string badlink "trs_snip_tree: bad links in binary tree"
begin
node = TREE_UP(current)
TREE_UP(current) = NULL
if (TREE_LEFT(node) == current) {
TREE_LEFT(node) = NULL
} else if (TREE_RIGHT(node) == current) {
TREE_RIGHT(node) = NULL
} else {
call error (1, badlink)
}
end
# TRS_UNDER_TREE -- Determine if current node is under a row range node
bool procedure trs_under_tree (current)
pointer current # i: node to be checked
#--
bool under
pointer node
begin
under = false
node = TREE_UP(current)
while (node != NULL) {
if (TREE_OPER(node) == YRANGE && TREE_RIGHT(node) == NULL) {
under = true
break
}
node = TREE_UP(node)
}
return (under)
end
# TRS_XCG_TREE -- Exchange position of node with its parent in binary tree
procedure trs_xcg_tree (current)
pointer current # i: node to be exchanged
#--
pointer child, parent, grandparent
string badlink "trs_xcg_tree: bad links in binary tree"
begin
child = TREE_LEFT(current)
parent = TREE_UP(current)
grandparent = TREE_UP(parent)
if (TREE_LEFT(grandparent) == parent) {
TREE_LEFT(grandparent) = current
} else if (TREE_RIGHT(grandparent) == parent) {
TREE_RIGHT(grandparent) = current
} else {
call error (1, badlink)
}
TREE_LEFT(parent) = TREE_LEFT(current)
TREE_UP(parent) = current
TREE_LEFT(current) = parent
TREE_UP(current) = grandparent
TREE_UP(child) = parent
end
|
