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 
  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 
  56   public long size() {
  57     return size;
  58   }
  59 
  60   // Accessors
  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 }