1 /*
2  * Copyright (c) 2019, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  *
23  */
24 
25 package sun.jvm.hotspot.utilities;
26 
27 /** A BitMap implementing the BitMapInterface. */
28 public class BitMapSegmented implements BitMapInterface {
29   private static final int SegmentSizeBits = 30;
30   private static final int SegmentSize = 1 << (SegmentSizeBits - 1);
31 
BitMapSegmented(long sizeInBits)32   public BitMapSegmented(long sizeInBits) {
33     this.size = sizeInBits;
34 
35     if (sizeInBits == 0) {
36       segmentBitMaps = new BitMap[0];
37       return;
38     }
39 
40     int lastSegmentSize = (int)(sizeInBits % SegmentSize);
41 
42     int segments = segmentIndex(sizeInBits - 1) + 1;
43     int completeSegments = segments - ((lastSegmentSize != 0) ? 1 : 0);
44 
45     segmentBitMaps = new BitMap[segments];
46 
47     for (int i = 0; i < completeSegments; i++) {
48       segmentBitMaps[i] = new BitMap(SegmentSize);
49     }
50 
51     if (lastSegmentSize != 0) {
52       segmentBitMaps[completeSegments] = new BitMap(lastSegmentSize);
53     }
54   }
55 
size()56   public long size() {
57     return size;
58   }
59 
60   // Accessors
at(long offset)61   public boolean at(long offset) {
62     assert offset < size;
63 
64     int segmentIndex = segmentIndex(offset);
65     int segmentOffset = segmentOffset(offset);
66     return segmentBitMaps[segmentIndex].at(segmentOffset);
67   }
68 
69   public void atPut(long offset, boolean value) {
70     assert offset < size;
71 
72     int segmentIndex = segmentIndex(offset);
73     int segmentOffset = segmentOffset(offset);
74     segmentBitMaps[segmentIndex].atPut(segmentOffset, value);
75   }
76 
77   public void clear() {
78     for (BitMap map : segmentBitMaps) {
79       map.clear();
80     }
81   }
82 
83   //----------------------------------------------------------------------
84   // Internals only below this point
85   //
86   private final long     size; // in bits
87   private final BitMap[] segmentBitMaps;
88 
89   private int segmentIndex(long offset) {
90     long longIndex = offset / SegmentSize;
91 
92     assert longIndex < Integer.MAX_VALUE;
93     return (int)longIndex;
94   }
95 
96   private int segmentOffset(long offset) {
97     return (int)(offset % SegmentSize);
98   }
99 }
100