Change PTreeImpl::insert to an iterative implementation

[atn34]

The previous implementation copied a reference for every node along the search path, for O(log n) expected refcounting. The new implementation does not copy any references on the way down the search path, and only copies references as necessary on the way back up, for O(1) expected refcounting.

We can still apply the same optimization for point clears. A simple way to do that would be to perform a search and then erase the finger.

Code-Reviewer Section

The general pull request guidelines can be found here.

Please check each of the following things and check all boxes before accepting a PR.

• [ ] The PR has a description, explaining both the problem and the solution.
• [ ] The description mentions which forms of testing were done and the testing seems reasonable.
• [ ] Every function/class/actor that was touched is reasonably well documented.

For Release-Branches

If this PR is made against a release-branch, please also check the following:

• [ ] This change/bugfix is a cherry-pick from the next younger branch (younger release-branch or main if this is the youngest branch)
• [ ] There is a good reason why this PR needs to go into a release branch and this reason is documented (either in the description above or in a linked GitHub issue)

[foundationdb-ci]

Result of foundationdb-pr-clang-ide on Linux CentOS 7

• Commit ID: 3a33327a945d4969edc99fed93a784377d7dbb2c
• Duration 0:20:48
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-macos-m1 on macOS Ventura 13.x

• Commit ID: 3a33327a945d4969edc99fed93a784377d7dbb2c
• Duration 0:29:34
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-macos on macOS Ventura 13.x

• Commit ID: 3a33327a945d4969edc99fed93a784377d7dbb2c
• Duration 0:44:11
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr on Linux CentOS 7

• Commit ID: 3a33327a945d4969edc99fed93a784377d7dbb2c
• Duration 1:16:12
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-clang on Linux CentOS 7

• Commit ID: 3a33327a945d4969edc99fed93a784377d7dbb2c
• Duration 1:21:13
• Result: :x: FAILED
• Error: Error while executing command: if python3 -m joshua.joshua list --stopped | grep ${ENSEMBLE_ID} | grep -q 'pass=10[0-9][0-9][0-9]'; then echo PASS; else echo FAIL && exit 1; fi. Reason: exit status 1
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-cluster-tests on Linux CentOS 7

• Commit ID: 3a33327a945d4969edc99fed93a784377d7dbb2c
• Duration 1:35:09
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)
• Cluster Test Logs zip file of the test logs (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-clang-ide on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:30:24
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-clang on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:33:11
• Result: :x: FAILED
• Error: Error while executing command: if python3 -m joshua.joshua list --stopped | grep ${ENSEMBLE_ID} | grep -q 'pass=10[0-9][0-9][0-9]'; then echo PASS; else echo FAIL && exit 1; fi. Reason: exit status 1
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:45:02
• Result: :x: FAILED
• Error: Error while executing command: if python3 -m joshua.joshua list --stopped | grep ${ENSEMBLE_ID} | grep -q 'pass=10[0-9][0-9][0-9]'; then echo PASS; else echo FAIL && exit 1; fi. Reason: exit status 1
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-cluster-tests on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 1:26:44
• Result: :x: FAILED
• Error: Error while executing command: if $fail_test; then exit 1; fi. Reason: exit status 1
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)
• Cluster Test Logs zip file of the test logs (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-clang-ide on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:12:22
• Result: :white_check_mark: SUCCEEDED
• Error: N/A
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-clang on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:16:08
• Result: :x: FAILED
• Error: Error while executing command: python3 -m joshua.joshua start --tarball $(find build_output/packages -name correctness\*.tar.gz) --username ${CORRECTNESS_USERNAME} --max-runs 10000. Reason: exit status 2
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-cluster-tests on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:17:09
• Result: :x: FAILED
• Error: Error while executing command: mvn install:install-file --batch-mode -Dorg.slf4j.simpleLogger.log.org.apache.maven.cli.transfer.Slf4jMavenTransferListener=warn -Dfile=packages/fdb-java-${FDB_VERSION}-SNAPSHOT.jar -DgroupId=org.foundationdb -DartifactId=fdb-java -Dversion=${FDB_VERSION}-SNAPSHOT -Dpackaging=jar -DgeneratePom=true. Reason: exit status 1
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)
• Cluster Test Logs zip file of the test logs (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr on Linux CentOS 7

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:18:15
• Result: :x: FAILED
• Error: Error while executing command: python3 -m joshua.joshua start --tarball $(find build_output/packages -name correctness\*.tar.gz) --username ${CORRECTNESS_USERNAME} --max-runs 10000. Reason: exit status 2
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-macos-m1 on macOS Ventura 13.x

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:31:13
• Result: :x: FAILED
• Error: no matching artifact paths found
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)

[foundationdb-ci]

Result of foundationdb-pr-macos on macOS Ventura 13.x

• Commit ID: 5faf31642ecd4ab4e428799a64de5acf7a7b04b1
• Duration 0:41:57
• Result: :x: FAILED
• Error: no matching artifact paths found
• Build Log terminal output (available for 30 days)
• Build Workspace zip file of the working directory (available for 30 days)