1/*
2 This file is part of Mtproto-proxy Library.
3
4 Mtproto-proxy Library is free software: you can redistribute it and/or modify
5 it under the terms of the GNU Lesser General Public License as published by
6 the Free Software Foundation, either version 2 of the License, or
7 (at your option) any later version.
8
9 Mtproto-proxy Library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU Lesser General Public License for more details.
13
14 You should have received a copy of the GNU Lesser General Public License
15 along with Mtproto-proxy Library. If not, see <http://www.gnu.org/licenses/>.
16
17 Copyright 2015-2016 Telegram Messenger Inc
18 2015-2016 Vitaly Valtman
19*/
20
21
22#include <assert.h>
23
24long long total_vv_tree_nodes;
25
26#define SUFFIX2(a,b) a ## b
27#define SUFFIX(a,b) SUFFIX2(a,b)
28
29#ifndef TREE_NAME
30# define TREE_NAME any
31#endif
32
33#ifndef Y_TYPE
34# define Y_TYPE int
35#endif
36
37#ifndef Y_CMP
38# define Y_CMP(a,b) ((a) - (b))
39#endif
40
41#ifdef TREE_GLOBAL
42# define TREE_PREFIX
43#else
44# define TREE_PREFIX static
45#endif
46
47#ifndef TREE_NODE_TYPE
48# define TREE_NODE_TYPE struct SUFFIX(tree_, TREE_NAME)
49#endif
50
51#ifndef X_TYPE
52# define X_TYPE int
53#endif
54
55#ifndef X_CMP
56# define X_CMP(a,b) ((a) - (b))
57#endif
58
59#ifndef TREE_BODY_ONLY
60TREE_NODE_TYPE {
61 TREE_NODE_TYPE *left, *right;
62 X_TYPE x;
63 Y_TYPE y;
64#ifdef TREE_WEIGHT
65 int weight;
66#endif
67#if defined(TREE_COUNT) || defined (TREE_WEIGHT)
68 int count;
69#endif
70#ifdef TREE_PTHREAD
71 int refcnt;
72#endif
73};
74
75TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_alloc_,TREE_NAME) (X_TYPE x, Y_TYPE y) __attribute__ ((unused, warn_unused_result));
76TREE_PREFIX void SUFFIX(tree_free_,TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
77#if defined(TREE_COUNT) || defined(TREE_WEIGHT)
78 TREE_PREFIX void SUFFIX(tree_relax_,TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
79#endif
80
81TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_lookup_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) __attribute__ ((unused));
82TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_lookup_next_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) __attribute__ ((unused));
83#ifdef TREE_NOPTR
84TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_lookup_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x) __attribute__ ((unused));
85TREE_PREFIX X_TYPE *SUFFIX(tree_lookup_value_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) __attribute__ ((unused));
86TREE_PREFIX X_TYPE *SUFFIX(tree_lookup_value_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x) __attribute__ ((unused));
87#else
88TREE_PREFIX X_TYPE SUFFIX(tree_lookup_ptr_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) __attribute__ ((unused));
89#ifdef TREE_PTHREAD
90TREE_PREFIX X_TYPE SUFFIX(tree_lookup_sub_ptr_,TREE_NAME) (TREE_NODE_TYPE **T, X_TYPE x) __attribute__ ((unused));
91#endif
92#endif
93TREE_PREFIX void SUFFIX(tree_split_,TREE_NAME) (TREE_NODE_TYPE **L, TREE_NODE_TYPE **R,
94 TREE_NODE_TYPE *T, X_TYPE x) __attribute__ ((unused));
95
96TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_insert_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x, Y_TYPE y
97#ifdef TREE_WEIGHT
98 , int weight
99#endif
100) __attribute__ ((unused, warn_unused_result));
101
102TREE_PREFIX void SUFFIX(tree_insert_sub_,TREE_NAME) (TREE_NODE_TYPE **T, X_TYPE x, Y_TYPE y
103#ifdef TREE_WEIGHT
104 , int weight
105#endif
106) __attribute__ ((unused));
107
108#ifdef TREE_NOPTR
109TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_insert_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x, Y_TYPE y
110#ifdef TREE_WEIGHT
111 , int weight
112#endif
113) __attribute__ ((unused, warn_unused_result));
114#endif
115TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_merge_,TREE_NAME) (TREE_NODE_TYPE *L, TREE_NODE_TYPE *R) __attribute__ ((unused, warn_unused_result));
116TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_delete_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) __attribute__ ((unused, warn_unused_result));
117TREE_PREFIX void SUFFIX(tree_delete_sub_,TREE_NAME) (TREE_NODE_TYPE **T, X_TYPE x) __attribute__ ((unused));
118#ifdef TREE_NOPTR
119TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_delete_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x) __attribute__ ((unused, warn_unused_result));
120#endif
121TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_get_min_, TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
122TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_get_max_, TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
123TREE_PREFIX void SUFFIX(tree_act_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE)) __attribute__ ((unused));
124TREE_PREFIX void SUFFIX(tree_act_ex_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE, void *), void *ex) __attribute__ ((unused));
125TREE_PREFIX void SUFFIX(tree_act_ex2_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE, void *, void *), void *ex, void *ex2) __attribute__ ((unused));
126TREE_PREFIX void SUFFIX(tree_act_ex3_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE, void *, void *, void *), void *ex, void *ex2, void *ex3) __attribute__ ((unused));
127
128TREE_PREFIX void SUFFIX(tree_check_,TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
129TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_clear_, TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
130TREE_PREFIX int SUFFIX(tree_count_,TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
131
132#ifdef TREE_PTHREAD
133TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_clone_, TREE_NAME) (TREE_NODE_TYPE *T) __attribute__ ((unused));
134TREE_PREFIX TREE_NODE_TYPE *SUFFIX(get_tree_ptr_, TREE_NAME) (TREE_NODE_TYPE **T) __attribute__ ((unused));
135TREE_PREFIX void SUFFIX(free_tree_ptr_, TREE_NAME)(TREE_NODE_TYPE *T) __attribute__ ((unused));
136#endif
137
138#endif
139
140#ifndef TREE_HEADER_ONLY
141TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_lookup_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) {
142 long long c;
143 while (T && (c = X_CMP (x, T->x))) {
144 T = (c < 0) ? T->left : T->right;
145 }
146 return T;
147}
148
149TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_lookup_next_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) {
150 long long c;
151 TREE_NODE_TYPE *B = 0;
152 while (T && (c = X_CMP (x, T->x))) {
153 if (c < 0) { B = T; T = T->left; }
154 else { T = T->right; }
155 }
156 return T ? T : B;
157}
158
159#ifdef TREE_NOPTR
160TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_lookup_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x) {
161 long long c;
162 while (T && (c = X_CMP ((*x), T->x))) {
163 T = (c < 0) ? T->left : T->right;
164 }
165 return T;
166}
167
168TREE_PREFIX X_TYPE *SUFFIX(tree_lookup_value_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) {
169 long long c;
170 while (T && (c = X_CMP (x, T->x))) {
171 T = (c < 0) ? T->left : T->right;
172 }
173 return T ? &T->x : NULL;
174}
175
176TREE_PREFIX X_TYPE *SUFFIX(tree_lookup_value_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x) {
177 long long c;
178 while (T && (c = X_CMP ((*x), T->x))) {
179 T = (c < 0) ? T->left : T->right;
180 }
181 return T ? &T->x : NULL;
182}
183#else
184TREE_PREFIX X_TYPE SUFFIX(tree_lookup_ptr_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) {
185 long long c;
186 while (T && (c = X_CMP (x, T->x))) {
187 T = (c < 0) ? T->left : T->right;
188 }
189 return T ? T->x : 0;
190}
191
192#ifdef TREE_PTHREAD
193TREE_PREFIX X_TYPE SUFFIX(tree_lookup_sub_ptr_,TREE_NAME) (TREE_NODE_TYPE **T, X_TYPE x) {
194 TREE_NODE_TYPE *copy = SUFFIX(get_tree_ptr_,TREE_NAME)(T);
195
196 X_TYPE R = SUFFIX(tree_lookup_ptr_,TREE_NAME) (copy, x);
197 #ifdef TREE_INCREF
198 if (R) {
199 TREE_INCREF (R);
200 }
201 #endif
202
203 SUFFIX(tree_free_,TREE_NAME) (copy);
204
205 return R;
206}
207#endif
208#endif
209
210TREE_PREFIX void SUFFIX(tree_split_,TREE_NAME) (TREE_NODE_TYPE **L, TREE_NODE_TYPE **R,
211 TREE_NODE_TYPE *T, X_TYPE x) {
212 if (!T) { *L = *R = NULL; return; }
213
214 #ifdef TREE_PTHREAD
215 T = SUFFIX(tree_clone_,TREE_NAME) (T);
216 #endif
217
218 long long c = X_CMP (x, T->x);
219 if (c < 0) {
220 *R = T;
221 SUFFIX(tree_split_,TREE_NAME) (L, &T->left, T->left, x);
222 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
223 SUFFIX(tree_relax_,TREE_NAME) (*R);
224 #endif
225 } else {
226 *L = T;
227 SUFFIX(tree_split_,TREE_NAME) (&T->right, R, T->right, x);
228 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
229 SUFFIX(tree_relax_,TREE_NAME) (*L);
230 #endif
231 }
232}
233
234#ifdef TREE_NOPTR
235TREE_PREFIX void SUFFIX(tree_split_p_,TREE_NAME) (TREE_NODE_TYPE **L, TREE_NODE_TYPE **R,
236 TREE_NODE_TYPE *T, X_TYPE *x) {
237 if (!T) { *L = *R = NULL; return; }
238
239 #ifdef TREE_PTHREAD
240 T = SUFFIX(tree_clone_,TREE_NAME) (T);
241 #endif
242
243 long long c = X_CMP ((*x), T->x);
244 if (c < 0) {
245 *R = T;
246 SUFFIX(tree_split_p_,TREE_NAME) (L, &T->left, T->left, x);
247 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
248 SUFFIX(tree_relax_,TREE_NAME) (*R);
249 #endif
250 } else {
251 *L = T;
252 SUFFIX(tree_split_p_,TREE_NAME) (&T->right, R, T->right, x);
253 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
254 SUFFIX(tree_relax_,TREE_NAME) (*L);
255 #endif
256 }
257}
258#endif
259
260
261TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_insert_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x, Y_TYPE y
262#ifdef TREE_WEIGHT
263 , int weight
264#endif
265) {
266 TREE_NODE_TYPE *P;
267 if (!T) {
268 P = SUFFIX (tree_alloc_, TREE_NAME) (x, y);
269 #ifdef TREE_WEIGHT
270 P->weight = weight;
271 #endif
272 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
273 SUFFIX(tree_relax_,TREE_NAME) (P);
274 #endif
275 return P;
276 }
277
278 #ifdef TREE_PTHREAD
279 T = SUFFIX(tree_clone_,TREE_NAME) (T);
280 #endif
281 long long c = Y_CMP (y, T->y);
282 if (c < 0) {
283 c = X_CMP (x, T->x);
284 assert (c);
285 if (c < 0) {
286 T->left = SUFFIX(tree_insert_,TREE_NAME) (T->left, x, y
287 #ifdef TREE_WEIGHT
288 ,weight
289 #endif
290 );
291 } else {
292 T->right = SUFFIX(tree_insert_,TREE_NAME) (T->right, x, y
293 #ifdef TREE_WEIGHT
294 ,weight
295 #endif
296 );
297 }
298 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
299 SUFFIX(tree_relax_,TREE_NAME) (T);
300 #endif
301 return T;
302 }
303 P = SUFFIX (tree_alloc_, TREE_NAME) (x, y);
304 #ifdef TREE_WEIGHT
305 P->weight = weight;
306 #endif
307 SUFFIX(tree_split_,TREE_NAME) (&P->left, &P->right, T, x);
308 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
309 SUFFIX(tree_relax_,TREE_NAME) (P);
310 #endif
311 return P;
312}
313
314TREE_PREFIX void SUFFIX(tree_insert_sub_,TREE_NAME) (TREE_NODE_TYPE **T, X_TYPE x, Y_TYPE y
315#ifdef TREE_WEIGHT
316 , int weight
317#endif
318) {
319 #ifdef TREE_PTHREAD
320 TREE_NODE_TYPE *TT = *T;
321
322 if (TT) {
323 __sync_fetch_and_add (&TT->refcnt, 1);
324 }
325 #endif
326
327 *T = SUFFIX(tree_insert_,TREE_NAME)(*T, x, y
328 #ifdef TREE_WEIGHT
329 , weight
330 #endif
331 );
332
333 #ifdef TREE_PTHREAD
334 if (TT) {
335 mfence ();
336 SUFFIX(free_tree_ptr_,TREE_NAME)(TT);
337 }
338 #endif
339}
340
341#ifdef TREE_NOPTR
342TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_insert_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x, Y_TYPE y
343#ifdef TREE_WEIGHT
344 , int weight
345#endif
346) {
347 TREE_NODE_TYPE *P;
348 if (!T) {
349 P = SUFFIX (tree_alloc_, TREE_NAME) (*x, y);
350 #ifdef TREE_WEIGHT
351 P->weight = weight;
352 #endif
353 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
354 SUFFIX(tree_relax_,TREE_NAME) (P);
355 #endif
356 return P;
357 }
358
359 #ifdef TREE_PTHREAD
360 T = SUFFIX(tree_clone_,TREE_NAME) (T);
361 #endif
362 long long c = Y_CMP (y, T->y);
363 if (c < 0) {
364 c = X_CMP ((*x), T->x);
365 assert (c);
366 if (c < 0) {
367 T->left = SUFFIX(tree_insert_p_,TREE_NAME) (T->left, x, y
368 #ifdef TREE_WEIGHT
369 ,weight
370 #endif
371 );
372 } else {
373 T->right = SUFFIX(tree_insert_p_,TREE_NAME) (T->right, x, y
374 #ifdef TREE_WEIGHT
375 ,weight
376 #endif
377 );
378 }
379 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
380 SUFFIX(tree_relax_,TREE_NAME) (T);
381 #endif
382 return T;
383 }
384 P = SUFFIX (tree_alloc_, TREE_NAME) (*x, y);
385 #ifdef TREE_WEIGHT
386 P->weight = weight;
387 #endif
388 SUFFIX(tree_split_p_,TREE_NAME) (&P->left, &P->right, T, x);
389 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
390 SUFFIX(tree_relax_,TREE_NAME) (P);
391 #endif
392 return P;
393}
394#endif
395
396TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_merge_,TREE_NAME) (TREE_NODE_TYPE *L, TREE_NODE_TYPE *R) {
397 if (!L) { return R; }
398 if (!R) { return L; }
399 if (Y_CMP (L->y, R->y) > 0) {
400 #ifdef TREE_PTHREAD
401 L = SUFFIX(tree_clone_,TREE_NAME) (L);
402 #endif
403 L->right = SUFFIX (tree_merge_,TREE_NAME) (L->right, R);
404 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
405 SUFFIX(tree_relax_,TREE_NAME) (L);
406 #endif
407 return L;
408 } else {
409 #ifdef TREE_PTHREAD
410 R = SUFFIX(tree_clone_,TREE_NAME) (R);
411 #endif
412 R->left = SUFFIX (tree_merge_,TREE_NAME) (L, R->left);
413 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
414 SUFFIX(tree_relax_,TREE_NAME) (R);
415 #endif
416 return R;
417 }
418}
419
420TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_delete_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE x) {
421 assert (T);
422 #ifdef TREE_PTHREAD
423 T = SUFFIX(tree_clone_,TREE_NAME) (T);
424 #endif
425 long long c = X_CMP (x, T->x);
426 if (!c) {
427 TREE_NODE_TYPE *N = SUFFIX(tree_merge_,TREE_NAME) (T->left, T->right);
428
429 T->left = T->right = NULL;
430 SUFFIX(tree_free_,TREE_NAME)(T);
431 return N;
432 } else if (c < 0) {
433 T->left = SUFFIX(tree_delete_,TREE_NAME) (T->left, x);
434 } else {
435 T->right = SUFFIX(tree_delete_,TREE_NAME) (T->right, x);
436 }
437 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
438 SUFFIX(tree_relax_,TREE_NAME) (T);
439 #endif
440 return T;
441}
442
443TREE_PREFIX void SUFFIX(tree_delete_sub_,TREE_NAME) (TREE_NODE_TYPE **T, X_TYPE x) {
444 #ifdef TREE_PTHREAD
445 TREE_NODE_TYPE *TT = *T;
446
447 if (TT) {
448 __sync_fetch_and_add (&TT->refcnt, 1);
449 }
450 #endif
451
452 *T = SUFFIX(tree_delete_,TREE_NAME)(*T, x);
453
454 #ifdef TREE_PTHREAD
455 if (TT) {
456 mfence ();
457 SUFFIX(free_tree_ptr_,TREE_NAME)(TT);
458 }
459 #endif
460}
461
462#ifdef TREE_NOPTR
463TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_delete_p_,TREE_NAME) (TREE_NODE_TYPE *T, X_TYPE *x) {
464 assert (T);
465 #ifdef TREE_PTHREAD
466 T = SUFFIX(tree_clone_,TREE_NAME) (T);
467 #endif
468 long long c = X_CMP ((*x), T->x);
469 if (!c) {
470 TREE_NODE_TYPE *N = SUFFIX(tree_merge_,TREE_NAME) (T->left, T->right);
471
472 T->left = T->right = NULL;
473 SUFFIX(tree_free_,TREE_NAME)(T);
474 return N;
475 } else if (c < 0) {
476 T->left = SUFFIX(tree_delete_p_,TREE_NAME) (T->left, x);
477 } else {
478 T->right = SUFFIX(tree_delete_p_,TREE_NAME) (T->right, x);
479 }
480 #if defined(TREE_COUNT) || defined(TREE_WEIGHT)
481 SUFFIX(tree_relax_,TREE_NAME) (T);
482 #endif
483 return T;
484}
485#endif
486
487TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_get_min_, TREE_NAME) (TREE_NODE_TYPE *T) {
488 while (T && T->left) {
489 T = T->left;
490 }
491 return T;
492}
493
494TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_get_max_, TREE_NAME) (TREE_NODE_TYPE *T) {
495 while (T && T->right) {
496 T = T->right;
497 }
498 return T;
499}
500
501TREE_PREFIX void SUFFIX(tree_act_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE x)) {
502 if (!T) { return; }
503 SUFFIX(tree_act_, TREE_NAME)(T->left, act);
504 act (T->x);
505 SUFFIX(tree_act_, TREE_NAME)(T->right, act);
506}
507
508TREE_PREFIX void SUFFIX(tree_act_ex_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE, void *), void *ex) {
509 if (!T) { return; }
510 SUFFIX(tree_act_ex_, TREE_NAME)(T->left, act, ex);
511 act (T->x, ex);
512 SUFFIX(tree_act_ex_, TREE_NAME)(T->right, act, ex);
513}
514
515TREE_PREFIX void SUFFIX(tree_act_ex2_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE, void *, void *), void *ex, void *ex2) {
516 if (!T) { return; }
517 SUFFIX(tree_act_ex2_, TREE_NAME)(T->left, act, ex, ex2);
518 act (T->x, ex, ex2);
519 SUFFIX(tree_act_ex2_, TREE_NAME)(T->right, act, ex, ex2);
520}
521
522TREE_PREFIX void SUFFIX(tree_act_ex3_, TREE_NAME) (TREE_NODE_TYPE *T, void (*act)(X_TYPE, void *, void *, void *), void *ex, void *ex2, void *ex3) {
523 if (!T) { return; }
524 SUFFIX(tree_act_ex3_, TREE_NAME)(T->left, act, ex, ex2, ex3);
525 act (T->x, ex, ex2, ex3);
526 SUFFIX(tree_act_ex3_, TREE_NAME)(T->right, act, ex, ex2, ex3);
527}
528
529
530#ifndef TREE_PTHREAD
531TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_clear_, TREE_NAME) (TREE_NODE_TYPE *T) {
532 if (!T) {
533 return 0;
534 }
535 SUFFIX(tree_clear_, TREE_NAME) (T->left);
536 SUFFIX(tree_clear_, TREE_NAME) (T->right);
537 SUFFIX(tree_free_, TREE_NAME) (T);
538 return 0;
539}
540#else
541TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_clear_, TREE_NAME) (TREE_NODE_TYPE *T) {
542 if (!T) {
543 return 0;
544 }
545 SUFFIX(tree_free_, TREE_NAME) (T);
546 return 0;
547}
548#endif
549
550TREE_PREFIX void SUFFIX(tree_check_,TREE_NAME) (TREE_NODE_TYPE *T) {
551 if (!T) {
552 return;
553 }
554 if (T->left) { assert (Y_CMP (T->left->y, T->y) <= 0); assert (X_CMP (T->left->x, T->x) < 0); }
555 if (T->right) { assert (Y_CMP (T->right->y, T->y) <= 0); assert (X_CMP (T->right->x, T->x) > 0); }
556 SUFFIX (tree_check_, TREE_NAME) (T->left);
557 SUFFIX (tree_check_, TREE_NAME) (T->right);
558}
559
560TREE_PREFIX int SUFFIX(tree_count_,TREE_NAME) (TREE_NODE_TYPE *T) {
561 if (!T) {
562 return 0;
563 }
564 return 1 + SUFFIX (tree_count_, TREE_NAME) (T->left) + SUFFIX (tree_count_, TREE_NAME) (T->right);
565}
566
567
568TREE_PREFIX TREE_NODE_TYPE *SUFFIX (tree_alloc_, TREE_NAME) (X_TYPE x, Y_TYPE y) {
569 TREE_NODE_TYPE *T =
570 #ifndef TREE_MALLOC
571 zmalloc0 (sizeof (*T));
572 #else
573 calloc (sizeof (*T), 1);
574 #endif
575 T->x = x;
576 T->y = y;
577 #ifdef TREE_PTHREAD
578 T->refcnt = 1;
579 #endif
580 T->left = T->right = NULL;
581 __sync_fetch_and_add (&total_vv_tree_nodes, 1);
582 return T;
583}
584
585
586TREE_PREFIX void SUFFIX (tree_free_, TREE_NAME) (TREE_NODE_TYPE *T) {
587 #ifdef TREE_PTHREAD
588 if (!T) { return; }
589 if (__sync_fetch_and_add (&T->refcnt, -1) > 1) {
590 return;
591 }
592 assert (!T->refcnt);
593 if (T->left) { SUFFIX (tree_free_, TREE_NAME) ( T->left ); }
594 if (T->right) { SUFFIX (tree_free_, TREE_NAME) ( T->right ); }
595 #else
596 assert (T);
597 #endif
598 #ifdef TREE_DECREF
599 TREE_DECREF (T->x);
600 #endif
601 #ifndef TREE_MALLOC
602 zfree (T, sizeof (*T));
603 #else
604 free (T);
605 #endif
606 __sync_fetch_and_add (&total_vv_tree_nodes, -1);
607}
608
609#ifdef TREE_PTHREAD
610TREE_PREFIX TREE_NODE_TYPE *SUFFIX(tree_clone_, TREE_NAME) (TREE_NODE_TYPE *T) {
611 assert (T);
612 #ifdef TREE_INCREF
613 TREE_INCREF (T->x);
614 #endif
615 TREE_NODE_TYPE *R = SUFFIX (tree_alloc_, TREE_NAME) (T->x, T->y);
616 assert (R);
617
618 if (T->left) {
619 __sync_fetch_and_add (&T->left->refcnt, 1);
620 R->left = T->left;
621 }
622
623 if (T->right) {
624 __sync_fetch_and_add (&T->right->refcnt, 1);
625 R->right = T->right;
626 }
627
628 SUFFIX (tree_free_, TREE_NAME) (T);
629 return R;
630}
631#endif
632
633
634#ifdef TREE_COUNT
635TREE_PREFIX void SUFFIX(tree_relax_,TREE_NAME) (TREE_NODE_TYPE *T) {
636 T->count = 1 + (T->left ? T->left->count : 0) + (T->right ? T->right->count : 0);
637}
638#endif
639#ifdef TREE_WEIGHT
640TREE_PREFIX void SUFFIX(tree_relax_,TREE_NAME) (TREE_NODE_TYPE *T) {
641 T->count = T->weight + (T->left ? T->left->count : 0) + (T->right ? T->right->count : 0);
642}
643#endif
644
645#ifdef TREE_PTHREAD
646
647TREE_PREFIX void SUFFIX(incref_tree_ptr_,TREE_NAME) (TREE_NODE_TYPE *T) {
648 if (T) {
649 assert (__sync_fetch_and_add (&T->refcnt, 1) > 0);
650 }
651}
652
653TREE_PREFIX TREE_NODE_TYPE *SUFFIX(get_tree_ptr_, TREE_NAME) (TREE_NODE_TYPE **T) {
654 return get_ptr_multithread_copy ((void **)T, (void *)SUFFIX(incref_tree_ptr_,TREE_NAME));
655}
656
657TREE_PREFIX void SUFFIX(free_tree_ptr_, TREE_NAME)(TREE_NODE_TYPE *T) {
658 if (T && is_hazard_ptr (T, COMMON_HAZARD_PTR_NUM, COMMON_HAZARD_PTR_NUM)) {
659 struct free_later *F = malloc (sizeof (*F));
660 F->ptr = T;
661 F->free = (void *)SUFFIX(free_tree_ptr_, TREE_NAME);
662 insert_free_later_struct (F);
663 } else {
664 SUFFIX(tree_free_, TREE_NAME) (T);
665 }
666}
667
668#endif
669
670
671
672#endif
673#undef TREE_NAME
674#undef Y_TYPE
675#undef Y_CMP
676#undef TREE_GLOBAL
677#undef TREE_NODE_TYPE
678#undef X_TYPE
679#undef X_CMP
680#undef SUFFIX2
681#undef SUFFIX
682#undef TREE_NOPTR
683#undef TREE_GLOBAL
684#undef TREE_MALLOC
685#undef TREE_COUNT
686#undef TREE_WEIGHT
687#undef TREE_PREFIX
688#undef TREE_INCREF
689#undef TREE_DECREF
690#undef TREE_HEADER_ONLY
691#undef TREE_BODY_ONLY
692#undef TREE_PTHREAD
693