1 /*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2002, 2014 Oracle and/or its affiliates. All rights reserved. 5 * 6 */ 7 8 package com.sleepycat.je.utilint; 9 10 import java.util.BitSet; 11 import java.util.HashMap; 12 import java.util.Iterator; 13 import java.util.Map; 14 15 import com.sleepycat.je.EnvironmentFailureException; 16 17 /** 18 * Bitmap which supports indexing with long arguments. java.util.BitSet 19 * provides all the functionality and performance we need, but requires integer 20 * indexing. 21 * 22 * Long indexing is implemented by keeping a Map of java.util.BitSets, where 23 * each bitset covers 2^16 bits worth of values. The Bitmap may be sparse, in 24 * that each segment is only instantiated when needed. 25 * 26 * Note that this class is currently not thread safe; adding a new bitset 27 * segment is not protected. 28 */ 29 public class BitMap { 30 31 private static final int SEGMENT_SIZE = 16; 32 private static final int SEGMENT_MASK = 0xffff; 33 34 /* 35 * Map of segment value -> bitset, where the segment value is index >>16 36 */ 37 private Map<Long, BitSet> bitSegments; 38 BitMap()39 public BitMap() { 40 bitSegments = new HashMap<Long, BitSet>(); 41 } 42 43 /* 44 * @throws IndexOutOfBoundsException if index is negative. 45 */ set(long index)46 public void set(long index) 47 throws IndexOutOfBoundsException { 48 49 if (index < 0) { 50 throw new IndexOutOfBoundsException(index + " is negative."); 51 } 52 53 BitSet bitset = getBitSet(index, true); 54 if (bitset == null) { 55 throw EnvironmentFailureException.unexpectedState 56 (index + " is out of bounds"); 57 } 58 int useIndex = getIntIndex(index); 59 bitset.set(useIndex); 60 } 61 62 /* 63 * @throws IndexOutOfBoundsException if index is negative. 64 */ get(long index)65 public boolean get(long index) 66 throws IndexOutOfBoundsException { 67 68 if (index < 0) { 69 throw new IndexOutOfBoundsException(index + " is negative."); 70 } 71 72 BitSet bitset = getBitSet(index, false); 73 if (bitset == null) { 74 return false; 75 } 76 77 int useIndex = getIntIndex(index); 78 return bitset.get(useIndex); 79 } 80 81 /* 82 * Since the BitMap is implemented by a collection of BitSets, return 83 * the one which covers the numeric range for this index. 84 * 85 * @param index the bit we want to access 86 * @param allowCreate if true, return the BitSet that would hold this 87 * index even if it wasn't previously set. If false, return null 88 * if the bit has not been set. 89 */ getBitSet(long index, boolean allowCreate)90 private BitSet getBitSet(long index, boolean allowCreate) { 91 92 Long segmentId = Long.valueOf(index >> SEGMENT_SIZE); 93 94 BitSet bitset = bitSegments.get(segmentId); 95 if (allowCreate) { 96 if (bitset == null) { 97 bitset = new BitSet(); 98 bitSegments.put(segmentId, bitset); 99 } 100 } 101 102 return bitset; 103 } 104 getIntIndex(long index)105 private int getIntIndex(long index) { 106 return (int) (index & SEGMENT_MASK); 107 } 108 109 /* For unit testing. */ getNumSegments()110 int getNumSegments() { 111 return bitSegments.size(); 112 } 113 114 /* 115 * Currently for unit testing, though note that java.util.BitSet does 116 * support cardinality(). 117 */ cardinality()118 int cardinality() { 119 int count = 0; 120 Iterator<BitSet> iter = bitSegments.values().iterator(); 121 while (iter.hasNext()) { 122 BitSet b = iter.next(); 123 count += b.cardinality(); 124 } 125 return count; 126 } 127 } 128