marktree_spec.lua (20324B)
1 local t = require('test.unit.testutil') 2 local itp = t.gen_itp(it) 3 4 local ffi = t.ffi 5 local eq = t.eq 6 local ok = t.ok 7 8 local lib = t.cimport('./src/nvim/marktree.h') 9 10 local function tablelength(tbl) 11 local count = 0 12 for _ in pairs(tbl) do 13 count = count + 1 14 end 15 return count 16 end 17 18 local function pos_leq(a, b) 19 return a[1] < b[1] or (a[1] == b[1] and a[2] <= b[2]) 20 end 21 22 -- Checks that shadow and tree is consistent, and optionally 23 -- return the order 24 local function shadoworder(tree, shadow, iter, giveorder) 25 ok(iter ~= nil) 26 local status = lib.marktree_itr_first(tree, iter) 27 local count = 0 28 local pos2id, id2pos = {}, {} 29 local last 30 if not status and next(shadow) == nil then 31 return pos2id, id2pos 32 end 33 repeat 34 local mark = lib.marktree_itr_current(iter) 35 local id = tonumber(mark.id) 36 local spos = shadow[id] 37 eq(mark.pos.row, spos[1], mark.id) 38 eq(mark.pos.col, spos[2], mark.id) 39 if lib.mt_right_test(mark) ~= spos[3] then 40 error('invalid gravity for ' .. id .. ':(' .. mark.pos.row .. ', ' .. mark.pos.col .. ')') 41 end 42 if count > 0 then 43 if not pos_leq(last, spos) then 44 error('DISORDER') 45 end 46 end 47 count = count + 1 48 last = spos 49 if giveorder then 50 pos2id[count] = id 51 id2pos[id] = count 52 end 53 until not lib.marktree_itr_next(tree, iter) 54 local shadowlen = tablelength(shadow) 55 if shadowlen ~= count then 56 error('missed some keys? (shadow ' .. shadowlen .. ', tree ' .. count .. ')') 57 end 58 return id2pos, pos2id 59 end 60 61 local function shadowsplice(shadow, start, old_extent, new_extent) 62 local old_end = { 63 start[1] + old_extent[1], 64 (old_extent[1] == 0 and start[2] or 0) + old_extent[2], 65 } 66 local new_end = { 67 start[1] + new_extent[1], 68 (new_extent[1] == 0 and start[2] or 0) + new_extent[2], 69 } 70 local delta = { new_end[1] - old_end[1], new_end[2] - old_end[2] } 71 for _, pos in pairs(shadow) do 72 if pos_leq(start, pos) then 73 if pos_leq(pos, old_end) then 74 -- delete region 75 if pos[3] then -- right gravity 76 pos[1], pos[2] = new_end[1], new_end[2] 77 else 78 pos[1], pos[2] = start[1], start[2] 79 end 80 else 81 if pos[1] == old_end[1] then 82 pos[2] = pos[2] + delta[2] 83 end 84 pos[1] = pos[1] + delta[1] 85 end 86 end 87 end 88 end 89 90 local function dosplice(tree, shadow, start, old, new) 91 lib.marktree_splice(tree, start[1], start[2], old[1], old[2], new[1], new[2]) 92 shadowsplice(shadow, start, old, new) 93 end 94 95 local ns = 10 96 local last_id = nil 97 98 local function put(tree, row, col, gravity, end_row, end_col, end_gravity) 99 last_id = last_id + 1 100 local my_id = last_id 101 102 end_row = end_row or -1 103 end_col = end_col or -1 104 end_gravity = end_gravity or false 105 106 lib.marktree_put_test(tree, ns, my_id, row, col, gravity, end_row, end_col, end_gravity, false) 107 return my_id 108 end 109 110 local function put_meta(tree, row, col, gravitate, meta) 111 last_id = last_id + 1 112 local my_id = last_id 113 114 lib.marktree_put_test(tree, ns, my_id, row, col, gravitate, -1, -1, false, meta) 115 return my_id 116 end 117 118 describe('marktree', function() 119 before_each(function() 120 last_id = 0 121 end) 122 123 itp('works', function() 124 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 125 local shadow = {} 126 local iter = ffi.new('MarkTreeIter[1]') 127 local iter2 = ffi.new('MarkTreeIter[1]') 128 129 for i = 1, 100 do 130 for j = 1, 100 do 131 local gravitate = (i % 2) > 0 132 local id = put(tree, j, i, gravitate) 133 ok(id > 0) 134 eq(nil, shadow[id]) 135 shadow[id] = { j, i, gravitate } 136 end 137 -- checking every insert is too slow, but this is ok 138 lib.marktree_check(tree) 139 end 140 141 -- ss = lib.mt_inspect_rec(tree) 142 -- io.stdout:write(ffi.string(ss)) 143 -- io.stdout:flush() 144 145 local id2pos, pos2id = shadoworder(tree, shadow, iter) 146 eq({}, pos2id) -- not set if not requested 147 eq({}, id2pos) 148 149 for i, ipos in pairs(shadow) do 150 local p = lib.marktree_lookup_ns(tree, ns, i, false, iter) 151 eq(ipos[1], p.pos.row) 152 eq(ipos[2], p.pos.col) 153 local k = lib.marktree_itr_current(iter) 154 eq(ipos[1], k.pos.row) 155 eq(ipos[2], k.pos.col, ipos[1]) 156 lib.marktree_itr_next(tree, iter) 157 -- TODO(bfredl): use id2pos to check neighbour? 158 -- local k2 = lib.marktree_itr_current(iter) 159 end 160 161 for i, ipos in pairs(shadow) do 162 lib.marktree_itr_get(tree, ipos[1], ipos[2], iter) 163 local k = lib.marktree_itr_current(iter) 164 eq(i, tonumber(k.id)) 165 eq(ipos[1], k.pos.row) 166 eq(ipos[2], k.pos.col) 167 end 168 169 ok(lib.marktree_itr_first(tree, iter)) 170 local del = lib.marktree_itr_current(iter) 171 172 lib.marktree_del_itr(tree, iter, false) 173 shadow[tonumber(del.id)] = nil 174 shadoworder(tree, shadow, iter) 175 176 for _, ci in ipairs({ 0, -1, 1, -2, 2, -10, 10 }) do 177 for i = 1, 100 do 178 lib.marktree_itr_get(tree, i, 50 + ci, iter) 179 local k = lib.marktree_itr_current(iter) 180 local id = tonumber(k.id) 181 eq(shadow[id][1], k.pos.row) 182 eq(shadow[id][2], k.pos.col) 183 lib.marktree_del_itr(tree, iter, false) 184 shadow[id] = nil 185 end 186 lib.marktree_check(tree) 187 shadoworder(tree, shadow, iter) 188 end 189 190 -- NB: this is quite rudimentary. We rely on 191 -- functional tests exercising splicing quite a bit 192 lib.marktree_check(tree) 193 dosplice(tree, shadow, { 2, 2 }, { 0, 5 }, { 1, 2 }) 194 lib.marktree_check(tree) 195 shadoworder(tree, shadow, iter) 196 dosplice(tree, shadow, { 30, 2 }, { 30, 5 }, { 1, 2 }) 197 lib.marktree_check(tree) 198 shadoworder(tree, shadow, iter) 199 200 dosplice(tree, shadow, { 5, 3 }, { 0, 2 }, { 0, 5 }) 201 shadoworder(tree, shadow, iter) 202 lib.marktree_check(tree) 203 204 -- build then burn (HOORAY! HOORAY!) 205 while next(shadow) do 206 lib.marktree_itr_first(tree, iter) 207 -- delete every other key for fun and profit 208 while true do 209 local k = lib.marktree_itr_current(iter) 210 lib.marktree_del_itr(tree, iter, false) 211 ok(shadow[tonumber(k.id)] ~= nil) 212 shadow[tonumber(k.id)] = nil 213 local stat = lib.marktree_itr_next(tree, iter) 214 if not stat then 215 break 216 end 217 end 218 lib.marktree_check(tree) 219 shadoworder(tree, shadow, iter2) 220 end 221 222 -- Check iterator validity for 2 specific edge cases: 223 -- https://github.com/neovim/neovim/pull/14719 224 lib.marktree_clear(tree) 225 for i = 1, 20 do 226 put(tree, i, i, false) 227 end 228 229 lib.marktree_itr_get(tree, 10, 10, iter) 230 lib.marktree_del_itr(tree, iter, false) 231 eq(11, iter[0].x.key[iter[0].i].pos.col) 232 233 lib.marktree_itr_get(tree, 11, 11, iter) 234 lib.marktree_del_itr(tree, iter, false) 235 eq(12, iter[0].x.key[iter[0].i].pos.col) 236 end) 237 238 itp("'intersect_mov' function works correctly", function() 239 local function mov(x, y, w) 240 local xa = ffi.new('uint64_t[?]', #x) 241 for i, xi in ipairs(x) do 242 xa[i - 1] = xi 243 end 244 local ya = ffi.new('uint64_t[?]', #y) 245 for i, yi in ipairs(y) do 246 ya[i - 1] = yi 247 end 248 local wa = ffi.new('uint64_t[?]', #w) 249 for i, wi in ipairs(w) do 250 wa[i - 1] = wi 251 end 252 253 local dummy_size = #x + #y + #w 254 local wouta = ffi.new('uint64_t[?]', dummy_size) 255 local douta = ffi.new('uint64_t[?]', dummy_size) 256 local wsize = ffi.new('size_t[1]') 257 wsize[0] = dummy_size 258 local dsize = ffi.new('size_t[1]') 259 dsize[0] = dummy_size 260 261 local status = lib.intersect_mov_test(xa, #x, ya, #y, wa, #w, wouta, wsize, douta, dsize) 262 if status == 0 then 263 error 'wowza' 264 end 265 266 local wout, dout = {}, {} 267 for i = 0, tonumber(wsize[0]) - 1 do 268 table.insert(wout, tonumber(wouta[i])) 269 end 270 for i = 0, tonumber(dsize[0]) - 1 do 271 table.insert(dout, tonumber(douta[i])) 272 end 273 return { wout, dout } 274 end 275 276 eq({ {}, {} }, mov({}, { 2, 3 }, { 2, 3 })) 277 eq({ { 2, 3 }, {} }, mov({}, {}, { 2, 3 })) 278 eq({ { 2, 3 }, {} }, mov({ 2, 3 }, {}, {})) 279 eq({ {}, { 2, 3 } }, mov({}, { 2, 3 }, {})) 280 281 eq({ { 1, 5 }, {} }, mov({ 1, 2, 5 }, { 2, 3 }, { 3 })) 282 eq({ { 1, 2 }, {} }, mov({ 1, 2, 5 }, { 5, 10 }, { 10 })) 283 eq({ { 1, 2 }, { 5 } }, mov({ 1, 2 }, { 5, 10 }, { 10 })) 284 eq({ { 1, 3, 5, 7, 9 }, { 2, 4, 6, 8, 10 } }, mov({ 1, 3, 5, 7, 9 }, { 2, 4, 6, 8, 10 }, {})) 285 eq({ { 1, 3, 5, 7, 9 }, { 2, 6, 10 } }, mov({ 1, 3, 5, 7, 9 }, { 2, 4, 6, 8, 10 }, { 4, 8 })) 286 eq({ { 1, 4, 7 }, { 2, 5, 8 } }, mov({ 1, 3, 4, 6, 7, 9 }, { 2, 3, 5, 6, 8, 9 }, {})) 287 eq({ { 1, 4, 7 }, {} }, mov({ 1, 3, 4, 6, 7, 9 }, { 2, 3, 5, 6, 8, 9 }, { 2, 5, 8 })) 288 eq( 289 { { 0, 1, 4, 7, 10 }, {} }, 290 mov({ 1, 3, 4, 6, 7, 9 }, { 2, 3, 5, 6, 8, 9 }, { 0, 2, 5, 8, 10 }) 291 ) 292 end) 293 294 local function check_intersections(tree) 295 lib.marktree_check(tree) 296 -- to debug stuff disable this branch 297 if true == true then 298 ok(lib.marktree_check_intersections(tree)) 299 return 300 end 301 302 local str1 = lib.mt_inspect(tree, true, true) 303 local dot1 = ffi.string(str1.data, str1.size) 304 305 local val = lib.marktree_check_intersections(tree) 306 if not val then 307 local str2 = lib.mt_inspect(tree, true, true) 308 local dot2 = ffi.string(str2.data, str2.size) 309 print('actual:\n\n' .. 'Xafile.dot' .. '\n\nexpected:\n\n' .. 'Xefile.dot' .. '\n') 310 print('nivå', tree[0].root.level) 311 io.stdout:flush() 312 local afil = io.open('Xafile.dot', 'wb') 313 afil:write(dot1) 314 afil:close() 315 local efil = io.open('Xefile.dot', 'wb') 316 efil:write(dot2) 317 efil:close() 318 ok(false) 319 else 320 ffi.C.xfree(str1.data) 321 end 322 end 323 324 itp('works with intersections', function() 325 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 326 327 local ids = {} 328 329 for i = 1, 80 do 330 table.insert(ids, put(tree, 1, i, false, 2, 100 - i, false)) 331 check_intersections(tree) 332 end 333 for i = 1, 80 do 334 lib.marktree_del_pair_test(tree, ns, ids[i]) 335 check_intersections(tree) 336 end 337 ids = {} 338 339 for i = 1, 80 do 340 table.insert(ids, put(tree, 1, i, false, 2, 100 - i, false)) 341 check_intersections(tree) 342 end 343 344 for i = 1, 10 do 345 for j = 1, 8 do 346 local ival = (j - 1) * 10 + i 347 lib.marktree_del_pair_test(tree, ns, ids[ival]) 348 check_intersections(tree) 349 end 350 end 351 end) 352 353 itp('works with intersections with a big tree', function() 354 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 355 356 local ids = {} 357 358 for i = 1, 1000 do 359 table.insert(ids, put(tree, 1, i, false, 2, 1000 - i, false)) 360 if i % 10 == 1 then 361 check_intersections(tree) 362 end 363 end 364 365 check_intersections(tree) 366 eq(2000, tree[0].n_keys) 367 ok(tree[0].root.level >= 2) 368 369 local iter = ffi.new('MarkTreeIter[1]') 370 371 local k = 0 372 for i = 1, 20 do 373 for j = 1, 50 do 374 k = k + 1 375 local ival = (j - 1) * 20 + i 376 if false == true then -- if there actually is a failure, this branch will fail out at the actual spot of the error 377 lib.marktree_lookup_ns(tree, ns, ids[ival], false, iter) 378 lib.marktree_del_itr(tree, iter, false) 379 check_intersections(tree) 380 381 lib.marktree_lookup_ns(tree, ns, ids[ival], true, iter) 382 lib.marktree_del_itr(tree, iter, false) 383 check_intersections(tree) 384 else 385 lib.marktree_del_pair_test(tree, ns, ids[ival]) 386 if k % 5 == 1 then 387 check_intersections(tree) 388 end 389 end 390 end 391 end 392 393 eq(0, tree[0].n_keys) 394 end) 395 396 itp('works with intersections and marktree_splice', function() 397 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 398 399 for i = 1, 1000 do 400 put(tree, 1, i, false, 2, 1000 - i, false) 401 if i % 10 == 1 then 402 check_intersections(tree) 403 end 404 end 405 406 check_intersections(tree) 407 eq(2000, tree[0].n_keys) 408 ok(tree[0].root.level >= 2) 409 410 for _ = 1, 10 do 411 lib.marktree_splice(tree, 0, 0, 0, 100, 0, 0) 412 check_intersections(tree) 413 end 414 end) 415 416 itp('marktree_move should preserve key order', function() 417 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 418 local iter = ffi.new('MarkTreeIter[1]') 419 local ids = {} 420 421 -- new index and old index look the same, but still have to move because 422 -- pos will get updated 423 table.insert(ids, put(tree, 1, 1, false, 1, 3, false)) 424 table.insert(ids, put(tree, 1, 3, false, 1, 3, false)) 425 table.insert(ids, put(tree, 1, 3, false, 1, 3, false)) 426 table.insert(ids, put(tree, 1, 3, false, 1, 3, false)) 427 428 lib.marktree_lookup_ns(tree, ns, ids[3], false, iter) 429 lib.marktree_move(tree, iter, 1, 2) 430 431 check_intersections(tree) 432 end) 433 434 itp('works with intersections and marktree_move', function() 435 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 436 437 local ids = {} 438 439 for i = 1, 1000 do 440 table.insert(ids, put(tree, 1, i, false, 2, 1000 - i, false)) 441 if i % 10 == 1 then 442 check_intersections(tree) 443 end 444 end 445 446 local iter = ffi.new('MarkTreeIter[1]') 447 for i = 1, 1000 do 448 local which = i % 2 449 lib.marktree_lookup_ns(tree, ns, ids[i], which, iter) 450 lib.marktree_move(tree, iter, 1 + which, 500 + i) 451 if i % 10 == 1 then 452 check_intersections(tree) 453 end 454 end 455 end) 456 457 itp('works with intersections with a even bigger tree', function() 458 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 459 460 local ids = {} 461 462 -- too much overhead on ASAN 463 local size_factor = t.is_asan() and 3 or 10 464 465 local at_row = {} 466 for i = 1, 10 do 467 at_row[i] = {} 468 end 469 470 local size = 1000 * size_factor 471 local k = 1 472 while k <= size do 473 for row1 = 1, 9 do 474 for row2 = row1, 10 do -- note row2 can be == row1, leads to empty ranges being tested when k > size/2 475 if k > size then 476 break 477 end 478 local id = put(tree, row1, k, false, row2, size - k, false) 479 table.insert(ids, id) 480 for i = row1 + 1, row2 do 481 table.insert(at_row[i], id) 482 end 483 --if tree[0].root.level == 4 then error("kk"..k) end 484 if k % 100 * size_factor == 1 or (k < 2000 and k % 100 == 1) then 485 check_intersections(tree) 486 end 487 k = k + 1 488 end 489 end 490 end 491 492 eq(2 * size, tree[0].n_keys) 493 ok(tree[0].root.level >= 3) 494 check_intersections(tree) 495 496 local iter = ffi.new('MarkTreeIter[1]') 497 local pair = ffi.new('MTPair[1]') 498 for i = 1, 10 do 499 -- use array as set and not {[id]=true} map, to detect duplicates 500 local set = {} 501 eq(true, ffi.C.marktree_itr_get_overlap(tree, i, 0, iter)) 502 while ffi.C.marktree_itr_step_overlap(tree, iter, pair) do 503 local id = tonumber(pair[0].start.id) 504 table.insert(set, id) 505 end 506 table.sort(set) 507 eq(at_row[i], set) 508 end 509 510 k = 0 511 for i = 1, 100 do 512 for j = 1, (10 * size_factor) do 513 k = k + 1 514 local ival = (j - 1) * 100 + i 515 lib.marktree_del_pair_test(tree, ns, ids[ival]) 516 -- just a few stickprov, if there is trouble we need to check 517 -- everyone using the code in the "big tree" case above 518 if k % 100 * size_factor == 0 or (k > 3000 and k % 200 == 0) then 519 check_intersections(tree) 520 end 521 end 522 end 523 524 eq(0, tree[0].n_keys) 525 end) 526 527 itp('works with intersections with a even bigger tree and splice', function() 528 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 529 530 -- too much overhead on ASAN 531 local size_factor = t.is_asan() and 3 or 10 532 533 local at_row = {} 534 for i = 1, 10 do 535 at_row[i] = {} 536 end 537 538 local size = 1000 * size_factor 539 local k = 1 540 while k <= size do 541 for row1 = 1, 9 do 542 for row2 = row1, 10 do -- note row2 can be == row1, leads to empty ranges being tested when k > size/2 543 if k > size then 544 break 545 end 546 local id = put(tree, row1, k, false, row2, size - k, false) 547 for i = row1 + 1, row2 do 548 table.insert(at_row[i], id) 549 end 550 --if tree[0].root.level == 4 then error("kk"..k) end 551 if k % 100 * size_factor == 1 or (k < 2000 and k % 100 == 1) then 552 check_intersections(tree) 553 end 554 k = k + 1 555 end 556 end 557 end 558 559 eq(2 * size, tree[0].n_keys) 560 ok(tree[0].root.level >= 3) 561 check_intersections(tree) 562 563 for _ = 1, 10 do 564 for j = 3, 8 do 565 lib.marktree_splice(tree, j, 0, 0, 200, 0, 0) 566 check_intersections(tree) 567 end 568 end 569 end) 570 571 itp('works with meta counts', function() 572 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 573 574 -- add 575 local shadow = {} 576 for i = 1, 100 do 577 for j = 1, 100 do 578 local gravitate = (i % 2) > 0 579 local inline = (j == 3 or j == 50 or j == 51 or j == 55) and i % 11 == 1 580 inline = inline or ((j >= 80 and j < 85) and i % 3 == 1) 581 local id = put_meta(tree, j, i, gravitate, inline) 582 if inline then 583 shadow[id] = { j, i, gravitate } 584 end 585 end 586 -- checking every insert is too slow, but this is ok 587 lib.marktree_check(tree) 588 end 589 590 lib.marktree_check(tree) 591 local iter = ffi.new('MarkTreeIter[1]') 592 local filter = ffi.new('uint32_t[4]') 593 filter[0] = -1ULL 594 ok(lib.marktree_itr_get_filter(tree, 0, 0, 101, 0, filter, iter)) 595 local seen = {} 596 repeat 597 local mark = lib.marktree_itr_current(iter) 598 eq(nil, seen[mark.id]) 599 seen[mark.id] = true 600 eq(mark.pos.row, shadow[mark.id][1]) 601 eq(mark.pos.col, shadow[mark.id][2]) 602 until not lib.marktree_itr_next_filter(tree, iter, 101, 0, filter) 603 eq(tablelength(seen), tablelength(shadow)) 604 605 -- test skipping subtrees to find the filtered mark at line 50 606 for i = 4, 50 do 607 ok(lib.marktree_itr_get_filter(tree, i, 0, 60, 0, filter, iter)) 608 local mark = lib.marktree_itr_current(iter) 609 eq({ 50, 50, 1 }, { mark.id, mark.pos.row, mark.pos.col }) 610 end 611 612 -- delete 613 for id = 1, 10000, 2 do 614 lib.marktree_lookup_ns(tree, ns, id, false, iter) 615 if shadow[id] then 616 local mark = lib.marktree_itr_current(iter) 617 eq(mark.pos.row, shadow[id][1]) 618 eq(mark.pos.col, shadow[id][2]) 619 shadow[id] = nil 620 end 621 lib.marktree_del_itr(tree, iter, false) 622 if id % 100 == 1 then 623 lib.marktree_check(tree) 624 end 625 end 626 627 -- Splice! 628 dosplice(tree, shadow, { 82, 0 }, { 0, 50 }, { 0, 0 }) 629 lib.marktree_check(tree) 630 631 dosplice(tree, shadow, { 81, 50 }, { 2, 50 }, { 1, 0 }) 632 lib.marktree_check(tree) 633 634 dosplice(tree, shadow, { 2, 50 }, { 1, 50 }, { 0, 10 }) 635 lib.marktree_check(tree) 636 637 ok(lib.marktree_itr_get_filter(tree, 0, 0, 101, 0, filter, iter)) 638 seen = {} 639 repeat 640 local mark = lib.marktree_itr_current(iter) 641 eq(nil, seen[mark.id]) 642 seen[mark.id] = true 643 eq(mark.pos.row, shadow[mark.id][1]) 644 eq(mark.pos.col, shadow[mark.id][2]) 645 until not lib.marktree_itr_next_filter(tree, iter, 101, 0, filter) 646 eq(tablelength(seen), tablelength(shadow)) 647 end) 648 649 itp('works with edge case splicing overlapping ranges #37867', function() 650 local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit 651 put(tree, 190, 48, false) 652 put(tree, 48, 48, true) 653 put(tree, 190, 48, false) 654 put(tree, 166, 48, false, 166, 48, false) 655 put(tree, 48, 48, true, 48, 48, false) 656 put(tree, 48, 48, true, 48, 48, false) 657 put(tree, 48, 48, true, 255, 48, false) 658 put(tree, 131, 48, false, 48, 48, false) 659 put(tree, 131, 48, false, 48, 48, false) 660 put(tree, 48, 48, true, 131, 48, false) 661 put(tree, 48, 48, false, 216, 48, false) 662 put(tree, 172, 48, false, 51, 48, false) 663 put(tree, 131, 48, false, 131, 48, false) 664 put(tree, 156, 48, false, 131, 48, false) 665 put(tree, 135, 48, false, 166, 48, false) 666 put(tree, 172, 48, false, 250, 48, false) 667 put(tree, 48, 48, false, 143, 48, false) 668 ok(lib.marktree_check_intersections(tree)) 669 lib.marktree_splice(tree, 48, 0, 139, 0, 0, 0) 670 ok(lib.marktree_check_intersections(tree)) 671 end) 672 end)