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