indexed-bitmap

A (perhaps) obvious indexed bitmap in Rust.

Overview

This bitmap is indexed for accelerating the operations related to pinpointing zeroes and ones.

The indexed bitmap works in the following way:

• On the bottom, it is the bitmap layer, which stores the zeroes and ones and fulfils the responsibility of an ordinary bitmap. Physically, the bitmap is implemented by a Vec<u128>, where every cell of u128 is called a page.
• On the top of it, we recursively build multiple layers of indexes. Again, every index is also implemented by Vec<u128>, where every cell of u128 is also called a page. The responsibility of every index is to summarize the status of pages from the bitmap or the previous index layer.
• Every page status is summarized into 2 bits: the lower bit indicates the summarized page contains one, and the higher bit indicates the summarized page is all one. Therefore, every page in the index layer summarizes 64 pages from its lower layer. It won't be hard to see: A page of all ones will be summarized into 0b11, a page of mixture of zeroes and ones will be summarized into 0b01, and a page of all zeroes will be summarized into 0b00.
• For an index page, if the 64 lower pages it governs are all ones; it will also be all ones; if the lower pages it governs are all zeroes, it will also be all zeroes; and if any lower page is the mixture of zeroes and ones, it will also contain a 0b01 field corresponding to that page, and thus a mixture of zeroes and ones. In this way, we are able to use the index layers as a "telescope".

To see how such an indexing will help, consider the case of finding the first zero:

• Without index, one will have to scan the bitmap until the first non all-one page. This should be done within linear complexity $O(N)$.
• With index, from the topmost layer, we can quickly locate the first page containing a zero bit in the adjacent lower level, telescoping into it recursively, until we locate the first page in the bitmap layer that contains a zero. This should be done within logarithmic complexity $O(\log_{64} N)$.

Core APIs

The core APIs of the indexed-bitmap are:

• The indexed bitmap can be viewed as a map from any usize to zero initially. That is, for any bit untouched by any operation, it is initially zero.
• bitget, bitset: Ordinary bitmap operations.
• lowest_zero, lowest_one: Locate the first zero or one bit.
• highest_one, size: The highest_one locates the last one bit. The size locates the first zero bit after the last one bit. (The highest_zero does not make sense, due to our way of conceptually defining the indexed bitmap, it will be usize::MAX if usize::MAX-th bit is not set or not exist if usize::MAX-th bit is set. If you want one, you gotta see if size fulfils your need.)
• this_one_or_next_one, next_one: Locate the next one bit after the specified bit.
• shrink_to, shrink_to_fit: Shrink the underlying containers of the bitmap.

What will never be implemented?

1. count_ones / count_zeroes: Although we can skip many pages utilizing the index, the worst case degrades to linearly scanning the bitmap, that is, $O(N)$. However, this can be implemented in $O(1)$ by simply maintaining a counter. Maintaining such a counter will add to the size and book-keeping works, and those who don't need this functionality will really grudge.
2. highest_zero: Do you mean size?

License

This project is licensed under the MIT license.