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