Bitmap.h   [plain text]


/*
 * Copyright (c) 2011 Apple Inc. All rights reserved.
 *
 * @APPLE_APACHE_LICENSE_HEADER_START@
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 * 
 *     http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 * @APPLE_APACHE_LICENSE_HEADER_END@
 */
/*
    Bitmap.h
    High Performance Bitmap
    Copyright (c) 2004-2011 Apple Inc. All rights reserved.
 */

#pragma once
#ifndef __AUTO_BITMAP__
#define __AUTO_BITMAP__

#include "Definitions.h"
#include "Range.h"


namespace Auto {

    //----- Bitmap -----//

    //
    // Bitmaps (bit vectors) are a fast and lightweight means of showing set
    // representation.  A single bit is used to indicate membership in the set; 1
    // indicating membership and 0 indicating exclusion.  In this representation we use
    // an array of unsigned long words. Each word represents a unit of bits_per_word members
    // numbered from the least significant bit (endian representation is not
    // important.)  Thus for any member k its word index would be equal to (k / bits_per_word) or
    // (k >> ilog2(bits_per_word)) and its bit position would be equal to (k % bits_per_word).
    //
    
    class Bitmap : public Range {

     private:         

        //
        // index
        //
        // Returns the word index of a specified bit.
        //
        static inline const usword_t index(const usword_t bp) { return bp >> bits_per_word_log2; }
        
        
        //
        // shift
        //
        // Returns the shift of a specified bit.
        //
        static inline const usword_t shift(const usword_t bp) { return bp & bits_mask; }
        
        
        //
        // cursor_bp
        //
        // Returns the bit position of the specified cursor.
        //
        inline usword_t cursor_bp(const usword_t *cursor) const { return ((uintptr_t)cursor - (uintptr_t)address()) << bits_per_byte_log2; }
        
        
        //
        // end_cursor
        //
        // Returns the end of the bits as a word address.
        //
        inline usword_t *end_cursor() const { return (usword_t *)Range::end(); }
        
        
     public:
     
        //
        // Constructors
        //
        Bitmap() {}
        Bitmap(usword_t n, void *bits) {
            // keep aligned for vector operations
            ASSERTION(!((uintptr_t)bits & mask(bytes_per_quad_log2)) && !(bytes_needed(n) & mask(bytes_per_quad_log2)));
            set_range(bits, bytes_needed(n));
        }
        
        
        //
        // bp_cursor
        //
        // Returns the word address containing a specified bit.
        //
        inline usword_t *bp_cursor(const usword_t bp) const {
            return (usword_t *)displace(address(), (bp >> (bits_per_word_log2 - bytes_per_word_log2)) & ~mask(bytes_per_word_log2));
        }
        
        
        //
        // size_in_bits
        //
        // Return the number of bits in the bitmap.
        //
        inline usword_t size_in_bits() const { return size() << bits_per_byte_log2; }
        
        
        //
        // initialize
        //
        // Set up the bit map for use.
        //
        inline void initialize(usword_t n, void *bits) { set_range(bits, bytes_needed(n)); }
        

        //
        // bytes_needed
        //
        // Returns the number of bytes needed to represent 'n' bits.
        //
        static inline const usword_t bytes_needed(usword_t n) { return partition2(n, bits_per_word_log2) << bytes_per_word_log2; }
        
        
        //
        // bit
        //
        // Returns the state of a bit in the bit map.
        //
        inline usword_t bit(const usword_t bp) const { return (*bp_cursor(bp) >> shift(bp)) & 1L; }

        
        //
        // set_bit
        //
        // Set a bit in the bit map to 1.
        //
        inline void set_bit(const usword_t bp) const {
            usword_t *cursor = bp_cursor(bp);
            *cursor |= (1L << shift(bp));
        }

        
        //
        // set_bits_large
        //
        // Set n bits in the bit map to 1 spanning more than one word.
        // Assumes that range spans more than one word.
        //
        void set_bits_large(const usword_t bp, const usword_t n) const;
        

        //
        // set_bits
        //
        // Set bits in the bit map to 1.
        //
        inline void set_bits(const usword_t bp, const usword_t n) const {
            const usword_t sh = shift(bp);                  // bit shift
            
            if ((sh + n) > bits_per_word) {
                set_bits_large(bp, n);
            } else {
                usword_t m = mask(n);                       // mask of n bits
                *bp_cursor(bp) |= (m << sh);                // set bits to 1
            }
        }

        //
        // clear_bit
        //
        // Set a bit in the bit map to 0.
        //
        inline void clear_bit(const usword_t bp) const {
            usword_t *cursor = bp_cursor(bp);
            *cursor &= ~(1L << shift(bp));
        }
        
        
        //
        // clear_bits_large
        //
        // Set n bits in the bit map to 0 spanning more than one word.
        // Assumes that range spans more than one word.
        //
        void clear_bits_large(const usword_t bp, const usword_t n) const; 
               
        //
        // clear_bits
        //
        // Set n bits in the bit map to 0.
        //
        inline void clear_bits(const usword_t bp, const usword_t n) const {
            const usword_t sh = shift(bp);                  // bit shift
            
            if ((sh + n) > bits_per_word) {
                clear_bits_large(bp, n);
            } else {
                usword_t m = mask(n);                       // mask of n bits
                *bp_cursor(bp) &= ~(m << sh);               // set bits to 0
            }
        }
        
        //
        // bits_are_clear_large
        //
        // Checks to see if a range of bits, spanning more than one word, are all 0.
        //
        bool bits_are_clear_large(const usword_t bp, const usword_t n) const;
        
        
        //
        // bits_are_clear
        //
        inline bool bits_are_clear(const usword_t bp, const usword_t n) const {
            const usword_t sh = shift(bp);                  // bit shift

            if ((sh + n) > bits_per_word) {
                return bits_are_clear_large(bp, n);
            } else {
                usword_t m = mask(n);                       // mask of n bits
                return (*bp_cursor(bp) & (m << sh)) == 0;   // see if bits are 0
            }
        }
        

        //
        // skip_all_zeros
        //
        // Rapidly skips through words of all zeros.
        //
        static inline usword_t *skip_all_zeros(usword_t *cursor, usword_t *end) {
            // near end address (allows multiple reads)
            usword_t *near_end = end - 4;
            
            // skip through as many all zeros as we can
            while (cursor < near_end) {
                // prefetch four words
                usword_t word0 = cursor[0];
                usword_t word1 = cursor[1];
                usword_t word2 = cursor[2];
                usword_t word3 = cursor[3];

                // assume they are all filled with zeros
                cursor += 4;

                // backtrack if we find out otherwise
                if (!is_all_zeros(word0)) { cursor -= 4; break; }
                if (!is_all_zeros(word1)) { cursor -= 3; break; }
                if (!is_all_zeros(word2)) { cursor -= 2; break; }
                if (!is_all_zeros(word3)) { cursor -= 1; break; }
            }
            
            // finish off the rest
            while (cursor < end) {
                usword_t word = *cursor++;
                if (!is_all_zeros(word)) { cursor--; break; }
            }

            return cursor;
        }
        
        
        //
        // skip_backward_all_zeros
        //
        // Rapidly skips through words of all zeros.
        //
        static inline usword_t *skip_backward_all_zeros(usword_t *cursor, usword_t *first) {
            // near first address (allows multiple reads)
            usword_t *near_first = first + 3;
            
            // skip through as many all zeros as we can
            while (near_first <= cursor) {
                // prefetch four words
                usword_t word0 = cursor[0];
                usword_t word1 = cursor[-1];
                usword_t word2 = cursor[-2];
                usword_t word3 = cursor[-3];

                // assume they are all filled with zeros
                cursor -= 4;

                // backtrack if we find out otherwise
                if (!is_all_zeros(word0)) { cursor += 4; break; }
                if (!is_all_zeros(word1)) { cursor += 3; break; }
                if (!is_all_zeros(word2)) { cursor += 2; break; }
                if (!is_all_zeros(word3)) { cursor += 1; break; }
            }
            
            // finish off the rest
            while (first <= cursor) {
                usword_t word = *cursor--;
                if (!is_all_zeros(word)) { cursor++; break; }
            }

            return cursor;
        }
 
 
        //
        // count_set
        // 
        // Returns the number of bits set (one) in the bit map using
        // a standard bit population algoirithm.
        //
        usword_t count_set() const ;


        //
        // previous_set
        //
        // Return the bit postion of the 1 that comes at or prior to the bit position 'bp'.
        //
        usword_t previous_set(const usword_t bp) const ;
        
        
        //
        // next_set
        //
        // Return the bit postion of the 1 that comes at or after to the bit position 'bp'.
        //
        usword_t next_set(const usword_t bp) const;
        
       
        // ***** Atomic bitmap operations

        //
        // atomic_compare_and_swap_word
        //
        // This is the basis for all the Bitmap atomic operations
        //
        static inline bool atomic_compare_and_swap_word(usword_t old_value, usword_t new_value, volatile usword_t *addr) {
            ASSERTION(((uintptr_t)addr & mask(bytes_per_word_log2)) == 0);
            return auto_atomic_compare_and_swap(old_value, new_value, addr);
        }
        
        //
        // atomic_and_return_orig
        //
        // Perform an atomic and operation and return the original value
        //
        static usword_t atomic_and_return_orig(usword_t mask, volatile usword_t *addr) {
            usword_t old_value;
            do {
                old_value = *addr;
            } while (!atomic_compare_and_swap_word(old_value, old_value & mask, addr));
            return old_value;
        }
        
        //
        // atomic_or_return_orig
        //
        // Perform an atomic or operation and return the original value
        //
        static usword_t atomic_or_return_orig(usword_t mask, volatile usword_t *addr) {
            usword_t old_value;
            do {
                old_value = *addr;
            } while (!atomic_compare_and_swap_word(old_value, old_value | mask, addr));
            return old_value;
        }
        
        //
        // set_bit_atomic
        //
        // Set a bit in the bit map to 1 atomically.
        //
        inline void set_bit_atomic(const usword_t bp) const {
            test_set_bit_atomic(bp);
        }
        
        //
        // test_and_set_bit_atomic
        //
        // Test a bit, and set it atomically if it hasn't bee set yet. Returns old bit value.
        //
        inline bool test_set_bit_atomic(const usword_t bp) const {
            usword_t bit = 1L << shift(bp);
            volatile usword_t *cursor = bp_cursor(bp);
            usword_t old = *cursor;
            if ((old & bit)==0) {
                old = atomic_or_return_orig(bit, cursor);
            }
            return (old & bit) != 0; // return false if the bit was set by this call
        }
        
        //
        // clear_bit_atomic
        //
        // Set a bit in the bit map to 0 atomically.
        //
        inline void clear_bit_atomic(const usword_t bp) const {
            test_clear_bit_atomic(bp);
        }
        
        
        //
        // test_and_clear_bit
        //
        // Test a bit, and clear it if was set. Returns old bit value.
        //
        inline bool test_clear_bit_atomic(const usword_t bp) const {
            usword_t bit = 1L << shift(bp);
            volatile usword_t *cursor = bp_cursor(bp);
            usword_t old = *cursor;
            if ((old & bit)!=0) {
                old = atomic_and_return_orig(~bit, cursor);
            }
            return (old & bit)!=0; // return true if the bit was cleared by this call
        }
        
        
        //----- AtomicCursor -----//
        
        //
        // AtomicCursor provides a specialized way of doing test and clear searching of a range in a bitmap.
        // It returns the indices for bits which are found to be set, clearing the bits as a side effect.
        // The bitmap is accessed using atomic operations, but a word at a time. A word worth of bits is fetched
        // into a local buffer which is then accessed using nonatomic operations.
        //
        class AtomicCursor {
            Bitmap &_bitmap;        // the bitmap being examined
            usword_t _index;        // the "current bit" - the value that will be returned from next_set_bit() if the bit is set
            usword_t _offset;       // arbitrary offset that is subtracted from values returned by next_set_bit() (adjusts for subzone quanum bias
            usword_t _max_index;    // end point of the scan. the last possible return from next_set_bit() is _max_index-1
            usword_t _copied_bits;  // bits copied out of the bitmap
            usword_t _valid_bits;   // number of valid bits in _copied_bits
            
        public:
            
            //
            // Constructor
            //
            // arguments are the bitmap, starting index, and number of bits to enumerate
            AtomicCursor(Bitmap &b, usword_t start, usword_t length) : _bitmap(b), _index(start), _offset(start), _max_index(start + length) {
                // Perform the first fetch, which may not be word aligned. 
                // This lets us assume _index is word aligned when we fetch in next_set_bit().
                _copied_bits = fetch_clear_bits_atomic(_index, _max_index, _valid_bits);
            };
            
            //
            // fetch_clear_bits_atomic
            //
            // fetch and clear multiple bits at a time
            // bp is the index of the first bit to fetch, max is the first index *not* to be fetched
            // returns a word containing the fetched bits, and by reference in count the number of valid bits in the return
            // returned bits start at bit 0, and bits higher than count are zeroed
            //
            usword_t fetch_clear_bits_atomic(const usword_t bp, const usword_t max, usword_t &count);   
            
            //
            // next_set_bit
            //
            // Returns the index of a set bit from the bitmap range. If no bits are set, returns -1.
            // The returned value is the offset from the start index passed to the constructor.
            // So if 5 is passed as the start bit to the constructor and bit 8 is the first set bit in the bitmap,
            // the first callto next_set_bit() will return 3. (This is done because the cursor is used
            // to enumerate subzone quanta, which are zero based.)
            //
            usword_t next_set_bit();
        };    
    };


};


#endif // __AUTO_BITMAP__