[ 0:00] compiling /home/xrockai/src/divine/nightly/test/libcxx/containers/tree_balance_after_insert.pass.cpp [ 0:00] In file included from /home/xrockai/src/divine/nightly/test/libcxx/containers/tree_balance_after_insert.pass.cpp:19: [ 0:00] In file included from /dios/libcxx/include/__tree:14: [ 0:00] In file included from /dios/libcxx/include/iterator:420: [ 0:00] In file included from /dios/libcxx/include/iosfwd:95: [ 0:00] In file included from /dios/libcxx/include/wchar.h:118: [ 0:00] In file included from /dios/include/wchar.h:9: [ 0:00] In file included from /dios/include/_PDCLIB/int.h:16: [ 0:00] /dios/include/_PDCLIB/cdefs.h:69:10: warning: Unsupported _ _cplusplus (__cplusplus) (too new) (supported: ISO/IEC 14882:1997, ISO/IEC 14882:2011). [ 0:00] #warning Unsupported _ _cplusplus (__cplusplus) (too new) (supported: ISO/IEC 14882:1997, ISO/IEC 14882:2011). [ 0:00] ^ [ 0:00] 1 warning generated. [ 0:01] compiling /dios/lib/config/seqklee.bc [ 0:01] setting up pass: functionmeta, options = [ 0:02] setting up pass: fuse-ctors, options = [ 0:02] KLEE: output directory is "/var/obj/divine-nightly/semidbg/test/__test_work_dir.20/_klee_out" [ 0:06] KLEE: Using Z3 solver backend [ 0:06] WARNING: this target does not support the llvm.stacksave intrinsic. [ 0:06] warning: Linking two modules of different target triples: klee_div_zero_check.bc' is 'x86_64-unknown-linux-gnu' whereas 'klee.bc' is 'x86_64-unknown-none-elf' [ 0:06] [ 0:06] KLEE: WARNING: undefined reference to function: _Z10klee_abortv [ 0:10] KLEE: WARNING: undefined reference to function: __dios_tainted_init [ 0:10] KLEE: WARNING: undefined reference to function: klee_free [ 0:10] KLEE: WARNING: undefined reference to function: klee_malloc [ 0:10] KLEE: WARNING ONCE: Using zero size array fix for landingpad instruction filter [ 0:11] i:1 [ 0:11] KLEE: WARNING ONCE: Alignment of memory from call "klee_malloc" is not modelled. Using alignment of 8. [ 0:11] about to __boot:0 [ 0:11] about to run the scheduler:0 [ 0:11] KLEE: WARNING ONCE: calling external: __dios_tainted_init() at /dios/libc/sys/start.cpp:49 5 [ 0:11] KLEE: ERROR: /dios/libc/sys/start.cpp:87: failed external call: __dios_tainted_init [ 0:11] KLEE: NOTE: now ignoring this error at this location [ 0:11] KLEE: ERROR: EXITING ON ERROR: [ 0:11] Error: failed external call: __dios_tainted_init [ 0:11] File: /dios/libc/sys/start.cpp [ 0:11] Line: 87 [ 0:11] assembly.ll line: 75257 [ 0:11] Stack: [ 0:11] #000075257 in __dios_start (l=2, argc=1, argv=94490499838472, envp=94490499899400) at /dios/libc/sys/start.cpp:87 [ 0:11] #100023259 in _ZN6__dios10sched_nullINS_5ClockINS_10NondetKleeINS_4BaseEEEEEE13run_schedulerINS_7ContextEEEvv () at /dios/sys/sched_null.hpp:163 [ 0:11] #200083837 in klee_boot (argc=2, argv=94490466545024) at /dios/arch/klee/boot.c:41 [ 0:11] [ 0:11] [ 0:11] 1 /* TAGS: c++ fin */ [ 0:11] 2 /* CC_OPTS: -std=c++2a */ [ 0:11] 3 /* VERIFY_OPTS: -o nofail:malloc */ [ 0:11] 4 //===----------------------------------------------------------------------===// [ 0:11] 5 // [ 0:11] 6 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. [ 0:11] 7 // See https://llvm.org/LICENSE.txt for license information. [ 0:11] 8 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception [ 0:11] 9 // [ 0:11] 10 //===----------------------------------------------------------------------===// [ 0:11] 11 [ 0:11] 12 // Not a portable test [ 0:11] 13 [ 0:11] 14 // Precondition: __root->__is_black_ == true [ 0:11] 15 // template [ 0:11] 16 // void [ 0:11] 17 // __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) [ 0:11] 18 [ 0:11] 19 #include <__tree> [ 0:11] 20 #include [ 0:11] 21 [ 0:11] 22 #include "test_macros.h" [ 0:11] 23 [ 0:11] 24 struct Node [ 0:11] 25 { [ 0:11] 26 Node* __left_; [ 0:11] 27 Node* __right_; [ 0:11] 28 Node* __parent_; [ 0:11] 29 bool __is_black_; [ 0:11] 30 [ 0:11] 31 Node* __parent_unsafe() const { return __parent_; } [ 0:11] 32 void __set_parent(Node* x) { __parent_ = x;} [ 0:11] 33 [ 0:11] 34 Node() : __left_(), __right_(), __parent_(), __is_black_() {} [ 0:11] 35 }; [ 0:11] 36 [ 0:11] 37 void [ 0:11] 38 test1() [ 0:11] 39 { [ 0:11] 40 { [ 0:11] 41 Node root; [ 0:11] 42 Node a; [ 0:11] 43 Node b; [ 0:11] 44 Node c; [ 0:11] 45 Node d; [ 0:11] 46 [ 0:11] 47 root.__left_ = &c; [ 0:11] 48 [ 0:11] 49 c.__parent_ = &root; [ 0:11] 50 c.__left_ = &b; [ 0:11] 51 c.__right_ = &d; [ 0:11] 52 c.__is_black_ = true; [ 0:11] 53 [ 0:11] 54 b.__parent_ = &c; [ 0:11] 55 b.__left_ = &a; [ 0:11] 56 b.__right_ = 0; [ 0:11] 57 b.__is_black_ = false; [ 0:11] 58 [ 0:11] 59 d.__parent_ = &c; [ 0:11] 60 d.__left_ = 0; [ 0:11] 61 d.__right_ = 0; [ 0:11] 62 d.__is_black_ = false; [ 0:11] 63 [ 0:11] 64 a.__parent_ = &b; [ 0:11] 65 a.__left_ = 0; [ 0:11] 66 a.__right_ = 0; [ 0:11] 67 a.__is_black_ = false; [ 0:11] 68 [ 0:11] 69 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 70 [ 0:11] 71 assert(std::__tree_invariant(root.__left_)); [ 0:11] 72 [ 0:11] 73 assert(root.__left_ == &c); [ 0:11] 74 [ 0:11] 75 assert(c.__parent_ == &root); [ 0:11] 76 assert(c.__left_ == &b); [ 0:11] 77 assert(c.__right_ == &d); [ 0:11] 78 assert(c.__is_black_ == true); [ 0:11] 79 [ 0:11] 80 assert(b.__parent_ == &c); [ 0:11] 81 assert(b.__left_ == &a); [ 0:11] 82 assert(b.__right_ == 0); [ 0:11] 83 assert(b.__is_black_ == true); [ 0:11] 84 [ 0:11] 85 assert(d.__parent_ == &c); [ 0:11] 86 assert(d.__left_ == 0); [ 0:11] 87 assert(d.__right_ == 0); [ 0:11] 88 assert(d.__is_black_ == true); [ 0:11] 89 [ 0:11] 90 assert(a.__parent_ == &b); [ 0:11] 91 assert(a.__left_ == 0); [ 0:11] 92 assert(a.__right_ == 0); [ 0:11] 93 assert(a.__is_black_ == false); [ 0:11] 94 } [ 0:11] 95 { [ 0:11] 96 Node root; [ 0:11] 97 Node a; [ 0:11] 98 Node b; [ 0:11] 99 Node c; [ 0:11] 100 Node d; [ 0:11] 101 [ 0:11] 102 root.__left_ = &c; [ 0:11] 103 [ 0:11] 104 c.__parent_ = &root; [ 0:11] 105 c.__left_ = &b; [ 0:11] 106 c.__right_ = &d; [ 0:11] 107 c.__is_black_ = true; [ 0:11] 108 [ 0:11] 109 b.__parent_ = &c; [ 0:11] 110 b.__left_ = 0; [ 0:11] 111 b.__right_ = &a; [ 0:11] 112 b.__is_black_ = false; [ 0:11] 113 [ 0:11] 114 d.__parent_ = &c; [ 0:11] 115 d.__left_ = 0; [ 0:11] 116 d.__right_ = 0; [ 0:11] 117 d.__is_black_ = false; [ 0:11] 118 [ 0:11] 119 a.__parent_ = &b; [ 0:11] 120 a.__left_ = 0; [ 0:11] 121 a.__right_ = 0; [ 0:11] 122 a.__is_black_ = false; [ 0:11] 123 [ 0:11] 124 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 125 [ 0:11] 126 assert(std::__tree_invariant(root.__left_)); [ 0:11] 127 [ 0:11] 128 assert(root.__left_ == &c); [ 0:11] 129 [ 0:11] 130 assert(c.__parent_ == &root); [ 0:11] 131 assert(c.__left_ == &b); [ 0:11] 132 assert(c.__right_ == &d); [ 0:11] 133 assert(c.__is_black_ == true); [ 0:11] 134 [ 0:11] 135 assert(b.__parent_ == &c); [ 0:11] 136 assert(b.__left_ == 0); [ 0:11] 137 assert(b.__right_ == &a); [ 0:11] 138 assert(b.__is_black_ == true); [ 0:11] 139 [ 0:11] 140 assert(d.__parent_ == &c); [ 0:11] 141 assert(d.__left_ == 0); [ 0:11] 142 assert(d.__right_ == 0); [ 0:11] 143 assert(d.__is_black_ == true); [ 0:11] 144 [ 0:11] 145 assert(a.__parent_ == &b); [ 0:11] 146 assert(a.__left_ == 0); [ 0:11] 147 assert(a.__right_ == 0); [ 0:11] 148 assert(a.__is_black_ == false); [ 0:11] 149 } [ 0:11] 150 { [ 0:11] 151 Node root; [ 0:11] 152 Node a; [ 0:11] 153 Node b; [ 0:11] 154 Node c; [ 0:11] 155 Node d; [ 0:11] 156 [ 0:11] 157 root.__left_ = &c; [ 0:11] 158 [ 0:11] 159 c.__parent_ = &root; [ 0:11] 160 c.__left_ = &b; [ 0:11] 161 c.__right_ = &d; [ 0:11] 162 c.__is_black_ = true; [ 0:11] 163 [ 0:11] 164 b.__parent_ = &c; [ 0:11] 165 b.__left_ = 0; [ 0:11] 166 b.__right_ = 0; [ 0:11] 167 b.__is_black_ = false; [ 0:11] 168 [ 0:11] 169 d.__parent_ = &c; [ 0:11] 170 d.__left_ = &a; [ 0:11] 171 d.__right_ = 0; [ 0:11] 172 d.__is_black_ = false; [ 0:11] 173 [ 0:11] 174 a.__parent_ = &d; [ 0:11] 175 a.__left_ = 0; [ 0:11] 176 a.__right_ = 0; [ 0:11] 177 a.__is_black_ = false; [ 0:11] 178 [ 0:11] 179 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 180 [ 0:11] 181 assert(std::__tree_invariant(root.__left_)); [ 0:11] 182 [ 0:11] 183 assert(root.__left_ == &c); [ 0:11] 184 [ 0:11] 185 assert(c.__parent_ == &root); [ 0:11] 186 assert(c.__left_ == &b); [ 0:11] 187 assert(c.__right_ == &d); [ 0:11] 188 assert(c.__is_black_ == true); [ 0:11] 189 [ 0:11] 190 assert(b.__parent_ == &c); [ 0:11] 191 assert(b.__left_ == 0); [ 0:11] 192 assert(b.__right_ == 0); [ 0:11] 193 assert(b.__is_black_ == true); [ 0:11] 194 [ 0:11] 195 assert(d.__parent_ == &c); [ 0:11] 196 assert(d.__left_ == &a); [ 0:11] 197 assert(d.__right_ == 0); [ 0:11] 198 assert(d.__is_black_ == true); [ 0:11] 199 [ 0:11] 200 assert(a.__parent_ == &d); [ 0:11] 201 assert(a.__left_ == 0); [ 0:11] 202 assert(a.__right_ == 0); [ 0:11] 203 assert(a.__is_black_ == false); [ 0:11] 204 } [ 0:11] 205 { [ 0:11] 206 Node root; [ 0:11] 207 Node a; [ 0:11] 208 Node b; [ 0:11] 209 Node c; [ 0:11] 210 Node d; [ 0:11] 211 [ 0:11] 212 root.__left_ = &c; [ 0:11] 213 [ 0:11] 214 c.__parent_ = &root; [ 0:11] 215 c.__left_ = &b; [ 0:11] 216 c.__right_ = &d; [ 0:11] 217 c.__is_black_ = true; [ 0:11] 218 [ 0:11] 219 b.__parent_ = &c; [ 0:11] 220 b.__left_ = 0; [ 0:11] 221 b.__right_ = 0; [ 0:11] 222 b.__is_black_ = false; [ 0:11] 223 [ 0:11] 224 d.__parent_ = &c; [ 0:11] 225 d.__left_ = 0; [ 0:11] 226 d.__right_ = &a; [ 0:11] 227 d.__is_black_ = false; [ 0:11] 228 [ 0:11] 229 a.__parent_ = &d; [ 0:11] 230 a.__left_ = 0; [ 0:11] 231 a.__right_ = 0; [ 0:11] 232 a.__is_black_ = false; [ 0:11] 233 [ 0:11] 234 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 235 [ 0:11] 236 assert(std::__tree_invariant(root.__left_)); [ 0:11] 237 [ 0:11] 238 assert(root.__left_ == &c); [ 0:11] 239 [ 0:11] 240 assert(c.__parent_ == &root); [ 0:11] 241 assert(c.__left_ == &b); [ 0:11] 242 assert(c.__right_ == &d); [ 0:11] 243 assert(c.__is_black_ == true); [ 0:11] 244 [ 0:11] 245 assert(b.__parent_ == &c); [ 0:11] 246 assert(b.__left_ == 0); [ 0:11] 247 assert(b.__right_ == 0); [ 0:11] 248 assert(b.__is_black_ == true); [ 0:11] 249 [ 0:11] 250 assert(d.__parent_ == &c); [ 0:11] 251 assert(d.__left_ == 0); [ 0:11] 252 assert(d.__right_ == &a); [ 0:11] 253 assert(d.__is_black_ == true); [ 0:11] 254 [ 0:11] 255 assert(a.__parent_ == &d); [ 0:11] 256 assert(a.__left_ == 0); [ 0:11] 257 assert(a.__right_ == 0); [ 0:11] 258 assert(a.__is_black_ == false); [ 0:11] 259 } [ 0:11] 260 { [ 0:11] 261 Node root; [ 0:11] 262 Node a; [ 0:11] 263 Node b; [ 0:11] 264 Node c; [ 0:11] 265 Node d; [ 0:11] 266 Node e; [ 0:11] 267 Node f; [ 0:11] 268 Node g; [ 0:11] 269 Node h; [ 0:11] 270 Node i; [ 0:11] 271 [ 0:11] 272 root.__left_ = &c; [ 0:11] 273 [ 0:11] 274 c.__parent_ = &root; [ 0:11] 275 c.__left_ = &b; [ 0:11] 276 c.__right_ = &d; [ 0:11] 277 c.__is_black_ = true; [ 0:11] 278 [ 0:11] 279 b.__parent_ = &c; [ 0:11] 280 b.__left_ = &a; [ 0:11] 281 b.__right_ = &g; [ 0:11] 282 b.__is_black_ = false; [ 0:11] 283 [ 0:11] 284 d.__parent_ = &c; [ 0:11] 285 d.__left_ = &h; [ 0:11] 286 d.__right_ = &i; [ 0:11] 287 d.__is_black_ = false; [ 0:11] 288 [ 0:11] 289 a.__parent_ = &b; [ 0:11] 290 a.__left_ = &e; [ 0:11] 291 a.__right_ = &f; [ 0:11] 292 a.__is_black_ = false; [ 0:11] 293 [ 0:11] 294 e.__parent_ = &a; [ 0:11] 295 e.__is_black_ = true; [ 0:11] 296 [ 0:11] 297 f.__parent_ = &a; [ 0:11] 298 f.__is_black_ = true; [ 0:11] 299 [ 0:11] 300 g.__parent_ = &b; [ 0:11] 301 g.__is_black_ = true; [ 0:11] 302 [ 0:11] 303 h.__parent_ = &d; [ 0:11] 304 h.__is_black_ = true; [ 0:11] 305 [ 0:11] 306 i.__parent_ = &d; [ 0:11] 307 i.__is_black_ = true; [ 0:11] 308 [ 0:11] 309 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 310 [ 0:11] 311 assert(std::__tree_invariant(root.__left_)); [ 0:11] 312 [ 0:11] 313 assert(root.__left_ == &c); [ 0:11] 314 [ 0:11] 315 assert(c.__parent_ == &root); [ 0:11] 316 assert(c.__left_ == &b); [ 0:11] 317 assert(c.__right_ == &d); [ 0:11] 318 assert(c.__is_black_ == true); [ 0:11] 319 [ 0:11] 320 assert(b.__parent_ == &c); [ 0:11] 321 assert(b.__left_ == &a); [ 0:11] 322 assert(b.__right_ == &g); [ 0:11] 323 assert(b.__is_black_ == true); [ 0:11] 324 [ 0:11] 325 assert(d.__parent_ == &c); [ 0:11] 326 assert(d.__left_ == &h); [ 0:11] 327 assert(d.__right_ == &i); [ 0:11] 328 assert(d.__is_black_ == true); [ 0:11] 329 [ 0:11] 330 assert(a.__parent_ == &b); [ 0:11] 331 assert(a.__left_ == &e); [ 0:11] 332 assert(a.__right_ == &f); [ 0:11] 333 assert(a.__is_black_ == false); [ 0:11] 334 } [ 0:11] 335 { [ 0:11] 336 Node root; [ 0:11] 337 Node a; [ 0:11] 338 Node b; [ 0:11] 339 Node c; [ 0:11] 340 Node d; [ 0:11] 341 Node e; [ 0:11] 342 Node f; [ 0:11] 343 Node g; [ 0:11] 344 Node h; [ 0:11] 345 Node i; [ 0:11] 346 [ 0:11] 347 root.__left_ = &c; [ 0:11] 348 [ 0:11] 349 c.__parent_ = &root; [ 0:11] 350 c.__left_ = &b; [ 0:11] 351 c.__right_ = &d; [ 0:11] 352 c.__is_black_ = true; [ 0:11] 353 [ 0:11] 354 b.__parent_ = &c; [ 0:11] 355 b.__left_ = &g; [ 0:11] 356 b.__right_ = &a; [ 0:11] 357 b.__is_black_ = false; [ 0:11] 358 [ 0:11] 359 d.__parent_ = &c; [ 0:11] 360 d.__left_ = &h; [ 0:11] 361 d.__right_ = &i; [ 0:11] 362 d.__is_black_ = false; [ 0:11] 363 [ 0:11] 364 a.__parent_ = &b; [ 0:11] 365 a.__left_ = &e; [ 0:11] 366 a.__right_ = &f; [ 0:11] 367 a.__is_black_ = false; [ 0:11] 368 [ 0:11] 369 e.__parent_ = &a; [ 0:11] 370 e.__is_black_ = true; [ 0:11] 371 [ 0:11] 372 f.__parent_ = &a; [ 0:11] 373 f.__is_black_ = true; [ 0:11] 374 [ 0:11] 375 g.__parent_ = &b; [ 0:11] 376 g.__is_black_ = true; [ 0:11] 377 [ 0:11] 378 h.__parent_ = &d; [ 0:11] 379 h.__is_black_ = true; [ 0:11] 380 [ 0:11] 381 i.__parent_ = &d; [ 0:11] 382 i.__is_black_ = true; [ 0:11] 383 [ 0:11] 384 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 385 [ 0:11] 386 assert(std::__tree_invariant(root.__left_)); [ 0:11] 387 [ 0:11] 388 assert(root.__left_ == &c); [ 0:11] 389 [ 0:11] 390 assert(c.__parent_ == &root); [ 0:11] 391 assert(c.__left_ == &b); [ 0:11] 392 assert(c.__right_ == &d); [ 0:11] 393 assert(c.__is_black_ == true); [ 0:11] 394 [ 0:11] 395 assert(b.__parent_ == &c); [ 0:11] 396 assert(b.__left_ == &g); [ 0:11] 397 assert(b.__right_ == &a); [ 0:11] 398 assert(b.__is_black_ == true); [ 0:11] 399 [ 0:11] 400 assert(d.__parent_ == &c); [ 0:11] 401 assert(d.__left_ == &h); [ 0:11] 402 assert(d.__right_ == &i); [ 0:11] 403 assert(d.__is_black_ == true); [ 0:11] 404 [ 0:11] 405 assert(a.__parent_ == &b); [ 0:11] 406 assert(a.__left_ == &e); [ 0:11] 407 assert(a.__right_ == &f); [ 0:11] 408 assert(a.__is_black_ == false); [ 0:11] 409 } [ 0:11] 410 { [ 0:11] 411 Node root; [ 0:11] 412 Node a; [ 0:11] 413 Node b; [ 0:11] 414 Node c; [ 0:11] 415 Node d; [ 0:11] 416 Node e; [ 0:11] 417 Node f; [ 0:11] 418 Node g; [ 0:11] 419 Node h; [ 0:11] 420 Node i; [ 0:11] 421 [ 0:11] 422 root.__left_ = &c; [ 0:11] 423 [ 0:11] 424 c.__parent_ = &root; [ 0:11] 425 c.__left_ = &b; [ 0:11] 426 c.__right_ = &d; [ 0:11] 427 c.__is_black_ = true; [ 0:11] 428 [ 0:11] 429 b.__parent_ = &c; [ 0:11] 430 b.__left_ = &g; [ 0:11] 431 b.__right_ = &h; [ 0:11] 432 b.__is_black_ = false; [ 0:11] 433 [ 0:11] 434 d.__parent_ = &c; [ 0:11] 435 d.__left_ = &a; [ 0:11] 436 d.__right_ = &i; [ 0:11] 437 d.__is_black_ = false; [ 0:11] 438 [ 0:11] 439 a.__parent_ = &d; [ 0:11] 440 a.__left_ = &e; [ 0:11] 441 a.__right_ = &f; [ 0:11] 442 a.__is_black_ = false; [ 0:11] 443 [ 0:11] 444 e.__parent_ = &a; [ 0:11] 445 e.__is_black_ = true; [ 0:11] 446 [ 0:11] 447 f.__parent_ = &a; [ 0:11] 448 f.__is_black_ = true; [ 0:11] 449 [ 0:11] 450 g.__parent_ = &b; [ 0:11] 451 g.__is_black_ = true; [ 0:11] 452 [ 0:11] 453 h.__parent_ = &b; [ 0:11] 454 h.__is_black_ = true; [ 0:11] 455 [ 0:11] 456 i.__parent_ = &d; [ 0:11] 457 i.__is_black_ = true; [ 0:11] 458 [ 0:11] 459 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 460 [ 0:11] 461 assert(std::__tree_invariant(root.__left_)); [ 0:11] 462 [ 0:11] 463 assert(root.__left_ == &c); [ 0:11] 464 [ 0:11] 465 assert(c.__parent_ == &root); [ 0:11] 466 assert(c.__left_ == &b); [ 0:11] 467 assert(c.__right_ == &d); [ 0:11] 468 assert(c.__is_black_ == true); [ 0:11] 469 [ 0:11] 470 assert(b.__parent_ == &c); [ 0:11] 471 assert(b.__left_ == &g); [ 0:11] 472 assert(b.__right_ == &h); [ 0:11] 473 assert(b.__is_black_ == true); [ 0:11] 474 [ 0:11] 475 assert(d.__parent_ == &c); [ 0:11] 476 assert(d.__left_ == &a); [ 0:11] 477 assert(d.__right_ == &i); [ 0:11] 478 assert(d.__is_black_ == true); [ 0:11] 479 [ 0:11] 480 assert(a.__parent_ == &d); [ 0:11] 481 assert(a.__left_ == &e); [ 0:11] 482 assert(a.__right_ == &f); [ 0:11] 483 assert(a.__is_black_ == false); [ 0:11] 484 } [ 0:11] 485 { [ 0:11] 486 Node root; [ 0:11] 487 Node a; [ 0:11] 488 Node b; [ 0:11] 489 Node c; [ 0:11] 490 Node d; [ 0:11] 491 Node e; [ 0:11] 492 Node f; [ 0:11] 493 Node g; [ 0:11] 494 Node h; [ 0:11] 495 Node i; [ 0:11] 496 [ 0:11] 497 root.__left_ = &c; [ 0:11] 498 [ 0:11] 499 c.__parent_ = &root; [ 0:11] 500 c.__left_ = &b; [ 0:11] 501 c.__right_ = &d; [ 0:11] 502 c.__is_black_ = true; [ 0:11] 503 [ 0:11] 504 b.__parent_ = &c; [ 0:11] 505 b.__left_ = &g; [ 0:11] 506 b.__right_ = &h; [ 0:11] 507 b.__is_black_ = false; [ 0:11] 508 [ 0:11] 509 d.__parent_ = &c; [ 0:11] 510 d.__left_ = &i; [ 0:11] 511 d.__right_ = &a; [ 0:11] 512 d.__is_black_ = false; [ 0:11] 513 [ 0:11] 514 a.__parent_ = &d; [ 0:11] 515 a.__left_ = &e; [ 0:11] 516 a.__right_ = &f; [ 0:11] 517 a.__is_black_ = false; [ 0:11] 518 [ 0:11] 519 e.__parent_ = &a; [ 0:11] 520 e.__is_black_ = true; [ 0:11] 521 [ 0:11] 522 f.__parent_ = &a; [ 0:11] 523 f.__is_black_ = true; [ 0:11] 524 [ 0:11] 525 g.__parent_ = &b; [ 0:11] 526 g.__is_black_ = true; [ 0:11] 527 [ 0:11] 528 h.__parent_ = &b; [ 0:11] 529 h.__is_black_ = true; [ 0:11] 530 [ 0:11] 531 i.__parent_ = &d; [ 0:11] 532 i.__is_black_ = true; [ 0:11] 533 [ 0:11] 534 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 535 [ 0:11] 536 assert(std::__tree_invariant(root.__left_)); [ 0:11] 537 [ 0:11] 538 assert(root.__left_ == &c); [ 0:11] 539 [ 0:11] 540 assert(c.__parent_ == &root); [ 0:11] 541 assert(c.__left_ == &b); [ 0:11] 542 assert(c.__right_ == &d); [ 0:11] 543 assert(c.__is_black_ == true); [ 0:11] 544 [ 0:11] 545 assert(b.__parent_ == &c); [ 0:11] 546 assert(b.__left_ == &g); [ 0:11] 547 assert(b.__right_ == &h); [ 0:11] 548 assert(b.__is_black_ == true); [ 0:11] 549 [ 0:11] 550 assert(d.__parent_ == &c); [ 0:11] 551 assert(d.__left_ == &i); [ 0:11] 552 assert(d.__right_ == &a); [ 0:11] 553 assert(d.__is_black_ == true); [ 0:11] 554 [ 0:11] 555 assert(a.__parent_ == &d); [ 0:11] 556 assert(a.__left_ == &e); [ 0:11] 557 assert(a.__right_ == &f); [ 0:11] 558 assert(a.__is_black_ == false); [ 0:11] 559 } [ 0:11] 560 } [ 0:11] 561 [ 0:11] 562 void [ 0:11] 563 test2() [ 0:11] 564 { [ 0:11] 565 { [ 0:11] 566 Node root; [ 0:11] 567 Node a; [ 0:11] 568 Node b; [ 0:11] 569 Node c; [ 0:11] 570 [ 0:11] 571 root.__left_ = &c; [ 0:11] 572 [ 0:11] 573 c.__parent_ = &root; [ 0:11] 574 c.__left_ = &a; [ 0:11] 575 c.__right_ = 0; [ 0:11] 576 c.__is_black_ = true; [ 0:11] 577 [ 0:11] 578 a.__parent_ = &c; [ 0:11] 579 a.__left_ = 0; [ 0:11] 580 a.__right_ = &b; [ 0:11] 581 a.__is_black_ = false; [ 0:11] 582 [ 0:11] 583 b.__parent_ = &a; [ 0:11] 584 b.__left_ = 0; [ 0:11] 585 b.__right_ = 0; [ 0:11] 586 b.__is_black_ = false; [ 0:11] 587 [ 0:11] 588 std::__tree_balance_after_insert(root.__left_, &b); [ 0:11] 589 [ 0:11] 590 assert(std::__tree_invariant(root.__left_)); [ 0:11] 591 [ 0:11] 592 assert(root.__left_ == &b); [ 0:11] 593 [ 0:11] 594 assert(c.__parent_ == &b); [ 0:11] 595 assert(c.__left_ == 0); [ 0:11] 596 assert(c.__right_ == 0); [ 0:11] 597 assert(c.__is_black_ == false); [ 0:11] 598 [ 0:11] 599 assert(a.__parent_ == &b); [ 0:11] 600 assert(a.__left_ == 0); [ 0:11] 601 assert(a.__right_ == 0); [ 0:11] 602 assert(a.__is_black_ == false); [ 0:11] 603 [ 0:11] 604 assert(b.__parent_ == &root); [ 0:11] 605 assert(b.__left_ == &a); [ 0:11] 606 assert(b.__right_ == &c); [ 0:11] 607 assert(b.__is_black_ == true); [ 0:11] 608 } [ 0:11] 609 { [ 0:11] 610 Node root; [ 0:11] 611 Node a; [ 0:11] 612 Node b; [ 0:11] 613 Node c; [ 0:11] 614 [ 0:11] 615 root.__left_ = &a; [ 0:11] 616 [ 0:11] 617 a.__parent_ = &root; [ 0:11] 618 a.__left_ = 0; [ 0:11] 619 a.__right_ = &c; [ 0:11] 620 a.__is_black_ = true; [ 0:11] 621 [ 0:11] 622 c.__parent_ = &a; [ 0:11] 623 c.__left_ = &b; [ 0:11] 624 c.__right_ = 0; [ 0:11] 625 c.__is_black_ = false; [ 0:11] 626 [ 0:11] 627 b.__parent_ = &c; [ 0:11] 628 b.__left_ = 0; [ 0:11] 629 b.__right_ = 0; [ 0:11] 630 b.__is_black_ = false; [ 0:11] 631 [ 0:11] 632 std::__tree_balance_after_insert(root.__left_, &b); [ 0:11] 633 [ 0:11] 634 assert(std::__tree_invariant(root.__left_)); [ 0:11] 635 [ 0:11] 636 assert(root.__left_ == &b); [ 0:11] 637 [ 0:11] 638 assert(a.__parent_ == &b); [ 0:11] 639 assert(a.__left_ == 0); [ 0:11] 640 assert(a.__right_ == 0); [ 0:11] 641 assert(a.__is_black_ == false); [ 0:11] 642 [ 0:11] 643 assert(c.__parent_ == &b); [ 0:11] 644 assert(c.__left_ == 0); [ 0:11] 645 assert(c.__right_ == 0); [ 0:11] 646 assert(c.__is_black_ == false); [ 0:11] 647 [ 0:11] 648 assert(b.__parent_ == &root); [ 0:11] 649 assert(b.__left_ == &a); [ 0:11] 650 assert(b.__right_ == &c); [ 0:11] 651 assert(b.__is_black_ == true); [ 0:11] 652 } [ 0:11] 653 { [ 0:11] 654 Node root; [ 0:11] 655 Node a; [ 0:11] 656 Node b; [ 0:11] 657 Node c; [ 0:11] 658 Node d; [ 0:11] 659 Node e; [ 0:11] 660 Node f; [ 0:11] 661 Node g; [ 0:11] 662 [ 0:11] 663 root.__left_ = &c; [ 0:11] 664 [ 0:11] 665 c.__parent_ = &root; [ 0:11] 666 c.__left_ = &a; [ 0:11] 667 c.__right_ = &g; [ 0:11] 668 c.__is_black_ = true; [ 0:11] 669 [ 0:11] 670 a.__parent_ = &c; [ 0:11] 671 a.__left_ = &d; [ 0:11] 672 a.__right_ = &b; [ 0:11] 673 a.__is_black_ = false; [ 0:11] 674 [ 0:11] 675 b.__parent_ = &a; [ 0:11] 676 b.__left_ = &e; [ 0:11] 677 b.__right_ = &f; [ 0:11] 678 b.__is_black_ = false; [ 0:11] 679 [ 0:11] 680 d.__parent_ = &a; [ 0:11] 681 d.__is_black_ = true; [ 0:11] 682 [ 0:11] 683 e.__parent_ = &b; [ 0:11] 684 e.__is_black_ = true; [ 0:11] 685 [ 0:11] 686 f.__parent_ = &b; [ 0:11] 687 f.__is_black_ = true; [ 0:11] 688 [ 0:11] 689 g.__parent_ = &c; [ 0:11] 690 g.__is_black_ = true; [ 0:11] 691 [ 0:11] 692 std::__tree_balance_after_insert(root.__left_, &b); [ 0:11] 693 [ 0:11] 694 assert(std::__tree_invariant(root.__left_)); [ 0:11] 695 [ 0:11] 696 assert(root.__left_ == &b); [ 0:11] 697 [ 0:11] 698 assert(c.__parent_ == &b); [ 0:11] 699 assert(c.__left_ == &f); [ 0:11] 700 assert(c.__right_ == &g); [ 0:11] 701 assert(c.__is_black_ == false); [ 0:11] 702 [ 0:11] 703 assert(a.__parent_ == &b); [ 0:11] 704 assert(a.__left_ == &d); [ 0:11] 705 assert(a.__right_ == &e); [ 0:11] 706 assert(a.__is_black_ == false); [ 0:11] 707 [ 0:11] 708 assert(b.__parent_ == &root); [ 0:11] 709 assert(b.__left_ == &a); [ 0:11] 710 assert(b.__right_ == &c); [ 0:11] 711 assert(b.__is_black_ == true); [ 0:11] 712 [ 0:11] 713 assert(d.__parent_ == &a); [ 0:11] 714 assert(d.__is_black_ == true); [ 0:11] 715 [ 0:11] 716 assert(e.__parent_ == &a); [ 0:11] 717 assert(e.__is_black_ == true); [ 0:11] 718 [ 0:11] 719 assert(f.__parent_ == &c); [ 0:11] 720 assert(f.__is_black_ == true); [ 0:11] 721 [ 0:11] 722 assert(g.__parent_ == &c); [ 0:11] 723 assert(g.__is_black_ == true); [ 0:11] 724 } [ 0:11] 725 { [ 0:11] 726 Node root; [ 0:11] 727 Node a; [ 0:11] 728 Node b; [ 0:11] 729 Node c; [ 0:11] 730 Node d; [ 0:11] 731 Node e; [ 0:11] 732 Node f; [ 0:11] 733 Node g; [ 0:11] 734 [ 0:11] 735 root.__left_ = &a; [ 0:11] 736 [ 0:11] 737 a.__parent_ = &root; [ 0:11] 738 a.__left_ = &d; [ 0:11] 739 a.__right_ = &c; [ 0:11] 740 a.__is_black_ = true; [ 0:11] 741 [ 0:11] 742 c.__parent_ = &a; [ 0:11] 743 c.__left_ = &b; [ 0:11] 744 c.__right_ = &g; [ 0:11] 745 c.__is_black_ = false; [ 0:11] 746 [ 0:11] 747 b.__parent_ = &c; [ 0:11] 748 b.__left_ = &e; [ 0:11] 749 b.__right_ = &f; [ 0:11] 750 b.__is_black_ = false; [ 0:11] 751 [ 0:11] 752 d.__parent_ = &a; [ 0:11] 753 d.__is_black_ = true; [ 0:11] 754 [ 0:11] 755 e.__parent_ = &b; [ 0:11] 756 e.__is_black_ = true; [ 0:11] 757 [ 0:11] 758 f.__parent_ = &b; [ 0:11] 759 f.__is_black_ = true; [ 0:11] 760 [ 0:11] 761 g.__parent_ = &c; [ 0:11] 762 g.__is_black_ = true; [ 0:11] 763 [ 0:11] 764 std::__tree_balance_after_insert(root.__left_, &b); [ 0:11] 765 [ 0:11] 766 assert(std::__tree_invariant(root.__left_)); [ 0:11] 767 [ 0:11] 768 assert(root.__left_ == &b); [ 0:11] 769 [ 0:11] 770 assert(c.__parent_ == &b); [ 0:11] 771 assert(c.__left_ == &f); [ 0:11] 772 assert(c.__right_ == &g); [ 0:11] 773 assert(c.__is_black_ == false); [ 0:11] 774 [ 0:11] 775 assert(a.__parent_ == &b); [ 0:11] 776 assert(a.__left_ == &d); [ 0:11] 777 assert(a.__right_ == &e); [ 0:11] 778 assert(a.__is_black_ == false); [ 0:11] 779 [ 0:11] 780 assert(b.__parent_ == &root); [ 0:11] 781 assert(b.__left_ == &a); [ 0:11] 782 assert(b.__right_ == &c); [ 0:11] 783 assert(b.__is_black_ == true); [ 0:11] 784 [ 0:11] 785 assert(d.__parent_ == &a); [ 0:11] 786 assert(d.__is_black_ == true); [ 0:11] 787 [ 0:11] 788 assert(e.__parent_ == &a); [ 0:11] 789 assert(e.__is_black_ == true); [ 0:11] 790 [ 0:11] 791 assert(f.__parent_ == &c); [ 0:11] 792 assert(f.__is_black_ == true); [ 0:11] 793 [ 0:11] 794 assert(g.__parent_ == &c); [ 0:11] 795 assert(g.__is_black_ == true); [ 0:11] 796 } [ 0:11] 797 } [ 0:11] 798 [ 0:11] 799 void [ 0:11] 800 test3() [ 0:11] 801 { [ 0:11] 802 { [ 0:11] 803 Node root; [ 0:11] 804 Node a; [ 0:11] 805 Node b; [ 0:11] 806 Node c; [ 0:11] 807 [ 0:11] 808 root.__left_ = &c; [ 0:11] 809 [ 0:11] 810 c.__parent_ = &root; [ 0:11] 811 c.__left_ = &b; [ 0:11] 812 c.__right_ = 0; [ 0:11] 813 c.__is_black_ = true; [ 0:11] 814 [ 0:11] 815 b.__parent_ = &c; [ 0:11] 816 b.__left_ = &a; [ 0:11] 817 b.__right_ = 0; [ 0:11] 818 b.__is_black_ = false; [ 0:11] 819 [ 0:11] 820 a.__parent_ = &b; [ 0:11] 821 a.__left_ = 0; [ 0:11] 822 a.__right_ = 0; [ 0:11] 823 a.__is_black_ = false; [ 0:11] 824 [ 0:11] 825 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 826 [ 0:11] 827 assert(std::__tree_invariant(root.__left_)); [ 0:11] 828 [ 0:11] 829 assert(root.__left_ == &b); [ 0:11] 830 [ 0:11] 831 assert(c.__parent_ == &b); [ 0:11] 832 assert(c.__left_ == 0); [ 0:11] 833 assert(c.__right_ == 0); [ 0:11] 834 assert(c.__is_black_ == false); [ 0:11] 835 [ 0:11] 836 assert(a.__parent_ == &b); [ 0:11] 837 assert(a.__left_ == 0); [ 0:11] 838 assert(a.__right_ == 0); [ 0:11] 839 assert(a.__is_black_ == false); [ 0:11] 840 [ 0:11] 841 assert(b.__parent_ == &root); [ 0:11] 842 assert(b.__left_ == &a); [ 0:11] 843 assert(b.__right_ == &c); [ 0:11] 844 assert(b.__is_black_ == true); [ 0:11] 845 } [ 0:11] 846 { [ 0:11] 847 Node root; [ 0:11] 848 Node a; [ 0:11] 849 Node b; [ 0:11] 850 Node c; [ 0:11] 851 [ 0:11] 852 root.__left_ = &a; [ 0:11] 853 [ 0:11] 854 a.__parent_ = &root; [ 0:11] 855 a.__left_ = 0; [ 0:11] 856 a.__right_ = &b; [ 0:11] 857 a.__is_black_ = true; [ 0:11] 858 [ 0:11] 859 b.__parent_ = &a; [ 0:11] 860 b.__left_ = 0; [ 0:11] 861 b.__right_ = &c; [ 0:11] 862 b.__is_black_ = false; [ 0:11] 863 [ 0:11] 864 c.__parent_ = &b; [ 0:11] 865 c.__left_ = 0; [ 0:11] 866 c.__right_ = 0; [ 0:11] 867 c.__is_black_ = false; [ 0:11] 868 [ 0:11] 869 std::__tree_balance_after_insert(root.__left_, &c); [ 0:11] 870 [ 0:11] 871 assert(std::__tree_invariant(root.__left_)); [ 0:11] 872 [ 0:11] 873 assert(root.__left_ == &b); [ 0:11] 874 [ 0:11] 875 assert(a.__parent_ == &b); [ 0:11] 876 assert(a.__left_ == 0); [ 0:11] 877 assert(a.__right_ == 0); [ 0:11] 878 assert(a.__is_black_ == false); [ 0:11] 879 [ 0:11] 880 assert(c.__parent_ == &b); [ 0:11] 881 assert(c.__left_ == 0); [ 0:11] 882 assert(c.__right_ == 0); [ 0:11] 883 assert(c.__is_black_ == false); [ 0:11] 884 [ 0:11] 885 assert(b.__parent_ == &root); [ 0:11] 886 assert(b.__left_ == &a); [ 0:11] 887 assert(b.__right_ == &c); [ 0:11] 888 assert(b.__is_black_ == true); [ 0:11] 889 } [ 0:11] 890 { [ 0:11] 891 Node root; [ 0:11] 892 Node a; [ 0:11] 893 Node b; [ 0:11] 894 Node c; [ 0:11] 895 Node d; [ 0:11] 896 Node e; [ 0:11] 897 Node f; [ 0:11] 898 Node g; [ 0:11] 899 [ 0:11] 900 root.__left_ = &c; [ 0:11] 901 [ 0:11] 902 c.__parent_ = &root; [ 0:11] 903 c.__left_ = &b; [ 0:11] 904 c.__right_ = &g; [ 0:11] 905 c.__is_black_ = true; [ 0:11] 906 [ 0:11] 907 b.__parent_ = &c; [ 0:11] 908 b.__left_ = &a; [ 0:11] 909 b.__right_ = &f; [ 0:11] 910 b.__is_black_ = false; [ 0:11] 911 [ 0:11] 912 a.__parent_ = &b; [ 0:11] 913 a.__left_ = &d; [ 0:11] 914 a.__right_ = &e; [ 0:11] 915 a.__is_black_ = false; [ 0:11] 916 [ 0:11] 917 d.__parent_ = &a; [ 0:11] 918 d.__is_black_ = true; [ 0:11] 919 [ 0:11] 920 e.__parent_ = &a; [ 0:11] 921 e.__is_black_ = true; [ 0:11] 922 [ 0:11] 923 f.__parent_ = &b; [ 0:11] 924 f.__is_black_ = true; [ 0:11] 925 [ 0:11] 926 g.__parent_ = &c; [ 0:11] 927 g.__is_black_ = true; [ 0:11] 928 [ 0:11] 929 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 930 [ 0:11] 931 assert(std::__tree_invariant(root.__left_)); [ 0:11] 932 [ 0:11] 933 assert(root.__left_ == &b); [ 0:11] 934 [ 0:11] 935 assert(c.__parent_ == &b); [ 0:11] 936 assert(c.__left_ == &f); [ 0:11] 937 assert(c.__right_ == &g); [ 0:11] 938 assert(c.__is_black_ == false); [ 0:11] 939 [ 0:11] 940 assert(a.__parent_ == &b); [ 0:11] 941 assert(a.__left_ == &d); [ 0:11] 942 assert(a.__right_ == &e); [ 0:11] 943 assert(a.__is_black_ == false); [ 0:11] 944 [ 0:11] 945 assert(b.__parent_ == &root); [ 0:11] 946 assert(b.__left_ == &a); [ 0:11] 947 assert(b.__right_ == &c); [ 0:11] 948 assert(b.__is_black_ == true); [ 0:11] 949 [ 0:11] 950 assert(d.__parent_ == &a); [ 0:11] 951 assert(d.__is_black_ == true); [ 0:11] 952 [ 0:11] 953 assert(e.__parent_ == &a); [ 0:11] 954 assert(e.__is_black_ == true); [ 0:11] 955 [ 0:11] 956 assert(f.__parent_ == &c); [ 0:11] 957 assert(f.__is_black_ == true); [ 0:11] 958 [ 0:11] 959 assert(g.__parent_ == &c); [ 0:11] 960 assert(g.__is_black_ == true); [ 0:11] 961 } [ 0:11] 962 { [ 0:11] 963 Node root; [ 0:11] 964 Node a; [ 0:11] 965 Node b; [ 0:11] 966 Node c; [ 0:11] 967 Node d; [ 0:11] 968 Node e; [ 0:11] 969 Node f; [ 0:11] 970 Node g; [ 0:11] 971 [ 0:11] 972 root.__left_ = &a; [ 0:11] 973 [ 0:11] 974 a.__parent_ = &root; [ 0:11] 975 a.__left_ = &d; [ 0:11] 976 a.__right_ = &b; [ 0:11] 977 a.__is_black_ = true; [ 0:11] 978 [ 0:11] 979 b.__parent_ = &a; [ 0:11] 980 b.__left_ = &e; [ 0:11] 981 b.__right_ = &c; [ 0:11] 982 b.__is_black_ = false; [ 0:11] 983 [ 0:11] 984 c.__parent_ = &b; [ 0:11] 985 c.__left_ = &f; [ 0:11] 986 c.__right_ = &g; [ 0:11] 987 c.__is_black_ = false; [ 0:11] 988 [ 0:11] 989 d.__parent_ = &a; [ 0:11] 990 d.__is_black_ = true; [ 0:11] 991 [ 0:11] 992 e.__parent_ = &b; [ 0:11] 993 e.__is_black_ = true; [ 0:11] 994 [ 0:11] 995 f.__parent_ = &c; [ 0:11] 996 f.__is_black_ = true; [ 0:11] 997 [ 0:11] 998 g.__parent_ = &c; [ 0:11] 999 g.__is_black_ = true; [ 0:11] 1000 [ 0:11] 1001 std::__tree_balance_after_insert(root.__left_, &c); [ 0:11] 1002 [ 0:11] 1003 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1004 [ 0:11] 1005 assert(root.__left_ == &b); [ 0:11] 1006 [ 0:11] 1007 assert(c.__parent_ == &b); [ 0:11] 1008 assert(c.__left_ == &f); [ 0:11] 1009 assert(c.__right_ == &g); [ 0:11] 1010 assert(c.__is_black_ == false); [ 0:11] 1011 [ 0:11] 1012 assert(a.__parent_ == &b); [ 0:11] 1013 assert(a.__left_ == &d); [ 0:11] 1014 assert(a.__right_ == &e); [ 0:11] 1015 assert(a.__is_black_ == false); [ 0:11] 1016 [ 0:11] 1017 assert(b.__parent_ == &root); [ 0:11] 1018 assert(b.__left_ == &a); [ 0:11] 1019 assert(b.__right_ == &c); [ 0:11] 1020 assert(b.__is_black_ == true); [ 0:11] 1021 [ 0:11] 1022 assert(d.__parent_ == &a); [ 0:11] 1023 assert(d.__is_black_ == true); [ 0:11] 1024 [ 0:11] 1025 assert(e.__parent_ == &a); [ 0:11] 1026 assert(e.__is_black_ == true); [ 0:11] 1027 [ 0:11] 1028 assert(f.__parent_ == &c); [ 0:11] 1029 assert(f.__is_black_ == true); [ 0:11] 1030 [ 0:11] 1031 assert(g.__parent_ == &c); [ 0:11] 1032 assert(g.__is_black_ == true); [ 0:11] 1033 } [ 0:11] 1034 } [ 0:11] 1035 [ 0:11] 1036 void [ 0:11] 1037 test4() [ 0:11] 1038 { [ 0:11] 1039 Node root; [ 0:11] 1040 Node a; [ 0:11] 1041 Node b; [ 0:11] 1042 Node c; [ 0:11] 1043 Node d; [ 0:11] 1044 Node e; [ 0:11] 1045 Node f; [ 0:11] 1046 Node g; [ 0:11] 1047 Node h; [ 0:11] 1048 [ 0:11] 1049 root.__left_ = &a; [ 0:11] 1050 a.__parent_ = &root; [ 0:11] 1051 [ 0:11] 1052 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 1053 [ 0:11] 1054 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1055 [ 0:11] 1056 assert(root.__parent_ == 0); [ 0:11] 1057 assert(root.__left_ == &a); [ 0:11] 1058 assert(root.__right_ == 0); [ 0:11] 1059 assert(root.__is_black_ == false); [ 0:11] 1060 [ 0:11] 1061 assert(a.__parent_ == &root); [ 0:11] 1062 assert(a.__left_ == 0); [ 0:11] 1063 assert(a.__right_ == 0); [ 0:11] 1064 assert(a.__is_black_ == true); [ 0:11] 1065 [ 0:11] 1066 a.__right_ = &b; [ 0:11] 1067 b.__parent_ = &a; [ 0:11] 1068 [ 0:11] 1069 std::__tree_balance_after_insert(root.__left_, &b); [ 0:11] 1070 [ 0:11] 1071 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1072 [ 0:11] 1073 assert(root.__parent_ == 0); [ 0:11] 1074 assert(root.__left_ == &a); [ 0:11] 1075 assert(root.__right_ == 0); [ 0:11] 1076 assert(root.__is_black_ == false); [ 0:11] 1077 [ 0:11] 1078 assert(a.__parent_ == &root); [ 0:11] 1079 assert(a.__left_ == 0); [ 0:11] 1080 assert(a.__right_ == &b); [ 0:11] 1081 assert(a.__is_black_ == true); [ 0:11] 1082 [ 0:11] 1083 assert(b.__parent_ == &a); [ 0:11] 1084 assert(b.__left_ == 0); [ 0:11] 1085 assert(b.__right_ == 0); [ 0:11] 1086 assert(b.__is_black_ == false); [ 0:11] 1087 [ 0:11] 1088 b.__right_ = &c; [ 0:11] 1089 c.__parent_ = &b; [ 0:11] 1090 [ 0:11] 1091 std::__tree_balance_after_insert(root.__left_, &c); [ 0:11] 1092 [ 0:11] 1093 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1094 [ 0:11] 1095 assert(root.__parent_ == 0); [ 0:11] 1096 assert(root.__left_ == &b); [ 0:11] 1097 assert(root.__right_ == 0); [ 0:11] 1098 assert(root.__is_black_ == false); [ 0:11] 1099 [ 0:11] 1100 assert(a.__parent_ == &b); [ 0:11] 1101 assert(a.__left_ == 0); [ 0:11] 1102 assert(a.__right_ == 0); [ 0:11] 1103 assert(a.__is_black_ == false); [ 0:11] 1104 [ 0:11] 1105 assert(b.__parent_ == &root); [ 0:11] 1106 assert(b.__left_ == &a); [ 0:11] 1107 assert(b.__right_ == &c); [ 0:11] 1108 assert(b.__is_black_ == true); [ 0:11] 1109 [ 0:11] 1110 assert(c.__parent_ == &b); [ 0:11] 1111 assert(c.__left_ == 0); [ 0:11] 1112 assert(c.__right_ == 0); [ 0:11] 1113 assert(c.__is_black_ == false); [ 0:11] 1114 [ 0:11] 1115 c.__right_ = &d; [ 0:11] 1116 d.__parent_ = &c; [ 0:11] 1117 [ 0:11] 1118 std::__tree_balance_after_insert(root.__left_, &d); [ 0:11] 1119 [ 0:11] 1120 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1121 [ 0:11] 1122 assert(root.__parent_ == 0); [ 0:11] 1123 assert(root.__left_ == &b); [ 0:11] 1124 assert(root.__right_ == 0); [ 0:11] 1125 assert(root.__is_black_ == false); [ 0:11] 1126 [ 0:11] 1127 assert(a.__parent_ == &b); [ 0:11] 1128 assert(a.__left_ == 0); [ 0:11] 1129 assert(a.__right_ == 0); [ 0:11] 1130 assert(a.__is_black_ == true); [ 0:11] 1131 [ 0:11] 1132 assert(b.__parent_ == &root); [ 0:11] 1133 assert(b.__left_ == &a); [ 0:11] 1134 assert(b.__right_ == &c); [ 0:11] 1135 assert(b.__is_black_ == true); [ 0:11] 1136 [ 0:11] 1137 assert(c.__parent_ == &b); [ 0:11] 1138 assert(c.__left_ == 0); [ 0:11] 1139 assert(c.__right_ == &d); [ 0:11] 1140 assert(c.__is_black_ == true); [ 0:11] 1141 [ 0:11] 1142 assert(d.__parent_ == &c); [ 0:11] 1143 assert(d.__left_ == 0); [ 0:11] 1144 assert(d.__right_ == 0); [ 0:11] 1145 assert(d.__is_black_ == false); [ 0:11] 1146 [ 0:11] 1147 d.__right_ = &e; [ 0:11] 1148 e.__parent_ = &d; [ 0:11] 1149 [ 0:11] 1150 std::__tree_balance_after_insert(root.__left_, &e); [ 0:11] 1151 [ 0:11] 1152 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1153 [ 0:11] 1154 assert(root.__parent_ == 0); [ 0:11] 1155 assert(root.__left_ == &b); [ 0:11] 1156 assert(root.__right_ == 0); [ 0:11] 1157 assert(root.__is_black_ == false); [ 0:11] 1158 [ 0:11] 1159 assert(b.__parent_ == &root); [ 0:11] 1160 assert(b.__left_ == &a); [ 0:11] 1161 assert(b.__right_ == &d); [ 0:11] 1162 assert(b.__is_black_ == true); [ 0:11] 1163 [ 0:11] 1164 assert(a.__parent_ == &b); [ 0:11] 1165 assert(a.__left_ == 0); [ 0:11] 1166 assert(a.__right_ == 0); [ 0:11] 1167 assert(a.__is_black_ == true); [ 0:11] 1168 [ 0:11] 1169 assert(d.__parent_ == &b); [ 0:11] 1170 assert(d.__left_ == &c); [ 0:11] 1171 assert(d.__right_ == &e); [ 0:11] 1172 assert(d.__is_black_ == true); [ 0:11] 1173 [ 0:11] 1174 assert(c.__parent_ == &d); [ 0:11] 1175 assert(c.__left_ == 0); [ 0:11] 1176 assert(c.__right_ == 0); [ 0:11] 1177 assert(c.__is_black_ == false); [ 0:11] 1178 [ 0:11] 1179 assert(e.__parent_ == &d); [ 0:11] 1180 assert(e.__left_ == 0); [ 0:11] 1181 assert(e.__right_ == 0); [ 0:11] 1182 assert(e.__is_black_ == false); [ 0:11] 1183 [ 0:11] 1184 e.__right_ = &f; [ 0:11] 1185 f.__parent_ = &e; [ 0:11] 1186 [ 0:11] 1187 std::__tree_balance_after_insert(root.__left_, &f); [ 0:11] 1188 [ 0:11] 1189 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1190 [ 0:11] 1191 assert(root.__parent_ == 0); [ 0:11] 1192 assert(root.__left_ == &b); [ 0:11] 1193 assert(root.__right_ == 0); [ 0:11] 1194 assert(root.__is_black_ == false); [ 0:11] 1195 [ 0:11] 1196 assert(b.__parent_ == &root); [ 0:11] 1197 assert(b.__left_ == &a); [ 0:11] 1198 assert(b.__right_ == &d); [ 0:11] 1199 assert(b.__is_black_ == true); [ 0:11] 1200 [ 0:11] 1201 assert(a.__parent_ == &b); [ 0:11] 1202 assert(a.__left_ == 0); [ 0:11] 1203 assert(a.__right_ == 0); [ 0:11] 1204 assert(a.__is_black_ == true); [ 0:11] 1205 [ 0:11] 1206 assert(d.__parent_ == &b); [ 0:11] 1207 assert(d.__left_ == &c); [ 0:11] 1208 assert(d.__right_ == &e); [ 0:11] 1209 assert(d.__is_black_ == false); [ 0:11] 1210 [ 0:11] 1211 assert(c.__parent_ == &d); [ 0:11] 1212 assert(c.__left_ == 0); [ 0:11] 1213 assert(c.__right_ == 0); [ 0:11] 1214 assert(c.__is_black_ == true); [ 0:11] 1215 [ 0:11] 1216 assert(e.__parent_ == &d); [ 0:11] 1217 assert(e.__left_ == 0); [ 0:11] 1218 assert(e.__right_ == &f); [ 0:11] 1219 assert(e.__is_black_ == true); [ 0:11] 1220 [ 0:11] 1221 assert(f.__parent_ == &e); [ 0:11] 1222 assert(f.__left_ == 0); [ 0:11] 1223 assert(f.__right_ == 0); [ 0:11] 1224 assert(f.__is_black_ == false); [ 0:11] 1225 [ 0:11] 1226 f.__right_ = &g; [ 0:11] 1227 g.__parent_ = &f; [ 0:11] 1228 [ 0:11] 1229 std::__tree_balance_after_insert(root.__left_, &g); [ 0:11] 1230 [ 0:11] 1231 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1232 [ 0:11] 1233 assert(root.__parent_ == 0); [ 0:11] 1234 assert(root.__left_ == &b); [ 0:11] 1235 assert(root.__right_ == 0); [ 0:11] 1236 assert(root.__is_black_ == false); [ 0:11] 1237 [ 0:11] 1238 assert(b.__parent_ == &root); [ 0:11] 1239 assert(b.__left_ == &a); [ 0:11] 1240 assert(b.__right_ == &d); [ 0:11] 1241 assert(b.__is_black_ == true); [ 0:11] 1242 [ 0:11] 1243 assert(a.__parent_ == &b); [ 0:11] 1244 assert(a.__left_ == 0); [ 0:11] 1245 assert(a.__right_ == 0); [ 0:11] 1246 assert(a.__is_black_ == true); [ 0:11] 1247 [ 0:11] 1248 assert(d.__parent_ == &b); [ 0:11] 1249 assert(d.__left_ == &c); [ 0:11] 1250 assert(d.__right_ == &f); [ 0:11] 1251 assert(d.__is_black_ == false); [ 0:11] 1252 [ 0:11] 1253 assert(c.__parent_ == &d); [ 0:11] 1254 assert(c.__left_ == 0); [ 0:11] 1255 assert(c.__right_ == 0); [ 0:11] 1256 assert(c.__is_black_ == true); [ 0:11] 1257 [ 0:11] 1258 assert(f.__parent_ == &d); [ 0:11] 1259 assert(f.__left_ == &e); [ 0:11] 1260 assert(f.__right_ == &g); [ 0:11] 1261 assert(f.__is_black_ == true); [ 0:11] 1262 [ 0:11] 1263 assert(e.__parent_ == &f); [ 0:11] 1264 assert(e.__left_ == 0); [ 0:11] 1265 assert(e.__right_ == 0); [ 0:11] 1266 assert(e.__is_black_ == false); [ 0:11] 1267 [ 0:11] 1268 assert(g.__parent_ == &f); [ 0:11] 1269 assert(g.__left_ == 0); [ 0:11] 1270 assert(g.__right_ == 0); [ 0:11] 1271 assert(g.__is_black_ == false); [ 0:11] 1272 [ 0:11] 1273 g.__right_ = &h; [ 0:11] 1274 h.__parent_ = &g; [ 0:11] 1275 [ 0:11] 1276 std::__tree_balance_after_insert(root.__left_, &h); [ 0:11] 1277 [ 0:11] 1278 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1279 [ 0:11] 1280 assert(root.__parent_ == 0); [ 0:11] 1281 assert(root.__left_ == &d); [ 0:11] 1282 assert(root.__right_ == 0); [ 0:11] 1283 assert(root.__is_black_ == false); [ 0:11] 1284 [ 0:11] 1285 assert(d.__parent_ == &root); [ 0:11] 1286 assert(d.__left_ == &b); [ 0:11] 1287 assert(d.__right_ == &f); [ 0:11] 1288 assert(d.__is_black_ == true); [ 0:11] 1289 [ 0:11] 1290 assert(b.__parent_ == &d); [ 0:11] 1291 assert(b.__left_ == &a); [ 0:11] 1292 assert(b.__right_ == &c); [ 0:11] 1293 assert(b.__is_black_ == false); [ 0:11] 1294 [ 0:11] 1295 assert(a.__parent_ == &b); [ 0:11] 1296 assert(a.__left_ == 0); [ 0:11] 1297 assert(a.__right_ == 0); [ 0:11] 1298 assert(a.__is_black_ == true); [ 0:11] 1299 [ 0:11] 1300 assert(c.__parent_ == &b); [ 0:11] 1301 assert(c.__left_ == 0); [ 0:11] 1302 assert(c.__right_ == 0); [ 0:11] 1303 assert(c.__is_black_ == true); [ 0:11] 1304 [ 0:11] 1305 assert(f.__parent_ == &d); [ 0:11] 1306 assert(f.__left_ == &e); [ 0:11] 1307 assert(f.__right_ == &g); [ 0:11] 1308 assert(f.__is_black_ == false); [ 0:11] 1309 [ 0:11] 1310 assert(e.__parent_ == &f); [ 0:11] 1311 assert(e.__left_ == 0); [ 0:11] 1312 assert(e.__right_ == 0); [ 0:11] 1313 assert(e.__is_black_ == true); [ 0:11] 1314 [ 0:11] 1315 assert(g.__parent_ == &f); [ 0:11] 1316 assert(g.__left_ == 0); [ 0:11] 1317 assert(g.__right_ == &h); [ 0:11] 1318 assert(g.__is_black_ == true); [ 0:11] 1319 [ 0:11] 1320 assert(h.__parent_ == &g); [ 0:11] 1321 assert(h.__left_ == 0); [ 0:11] 1322 assert(h.__right_ == 0); [ 0:11] 1323 assert(h.__is_black_ == false); [ 0:11] 1324 } [ 0:11] 1325 [ 0:11] 1326 void [ 0:11] 1327 test5() [ 0:11] 1328 { [ 0:11] 1329 Node root; [ 0:11] 1330 Node a; [ 0:11] 1331 Node b; [ 0:11] 1332 Node c; [ 0:11] 1333 Node d; [ 0:11] 1334 Node e; [ 0:11] 1335 Node f; [ 0:11] 1336 Node g; [ 0:11] 1337 Node h; [ 0:11] 1338 [ 0:11] 1339 root.__left_ = &h; [ 0:11] 1340 h.__parent_ = &root; [ 0:11] 1341 [ 0:11] 1342 std::__tree_balance_after_insert(root.__left_, &h); [ 0:11] 1343 [ 0:11] 1344 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1345 [ 0:11] 1346 assert(root.__parent_ == 0); [ 0:11] 1347 assert(root.__left_ == &h); [ 0:11] 1348 assert(root.__right_ == 0); [ 0:11] 1349 assert(root.__is_black_ == false); [ 0:11] 1350 [ 0:11] 1351 assert(h.__parent_ == &root); [ 0:11] 1352 assert(h.__left_ == 0); [ 0:11] 1353 assert(h.__right_ == 0); [ 0:11] 1354 assert(h.__is_black_ == true); [ 0:11] 1355 [ 0:11] 1356 h.__left_ = &g; [ 0:11] 1357 g.__parent_ = &h; [ 0:11] 1358 [ 0:11] 1359 std::__tree_balance_after_insert(root.__left_, &g); [ 0:11] 1360 [ 0:11] 1361 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1362 [ 0:11] 1363 assert(root.__parent_ == 0); [ 0:11] 1364 assert(root.__left_ == &h); [ 0:11] 1365 assert(root.__right_ == 0); [ 0:11] 1366 assert(root.__is_black_ == false); [ 0:11] 1367 [ 0:11] 1368 assert(h.__parent_ == &root); [ 0:11] 1369 assert(h.__left_ == &g); [ 0:11] 1370 assert(h.__right_ == 0); [ 0:11] 1371 assert(h.__is_black_ == true); [ 0:11] 1372 [ 0:11] 1373 assert(g.__parent_ == &h); [ 0:11] 1374 assert(g.__left_ == 0); [ 0:11] 1375 assert(g.__right_ == 0); [ 0:11] 1376 assert(g.__is_black_ == false); [ 0:11] 1377 [ 0:11] 1378 g.__left_ = &f; [ 0:11] 1379 f.__parent_ = &g; [ 0:11] 1380 [ 0:11] 1381 std::__tree_balance_after_insert(root.__left_, &f); [ 0:11] 1382 [ 0:11] 1383 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1384 [ 0:11] 1385 assert(root.__parent_ == 0); [ 0:11] 1386 assert(root.__left_ == &g); [ 0:11] 1387 assert(root.__right_ == 0); [ 0:11] 1388 assert(root.__is_black_ == false); [ 0:11] 1389 [ 0:11] 1390 assert(g.__parent_ == &root); [ 0:11] 1391 assert(g.__left_ == &f); [ 0:11] 1392 assert(g.__right_ == &h); [ 0:11] 1393 assert(g.__is_black_ == true); [ 0:11] 1394 [ 0:11] 1395 assert(f.__parent_ == &g); [ 0:11] 1396 assert(f.__left_ == 0); [ 0:11] 1397 assert(f.__right_ == 0); [ 0:11] 1398 assert(f.__is_black_ == false); [ 0:11] 1399 [ 0:11] 1400 assert(h.__parent_ == &g); [ 0:11] 1401 assert(h.__left_ == 0); [ 0:11] 1402 assert(h.__right_ == 0); [ 0:11] 1403 assert(h.__is_black_ == false); [ 0:11] 1404 [ 0:11] 1405 f.__left_ = &e; [ 0:11] 1406 e.__parent_ = &f; [ 0:11] 1407 [ 0:11] 1408 std::__tree_balance_after_insert(root.__left_, &e); [ 0:11] 1409 [ 0:11] 1410 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1411 [ 0:11] 1412 assert(root.__parent_ == 0); [ 0:11] 1413 assert(root.__left_ == &g); [ 0:11] 1414 assert(root.__right_ == 0); [ 0:11] 1415 assert(root.__is_black_ == false); [ 0:11] 1416 [ 0:11] 1417 assert(g.__parent_ == &root); [ 0:11] 1418 assert(g.__left_ == &f); [ 0:11] 1419 assert(g.__right_ == &h); [ 0:11] 1420 assert(g.__is_black_ == true); [ 0:11] 1421 [ 0:11] 1422 assert(f.__parent_ == &g); [ 0:11] 1423 assert(f.__left_ == &e); [ 0:11] 1424 assert(f.__right_ == 0); [ 0:11] 1425 assert(f.__is_black_ == true); [ 0:11] 1426 [ 0:11] 1427 assert(e.__parent_ == &f); [ 0:11] 1428 assert(e.__left_ == 0); [ 0:11] 1429 assert(e.__right_ == 0); [ 0:11] 1430 assert(e.__is_black_ == false); [ 0:11] 1431 [ 0:11] 1432 assert(h.__parent_ == &g); [ 0:11] 1433 assert(h.__left_ == 0); [ 0:11] 1434 assert(h.__right_ == 0); [ 0:11] 1435 assert(h.__is_black_ == true); [ 0:11] 1436 [ 0:11] 1437 e.__left_ = &d; [ 0:11] 1438 d.__parent_ = &e; [ 0:11] 1439 [ 0:11] 1440 std::__tree_balance_after_insert(root.__left_, &d); [ 0:11] 1441 [ 0:11] 1442 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1443 [ 0:11] 1444 assert(root.__parent_ == 0); [ 0:11] 1445 assert(root.__left_ == &g); [ 0:11] 1446 assert(root.__right_ == 0); [ 0:11] 1447 assert(root.__is_black_ == false); [ 0:11] 1448 [ 0:11] 1449 assert(g.__parent_ == &root); [ 0:11] 1450 assert(g.__left_ == &e); [ 0:11] 1451 assert(g.__right_ == &h); [ 0:11] 1452 assert(g.__is_black_ == true); [ 0:11] 1453 [ 0:11] 1454 assert(e.__parent_ == &g); [ 0:11] 1455 assert(e.__left_ == &d); [ 0:11] 1456 assert(e.__right_ == &f); [ 0:11] 1457 assert(e.__is_black_ == true); [ 0:11] 1458 [ 0:11] 1459 assert(d.__parent_ == &e); [ 0:11] 1460 assert(d.__left_ == 0); [ 0:11] 1461 assert(d.__right_ == 0); [ 0:11] 1462 assert(d.__is_black_ == false); [ 0:11] 1463 [ 0:11] 1464 assert(f.__parent_ == &e); [ 0:11] 1465 assert(f.__left_ == 0); [ 0:11] 1466 assert(f.__right_ == 0); [ 0:11] 1467 assert(f.__is_black_ == false); [ 0:11] 1468 [ 0:11] 1469 assert(h.__parent_ == &g); [ 0:11] 1470 assert(h.__left_ == 0); [ 0:11] 1471 assert(h.__right_ == 0); [ 0:11] 1472 assert(h.__is_black_ == true); [ 0:11] 1473 [ 0:11] 1474 d.__left_ = &c; [ 0:11] 1475 c.__parent_ = &d; [ 0:11] 1476 [ 0:11] 1477 std::__tree_balance_after_insert(root.__left_, &c); [ 0:11] 1478 [ 0:11] 1479 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1480 [ 0:11] 1481 assert(root.__parent_ == 0); [ 0:11] 1482 assert(root.__left_ == &g); [ 0:11] 1483 assert(root.__right_ == 0); [ 0:11] 1484 assert(root.__is_black_ == false); [ 0:11] 1485 [ 0:11] 1486 assert(g.__parent_ == &root); [ 0:11] 1487 assert(g.__left_ == &e); [ 0:11] 1488 assert(g.__right_ == &h); [ 0:11] 1489 assert(g.__is_black_ == true); [ 0:11] 1490 [ 0:11] 1491 assert(e.__parent_ == &g); [ 0:11] 1492 assert(e.__left_ == &d); [ 0:11] 1493 assert(e.__right_ == &f); [ 0:11] 1494 assert(e.__is_black_ == false); [ 0:11] 1495 [ 0:11] 1496 assert(d.__parent_ == &e); [ 0:11] 1497 assert(d.__left_ == &c); [ 0:11] 1498 assert(d.__right_ == 0); [ 0:11] 1499 assert(d.__is_black_ == true); [ 0:11] 1500 [ 0:11] 1501 assert(c.__parent_ == &d); [ 0:11] 1502 assert(c.__left_ == 0); [ 0:11] 1503 assert(c.__right_ == 0); [ 0:11] 1504 assert(c.__is_black_ == false); [ 0:11] 1505 [ 0:11] 1506 assert(f.__parent_ == &e); [ 0:11] 1507 assert(f.__left_ == 0); [ 0:11] 1508 assert(f.__right_ == 0); [ 0:11] 1509 assert(f.__is_black_ == true); [ 0:11] 1510 [ 0:11] 1511 assert(h.__parent_ == &g); [ 0:11] 1512 assert(h.__left_ == 0); [ 0:11] 1513 assert(h.__right_ == 0); [ 0:11] 1514 assert(h.__is_black_ == true); [ 0:11] 1515 [ 0:11] 1516 c.__left_ = &b; [ 0:11] 1517 b.__parent_ = &c; [ 0:11] 1518 [ 0:11] 1519 std::__tree_balance_after_insert(root.__left_, &b); [ 0:11] 1520 [ 0:11] 1521 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1522 [ 0:11] 1523 assert(root.__parent_ == 0); [ 0:11] 1524 assert(root.__left_ == &g); [ 0:11] 1525 assert(root.__right_ == 0); [ 0:11] 1526 assert(root.__is_black_ == false); [ 0:11] 1527 [ 0:11] 1528 assert(g.__parent_ == &root); [ 0:11] 1529 assert(g.__left_ == &e); [ 0:11] 1530 assert(g.__right_ == &h); [ 0:11] 1531 assert(g.__is_black_ == true); [ 0:11] 1532 [ 0:11] 1533 assert(e.__parent_ == &g); [ 0:11] 1534 assert(e.__left_ == &c); [ 0:11] 1535 assert(e.__right_ == &f); [ 0:11] 1536 assert(e.__is_black_ == false); [ 0:11] 1537 [ 0:11] 1538 assert(c.__parent_ == &e); [ 0:11] 1539 assert(c.__left_ == &b); [ 0:11] 1540 assert(c.__right_ == &d); [ 0:11] 1541 assert(c.__is_black_ == true); [ 0:11] 1542 [ 0:11] 1543 assert(b.__parent_ == &c); [ 0:11] 1544 assert(b.__left_ == 0); [ 0:11] 1545 assert(b.__right_ == 0); [ 0:11] 1546 assert(b.__is_black_ == false); [ 0:11] 1547 [ 0:11] 1548 assert(d.__parent_ == &c); [ 0:11] 1549 assert(d.__left_ == 0); [ 0:11] 1550 assert(d.__right_ == 0); [ 0:11] 1551 assert(d.__is_black_ == false); [ 0:11] 1552 [ 0:11] 1553 assert(f.__parent_ == &e); [ 0:11] 1554 assert(f.__left_ == 0); [ 0:11] 1555 assert(f.__right_ == 0); [ 0:11] 1556 assert(f.__is_black_ == true); [ 0:11] 1557 [ 0:11] 1558 assert(h.__parent_ == &g); [ 0:11] 1559 assert(h.__left_ == 0); [ 0:11] 1560 assert(h.__right_ == 0); [ 0:11] 1561 assert(h.__is_black_ == true); [ 0:11] 1562 [ 0:11] 1563 b.__left_ = &a; [ 0:11] 1564 a.__parent_ = &b; [ 0:11] 1565 [ 0:11] 1566 std::__tree_balance_after_insert(root.__left_, &a); [ 0:11] 1567 [ 0:11] 1568 assert(std::__tree_invariant(root.__left_)); [ 0:11] 1569 [ 0:11] 1570 assert(root.__parent_ == 0); [ 0:11] 1571 assert(root.__left_ == &e); [ 0:11] 1572 assert(root.__right_ == 0); [ 0:11] 1573 assert(root.__is_black_ == false); [ 0:11] 1574 [ 0:11] 1575 assert(e.__parent_ == &root); [ 0:11] 1576 assert(e.__left_ == &c); [ 0:11] 1577 assert(e.__right_ == &g); [ 0:11] 1578 assert(e.__is_black_ == true); [ 0:11] 1579 [ 0:11] 1580 assert(c.__parent_ == &e); [ 0:11] 1581 assert(c.__left_ == &b); [ 0:11] 1582 assert(c.__right_ == &d); [ 0:11] 1583 assert(c.__is_black_ == false); [ 0:11] 1584 [ 0:11] 1585 assert(b.__parent_ == &c); [ 0:11] 1586 assert(b.__left_ == &a); [ 0:11] 1587 assert(b.__right_ == 0); [ 0:11] 1588 assert(b.__is_black_ == true); [ 0:11] 1589 [ 0:11] 1590 assert(a.__parent_ == &b); [ 0:11] 1591 assert(a.__left_ == 0); [ 0:11] 1592 assert(a.__right_ == 0); [ 0:11] 1593 assert(a.__is_black_ == false); [ 0:11] 1594 [ 0:11] 1595 assert(d.__parent_ == &c); [ 0:11] 1596 assert(d.__left_ == 0); [ 0:11] 1597 assert(d.__right_ == 0); [ 0:11] 1598 assert(d.__is_black_ == true); [ 0:11] 1599 [ 0:11] 1600 assert(g.__parent_ == &e); [ 0:11] 1601 assert(g.__left_ == &f); [ 0:11] 1602 assert(g.__right_ == &h); [ 0:11] 1603 assert(g.__is_black_ == false); [ 0:11] 1604 [ 0:11] 1605 assert(f.__parent_ == &g); [ 0:11] 1606 assert(f.__left_ == 0); [ 0:11] 1607 assert(f.__right_ == 0); [ 0:11] 1608 assert(f.__is_black_ == true); [ 0:11] 1609 [ 0:11] 1610 assert(h.__parent_ == &g); [ 0:11] 1611 assert(h.__left_ == 0); [ 0:11] 1612 assert(h.__right_ == 0); [ 0:11] 1613 assert(h.__is_black_ == true); [ 0:11] 1614 } [ 0:11] 1615 [ 0:11] 1616 int main(int, char**) [ 0:11] 1617 { [ 0:11] 1618 test1(); [ 0:11] 1619 test2(); [ 0:11] 1620 test3(); [ 0:11] 1621 test4(); [ 0:11] 1622 test5(); [ 0:11] 1623 [ 0:11] 1624 return 0; [ 0:11] 1625 } [ 0:11] # no errors were expected but one was found anyway