Lines Matching refs:a_type
56 * int (a_cmp *)(a_type *a_node, a_type *a_other);
81 #define rb_node(a_type) \
83 a_type *rbn_left; \
84 a_type *rbn_right_red; \
88 #define rb_tree(a_type) \
90 a_type *rbt_root; \
91 a_type rbt_nil; \
95 #define rbp_left_get(a_type, a_field, a_node) \
97 #define rbp_left_set(a_type, a_field, a_node, a_left) do { \
102 #define rbp_right_get(a_type, a_field, a_node) \
103 ((a_type *) (((intptr_t) (a_node)->a_field.rbn_right_red) \
105 #define rbp_right_set(a_type, a_field, a_node, a_right) do { \
106 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) a_right) \
111 #define rbp_red_get(a_type, a_field, a_node) \
114 #define rbp_color_set(a_type, a_field, a_node, a_red) do { \
115 (a_node)->a_field.rbn_right_red = (a_type *) ((((intptr_t) \
119 #define rbp_red_set(a_type, a_field, a_node) do { \
120 (a_node)->a_field.rbn_right_red = (a_type *) (((uintptr_t) \
123 #define rbp_black_set(a_type, a_field, a_node) do { \
124 (a_node)->a_field.rbn_right_red = (a_type *) (((intptr_t) \
129 #define rbp_node_new(a_type, a_field, a_tree, a_node) do { \
130 rbp_left_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil); \
131 rbp_right_set(a_type, a_field, (a_node), &(a_tree)->rbt_nil); \
132 rbp_red_set(a_type, a_field, (a_node)); \
136 #define rb_new(a_type, a_field, a_tree) do { \
138 rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil); \
139 rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil); \
143 #define rbp_black_height(a_type, a_field, a_tree, r_height) do { \
144 a_type *rbp_bh_t; \
147 rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) { \
148 if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) { \
154 #define rbp_first(a_type, a_field, a_tree, a_root, r_node) do { \
156 rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil; \
157 (r_node) = rbp_left_get(a_type, a_field, (r_node))) { \
161 #define rbp_last(a_type, a_field, a_tree, a_root, r_node) do { \
163 rbp_right_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil; \
164 (r_node) = rbp_right_get(a_type, a_field, (r_node))) { \
168 #define rbp_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \
169 if (rbp_right_get(a_type, a_field, (a_node)) \
171 rbp_first(a_type, a_field, a_tree, rbp_right_get(a_type, \
174 a_type *rbp_n_t = (a_tree)->rbt_root; \
181 rbp_n_t = rbp_left_get(a_type, a_field, rbp_n_t); \
183 rbp_n_t = rbp_right_get(a_type, a_field, rbp_n_t); \
192 #define rbp_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \
193 if (rbp_left_get(a_type, a_field, (a_node)) != &(a_tree)->rbt_nil) {\
194 rbp_last(a_type, a_field, a_tree, rbp_left_get(a_type, \
197 a_type *rbp_p_t = (a_tree)->rbt_root; \
203 rbp_p_t = rbp_left_get(a_type, a_field, rbp_p_t); \
206 rbp_p_t = rbp_right_get(a_type, a_field, rbp_p_t); \
215 #define rb_first(a_type, a_field, a_tree, r_node) do { \
216 rbp_first(a_type, a_field, a_tree, (a_tree)->rbt_root, (r_node)); \
222 #define rb_last(a_type, a_field, a_tree, r_node) do { \
223 rbp_last(a_type, a_field, a_tree, (a_tree)->rbt_root, r_node); \
229 #define rb_next(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \
230 rbp_next(a_type, a_field, a_cmp, a_tree, (a_node), (r_node)); \
236 #define rb_prev(a_type, a_field, a_cmp, a_tree, a_node, r_node) do { \
237 rbp_prev(a_type, a_field, a_cmp, a_tree, (a_node), (r_node)); \
243 #define rb_search(a_type, a_field, a_cmp, a_tree, a_key, r_node) do { \
249 (r_node) = rbp_left_get(a_type, a_field, (r_node)); \
251 (r_node) = rbp_right_get(a_type, a_field, (r_node)); \
263 #define rb_nsearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do { \
264 a_type *rbp_ns_t = (a_tree)->rbt_root; \
270 rbp_ns_t = rbp_left_get(a_type, a_field, rbp_ns_t); \
272 rbp_ns_t = rbp_right_get(a_type, a_field, rbp_ns_t); \
284 #define rb_psearch(a_type, a_field, a_cmp, a_tree, a_key, r_node) do { \
285 a_type *rbp_ps_t = (a_tree)->rbt_root; \
290 rbp_ps_t = rbp_left_get(a_type, a_field, rbp_ps_t); \
293 rbp_ps_t = rbp_right_get(a_type, a_field, rbp_ps_t); \
301 #define rbp_rotate_left(a_type, a_field, a_node, r_node) do { \
302 (r_node) = rbp_right_get(a_type, a_field, (a_node)); \
303 rbp_right_set(a_type, a_field, (a_node), \
304 rbp_left_get(a_type, a_field, (r_node))); \
305 rbp_left_set(a_type, a_field, (r_node), (a_node)); \
308 #define rbp_rotate_right(a_type, a_field, a_node, r_node) do { \
309 (r_node) = rbp_left_get(a_type, a_field, (a_node)); \
310 rbp_left_set(a_type, a_field, (a_node), \
311 rbp_right_get(a_type, a_field, (r_node))); \
312 rbp_right_set(a_type, a_field, (r_node), (a_node)); \
315 #define rbp_lean_left(a_type, a_field, a_node, r_node) do { \
317 rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
318 rbp_ll_red = rbp_red_get(a_type, a_field, (a_node)); \
319 rbp_color_set(a_type, a_field, (r_node), rbp_ll_red); \
320 rbp_red_set(a_type, a_field, (a_node)); \
323 #define rbp_lean_right(a_type, a_field, a_node, r_node) do { \
325 rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
326 rbp_lr_red = rbp_red_get(a_type, a_field, (a_node)); \
327 rbp_color_set(a_type, a_field, (r_node), rbp_lr_red); \
328 rbp_red_set(a_type, a_field, (a_node)); \
331 #define rbp_move_red_left(a_type, a_field, a_node, r_node) do { \
332 a_type *rbp_mrl_t, *rbp_mrl_u; \
333 rbp_mrl_t = rbp_left_get(a_type, a_field, (a_node)); \
334 rbp_red_set(a_type, a_field, rbp_mrl_t); \
335 rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node)); \
336 rbp_mrl_u = rbp_left_get(a_type, a_field, rbp_mrl_t); \
337 if (rbp_red_get(a_type, a_field, rbp_mrl_u)) { \
338 rbp_rotate_right(a_type, a_field, rbp_mrl_t, rbp_mrl_u); \
339 rbp_right_set(a_type, a_field, (a_node), rbp_mrl_u); \
340 rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
341 rbp_mrl_t = rbp_right_get(a_type, a_field, (a_node)); \
342 if (rbp_red_get(a_type, a_field, rbp_mrl_t)) { \
343 rbp_black_set(a_type, a_field, rbp_mrl_t); \
344 rbp_red_set(a_type, a_field, (a_node)); \
345 rbp_rotate_left(a_type, a_field, (a_node), rbp_mrl_t); \
346 rbp_left_set(a_type, a_field, (r_node), rbp_mrl_t); \
348 rbp_black_set(a_type, a_field, (a_node)); \
351 rbp_red_set(a_type, a_field, (a_node)); \
352 rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
356 #define rbp_move_red_right(a_type, a_field, a_node, r_node) do { \
357 a_type *rbp_mrr_t; \
358 rbp_mrr_t = rbp_left_get(a_type, a_field, (a_node)); \
359 if (rbp_red_get(a_type, a_field, rbp_mrr_t)) { \
360 a_type *rbp_mrr_u, *rbp_mrr_v; \
361 rbp_mrr_u = rbp_right_get(a_type, a_field, rbp_mrr_t); \
362 rbp_mrr_v = rbp_left_get(a_type, a_field, rbp_mrr_u); \
363 if (rbp_red_get(a_type, a_field, rbp_mrr_v)) { \
364 rbp_color_set(a_type, a_field, rbp_mrr_u, \
365 rbp_red_get(a_type, a_field, (a_node))); \
366 rbp_black_set(a_type, a_field, rbp_mrr_v); \
367 rbp_rotate_left(a_type, a_field, rbp_mrr_t, rbp_mrr_u); \
368 rbp_left_set(a_type, a_field, (a_node), rbp_mrr_u); \
369 rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
370 rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
371 rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \
373 rbp_color_set(a_type, a_field, rbp_mrr_t, \
374 rbp_red_get(a_type, a_field, (a_node))); \
375 rbp_red_set(a_type, a_field, rbp_mrr_u); \
376 rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
377 rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
378 rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \
380 rbp_red_set(a_type, a_field, (a_node)); \
382 rbp_red_set(a_type, a_field, rbp_mrr_t); \
383 rbp_mrr_t = rbp_left_get(a_type, a_field, rbp_mrr_t); \
384 if (rbp_red_get(a_type, a_field, rbp_mrr_t)) { \
385 rbp_black_set(a_type, a_field, rbp_mrr_t); \
386 rbp_rotate_right(a_type, a_field, (a_node), (r_node)); \
387 rbp_rotate_left(a_type, a_field, (a_node), rbp_mrr_t); \
388 rbp_right_set(a_type, a_field, (r_node), rbp_mrr_t); \
390 rbp_rotate_left(a_type, a_field, (a_node), (r_node)); \
395 #define rb_insert(a_type, a_field, a_cmp, a_tree, a_node) do { \
396 a_type rbp_i_s; \
397 a_type *rbp_i_g, *rbp_i_p, *rbp_i_c, *rbp_i_t, *rbp_i_u; \
400 rbp_left_set(a_type, a_field, &rbp_i_s, (a_tree)->rbt_root); \
401 rbp_right_set(a_type, a_field, &rbp_i_s, &(a_tree)->rbt_nil); \
402 rbp_black_set(a_type, a_field, &rbp_i_s); \
410 rbp_i_t = rbp_left_get(a_type, a_field, rbp_i_c); \
411 rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t); \
412 if (rbp_red_get(a_type, a_field, rbp_i_t) \
413 && rbp_red_get(a_type, a_field, rbp_i_u)) { \
419 rbp_rotate_right(a_type, a_field, rbp_i_c, rbp_i_t); \
421 rbp_i_u = rbp_left_get(a_type, a_field, rbp_i_t); \
422 rbp_black_set(a_type, a_field, rbp_i_u); \
423 if (rbp_left_get(a_type, a_field, rbp_i_p) == rbp_i_c) { \
424 rbp_left_set(a_type, a_field, rbp_i_p, rbp_i_t); \
430 assert(rbp_right_get(a_type, a_field, rbp_i_p) \
432 rbp_right_set(a_type, a_field, rbp_i_p, rbp_i_t); \
433 rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_u); \
434 if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
435 rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_u); \
437 assert(rbp_right_get(a_type, a_field, rbp_i_g) \
439 rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_u); \
444 rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_p); \
447 rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_p); \
456 rbp_i_c = rbp_left_get(a_type, a_field, rbp_i_c); \
459 rbp_i_c = rbp_right_get(a_type, a_field, rbp_i_c); \
463 rbp_node_new(a_type, a_field, a_tree, (a_node)); \
465 rbp_right_set(a_type, a_field, rbp_i_p, (a_node)); \
466 rbp_lean_left(a_type, a_field, rbp_i_p, rbp_i_t); \
467 if (rbp_left_get(a_type, a_field, rbp_i_g) == rbp_i_p) { \
468 rbp_left_set(a_type, a_field, rbp_i_g, rbp_i_t); \
469 } else if (rbp_right_get(a_type, a_field, rbp_i_g) == rbp_i_p) {\
470 rbp_right_set(a_type, a_field, rbp_i_g, rbp_i_t); \
473 rbp_left_set(a_type, a_field, rbp_i_p, (a_node)); \
476 (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_i_s); \
477 rbp_black_set(a_type, a_field, (a_tree)->rbt_root); \
480 #define rb_remove(a_type, a_field, a_cmp, a_tree, a_node) do { \
481 a_type rbp_r_s; \
482 a_type *rbp_r_p, *rbp_r_c, *rbp_r_xp, *rbp_r_t, *rbp_r_u; \
484 rbp_left_set(a_type, a_field, &rbp_r_s, (a_tree)->rbt_root); \
485 rbp_right_set(a_type, a_field, &rbp_r_s, &(a_tree)->rbt_nil); \
486 rbp_black_set(a_type, a_field, &rbp_r_s); \
497 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c); \
498 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \
499 if (rbp_red_get(a_type, a_field, rbp_r_t) == false \
500 && rbp_red_get(a_type, a_field, rbp_r_u) == false) { \
502 rbp_move_red_left(a_type, a_field, rbp_r_c, rbp_r_t); \
503 rbp_black_set(a_type, a_field, rbp_r_t); \
504 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t); \
509 rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c); \
514 if (rbp_right_get(a_type, a_field, rbp_r_c) \
517 if (rbp_left_get(a_type, a_field, rbp_r_c) \
519 rbp_lean_right(a_type, a_field, rbp_r_c, rbp_r_t); \
520 rbp_right_set(a_type, a_field, rbp_r_t, \
525 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t); \
536 if (rbp_red_get(a_type, a_field, rbp_left_get(a_type, \
537 a_field, rbp_right_get(a_type, a_field, rbp_r_c))) \
539 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c); \
540 if (rbp_red_get(a_type, a_field, rbp_r_t)) { \
542 rbp_move_red_right(a_type, a_field, rbp_r_c, \
546 rbp_red_set(a_type, a_field, rbp_r_c); \
547 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \
548 if (rbp_red_get(a_type, a_field, rbp_r_u)) { \
549 rbp_black_set(a_type, a_field, rbp_r_u); \
550 rbp_rotate_right(a_type, a_field, rbp_r_c, \
552 rbp_rotate_left(a_type, a_field, rbp_r_c, \
554 rbp_right_set(a_type, a_field, rbp_r_t, \
557 rbp_red_set(a_type, a_field, rbp_r_t); \
558 rbp_rotate_left(a_type, a_field, rbp_r_c, \
562 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t); \
567 rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c); \
576 rbp_r_t = rbp_left_get(a_type, a_field, rbp_r_c); \
581 if (rbp_left_get(a_type, a_field, rbp_r_xp) \
583 rbp_left_set(a_type, a_field, rbp_r_xp, \
586 assert(rbp_right_get(a_type, a_field, \
588 rbp_right_set(a_type, a_field, rbp_r_xp, \
591 rbp_left_set(a_type, a_field, rbp_r_c, \
592 rbp_left_get(a_type, a_field, (a_node))); \
593 rbp_right_set(a_type, a_field, rbp_r_c, \
594 rbp_right_get(a_type, a_field, (a_node))); \
595 rbp_color_set(a_type, a_field, rbp_r_c, \
596 rbp_red_get(a_type, a_field, (a_node))); \
597 if (rbp_left_get(a_type, a_field, rbp_r_p) \
599 rbp_left_set(a_type, a_field, rbp_r_p, \
602 assert(rbp_right_get(a_type, a_field, rbp_r_p) \
604 rbp_right_set(a_type, a_field, rbp_r_p, \
609 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \
610 if (rbp_red_get(a_type, a_field, rbp_r_t) == false \
611 && rbp_red_get(a_type, a_field, rbp_r_u) == false) { \
612 rbp_move_red_left(a_type, a_field, rbp_r_c, \
614 if (rbp_left_get(a_type, a_field, rbp_r_p) \
616 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
618 rbp_right_set(a_type, a_field, rbp_r_p, \
624 rbp_r_c = rbp_left_get(a_type, a_field, rbp_r_c); \
631 if (rbp_right_get(a_type, a_field, rbp_r_c) \
634 if (rbp_left_get(a_type, a_field, rbp_r_c) \
636 rbp_lean_right(a_type, a_field, rbp_r_c, \
638 rbp_right_set(a_type, a_field, rbp_r_t, \
643 if (rbp_left_get(a_type, a_field, rbp_r_p) \
645 rbp_left_set(a_type, a_field, rbp_r_p, \
648 rbp_right_set(a_type, a_field, rbp_r_p, \
661 rbp_r_t = rbp_right_get(a_type, a_field, rbp_r_c); \
662 rbp_r_u = rbp_left_get(a_type, a_field, rbp_r_t); \
663 if (rbp_red_get(a_type, a_field, rbp_r_u) == false) { \
664 rbp_move_red_right(a_type, a_field, rbp_r_c, \
666 if (rbp_left_get(a_type, a_field, rbp_r_p) \
668 rbp_left_set(a_type, a_field, rbp_r_p, rbp_r_t);\
670 rbp_right_set(a_type, a_field, rbp_r_p, \
676 rbp_r_c = rbp_right_get(a_type, a_field, rbp_r_c); \
682 (a_tree)->rbt_root = rbp_left_get(a_type, a_field, &rbp_r_s); \
693 #define rb_wrap(a_attr, a_prefix, a_tree_type, a_type, a_field, a_cmp) \
696 rb_new(a_type, a_field, tree); \
698 a_attr a_type * \
700 a_type *ret; \
701 rb_first(a_type, a_field, tree, ret); \
704 a_attr a_type * \
706 a_type *ret; \
707 rb_last(a_type, a_field, tree, ret); \
710 a_attr a_type * \
711 a_prefix##next(a_tree_type *tree, a_type *node) { \
712 a_type *ret; \
713 rb_next(a_type, a_field, a_cmp, tree, node, ret); \
716 a_attr a_type * \
717 a_prefix##prev(a_tree_type *tree, a_type *node) { \
718 a_type *ret; \
719 rb_prev(a_type, a_field, a_cmp, tree, node, ret); \
722 a_attr a_type * \
723 a_prefix##search(a_tree_type *tree, a_type *key) { \
724 a_type *ret; \
725 rb_search(a_type, a_field, a_cmp, tree, key, ret); \
728 a_attr a_type * \
729 a_prefix##nsearch(a_tree_type *tree, a_type *key) { \
730 a_type *ret; \
731 rb_nsearch(a_type, a_field, a_cmp, tree, key, ret); \
734 a_attr a_type * \
735 a_prefix##psearch(a_tree_type *tree, a_type *key) { \
736 a_type *ret; \
737 rb_psearch(a_type, a_field, a_cmp, tree, key, ret); \
741 a_prefix##insert(a_tree_type *tree, a_type *node) { \
742 rb_insert(a_type, a_field, a_cmp, tree, node); \
745 a_prefix##remove(a_tree_type *tree, a_type *node) { \
746 rb_remove(a_type, a_field, a_cmp, tree, node); \
760 * a_type *node, *tnode;
762 * rb_foreach_begin(a_type, a_field, a_tree, node) {
764 * rb_next(a_type, a_field, a_cmp, a_tree, node, tnode);
765 * rb_remove(a_type, a_field, a_cmp, a_tree, node);
766 * rb_foreach_next(a_type, a_field, a_cmp, a_tree, tnode);
768 * } rb_foreach_end(a_type, a_field, a_tree, node)
794 # define rbp_compute_f_height(a_type, a_field, a_tree)
796 # define rbp_compute_fr_height(a_type, a_field, a_tree)
799 # define rbp_compute_f_height(a_type, a_field, a_tree) \
802 rbp_black_height(a_type, a_field, a_tree, rbp_f_height); \
804 # define rbp_compute_fr_height(a_type, a_field, a_tree) \
807 rbp_black_height(a_type, a_field, a_tree, rbp_fr_height); \
811 #define rb_foreach_begin(a_type, a_field, a_tree, a_var) { \
812 rbp_compute_f_height(a_type, a_field, a_tree) \
815 a_type *rbp_f_path[rbp_f_height]; \
816 a_type *rbp_f_node; \
822 while ((rbp_f_node = rbp_left_get(a_type, a_field, \
833 #define rb_foreach_next(a_type, a_field, a_cmp, a_tree, a_node) \
845 rbp_f_node = rbp_left_get(a_type, a_field, \
848 rbp_f_node = rbp_right_get(a_type, a_field, \
861 #define rb_foreach_end(a_type, a_field, a_tree, a_var) \
867 if ((rbp_f_node = rbp_right_get(a_type, a_field, \
873 while ((rbp_f_node = rbp_left_get(a_type, a_field, \
883 if (rbp_left_get(a_type, a_field, \
894 #define rb_foreach_reverse_begin(a_type, a_field, a_tree, a_var) { \
895 rbp_compute_fr_height(a_type, a_field, a_tree) \
898 a_type *rbp_fr_path[rbp_fr_height]; \
899 a_type *rbp_fr_node; \
905 while ((rbp_fr_node = rbp_right_get(a_type, a_field, \
916 #define rb_foreach_reverse_prev(a_type, a_field, a_cmp, a_tree, a_node) \
928 rbp_fr_node = rbp_left_get(a_type, a_field, \
931 rbp_fr_node = rbp_right_get(a_type, a_field,\
944 #define rb_foreach_reverse_end(a_type, a_field, a_tree, a_var) \
955 if ((rbp_fr_node = rbp_left_get(a_type, a_field, \
961 while ((rbp_fr_node = rbp_right_get(a_type, a_field, \
971 if (rbp_right_get(a_type, a_field, \
