* vm_map_splay: * * The Sleator and Tarjan top-down splay algorithm with the * following variation. Max_free must be computed bottom-up, so * on the downward pass, maintain the left and right spines in * reverse order. Then, make a second pass up each side to fix * the pointers and compute max_free. The time bound is O(log n) * amortized. * * The tree is threaded, which means that ther
| 1367 | * Returns: the new root. |
| 1368 | */ |
| 1369 | static vm_map_entry_t |
| 1370 | vm_map_splay(vm_map_t map, vm_offset_t addr) |
| 1371 | { |
| 1372 | vm_map_entry_t header, llist, rlist, root; |
| 1373 | vm_size_t max_free_left, max_free_right; |
| 1374 | |
| 1375 | header = &map->header; |
| 1376 | root = vm_map_splay_split(map, addr, 0, &llist, &rlist); |
| 1377 | if (root != NULL) { |
| 1378 | max_free_left = vm_map_splay_merge_left(header, root, llist); |
| 1379 | max_free_right = vm_map_splay_merge_right(header, root, rlist); |
| 1380 | } else if (llist != header) { |
| 1381 | /* |
| 1382 | * Recover the greatest node in the left |
| 1383 | * subtree and make it the root. |
| 1384 | */ |
| 1385 | root = llist; |
| 1386 | llist = root->right; |
| 1387 | max_free_left = vm_map_splay_merge_left(header, root, llist); |
| 1388 | max_free_right = vm_map_splay_merge_succ(header, root, rlist); |
| 1389 | } else if (rlist != header) { |
| 1390 | /* |
| 1391 | * Recover the least node in the right |
| 1392 | * subtree and make it the root. |
| 1393 | */ |
| 1394 | root = rlist; |
| 1395 | rlist = root->left; |
| 1396 | max_free_left = vm_map_splay_merge_pred(header, root, llist); |
| 1397 | max_free_right = vm_map_splay_merge_right(header, root, rlist); |
| 1398 | } else { |
| 1399 | /* There is no root. */ |
| 1400 | return (NULL); |
| 1401 | } |
| 1402 | root->max_free = vm_size_max(max_free_left, max_free_right); |
| 1403 | map->root = root; |
| 1404 | VM_MAP_ASSERT_CONSISTENT(map); |
| 1405 | return (root); |
| 1406 | } |
| 1407 | |
| 1408 | /* |
| 1409 | * vm_map_entry_{un,}link: |
no test coverage detected