gnu/gcc/6ec6de8fcda3e68526c4630ddc0fed55bbc2966a bitmap: Avoid amortised O(E) behaviour for tree first/last bit
The comments in bitmap.h say that bitmap_first_set_bit and
bitmap_last_set_bit are amortised O(logE) and worst-case O(E).
But the implementation just does a simple pointer chase,
without any splaying. This can be amortised O(E) if, for example,
code sets bits in ascending order and then repeatedly tests for
the first bit. Nothing would then move the root away from the
last element or begin to balance the tree.
gcc/
* bitmap.cc: Include pretty-print.h and splay-tree-utils.h.
(bitmap_splay_tree_accessors): New class.
(bitmap_splay_tree): New type.
(bitmap_first_set_bit_worker): Use bitmap_splay_tree::min_node
for tree views.
(bitmap_last_set_bit_worker): Use bitmap_splay_tree::max_node
for tree views.
1 file changed