Lines Matching refs:nodes
25 /* Order used by nodes. */
35 * nodes.
41 * ordering to allow non-equal nodes that nevertheless compare equal.
176 unsigned nodes = 0;
178 &nodes, &specialness_filter_node, &specialness_filter_subtree,
180 expect_u_eq(0, nodes, "");
182 nodes = 0;
184 &nodes, &specialness_filter_node, &specialness_filter_subtree,
186 expect_u_eq(0, nodes, "");
231 /* Red nodes must be interleaved with black nodes. */
339 expect_u_gt(*nnodes, 0, "Destruction removed too many nodes");
352 node_t nodes[NNODES];
384 /* Initialize tree and nodes. */
387 nodes[k].magic = NODE_MAGIC;
388 nodes[k].key = bag[k];
389 nodes[k].specialness = gen_rand64_range(sfmt,
391 nodes[k].mid_remove = false;
392 nodes[k].allow_duplicates = false;
393 nodes[k].summary_lchild = NULL;
394 nodes[k].summary_rchild = NULL;
395 nodes[k].summary_max_specialness = 0;
398 /* Insert nodes. */
400 tree_insert(&tree, &nodes[k]);
421 tree_next(&tree, &nodes[k]);
422 tree_prev(&tree, &nodes[k]);
425 /* Remove nodes. */
429 node_remove(&tree, &nodes[k], j - k);
434 node_remove(&tree, &nodes[k-1], k);
503 node_t nodes[FILTER_NODES];
505 nodes[i].magic = NODE_MAGIC;
506 nodes[i].key = i;
508 nodes[i].specialness = 0;
510 nodes[i].specialness = ffs_u(i);
512 nodes[i].mid_remove = false;
513 nodes[i].allow_duplicates = false;
514 nodes[i].summary_lchild = NULL;
515 nodes[i].summary_rchild = NULL;
516 nodes[i].summary_max_specialness = 0;
528 /* Fill in just the odd nodes. */
530 tree_insert(&tree, &nodes[i]);
535 /* first */ &nodes[1], /* last */ &nodes[9]);
542 tree_insert(&tree, &nodes[4]);
544 /* first */ &nodes[4], /* last */ &nodes[4]);
547 tree_insert(&tree, &nodes[2]);
548 tree_insert(&tree, &nodes[8]);
555 /* first */ &nodes[2], /* last */ &nodes[8]);
561 tree_remove(&tree, &nodes[2]);
563 /* first */ &nodes[4], /* last */ &nodes[8]);
566 tree_insert(&tree, &nodes[2]);
568 /* first */ &nodes[2], /* last */ &nodes[8]);
572 /* first */ &nodes[4], /* last */ &nodes[8]);
576 /* first */ &nodes[8], /* last */ &nodes[8]);
598 "Should only invoke cb on nodes that pass the filter");
624 check_consistency(tree_t *tree, node_t nodes[UPDATE_TEST_MAX], int nnodes) {
634 if (nodes[i].specialness >= specialness) {
637 || node_cmp(&nodes[i], real_first) < 0) {
638 real_first = &nodes[i];
641 || node_cmp(&nodes[i], real_last) > 0) {
642 real_last = &nodes[i];
665 if (nodes[j].specialness < specialness) {
668 if (node_cmp(&nodes[j], &nodes[i]) < 0
670 || node_cmp(&nodes[j], real_prev_filtered) > 0)) {
671 real_prev_filtered = &nodes[j];
673 if (node_cmp(&nodes[j], &nodes[i]) > 0
675 || node_cmp(&nodes[j], real_next_filtered) < 0)) {
676 real_next_filtered = &nodes[j];
679 next_filtered = tree_next_filtered(tree, &nodes[i],
684 prev_filtered = tree_prev_filtered(tree, &nodes[i],
697 * search, nsearch, psearch from a node before nodes[i] in the
702 before.key = nodes[i].key - 1;
710 real_nsearch_filtered = (nodes[i].specialness >= specialness ?
711 &nodes[i] : real_next_filtered);
723 /* search, nsearch, psearch from nodes[i] */
724 real_search_filtered = (nodes[i].specialness >= specialness ?
725 &nodes[i] : NULL);
726 search_filtered = tree_search_filtered(tree, &nodes[i],
731 real_nsearch_filtered = (nodes[i].specialness >= specialness ?
732 &nodes[i] : real_next_filtered);
733 nsearch_filtered = tree_nsearch_filtered(tree, &nodes[i],
738 real_psearch_filtered = (nodes[i].specialness >= specialness ?
739 &nodes[i] : real_prev_filtered);
740 psearch_filtered = tree_psearch_filtered(tree, &nodes[i],
747 * distinct from nodes[i].
751 equiv.key = nodes[i].key;
753 real_search_filtered = (nodes[i].specialness >= specialness ?
754 &nodes[i] : NULL);
760 real_nsearch_filtered = (nodes[i].specialness >= specialness ?
761 &nodes[i] : real_next_filtered);
767 real_psearch_filtered = (nodes[i].specialness >= specialness ?
768 &nodes[i] : real_prev_filtered);
775 * search, nsearch, psearch from a node after nodes[i] in the
780 after.key = nodes[i].key + 1;
794 real_psearch_filtered = (nodes[i].specialness >= specialness ?
795 &nodes[i] : real_prev_filtered);
807 sorted_nodes[i] = &nodes[i];
837 iter_result = tree_iter_filtered(tree, &nodes[i],
841 expect_d_eq(nspecial - nodes[i].filtered_rank, ctx.ncalls, "");
856 for (int j = 0; j < nspecial - nodes[i].filtered_rank; j++) {
860 iter_result = tree_iter_filtered(tree, &nodes[i],
866 nodes[i].filtered_rank + j], iter_result, "");
886 iter_result = tree_reverse_iter_filtered(tree, &nodes[i],
890 int surplus_rank = (nodes[i].specialness >= 1 ? 1 : 0);
891 expect_d_eq(nodes[i].filtered_rank + surplus_rank, ctx.ncalls,
908 int surplus_rank = (nodes[i].specialness >= 1 ? 1 : 0);
909 for (int j = 0; j < nodes[i].filtered_rank + surplus_rank;
915 &nodes[i], &tree_iterate_filtered_cb, &ctx,
920 nodes[i].filtered_rank - j - 1 + surplus_rank],
929 node_t nodes[UPDATE_TEST_MAX];
937 nodes[j].magic = NODE_MAGIC;
944 nodes[j].key = 2 * gen_rand64(sfmt);
945 nodes[j].specialness = 0;
946 nodes[j].mid_remove = false;
947 nodes[j].allow_duplicates = false;
948 nodes[j].summary_lchild = NULL;
949 nodes[j].summary_rchild = NULL;
950 nodes[j].summary_max_specialness = 0;
951 tree_insert(&tree, &nodes[j]);
955 if (!nodes[victim].mid_remove) {
956 tree_remove(&tree, &nodes[victim]);
957 nodes[victim].mid_remove = true;
961 if (nodes[j].mid_remove) {
962 nodes[j].mid_remove = false;
963 nodes[j].key = 2 * gen_rand64(sfmt);
964 tree_insert(&tree, &nodes[j]);
969 nodes[ind].specialness = 1 - nodes[ind].specialness;
970 tree_update_summaries(&tree, &nodes[ind]);
971 check_consistency(&tree, nodes, nnodes);
Indexes created Mon Mar 02 05:31:46 UTC 2026