bitMap.hpp revision 1472
3528N/A * Copyright (c) 1997, 2009, Oracle and/or its affiliates. All rights reserved. 2038N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 2038N/A * This code is free software; you can redistribute it and/or modify it 2038N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. 2362N/A * This code is distributed in the hope that it will be useful, but WITHOUT 2038N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 2038N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 2038N/A * version 2 for more details (a copy is included in the LICENSE file that 2038N/A * You should have received a copy of the GNU General Public License version 2038N/A * 2 along with this work; if not, write to the Free Software Foundation, 2038N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2038N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 3907N/A// Operations for bitmaps represented as arrays of unsigned integers. 3907N/A// Bit offsets are numbered from 0 to size-1. 2038N/A // Puts the given value at the given offset, using resize() to size 2431N/A // the bitmap appropriately if needed using factor-of-two expansion. 5452N/A // Return the position of bit within the word that contains it (e.g., if 2435N/A // bitmap words are 32 bits, return a number 0 <= n <= 31). 2038N/A // Return a mask that will select the specified bit, when applied to the word 2038N/A // Return the index of the word containing the specified bit. 5452N/A // Return the bit number of the first bit in the specified word. 2038N/A // Return the array of bitmap words, or a specific word from it. 2431N/A // Return a pointer to the word containing the specified bit. 2040N/A // Set a word to a specified value or to all ones; clear a word. 2040N/A // Utilities for ranges of bits. Ranges are half-open [beg, end). 2040N/A // Ranges within a single word. 2431N/A // Ranges spanning entire words. 2040N/A // The index of the first full word in a range. 4250N/A // Constructs a bitmap with no map, and size 0. 4250N/A // Constructs a bitmap with the given map and size. 4250N/A // Constructs an empty bitmap of the given size (that is, this clears the 4250N/A // new bitmap). Allocates the map array in resource area if 4250N/A // "in_resource_area" is true, else in the C heap. 4250N/A // Allocates necessary data structure, either in the resource area 4250N/A // or in the C heap, as indicated by "in_resource_area." 4250N/A // Preserves state currently in bit map by copying data. 4250N/A // Zeros any newly-addressable bits. 5452N/A // If "in_resource_area" is false, frees the current map. 4250N/A // (Note that this assumes that all calls to "resize" on the same BitMap 2038N/A // use the same value for "in_resource_area".) 2435N/A // Align bit index up or down to the next bitmap word boundary, or check 2431N/A // Set or clear the specified bit. 2038N/A // Atomically set or clear the specified bit. 2038N/A // Put the given value at the given offset. The parallel version 2038N/A // will CAS the value into the bitmap and is quite a bit slower. 2431N/A // The parallel version also returns a value indicating if the 2038N/A // calling thread was the one that changed the value of the bit. 2435N/A // Update a range of bits. Ranges are half-open [beg, end). 2038N/A // Update a range of bits, using a hint about the size. Currently only 2038N/A // inlines the predominant case of a 1-bit range. Works best when hint is a 2038N/A // It performs the union operation between subsets of equal length 2038N/A // of two bitmaps (the target bitmap of the method and the 2431N/A // from_bitmap) and stores the result to the target bitmap. The 2038N/A // from_start_index represents the first bit index of the subrange 2038N/A // of the from_bitmap. The to_start_index is the equivalent of the 2038N/A // target bitmap. Both indexes should be word-aligned, i.e. they 2038N/A // should correspond to the first bit on a bitmap word (it's up to 2038N/A // the caller to ensure this; the method does check it). The length 2038N/A // of the subset is specified with word_num and it is in number of 2038N/A // bitmap words. The caller should ensure that this is at least 2 2038N/A // (smaller ranges are not support to save extra checks). Again, 2431N/A // this is checked in the method. 2038N/A // Atomicity concerns: it is assumed that any contention on the 2038N/A // target bitmap with other threads will happen on the first and 2038N/A // last words; the ones in between will be "owned" exclusively by 2038N/A // the calling thread and, in fact, they will already be 0. So, the 2038N/A // method performs a CAS on the first word, copies the next 2038N/A // word_num-2 words, and finally performs a CAS on the last word. 2038N/A // Iteration support. Returns "true" if the iteration completed, false 2038N/A // if the iteration terminated early (because the closure "blk" returned 2038N/A // call the version that takes an interval 2038N/A // Looking for 1's and 0's at indices equal to or greater than "l_index", 2040N/A // stopping if none has been found before "r_index", and returning 2040N/A // "r_index" (which must be at most "size") in that case. 2038N/A // Like "get_next_one_offset_inline", except requires that "r_index" is 2038N/A // aligned to bitsizeof(bm_word_t). 2431N/A // Non-inline versionsof the above. 2431N/A // Returns the number of bits set in the bitmap. 2431N/A // Returns true iff "this" is a superset of "bits". 2431N/A // Returns true iff "this and "bits" have a non-empty intersection. 2431N/A // Returns result of whether this map changed 2431N/A // Requires the submap of "bits" starting at offset to be at least as 2038N/A // large as "this". Modifies "this" to be the intersection of its 2038N/A // current contents and the submap of "bits" starting at "offset" of the 3793N/A // (For expedience, currently requires the offset to be aligned to the 2038N/A // bitsize of a uintptr_t. This should go away in the future though it 2038N/A // will probably remain a good case to optimize.) 3012N/A // Test if all bits are set or cleared 2038N/A// Convenience class wrapping BitMap which provides multiple bits per slot. 2038N/A // Construction. bits_per_slot must be greater than 0. 2038N/A // Allocates necessary data structure in resource area. bits_per_slot must be greater than 0. 2038N/A // Returns number of full slots that have been allocated 3529N/A// Closure for iterating over BitMaps 3529N/A // Callback when bit in map is set. Should normally return "true"; 3529N/A // return of false indicates that the bitmap iteration should terminate.