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