Changeset 0b9fe3ec in rtems


Ignore:
Timestamp:
Aug 7, 2014, 5:41:25 PM (6 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, master
Children:
1642d27
Parents:
0ef6e3bf
git-author:
Sebastian Huber <sebastian.huber@…> (08/07/14 17:41:25)
git-committer:
Sebastian Huber <sebastian.huber@…> (08/08/14 09:11:27)
Message:

sptests/sprbtree01: Add random ops test case

Location:
testsuites/sptests/sprbtree01
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • testsuites/sptests/sprbtree01/init.c

    r0ef6e3bf r0b9fe3ec  
    813813  rtems_test_assert( ctx->current < ctx->count );
    814814
    815   rtems_test_assert( td->key == tn->id );
    816815  rtems_test_assert( td->key == tn->key );
    817816
     
    829828
    830829  return false;
     830}
     831
     832static const test_node_description random_ops_tree_unique_1[] = {
     833  { 0, NULL, NULL, NULL, RBT_BLACK }
     834};
     835
     836static const test_node_description random_ops_tree_multiple_1[] = {
     837  { 0, NULL, NULL, NULL, RBT_BLACK }
     838};
     839
     840static const test_node_description random_ops_tree_unique_2[] = {
     841};
     842
     843static const test_node_description random_ops_tree_multiple_2[] = {
     844};
     845
     846static const test_node_description random_ops_tree_unique_3[] = {
     847  { 2, NULL, NULL, NULL, RBT_BLACK }
     848};
     849
     850static const test_node_description random_ops_tree_multiple_3[] = {
     851  { 1, NULL, NULL, NULL, RBT_BLACK }
     852};
     853
     854static const test_node_description random_ops_tree_unique_4[] = {
     855  { 0, NULL, NULL, TN( 3 ), RBT_BLACK },
     856  { 3, TN( 0 ), NULL, NULL, RBT_RED }
     857};
     858
     859static const test_node_description random_ops_tree_multiple_4[] = {
     860  { 0, NULL, NULL, TN( 3 ), RBT_BLACK },
     861  { 1, TN( 0 ), NULL, NULL, RBT_RED }
     862};
     863
     864static const test_node_description random_ops_tree_unique_5[] = {
     865  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     866  { 1, NULL, TN( 0 ), TN( 4 ), RBT_BLACK },
     867  { 4, TN( 1 ), NULL, NULL, RBT_RED }
     868};
     869
     870static const test_node_description random_ops_tree_multiple_5[] = {
     871  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     872  { 0, NULL, TN( 0 ), TN( 4 ), RBT_BLACK },
     873  { 2, TN( 1 ), NULL, NULL, RBT_RED }
     874};
     875
     876static const test_node_description random_ops_tree_unique_6[] = {
     877  { 0, TN( 2 ), NULL, NULL, RBT_RED },
     878  { 2, NULL, TN( 0 ), NULL, RBT_BLACK }
     879};
     880
     881static const test_node_description random_ops_tree_multiple_6[] = {
     882  { 0, TN( 2 ), NULL, NULL, RBT_RED },
     883  { 1, NULL, TN( 0 ), NULL, RBT_BLACK }
     884};
     885
     886static const test_node_description random_ops_tree_unique_7[] = {
     887  { 0, TN( 2 ), NULL, TN( 1 ), RBT_BLACK },
     888  { 1, TN( 0 ), NULL, NULL, RBT_RED },
     889  { 2, NULL, TN( 0 ), TN( 5 ), RBT_BLACK },
     890  { 4, TN( 5 ), NULL, NULL, RBT_RED },
     891  { 5, TN( 2 ), TN( 4 ), NULL, RBT_BLACK }
     892};
     893
     894static const test_node_description random_ops_tree_multiple_7[] = {
     895  { 0, TN( 2 ), NULL, TN( 1 ), RBT_BLACK },
     896  { 0, TN( 0 ), NULL, NULL, RBT_RED },
     897  { 1, NULL, TN( 0 ), TN( 4 ), RBT_BLACK },
     898  { 2, TN( 4 ), NULL, NULL, RBT_RED },
     899  { 2, TN( 2 ), TN( 5 ), NULL, RBT_BLACK }
     900};
     901
     902static const test_node_description random_ops_tree_unique_8[] = {
     903  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     904  { 1, TN( 5 ), TN( 0 ), NULL, RBT_BLACK },
     905  { 5, NULL, TN( 1 ), TN( 6 ), RBT_BLACK },
     906  { 6, TN( 5 ), NULL, NULL, RBT_BLACK }
     907};
     908
     909static const test_node_description random_ops_tree_multiple_8[] = {
     910  { 0, TN( 5 ), NULL, TN( 0 ), RBT_BLACK },
     911  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     912  { 2, NULL, TN( 1 ), TN( 6 ), RBT_BLACK },
     913  { 3, TN( 5 ), NULL, NULL, RBT_BLACK }
     914};
     915
     916static const test_node_description random_ops_tree_unique_9[] = {
     917  { 1, TN( 2 ), NULL, NULL, RBT_BLACK },
     918  { 2, TN( 6 ), TN( 1 ), TN( 4 ), RBT_RED },
     919  { 4, TN( 2 ), NULL, TN( 5 ), RBT_BLACK },
     920  { 5, TN( 4 ), NULL, NULL, RBT_RED },
     921  { 6, NULL, TN( 2 ), TN( 7 ), RBT_BLACK },
     922  { 7, TN( 6 ), NULL, TN( 8 ), RBT_BLACK },
     923  { 8, TN( 7 ), NULL, NULL, RBT_RED }
     924};
     925
     926static const test_node_description random_ops_tree_multiple_9[] = {
     927  { 0, TN( 2 ), NULL, NULL, RBT_BLACK },
     928  { 1, TN( 6 ), TN( 1 ), TN( 4 ), RBT_RED },
     929  { 2, TN( 2 ), NULL, TN( 5 ), RBT_BLACK },
     930  { 2, TN( 4 ), NULL, NULL, RBT_RED },
     931  { 3, NULL, TN( 2 ), TN( 7 ), RBT_BLACK },
     932  { 3, TN( 6 ), NULL, TN( 8 ), RBT_BLACK },
     933  { 4, TN( 7 ), NULL, NULL, RBT_RED }
     934};
     935
     936static const test_node_description random_ops_tree_unique_10[] = {
     937  { 0, TN( 2 ), NULL, NULL, RBT_BLACK },
     938  { 2, TN( 6 ), TN( 0 ), TN( 4 ), RBT_RED },
     939  { 3, TN( 4 ), NULL, NULL, RBT_RED },
     940  { 4, TN( 2 ), TN( 3 ), NULL, RBT_BLACK },
     941  { 6, NULL, TN( 2 ), TN( 8 ), RBT_BLACK },
     942  { 8, TN( 6 ), NULL, NULL, RBT_BLACK }
     943};
     944
     945static const test_node_description random_ops_tree_multiple_10[] = {
     946  { 0, TN( 2 ), NULL, NULL, RBT_BLACK },
     947  { 1, TN( 6 ), TN( 0 ), TN( 4 ), RBT_RED },
     948  { 1, TN( 4 ), NULL, NULL, RBT_RED },
     949  { 2, TN( 2 ), TN( 3 ), NULL, RBT_BLACK },
     950  { 3, NULL, TN( 2 ), TN( 8 ), RBT_BLACK },
     951  { 4, TN( 6 ), NULL, NULL, RBT_BLACK }
     952};
     953
     954static const test_node_description random_ops_tree_unique_11[] = {
     955  { 2, TN( 6 ), NULL, NULL, RBT_BLACK },
     956  { 6, NULL, TN( 2 ), TN( 8 ), RBT_BLACK },
     957  { 7, TN( 8 ), NULL, NULL, RBT_RED },
     958  { 8, TN( 6 ), TN( 7 ), TN( 9 ), RBT_BLACK },
     959  { 9, TN( 8 ), NULL, NULL, RBT_RED }
     960};
     961
     962static const test_node_description random_ops_tree_multiple_11[] = {
     963  { 1, TN( 6 ), NULL, NULL, RBT_BLACK },
     964  { 3, NULL, TN( 2 ), TN( 8 ), RBT_BLACK },
     965  { 3, TN( 8 ), NULL, NULL, RBT_RED },
     966  { 4, TN( 6 ), TN( 7 ), TN( 9 ), RBT_BLACK },
     967  { 4, TN( 8 ), NULL, NULL, RBT_RED }
     968};
     969
     970static const test_node_description random_ops_tree_unique_12[] = {
     971  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     972  { 1, TN( 3 ), TN( 0 ), TN( 2 ), RBT_BLACK },
     973  { 2, TN( 1 ), NULL, NULL, RBT_RED },
     974  { 3, TN( 5 ), TN( 1 ), TN( 4 ), RBT_RED },
     975  { 4, TN( 3 ), NULL, NULL, RBT_BLACK },
     976  { 5, NULL, TN( 3 ), TN( 9 ), RBT_BLACK },
     977  { 9, TN( 5 ), NULL, TN( 11 ), RBT_BLACK },
     978  { 11, TN( 9 ), NULL, NULL, RBT_RED }
     979};
     980
     981static const test_node_description random_ops_tree_multiple_12[] = {
     982  { 0, TN( 1 ), NULL, NULL, RBT_BLACK },
     983  { 0, TN( 5 ), TN( 0 ), TN( 3 ), RBT_RED },
     984  { 1, TN( 1 ), NULL, TN( 2 ), RBT_BLACK },
     985  { 1, TN( 3 ), NULL, NULL, RBT_RED },
     986  { 2, NULL, TN( 1 ), TN( 9 ), RBT_BLACK },
     987  { 2, TN( 9 ), NULL, NULL, RBT_BLACK },
     988  { 4, TN( 5 ), TN( 4 ), TN( 11 ), RBT_RED },
     989  { 5, TN( 9 ), NULL, NULL, RBT_BLACK }
     990};
     991
     992static const test_node_description random_ops_tree_unique_13[] = {
     993  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     994  { 1, TN( 3 ), TN( 0 ), NULL, RBT_BLACK },
     995  { 3, NULL, TN( 1 ), TN( 8 ), RBT_BLACK },
     996  { 4, TN( 5 ), NULL, NULL, RBT_RED },
     997  { 5, TN( 8 ), TN( 4 ), TN( 6 ), RBT_BLACK },
     998  { 6, TN( 5 ), NULL, NULL, RBT_RED },
     999  { 8, TN( 3 ), TN( 5 ), TN( 11 ), RBT_RED },
     1000  { 10, TN( 11 ), NULL, NULL, RBT_RED },
     1001  { 11, TN( 8 ), TN( 10 ), NULL, RBT_BLACK }
     1002};
     1003
     1004static const test_node_description random_ops_tree_multiple_13[] = {
     1005  { 0, TN( 0 ), NULL, NULL, RBT_BLACK },
     1006  { 0, TN( 4 ), TN( 1 ), TN( 3 ), RBT_RED },
     1007  { 1, TN( 0 ), NULL, NULL, RBT_BLACK },
     1008  { 2, NULL, TN( 0 ), TN( 8 ), RBT_BLACK },
     1009  { 2, TN( 6 ), NULL, NULL, RBT_RED },
     1010  { 3, TN( 8 ), TN( 5 ), NULL, RBT_BLACK },
     1011  { 4, TN( 4 ), TN( 6 ), TN( 11 ), RBT_RED },
     1012  { 5, TN( 8 ), NULL, TN( 10 ), RBT_BLACK },
     1013  { 5, TN( 11 ), NULL, NULL, RBT_RED }
     1014};
     1015
     1016static const test_node_description random_ops_tree_unique_14[] = {
     1017  { 3, TN( 6 ), NULL, TN( 5 ), RBT_BLACK },
     1018  { 5, TN( 3 ), NULL, NULL, RBT_RED },
     1019  { 6, NULL, TN( 3 ), TN( 12 ), RBT_BLACK },
     1020  { 8, TN( 12 ), NULL, NULL, RBT_BLACK },
     1021  { 12, TN( 6 ), TN( 8 ), TN( 13 ), RBT_RED },
     1022  { 13, TN( 12 ), NULL, NULL, RBT_BLACK }
     1023};
     1024
     1025static const test_node_description random_ops_tree_multiple_14[] = {
     1026  { 1, TN( 5 ), NULL, NULL, RBT_RED },
     1027  { 2, TN( 6 ), TN( 3 ), NULL, RBT_BLACK },
     1028  { 3, NULL, TN( 5 ), TN( 13 ), RBT_BLACK },
     1029  { 4, TN( 13 ), NULL, NULL, RBT_BLACK },
     1030  { 6, TN( 6 ), TN( 8 ), TN( 12 ), RBT_RED },
     1031  { 6, TN( 13 ), NULL, NULL, RBT_BLACK }
     1032};
     1033
     1034static const test_node_description random_ops_tree_unique_15[] = {
     1035  { 0, TN( 2 ), NULL, NULL, RBT_BLACK },
     1036  { 2, TN( 9 ), TN( 0 ), TN( 8 ), RBT_BLACK },
     1037  { 7, TN( 8 ), NULL, NULL, RBT_RED },
     1038  { 8, TN( 2 ), TN( 7 ), NULL, RBT_BLACK },
     1039  { 9, NULL, TN( 2 ), TN( 12 ), RBT_BLACK },
     1040  { 10, TN( 12 ), NULL, NULL, RBT_BLACK },
     1041  { 12, TN( 9 ), TN( 10 ), TN( 13 ), RBT_BLACK },
     1042  { 13, TN( 12 ), NULL, TN( 14 ), RBT_BLACK },
     1043  { 14, TN( 13 ), NULL, NULL, RBT_RED }
     1044};
     1045
     1046static const test_node_description random_ops_tree_multiple_15[] = {
     1047  { 0, TN( 2 ), NULL, NULL, RBT_RED },
     1048  { 1, TN( 9 ), TN( 0 ), TN( 7 ), RBT_BLACK },
     1049  { 3, TN( 2 ), NULL, NULL, RBT_RED },
     1050  { 4, NULL, TN( 2 ), TN( 13 ), RBT_BLACK },
     1051  { 4, TN( 13 ), NULL, TN( 10 ), RBT_BLACK },
     1052  { 5, TN( 8 ), NULL, NULL, RBT_RED },
     1053  { 6, TN( 9 ), TN( 8 ), TN( 12 ), RBT_RED },
     1054  { 6, TN( 13 ), NULL, TN( 14 ), RBT_BLACK },
     1055  { 7, TN( 12 ), NULL, NULL, RBT_RED }
     1056};
     1057
     1058static const test_node_description random_ops_tree_unique_16[] = {
     1059  { 0, TN( 5 ), NULL, TN( 3 ), RBT_BLACK },
     1060  { 3, TN( 0 ), NULL, NULL, RBT_RED },
     1061  { 5, NULL, TN( 0 ), TN( 10 ), RBT_BLACK },
     1062  { 7, TN( 10 ), NULL, NULL, RBT_BLACK },
     1063  { 10, TN( 5 ), TN( 7 ), TN( 12 ), RBT_RED },
     1064  { 12, TN( 10 ), NULL, NULL, RBT_BLACK }
     1065};
     1066
     1067static const test_node_description random_ops_tree_multiple_16[] = {
     1068  { 0, TN( 3 ), NULL, NULL, RBT_RED },
     1069  { 1, TN( 7 ), TN( 0 ), TN( 5 ), RBT_BLACK },
     1070  { 2, TN( 3 ), NULL, NULL, RBT_RED },
     1071  { 3, NULL, TN( 3 ), TN( 12 ), RBT_BLACK },
     1072  { 5, TN( 12 ), NULL, NULL, RBT_RED },
     1073  { 6, TN( 7 ), TN( 10 ), NULL, RBT_BLACK }
     1074};
     1075
     1076static const test_node_description random_ops_tree_unique_17[] = {
     1077  { 0, TN( 1 ), NULL, NULL, RBT_BLACK },
     1078  { 1, TN( 5 ), TN( 0 ), TN( 3 ), RBT_BLACK },
     1079  { 3, TN( 1 ), NULL, TN( 4 ), RBT_BLACK },
     1080  { 4, TN( 3 ), NULL, NULL, RBT_RED },
     1081  { 5, NULL, TN( 1 ), TN( 9 ), RBT_BLACK },
     1082  { 7, TN( 9 ), NULL, TN( 8 ), RBT_BLACK },
     1083  { 8, TN( 7 ), NULL, NULL, RBT_RED },
     1084  { 9, TN( 5 ), TN( 7 ), TN( 16 ), RBT_BLACK },
     1085  { 16, TN( 9 ), NULL, NULL, RBT_BLACK }
     1086};
     1087
     1088static const test_node_description random_ops_tree_multiple_17[] = {
     1089  { 0, TN( 0 ), NULL, NULL, RBT_BLACK },
     1090  { 0, TN( 5 ), TN( 1 ), TN( 3 ), RBT_BLACK },
     1091  { 1, TN( 0 ), NULL, NULL, RBT_BLACK },
     1092  { 2, NULL, TN( 0 ), TN( 9 ), RBT_BLACK },
     1093  { 2, TN( 9 ), NULL, TN( 7 ), RBT_BLACK },
     1094  { 3, TN( 4 ), NULL, NULL, RBT_RED },
     1095  { 4, TN( 5 ), TN( 4 ), TN( 16 ), RBT_BLACK },
     1096  { 4, TN( 16 ), NULL, NULL, RBT_RED },
     1097  { 8, TN( 9 ), TN( 8 ), NULL, RBT_BLACK }
     1098};
     1099
     1100static const test_node_description random_ops_tree_unique_18[] = {
     1101  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     1102  { 1, TN( 3 ), TN( 0 ), TN( 2 ), RBT_BLACK },
     1103  { 2, TN( 1 ), NULL, NULL, RBT_RED },
     1104  { 3, TN( 6 ), TN( 1 ), TN( 4 ), RBT_BLACK },
     1105  { 4, TN( 3 ), NULL, TN( 5 ), RBT_BLACK },
     1106  { 5, TN( 4 ), NULL, NULL, RBT_RED },
     1107  { 6, NULL, TN( 3 ), TN( 14 ), RBT_BLACK },
     1108  { 7, TN( 8 ), NULL, NULL, RBT_RED },
     1109  { 8, TN( 10 ), TN( 7 ), TN( 9 ), RBT_BLACK },
     1110  { 9, TN( 8 ), NULL, NULL, RBT_RED },
     1111  { 10, TN( 14 ), TN( 8 ), TN( 12 ), RBT_RED },
     1112  { 12, TN( 10 ), NULL, NULL, RBT_BLACK },
     1113  { 14, TN( 6 ), TN( 10 ), TN( 17 ), RBT_BLACK },
     1114  { 17, TN( 14 ), NULL, NULL, RBT_BLACK }
     1115};
     1116
     1117static const test_node_description random_ops_tree_multiple_18[] = {
     1118  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     1119  { 0, TN( 2 ), TN( 0 ), TN( 3 ), RBT_BLACK },
     1120  { 1, TN( 1 ), NULL, NULL, RBT_RED },
     1121  { 1, TN( 6 ), TN( 1 ), TN( 4 ), RBT_BLACK },
     1122  { 2, TN( 2 ), NULL, TN( 5 ), RBT_BLACK },
     1123  { 2, TN( 4 ), NULL, NULL, RBT_RED },
     1124  { 3, NULL, TN( 2 ), TN( 12 ), RBT_BLACK },
     1125  { 3, TN( 8 ), NULL, NULL, RBT_RED },
     1126  { 4, TN( 9 ), TN( 7 ), NULL, RBT_BLACK },
     1127  { 4, TN( 12 ), TN( 8 ), TN( 10 ), RBT_RED },
     1128  { 5, TN( 9 ), NULL, NULL, RBT_BLACK },
     1129  { 6, TN( 6 ), TN( 9 ), TN( 14 ), RBT_BLACK },
     1130  { 7, TN( 12 ), NULL, TN( 17 ), RBT_BLACK },
     1131  { 8, TN( 14 ), NULL, NULL, RBT_RED }
     1132};
     1133
     1134static const test_node_description random_ops_tree_unique_19[] = {
     1135  { 1, TN( 2 ), NULL, NULL, RBT_RED },
     1136  { 2, TN( 6 ), TN( 1 ), NULL, RBT_BLACK },
     1137  { 6, TN( 9 ), TN( 2 ), TN( 8 ), RBT_BLACK },
     1138  { 8, TN( 6 ), NULL, NULL, RBT_BLACK },
     1139  { 9, NULL, TN( 6 ), TN( 12 ), RBT_BLACK },
     1140  { 11, TN( 12 ), NULL, NULL, RBT_BLACK },
     1141  { 12, TN( 9 ), TN( 11 ), TN( 16 ), RBT_BLACK },
     1142  { 14, TN( 16 ), NULL, NULL, RBT_RED },
     1143  { 16, TN( 12 ), TN( 14 ), NULL, RBT_BLACK }
     1144};
     1145
     1146static const test_node_description random_ops_tree_multiple_19[] = {
     1147  { 0, TN( 2 ), NULL, NULL, RBT_RED },
     1148  { 1, TN( 6 ), TN( 1 ), NULL, RBT_BLACK },
     1149  { 3, TN( 8 ), TN( 2 ), TN( 9 ), RBT_BLACK },
     1150  { 4, TN( 6 ), NULL, NULL, RBT_BLACK },
     1151  { 4, NULL, TN( 6 ), TN( 12 ), RBT_BLACK },
     1152  { 5, TN( 12 ), NULL, NULL, RBT_BLACK },
     1153  { 6, TN( 8 ), TN( 11 ), TN( 16 ), RBT_BLACK },
     1154  { 7, TN( 16 ), NULL, NULL, RBT_RED },
     1155  { 8, TN( 12 ), TN( 14 ), NULL, RBT_BLACK }
     1156};
     1157
     1158static const test_node_description random_ops_tree_unique_20[] = {
     1159  { 0, TN( 3 ), NULL, TN( 1 ), RBT_BLACK },
     1160  { 1, TN( 0 ), NULL, NULL, RBT_RED },
     1161  { 3, TN( 9 ), TN( 0 ), TN( 4 ), RBT_RED },
     1162  { 4, TN( 3 ), NULL, TN( 7 ), RBT_BLACK },
     1163  { 7, TN( 4 ), NULL, NULL, RBT_RED },
     1164  { 9, NULL, TN( 3 ), TN( 14 ), RBT_BLACK },
     1165  { 10, TN( 14 ), NULL, TN( 12 ), RBT_BLACK },
     1166  { 12, TN( 10 ), NULL, NULL, RBT_RED },
     1167  { 14, TN( 9 ), TN( 10 ), TN( 18 ), RBT_RED },
     1168  { 17, TN( 18 ), NULL, NULL, RBT_RED },
     1169  { 18, TN( 14 ), TN( 17 ), TN( 19 ), RBT_BLACK },
     1170  { 19, TN( 18 ), NULL, NULL, RBT_RED }
     1171};
     1172
     1173static const test_node_description random_ops_tree_multiple_20[] = {
     1174  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     1175  { 0, TN( 4 ), TN( 0 ), TN( 3 ), RBT_BLACK },
     1176  { 1, TN( 1 ), NULL, NULL, RBT_RED },
     1177  { 2, TN( 9 ), TN( 1 ), TN( 7 ), RBT_BLACK },
     1178  { 3, TN( 4 ), NULL, NULL, RBT_BLACK },
     1179  { 4, NULL, TN( 4 ), TN( 12 ), RBT_BLACK },
     1180  { 5, TN( 12 ), NULL, NULL, RBT_BLACK },
     1181  { 6, TN( 9 ), TN( 10 ), TN( 17 ), RBT_BLACK },
     1182  { 7, TN( 17 ), NULL, NULL, RBT_BLACK },
     1183  { 8, TN( 12 ), TN( 14 ), TN( 18 ), RBT_RED },
     1184  { 9, TN( 17 ), NULL, TN( 19 ), RBT_BLACK },
     1185  { 9, TN( 18 ), NULL, NULL, RBT_RED }
     1186};
     1187
     1188static const test_node_description random_ops_tree_unique_21[] = {
     1189  { 0, TN( 1 ), NULL, NULL, RBT_BLACK },
     1190  { 1, TN( 8 ), TN( 0 ), TN( 4 ), RBT_BLACK },
     1191  { 3, TN( 4 ), NULL, NULL, RBT_BLACK },
     1192  { 4, TN( 1 ), TN( 3 ), TN( 5 ), RBT_RED },
     1193  { 5, TN( 4 ), NULL, NULL, RBT_BLACK },
     1194  { 8, NULL, TN( 1 ), TN( 13 ), RBT_BLACK },
     1195  { 11, TN( 13 ), NULL, NULL, RBT_BLACK },
     1196  { 13, TN( 8 ), TN( 11 ), TN( 16 ), RBT_BLACK },
     1197  { 15, TN( 16 ), NULL, NULL, RBT_BLACK },
     1198  { 16, TN( 13 ), TN( 15 ), TN( 17 ), RBT_RED },
     1199  { 17, TN( 16 ), NULL, NULL, RBT_BLACK }
     1200};
     1201
     1202static const test_node_description random_ops_tree_multiple_21[] = {
     1203  { 0, TN( 1 ), NULL, NULL, RBT_BLACK },
     1204  { 0, TN( 8 ), TN( 0 ), TN( 4 ), RBT_BLACK },
     1205  { 1, TN( 4 ), NULL, NULL, RBT_BLACK },
     1206  { 2, TN( 1 ), TN( 3 ), TN( 5 ), RBT_RED },
     1207  { 2, TN( 4 ), NULL, NULL, RBT_BLACK },
     1208  { 4, NULL, TN( 1 ), TN( 13 ), RBT_BLACK },
     1209  { 5, TN( 13 ), NULL, NULL, RBT_BLACK },
     1210  { 6, TN( 8 ), TN( 11 ), TN( 17 ), RBT_BLACK },
     1211  { 7, TN( 17 ), NULL, NULL, RBT_BLACK },
     1212  { 8, TN( 13 ), TN( 15 ), TN( 16 ), RBT_RED },
     1213  { 8, TN( 17 ), NULL, NULL, RBT_BLACK }
     1214};
     1215
     1216static const test_node_description random_ops_tree_unique_22[] = {
     1217  { 1, TN( 3 ), NULL, TN( 2 ), RBT_BLACK },
     1218  { 2, TN( 1 ), NULL, NULL, RBT_RED },
     1219  { 3, TN( 8 ), TN( 1 ), TN( 4 ), RBT_BLACK },
     1220  { 4, TN( 3 ), NULL, TN( 7 ), RBT_BLACK },
     1221  { 7, TN( 4 ), NULL, NULL, RBT_RED },
     1222  { 8, NULL, TN( 3 ), TN( 14 ), RBT_BLACK },
     1223  { 10, TN( 11 ), NULL, NULL, RBT_RED },
     1224  { 11, TN( 14 ), TN( 10 ), NULL, RBT_BLACK },
     1225  { 14, TN( 8 ), TN( 11 ), TN( 18 ), RBT_BLACK },
     1226  { 15, TN( 18 ), NULL, NULL, RBT_BLACK },
     1227  { 18, TN( 14 ), TN( 15 ), TN( 21 ), RBT_RED },
     1228  { 21, TN( 18 ), NULL, NULL, RBT_BLACK }
     1229};
     1230
     1231static const test_node_description random_ops_tree_multiple_22[] = {
     1232  { 0, TN( 3 ), NULL, NULL, RBT_BLACK },
     1233  { 1, TN( 8 ), TN( 1 ), TN( 4 ), RBT_BLACK },
     1234  { 1, TN( 4 ), NULL, NULL, RBT_BLACK },
     1235  { 2, TN( 3 ), TN( 2 ), TN( 7 ), RBT_RED },
     1236  { 3, TN( 4 ), NULL, NULL, RBT_BLACK },
     1237  { 4, NULL, TN( 3 ), TN( 14 ), RBT_BLACK },
     1238  { 5, TN( 14 ), NULL, TN( 10 ), RBT_BLACK },
     1239  { 5, TN( 11 ), NULL, NULL, RBT_RED },
     1240  { 7, TN( 8 ), TN( 11 ), TN( 18 ), RBT_BLACK },
     1241  { 7, TN( 18 ), NULL, NULL, RBT_BLACK },
     1242  { 9, TN( 14 ), TN( 15 ), TN( 21 ), RBT_RED },
     1243  { 10, TN( 18 ), NULL, NULL, RBT_BLACK }
     1244};
     1245
     1246static const test_node_description random_ops_tree_unique_23[] = {
     1247  { 0, TN( 2 ), NULL, NULL, RBT_BLACK },
     1248  { 2, TN( 8 ), TN( 0 ), TN( 7 ), RBT_BLACK },
     1249  { 7, TN( 2 ), NULL, NULL, RBT_BLACK },
     1250  { 8, NULL, TN( 2 ), TN( 16 ), RBT_BLACK },
     1251  { 11, TN( 12 ), NULL, NULL, RBT_BLACK },
     1252  { 12, TN( 16 ), TN( 11 ), TN( 14 ), RBT_RED },
     1253  { 13, TN( 14 ), NULL, NULL, RBT_RED },
     1254  { 14, TN( 12 ), TN( 13 ), TN( 15 ), RBT_BLACK },
     1255  { 15, TN( 14 ), NULL, NULL, RBT_RED },
     1256  { 16, TN( 8 ), TN( 12 ), TN( 20 ), RBT_BLACK },
     1257  { 17, TN( 20 ), NULL, NULL, RBT_RED },
     1258  { 20, TN( 16 ), TN( 17 ), TN( 21 ), RBT_BLACK },
     1259  { 21, TN( 20 ), NULL, NULL, RBT_RED }
     1260};
     1261
     1262static const test_node_description random_ops_tree_multiple_23[] = {
     1263  { 0, TN( 2 ), NULL, NULL, RBT_BLACK },
     1264  { 1, TN( 8 ), TN( 0 ), TN( 7 ), RBT_RED },
     1265  { 3, TN( 2 ), NULL, NULL, RBT_BLACK },
     1266  { 4, TN( 12 ), TN( 2 ), TN( 11 ), RBT_BLACK },
     1267  { 5, TN( 8 ), NULL, NULL, RBT_BLACK },
     1268  { 6, NULL, TN( 8 ), TN( 17 ), RBT_BLACK },
     1269  { 6, TN( 15 ), NULL, NULL, RBT_BLACK },
     1270  { 7, TN( 17 ), TN( 13 ), TN( 16 ), RBT_RED },
     1271  { 7, TN( 16 ), NULL, NULL, RBT_RED },
     1272  { 8, TN( 15 ), TN( 14 ), NULL, RBT_BLACK },
     1273  { 8, TN( 12 ), TN( 15 ), TN( 20 ), RBT_BLACK },
     1274  { 10, TN( 17 ), NULL, TN( 21 ), RBT_BLACK },
     1275  { 10, TN( 20 ), NULL, NULL, RBT_RED }
     1276};
     1277
     1278static const test_node_description random_ops_tree_unique_24[] = {
     1279  { 4, TN( 5 ), NULL, NULL, RBT_BLACK },
     1280  { 5, TN( 8 ), TN( 4 ), TN( 6 ), RBT_RED },
     1281  { 6, TN( 5 ), NULL, NULL, RBT_BLACK },
     1282  { 8, TN( 14 ), TN( 5 ), TN( 10 ), RBT_BLACK },
     1283  { 10, TN( 8 ), NULL, NULL, RBT_BLACK },
     1284  { 14, NULL, TN( 8 ), TN( 20 ), RBT_BLACK },
     1285  { 15, TN( 16 ), NULL, NULL, RBT_RED },
     1286  { 16, TN( 20 ), TN( 15 ), NULL, RBT_BLACK },
     1287  { 20, TN( 14 ), TN( 16 ), TN( 22 ), RBT_BLACK },
     1288  { 22, TN( 20 ), NULL, NULL, RBT_BLACK }
     1289};
     1290
     1291static const test_node_description random_ops_tree_multiple_24[] = {
     1292  { 2, TN( 6 ), NULL, TN( 5 ), RBT_BLACK },
     1293  { 2, TN( 4 ), NULL, NULL, RBT_RED },
     1294  { 3, TN( 10 ), TN( 4 ), TN( 8 ), RBT_BLACK },
     1295  { 4, TN( 6 ), NULL, NULL, RBT_BLACK },
     1296  { 5, NULL, TN( 6 ), TN( 16 ), RBT_BLACK },
     1297  { 7, TN( 16 ), NULL, TN( 15 ), RBT_BLACK },
     1298  { 7, TN( 14 ), NULL, NULL, RBT_RED },
     1299  { 8, TN( 10 ), TN( 14 ), TN( 22 ), RBT_BLACK },
     1300  { 10, TN( 22 ), NULL, NULL, RBT_RED },
     1301  { 11, TN( 16 ), TN( 20 ), NULL, RBT_BLACK }
     1302};
     1303
     1304static const test_node_description random_ops_tree_unique_25[] = {
     1305  { 0, TN( 1 ), NULL, NULL, RBT_BLACK },
     1306  { 1, TN( 13 ), TN( 0 ), TN( 4 ), RBT_BLACK },
     1307  { 3, TN( 4 ), NULL, NULL, RBT_BLACK },
     1308  { 4, TN( 1 ), TN( 3 ), TN( 6 ), RBT_RED },
     1309  { 5, TN( 6 ), NULL, NULL, RBT_RED },
     1310  { 6, TN( 4 ), TN( 5 ), TN( 9 ), RBT_BLACK },
     1311  { 9, TN( 6 ), NULL, NULL, RBT_RED },
     1312  { 13, NULL, TN( 1 ), TN( 19 ), RBT_BLACK },
     1313  { 14, TN( 15 ), NULL, NULL, RBT_RED },
     1314  { 15, TN( 16 ), TN( 14 ), NULL, RBT_BLACK },
     1315  { 16, TN( 19 ), TN( 15 ), TN( 17 ), RBT_RED },
     1316  { 17, TN( 16 ), NULL, NULL, RBT_BLACK },
     1317  { 19, TN( 13 ), TN( 16 ), TN( 23 ), RBT_BLACK },
     1318  { 23, TN( 19 ), NULL, TN( 24 ), RBT_BLACK },
     1319  { 24, TN( 23 ), NULL, NULL, RBT_RED }
     1320};
     1321
     1322static const test_node_description random_ops_tree_multiple_25[] = {
     1323  { 0, TN( 1 ), NULL, NULL, RBT_BLACK },
     1324  { 0, TN( 5 ), TN( 0 ), TN( 3 ), RBT_RED },
     1325  { 1, TN( 1 ), NULL, NULL, RBT_BLACK },
     1326  { 2, TN( 13 ), TN( 1 ), TN( 6 ), RBT_BLACK },
     1327  { 2, TN( 6 ), NULL, NULL, RBT_RED },
     1328  { 3, TN( 5 ), TN( 4 ), TN( 9 ), RBT_BLACK },
     1329  { 4, TN( 6 ), NULL, NULL, RBT_RED },
     1330  { 6, NULL, TN( 5 ), TN( 19 ), RBT_BLACK },
     1331  { 7, TN( 17 ), NULL, TN( 14 ), RBT_BLACK },
     1332  { 7, TN( 15 ), NULL, NULL, RBT_RED },
     1333  { 8, TN( 19 ), TN( 15 ), TN( 16 ), RBT_RED },
     1334  { 8, TN( 17 ), NULL, NULL, RBT_BLACK },
     1335  { 9, TN( 13 ), TN( 17 ), TN( 23 ), RBT_BLACK },
     1336  { 11, TN( 19 ), NULL, TN( 24 ), RBT_BLACK },
     1337  { 12, TN( 23 ), NULL, NULL, RBT_RED }
     1338};
     1339
     1340static const test_node_description random_ops_tree_unique_26[] = {
     1341  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     1342  { 1, TN( 6 ), TN( 0 ), TN( 3 ), RBT_BLACK },
     1343  { 3, TN( 1 ), NULL, NULL, RBT_RED },
     1344  { 6, TN( 11 ), TN( 1 ), TN( 9 ), RBT_BLACK },
     1345  { 9, TN( 6 ), NULL, TN( 10 ), RBT_BLACK },
     1346  { 10, TN( 9 ), NULL, NULL, RBT_RED },
     1347  { 11, NULL, TN( 6 ), TN( 14 ), RBT_BLACK },
     1348  { 12, TN( 14 ), NULL, TN( 13 ), RBT_BLACK },
     1349  { 13, TN( 12 ), NULL, NULL, RBT_RED },
     1350  { 14, TN( 11 ), TN( 12 ), TN( 20 ), RBT_BLACK },
     1351  { 18, TN( 20 ), NULL, NULL, RBT_BLACK },
     1352  { 20, TN( 14 ), TN( 18 ), TN( 23 ), RBT_RED },
     1353  { 21, TN( 23 ), NULL, NULL, RBT_RED },
     1354  { 23, TN( 20 ), TN( 21 ), NULL, RBT_BLACK }
     1355};
     1356
     1357static const test_node_description random_ops_tree_multiple_26[] = {
     1358  { 0, TN( 0 ), NULL, NULL, RBT_RED },
     1359  { 0, TN( 6 ), TN( 1 ), TN( 3 ), RBT_BLACK },
     1360  { 1, TN( 0 ), NULL, NULL, RBT_RED },
     1361  { 3, TN( 12 ), TN( 0 ), TN( 11 ), RBT_BLACK },
     1362  { 4, TN( 11 ), NULL, NULL, RBT_RED },
     1363  { 5, TN( 6 ), TN( 9 ), TN( 10 ), RBT_BLACK },
     1364  { 5, TN( 11 ), NULL, NULL, RBT_RED },
     1365  { 6, NULL, TN( 6 ), TN( 18 ), RBT_BLACK },
     1366  { 6, TN( 14 ), NULL, NULL, RBT_RED },
     1367  { 7, TN( 18 ), TN( 13 ), NULL, RBT_BLACK },
     1368  { 9, TN( 12 ), TN( 14 ), TN( 21 ), RBT_BLACK },
     1369  { 10, TN( 21 ), NULL, NULL, RBT_RED },
     1370  { 10, TN( 18 ), TN( 20 ), TN( 23 ), RBT_BLACK },
     1371  { 11, TN( 21 ), NULL, NULL, RBT_RED }
     1372};
     1373
     1374static const test_node_description random_ops_tree_unique_27[] = {
     1375  { 3, TN( 8 ), NULL, NULL, RBT_BLACK },
     1376  { 8, TN( 19 ), TN( 3 ), TN( 17 ), RBT_RED },
     1377  { 12, TN( 17 ), NULL, NULL, RBT_RED },
     1378  { 17, TN( 8 ), TN( 12 ), NULL, RBT_BLACK },
     1379  { 19, NULL, TN( 8 ), TN( 23 ), RBT_BLACK },
     1380  { 20, TN( 23 ), NULL, TN( 21 ), RBT_BLACK },
     1381  { 21, TN( 20 ), NULL, NULL, RBT_RED },
     1382  { 23, TN( 19 ), TN( 20 ), TN( 25 ), RBT_RED },
     1383  { 24, TN( 25 ), NULL, NULL, RBT_RED },
     1384  { 25, TN( 23 ), TN( 24 ), TN( 26 ), RBT_BLACK },
     1385  { 26, TN( 25 ), NULL, NULL, RBT_RED }
     1386};
     1387
     1388static const test_node_description random_ops_tree_multiple_27[] = {
     1389  { 1, TN( 8 ), NULL, NULL, RBT_BLACK },
     1390  { 4, TN( 19 ), TN( 3 ), TN( 17 ), RBT_RED },
     1391  { 6, TN( 17 ), NULL, NULL, RBT_RED },
     1392  { 8, TN( 8 ), TN( 12 ), NULL, RBT_BLACK },
     1393  { 9, NULL, TN( 8 ), TN( 23 ), RBT_BLACK },
     1394  { 10, TN( 23 ), NULL, TN( 21 ), RBT_BLACK },
     1395  { 10, TN( 20 ), NULL, NULL, RBT_RED },
     1396  { 11, TN( 19 ), TN( 20 ), TN( 24 ), RBT_RED },
     1397  { 12, TN( 24 ), NULL, NULL, RBT_RED },
     1398  { 12, TN( 23 ), TN( 25 ), TN( 26 ), RBT_BLACK },
     1399  { 13, TN( 24 ), NULL, NULL, RBT_RED }
     1400};
     1401
     1402static const test_node_description random_ops_tree_unique_28[] = {
     1403  { 0, TN( 5 ), NULL, NULL, RBT_BLACK },
     1404  { 5, TN( 13 ), TN( 0 ), TN( 7 ), RBT_RED },
     1405  { 7, TN( 5 ), NULL, NULL, RBT_BLACK },
     1406  { 13, NULL, TN( 5 ), TN( 17 ), RBT_BLACK },
     1407  { 15, TN( 17 ), NULL, NULL, RBT_BLACK },
     1408  { 17, TN( 13 ), TN( 15 ), TN( 26 ), RBT_RED },
     1409  { 21, TN( 26 ), NULL, NULL, RBT_RED },
     1410  { 26, TN( 17 ), TN( 21 ), NULL, RBT_BLACK }
     1411};
     1412
     1413static const test_node_description random_ops_tree_multiple_28[] = {
     1414  { 0, TN( 5 ), NULL, NULL, RBT_RED },
     1415  { 2, TN( 7 ), TN( 0 ), NULL, RBT_BLACK },
     1416  { 3, NULL, TN( 5 ), TN( 15 ), RBT_BLACK },
     1417  { 6, TN( 15 ), NULL, NULL, RBT_BLACK },
     1418  { 7, TN( 7 ), TN( 13 ), TN( 21 ), RBT_RED },
     1419  { 8, TN( 21 ), NULL, NULL, RBT_RED },
     1420  { 10, TN( 15 ), TN( 17 ), TN( 26 ), RBT_BLACK },
     1421  { 13, TN( 21 ), NULL, NULL, RBT_RED }
     1422};
     1423
     1424static const test_node_description random_ops_tree_unique_29[] = {
     1425  { 0, TN( 1 ), NULL, NULL, RBT_RED },
     1426  { 1, TN( 4 ), TN( 0 ), TN( 3 ), RBT_BLACK },
     1427  { 3, TN( 1 ), NULL, NULL, RBT_RED },
     1428  { 4, TN( 11 ), TN( 1 ), TN( 7 ), RBT_BLACK },
     1429  { 6, TN( 7 ), NULL, NULL, RBT_RED },
     1430  { 7, TN( 4 ), TN( 6 ), TN( 8 ), RBT_BLACK },
     1431  { 8, TN( 7 ), NULL, NULL, RBT_RED },
     1432  { 11, NULL, TN( 4 ), TN( 13 ), RBT_BLACK },
     1433  { 12, TN( 13 ), NULL, NULL, RBT_BLACK },
     1434  { 13, TN( 11 ), TN( 12 ), TN( 22 ), RBT_BLACK },
     1435  { 14, TN( 17 ), NULL, NULL, RBT_RED },
     1436  { 17, TN( 22 ), TN( 14 ), NULL, RBT_BLACK },
     1437  { 22, TN( 13 ), TN( 17 ), TN( 25 ), RBT_RED },
     1438  { 25, TN( 22 ), NULL, TN( 27 ), RBT_BLACK },
     1439  { 27, TN( 25 ), NULL, NULL, RBT_RED }
     1440};
     1441
     1442static const test_node_description random_ops_tree_multiple_29[] = {
     1443  { 0, TN( 3 ), NULL, TN( 1 ), RBT_BLACK },
     1444  { 0, TN( 0 ), NULL, NULL, RBT_RED },
     1445  { 1, TN( 11 ), TN( 0 ), TN( 6 ), RBT_BLACK },
     1446  { 2, TN( 6 ), NULL, NULL, RBT_BLACK },
     1447  { 3, TN( 3 ), TN( 4 ), TN( 7 ), RBT_RED },
     1448  { 3, TN( 6 ), NULL, TN( 8 ), RBT_BLACK },
     1449  { 4, TN( 7 ), NULL, NULL, RBT_RED },
     1450  { 5, NULL, TN( 3 ), TN( 12 ), RBT_BLACK },
     1451  { 6, TN( 12 ), NULL, NULL, RBT_BLACK },
     1452  { 6, TN( 11 ), TN( 13 ), TN( 22 ), RBT_BLACK },
     1453  { 7, TN( 17 ), NULL, NULL, RBT_RED },
     1454  { 8, TN( 22 ), TN( 14 ), NULL, RBT_BLACK },
     1455  { 11, TN( 12 ), TN( 17 ), TN( 25 ), RBT_RED },
     1456  { 12, TN( 22 ), NULL, TN( 27 ), RBT_BLACK },
     1457  { 13, TN( 25 ), NULL, NULL, RBT_RED }
     1458};
     1459
     1460static const test_node_description random_ops_tree_unique_30[] = {
     1461  { 0, TN( 4 ), NULL, NULL, RBT_BLACK },
     1462  { 4, TN( 12 ), TN( 0 ), TN( 8 ), RBT_RED },
     1463  { 6, TN( 8 ), NULL, NULL, RBT_RED },
     1464  { 8, TN( 4 ), TN( 6 ), TN( 9 ), RBT_BLACK },
     1465  { 9, TN( 8 ), NULL, NULL, RBT_RED },
     1466  { 12, TN( 14 ), TN( 4 ), TN( 13 ), RBT_BLACK },
     1467  { 13, TN( 12 ), NULL, NULL, RBT_BLACK },
     1468  { 14, NULL, TN( 12 ), TN( 17 ), RBT_BLACK },
     1469  { 16, TN( 17 ), NULL, NULL, RBT_BLACK },
     1470  { 17, TN( 14 ), TN( 16 ), TN( 20 ), RBT_BLACK },
     1471  { 18, TN( 20 ), NULL, NULL, RBT_BLACK },
     1472  { 20, TN( 17 ), TN( 18 ), TN( 28 ), RBT_RED },
     1473  { 27, TN( 28 ), NULL, NULL, RBT_RED },
     1474  { 28, TN( 20 ), TN( 27 ), NULL, RBT_BLACK }
     1475};
     1476
     1477static const test_node_description random_ops_tree_multiple_30[] = {
     1478  { 0, TN( 4 ), NULL, NULL, RBT_RED },
     1479  { 2, TN( 6 ), TN( 0 ), NULL, RBT_BLACK },
     1480  { 3, TN( 12 ), TN( 4 ), TN( 8 ), RBT_RED },
     1481  { 4, TN( 8 ), NULL, NULL, RBT_RED },
     1482  { 4, TN( 6 ), TN( 9 ), TN( 13 ), RBT_BLACK },
     1483  { 6, TN( 8 ), NULL, NULL, RBT_RED },
     1484  { 6, NULL, TN( 6 ), TN( 18 ), RBT_BLACK },
     1485  { 7, TN( 17 ), NULL, NULL, RBT_RED },
     1486  { 8, TN( 18 ), TN( 14 ), TN( 16 ), RBT_BLACK },
     1487  { 8, TN( 17 ), NULL, NULL, RBT_RED },
     1488  { 9, TN( 12 ), TN( 17 ), TN( 27 ), RBT_RED },
     1489  { 10, TN( 27 ), NULL, NULL, RBT_RED },
     1490  { 13, TN( 18 ), TN( 20 ), TN( 28 ), RBT_BLACK },
     1491  { 14, TN( 27 ), NULL, NULL, RBT_RED }
     1492};
     1493
     1494static const test_node_description random_ops_tree_unique_31[] = {
     1495  { 0, TN( 2 ), NULL, NULL, RBT_RED },
     1496  { 2, TN( 5 ), TN( 0 ), NULL, RBT_BLACK },
     1497  { 5, TN( 14 ), TN( 2 ), TN( 9 ), RBT_BLACK },
     1498  { 7, TN( 9 ), NULL, NULL, RBT_RED },
     1499  { 9, TN( 5 ), TN( 7 ), TN( 11 ), RBT_BLACK },
     1500  { 11, TN( 9 ), NULL, NULL, RBT_RED },
     1501  { 14, NULL, TN( 5 ), TN( 21 ), RBT_BLACK },
     1502  { 16, TN( 21 ), NULL, TN( 18 ), RBT_BLACK },
     1503  { 18, TN( 16 ), NULL, NULL, RBT_RED },
     1504  { 21, TN( 14 ), TN( 16 ), TN( 30 ), RBT_BLACK },
     1505  { 30, TN( 21 ), NULL, NULL, RBT_BLACK }
     1506};
     1507
     1508static const test_node_description random_ops_tree_multiple_31[] = {
     1509  { 0, TN( 2 ), NULL, NULL, RBT_RED },
     1510  { 1, TN( 5 ), TN( 0 ), NULL, RBT_BLACK },
     1511  { 2, TN( 11 ), TN( 2 ), TN( 9 ), RBT_BLACK },
     1512  { 3, TN( 9 ), NULL, NULL, RBT_RED },
     1513  { 4, TN( 5 ), TN( 7 ), NULL, RBT_BLACK },
     1514  { 5, NULL, TN( 5 ), TN( 21 ), RBT_BLACK },
     1515  { 7, TN( 16 ), NULL, NULL, RBT_RED },
     1516  { 8, TN( 21 ), TN( 14 ), TN( 18 ), RBT_BLACK },
     1517  { 9, TN( 16 ), NULL, NULL, RBT_RED },
     1518  { 10, TN( 11 ), TN( 16 ), TN( 30 ), RBT_BLACK },
     1519  { 15, TN( 21 ), NULL, NULL, RBT_BLACK }
     1520};
     1521
     1522#define RANDOM_OPS_TREE( i ) \
     1523  { &random_ops_tree_multiple_ ## i[ 0 ], &random_ops_tree_unique_ ## i[ 0 ] }
     1524
     1525static const test_node_description *const random_ops_trees[][2] = {
     1526  RANDOM_OPS_TREE( 1 ),
     1527  RANDOM_OPS_TREE( 2 ),
     1528  RANDOM_OPS_TREE( 3 ),
     1529  RANDOM_OPS_TREE( 4 ),
     1530  RANDOM_OPS_TREE( 5 ),
     1531  RANDOM_OPS_TREE( 6 ),
     1532  RANDOM_OPS_TREE( 7 ),
     1533  RANDOM_OPS_TREE( 8 ),
     1534  RANDOM_OPS_TREE( 9 ),
     1535  RANDOM_OPS_TREE( 10 ),
     1536  RANDOM_OPS_TREE( 11 ),
     1537  RANDOM_OPS_TREE( 12 ),
     1538  RANDOM_OPS_TREE( 13 ),
     1539  RANDOM_OPS_TREE( 14 ),
     1540  RANDOM_OPS_TREE( 15 ),
     1541  RANDOM_OPS_TREE( 16 ),
     1542  RANDOM_OPS_TREE( 17 ),
     1543  RANDOM_OPS_TREE( 18 ),
     1544  RANDOM_OPS_TREE( 19 ),
     1545  RANDOM_OPS_TREE( 20 ),
     1546  RANDOM_OPS_TREE( 21 ),
     1547  RANDOM_OPS_TREE( 22 ),
     1548  RANDOM_OPS_TREE( 23 ),
     1549  RANDOM_OPS_TREE( 24 ),
     1550  RANDOM_OPS_TREE( 25 ),
     1551  RANDOM_OPS_TREE( 26 ),
     1552  RANDOM_OPS_TREE( 27 ),
     1553  RANDOM_OPS_TREE( 28 ),
     1554  RANDOM_OPS_TREE( 29 ),
     1555  RANDOM_OPS_TREE( 30 ),
     1556  RANDOM_OPS_TREE( 31 )
     1557};
     1558
     1559#define RANDOM_OPS_TREE_COUNT( i ) \
     1560  { \
     1561    RTEMS_ARRAY_SIZE( random_ops_tree_multiple_ ## i ), \
     1562    RTEMS_ARRAY_SIZE( random_ops_tree_unique_ ## i ) \
     1563  }
     1564
     1565static const size_t random_ops_tree_counts[][2] = {
     1566  RANDOM_OPS_TREE_COUNT( 1 ),
     1567  RANDOM_OPS_TREE_COUNT( 2 ),
     1568  RANDOM_OPS_TREE_COUNT( 3 ),
     1569  RANDOM_OPS_TREE_COUNT( 4 ),
     1570  RANDOM_OPS_TREE_COUNT( 5 ),
     1571  RANDOM_OPS_TREE_COUNT( 6 ),
     1572  RANDOM_OPS_TREE_COUNT( 7 ),
     1573  RANDOM_OPS_TREE_COUNT( 8 ),
     1574  RANDOM_OPS_TREE_COUNT( 9 ),
     1575  RANDOM_OPS_TREE_COUNT( 10 ),
     1576  RANDOM_OPS_TREE_COUNT( 11 ),
     1577  RANDOM_OPS_TREE_COUNT( 12 ),
     1578  RANDOM_OPS_TREE_COUNT( 13 ),
     1579  RANDOM_OPS_TREE_COUNT( 14 ),
     1580  RANDOM_OPS_TREE_COUNT( 15 ),
     1581  RANDOM_OPS_TREE_COUNT( 16 ),
     1582  RANDOM_OPS_TREE_COUNT( 17 ),
     1583  RANDOM_OPS_TREE_COUNT( 18 ),
     1584  RANDOM_OPS_TREE_COUNT( 19 ),
     1585  RANDOM_OPS_TREE_COUNT( 20 ),
     1586  RANDOM_OPS_TREE_COUNT( 21 ),
     1587  RANDOM_OPS_TREE_COUNT( 22 ),
     1588  RANDOM_OPS_TREE_COUNT( 23 ),
     1589  RANDOM_OPS_TREE_COUNT( 24 ),
     1590  RANDOM_OPS_TREE_COUNT( 25 ),
     1591  RANDOM_OPS_TREE_COUNT( 26 ),
     1592  RANDOM_OPS_TREE_COUNT( 27 ),
     1593  RANDOM_OPS_TREE_COUNT( 28 ),
     1594  RANDOM_OPS_TREE_COUNT( 29 ),
     1595  RANDOM_OPS_TREE_COUNT( 30 ),
     1596  RANDOM_OPS_TREE_COUNT( 31 )
     1597};
     1598
     1599static uint32_t simple_random( uint32_t v )
     1600{
     1601  v *= 1664525;
     1602  v += 1013904223;
     1603
     1604  return v;
     1605}
     1606
     1607static void random_ops( size_t n, bool unique )
     1608{
     1609  visitor_context ctx = {
     1610    0,
     1611    random_ops_tree_counts[ n - 1 ][ unique ],
     1612    random_ops_trees[ n - 1 ][ unique ]
     1613  };
     1614  rtems_rbtree_control tree;
     1615  test_node *nodes = &node_array[ 0 ];
     1616  size_t m = n * n * n;
     1617  size_t s = unique ? 1 : 2;
     1618  uint32_t v = 0xdeadbeef;
     1619  size_t i;
     1620
     1621  rtems_rbtree_initialize_empty( &tree );
     1622
     1623  memset( nodes, 0, n * sizeof( *nodes ) );
     1624
     1625  for ( i = 0; i < n; ++i ) {
     1626    nodes[ i ].key = (int) ( i / s );
     1627  }
     1628
     1629  for ( i = 0; i < m; ++i ) {
     1630    size_t j = ( v >> 13 ) % n;
     1631    test_node *tn = &nodes[ j ];
     1632
     1633    if ( tn->id == 0 ) {
     1634      tn->id = 1;
     1635      rtems_rbtree_insert( &tree, &tn->Node, test_compare_function, unique );
     1636    } else {
     1637      tn->id = 0;
     1638      rtems_rbtree_extract( &tree, &tn->Node );
     1639    }
     1640
     1641    rtems_test_assert( rb_assert( tree.root ) != -1 );
     1642
     1643    v = simple_random( v );
     1644  }
     1645
     1646  _RBTree_Iterate( &tree, RBT_RIGHT, visit_nodes, &ctx );
     1647  rtems_test_assert( ctx.current == ctx.count );
     1648}
     1649
     1650static void test_rbtree_random_ops( void )
     1651{
     1652  size_t n;
     1653
     1654  puts( "INIT - Random operations" );
     1655
     1656  for ( n = 1; n < RTEMS_ARRAY_SIZE( random_ops_trees ); ++n ) {
     1657    random_ops( n, true );
     1658    random_ops( n, false );
     1659  }
    8311660}
    8321661
     
    13882217
    13892218  test_rbtree_min_max();
     2219  test_rbtree_random_ops();
    13902220
    13912221  TEST_END();
  • testsuites/sptests/sprbtree01/sprbtree01.scn

    r0ef6e3bf r0b9fe3ec  
    3333INIT - Removing 100 nodes
    3434INIT - Verify min/max node updates
     35INIT - Random operations
    3536*** END OF TEST SPRBTREE 1 ***
Note: See TracChangeset for help on using the changeset viewer.