bitMap.hpp revision 0
2362N/A * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved. 1631N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1631N/A * This code is free software; you can redistribute it and/or modify it 1631N/A * under the terms of the GNU General Public License version 2 only, as 1631N/A * published by the Free Software Foundation. 1631N/A * This code is distributed in the hope that it will be useful, but WITHOUT 1631N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1631N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1631N/A * version 2 for more details (a copy is included in the LICENSE file that 1631N/A * You should have received a copy of the GNU General Public License version 1631N/A * 2 along with this work; if not, write to the Free Software Foundation, 1631N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 2362N/A * CA 95054 USA or visit www.sun.com if you need additional information or 1631N/A// Closure for iterating over BitMaps 1631N/A // Callback when bit in map is set 1631N/A// Operations for bitmaps represented as arrays of unsigned 32- or 64-bit 1631N/A// Bit offsets are numbered from 0 to size-1 1631N/A // Puts the given value at the given offset, using resize() to size 1631N/A // the bitmap appropriately if needed using factor-of-two expansion. 1631N/A // Return the position of bit within the word that contains it (e.g., if 1631N/A // bitmap words are 32 bits, return a number 0 <= n <= 31). 1631N/A // Return a mask that will select the specified bit, when applied to the word 1631N/A // Return the index of the word containing the specified bit. 1631N/A // Return the bit number of the first bit in the specified word. 1631N/A // Return the array of bitmap words, or a specific word from it. 1631N/A // Return a pointer to the word containing the specified bit. 1631N/A // Set a word to a specified value or to all ones; clear a word. 1631N/A // Utilities for ranges of bits. Ranges are half-open [beg, end). 1631N/A // Ranges within a single word. 1631N/A // Ranges spanning entire words. 1631N/A // The index of the first full word in a range. 1631N/A // Verification, statistics. 1631N/A // Note that [0,0) and [size,size) are both valid ranges. 1631N/A // Constructs a bitmap with no map, and size 0. 1631N/A // Allocates necessary data structure in resource area 1631N/A // Allocates necessary data structure in resource area. 1631N/A // Preserves state currently in bit map by copying data. 1631N/A // Zeros any newly-addressable bits. 1631N/A // Does not perform any frees (i.e., of current _map). // Align bit index up or down to the next bitmap word boundary, or check // Set or clear the specified bit. // Atomically set or clear the specified bit. // Put the given value at the given offset. The parallel version // will CAS the value into the bitmap and is quite a bit slower. // The parallel version also returns a value indicating if the // calling thread was the one that changed the value of the bit. // Update a range of bits. Ranges are half-open [beg, end). // Update a range of bits, using a hint about the size. Currently only // inlines the predominant case of a 1-bit range. Works best when hint is a // compile-time constant. // call the version that takes an interval // Looking for 1's and 0's to the "right" // Find the next one bit in the range [beg_bit, end_bit), or return end_bit if // no one bit is found. Equivalent to get_next_one_offset(), but inline for // use in performance-critical code. // Returns true iff "this" is a superset of "bits". // Returns true iff "this and "bits" have a non-empty intersection. // Returns result of whether this map changed // Test if all bits are set or cleared // Convenience class wrapping BitMap which provides multiple bits per slot. typedef size_t idx_t;
// Type used for bit and word indices. // Construction. bits_per_slot must be greater than 0. // Allocates necessary data structure in resource area. bits_per_slot must be greater than 0. // Returns number of full slots that have been allocated