1 /*
2 Copyright (C) 2017 Daniel Schultz
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #include <gmp.h>
13 #include "flint.h"
14 #include "mpoly.h"
15
16
mpoly_rbtree_init(mpoly_rbtree_t tree)17 void mpoly_rbtree_init(mpoly_rbtree_t tree)
18 {
19 tree->size = 0;
20 tree->head->up = tree->null;
21 tree->head->left = tree->null;
22 tree->head->right = tree->null;
23 tree->head->key = 0;
24 tree->head->col = 0;
25 tree->null->up = NULL;
26 tree->null->left = NULL;
27 tree->null->right = NULL;
28 tree->null->key = 0;
29 tree->null->col = 0;
30 }
31
32
_mpoly_rbnode_clear(mpoly_rbtree_t tree,mpoly_rbnode_t node,void ** dataout,slong * keysout,slong * idx)33 void _mpoly_rbnode_clear(mpoly_rbtree_t tree, mpoly_rbnode_t node,
34 void ** dataout, slong * keysout, slong * idx)
35 {
36 if (node->right != tree->null)
37 _mpoly_rbnode_clear(tree, node->right, dataout, keysout, idx);
38 dataout[*idx] = node->data;
39 keysout[*idx] = node->key;
40 (*idx)++;
41 if (node->left != tree->null)
42 _mpoly_rbnode_clear(tree, node->left, dataout, keysout, idx);
43 flint_free(node);
44 }
45
46
mpoly_rbtree_clear(mpoly_rbtree_t tree,void ** dataout,slong * keysout)47 void mpoly_rbtree_clear(mpoly_rbtree_t tree, void ** dataout, slong * keysout)
48 {
49 slong idx = 0;
50 if (tree->head->left != tree->null)
51 _mpoly_rbnode_clear(tree, tree->head->left, dataout, keysout, &idx);
52 }
53
54 /*
55 get the node with key "rcx"
56 if such a node doesn't exist, one is created and "new" is set to 1
57 */
mpoly_rbtree_get(int * new,struct mpoly_rbtree * tree,slong rcx)58 mpoly_rbnode_struct * mpoly_rbtree_get(int * new, struct mpoly_rbtree * tree,
59 slong rcx)
60 {
61 mpoly_rbnode_struct * t, * head, * null;
62 mpoly_rbnode_struct * rax, * rdx, * r8, * r9, * r10, * r11;
63
64 * new = 0;
65 head = tree->head;
66 null = tree->null;
67
68 r10 = head->left;
69
70 if (tree->size == 0)
71 {
72 rax = flint_malloc(sizeof(struct mpoly_rbnode));
73 rax->up = head;
74 rax->left = null;
75 rax->right = null;
76 rax->data = NULL;
77 rax->col = 0;
78 rax->key = rcx;
79 tree->size++;
80 * new = 1;
81 head->left = rax;
82 return rax;
83 }
84
85 Compare:
86 r8 = r10->left;
87 r9 = r10->right;
88 if (rcx < r10->key)
89 goto GoLeft;
90 if (rcx > r10->key)
91 goto GoRight;
92
93 rax = r10;
94 return rax;
95
96 GoLeft:
97 if (r8 == null)
98 goto MakeNewLeft;
99 r10 = r8;
100 goto Compare;
101
102 GoRight:
103 if (r9 == null)
104 goto MakeNewRight;
105 r10 = r9;
106 goto Compare;
107
108 MakeNewLeft:
109 rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
110 r10->left = rdx;
111 goto FixTree;
112
113 MakeNewRight:
114 rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
115 r10->right = rdx;
116
117 FixTree:
118 rdx->up = r10;
119 rdx->left = null;
120 rdx->right = null;
121 rdx->data = NULL;
122 rdx->col = 1;
123 rdx->key = rcx;
124 tree->size++;
125 * new = 1;
126 rax = rdx;
127
128 FixNode:
129
130 /*Case1:*/
131 r8 = rdx->up;
132 if (r8 == head)
133 {
134 rdx->col = 0;
135 return rax;
136 }
137
138
139 /*Case2:*/
140 if (r8->col == 0)
141 return rax;
142
143 /*Case3:*/
144 r9 = r8->up;
145 r10 = r9->left;
146 r11 = r9-> right;
147 if (r8 == r10)
148 r10 = r11;
149 if (r10 == null || r10->col == 0)
150 goto Case4;
151 rdx = r9;
152 r8->col = 0;
153 r9->col = 1;
154 r10->col = 0;
155 goto FixNode;
156
157 Case4:
158 r10 = r9->up;
159 /*Case4A:*/
160 if (rdx != r8->right || r8 != r9->left)
161 goto Case4B;
162 r11 = rdx->left;
163 r9->left = rdx;
164 rdx->left = r8;
165 r8->right = r11;
166 r8->up = rdx;
167 rdx->up = r9;
168 r11->up = r8;
169 goto Case4Done;
170
171 Case4B:
172 if (rdx != r8->left || r8 != r9->right)
173 goto Case5;
174 r11 = rdx->right;
175 r9->right = rdx;
176 rdx->right = r8;
177 r8->left = r11;
178 r8->up = rdx;
179 rdx->up = r9;
180 r11->up = r8;
181
182 Case4Done:
183 t = rdx;
184 rdx = r8;
185 r8 = t;
186
187 Case5:
188 if (r10->right == r9)
189 r10->right = r8;
190 if (r10->left == r9)
191 r10->left = r8;
192
193 r8->up = r10;
194 r8->col = 0;
195 r9->up = r8;
196 r9->col = 1;
197
198 r11 = r8->right;
199 r10 = r8->left;
200 if (rdx == r10)
201 {
202 r8->right = r9;
203 r9->left = r11;
204 r11->up = r9;
205 } else
206 {
207 r8->left = r9;
208 r9->right = r10;
209 r10->up = r9;
210 }
211
212 return rax;
213 }
214
215 /*
216 get the node with key "rcx"
217 if such a node doesn't exist, one is created and "new" is set to 1
218 */
mpoly_rbtree_get_fmpz(int * new,struct mpoly_rbtree * tree,fmpz_t rcx)219 mpoly_rbnode_struct * mpoly_rbtree_get_fmpz(int * new,
220 struct mpoly_rbtree * tree, fmpz_t rcx)
221 {
222 int cmp;
223 mpoly_rbnode_struct * t, * head, * null;
224 mpoly_rbnode_struct * rax, * rdx, * r8, * r9, * r10, * r11;
225 * new = 0;
226 head = tree->head;
227 null = tree->null;
228 r10 = head->left;
229 if (tree->size == 0)
230 {
231 rax = flint_malloc(sizeof(struct mpoly_rbnode));
232 rax->up = head;
233 rax->left = null;
234 rax->right = null;
235 rax->data = NULL;
236 rax->col = 0;
237 fmpz_init_set(&rax->key, rcx);
238 tree->size++;
239 * new = 1;
240 head->left = rax;
241 return rax;
242 }
243 Compare:
244 r8 = r10->left;
245 r9 = r10->right;
246 cmp = fmpz_cmp(rcx, &r10->key);
247 if (cmp < 0)
248 goto GoLeft;
249 if (cmp > 0)
250 goto GoRight;
251 rax = r10;
252 return rax;
253 GoLeft:
254 if (r8 == null)
255 goto MakeNewLeft;
256 r10 = r8;
257 goto Compare;
258 GoRight:
259 if (r9 == null)
260 goto MakeNewRight;
261 r10 = r9;
262 goto Compare;
263 MakeNewLeft:
264 rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
265 r10->left = rdx;
266 goto FixTree;
267 MakeNewRight:
268 rdx = flint_malloc(sizeof(mpoly_rbnode_struct));
269 r10->right = rdx;
270 FixTree:
271 rdx->up = r10;
272 rdx->left = null;
273 rdx->right = null;
274 rdx->data = NULL;
275 rdx->col = 1;
276 fmpz_init_set(&rdx->key, rcx);
277 tree->size++;
278 * new = 1;
279 rax = rdx;
280 FixNode:
281 /*Case1:*/
282 r8 = rdx->up;
283 if (r8 == head)
284 {
285 rdx->col = 0;
286 return rax;
287 }
288 /*Case2:*/
289 if (r8->col == 0)
290 return rax;
291 /*Case3:*/
292 r9 = r8->up;
293 r10 = r9->left;
294 r11 = r9-> right;
295 if (r8 == r10)
296 r10 = r11;
297 if (r10 == null || r10->col == 0)
298 goto Case4;
299 rdx = r9;
300 r8->col = 0;
301 r9->col = 1;
302 r10->col = 0;
303 goto FixNode;
304 Case4:
305 r10 = r9->up;
306 /*Case4A:*/
307 if (rdx != r8->right || r8 != r9->left)
308 goto Case4B;
309 r11 = rdx->left;
310 r9->left = rdx;
311 rdx->left = r8;
312 r8->right = r11;
313 r8->up = rdx;
314 rdx->up = r9;
315 r11->up = r8;
316 goto Case4Done;
317 Case4B:
318 if (rdx != r8->left || r8 != r9->right)
319 goto Case5;
320 r11 = rdx->right;
321 r9->right = rdx;
322 rdx->right = r8;
323 r8->left = r11;
324 r8->up = rdx;
325 rdx->up = r9;
326 r11->up = r8;
327 Case4Done:
328 t = rdx;
329 rdx = r8;
330 r8 = t;
331 Case5:
332 if (r10->right == r9)
333 r10->right = r8;
334 if (r10->left == r9)
335 r10->left = r8;
336 r8->up = r10;
337 r8->col = 0;
338 r9->up = r8;
339 r9->col = 1;
340 r11 = r8->right;
341 r10 = r8->left;
342 if (rdx == r10)
343 {
344 r8->right = r9;
345 r9->left = r11;
346 r11->up = r9;
347 } else
348 {
349 r8->left = r9;
350 r9->right = r10;
351 r10->up = r9;
352 }
353 return rax;
354 }
355