Skip to content

Proto/Skip_list: Fix non-minimal back_path bug

Edwin Ansari requested to merge nomadic-labs/tezos:edwin@skiplist-bs-optimization into master

The best_skip function didn't return a minimal path as expected because of an extra stop condition nomadic-labs/tezos@b16b56f1.
In general, best_skip will stop to search in the array of back_pointers for finding a closer ptr to the target every time that two (or more) succeeding back_pointer are equals.

Example: current pointer is cell[6] with back_pointers = [5;5;3] and the target is cell[3].
best_skip will stop searching right after the first back_pointer because back_pointers[0] = back_pointers[1] => skip = best_skip => Option.equal Compare.Int.equal (Some skip) best_skip = true. The test examples are implemented in test_skip_list_repr.ml nomadic-labs/tezos@46b102b6.

Omitting the stop condition solves the problem.

Edited by Yann Regis-Gianas

Merge request reports