001: /*-
002: * See the file LICENSE for redistribution information.
003: *
004: * Copyright (c) 2002,2008 Oracle. All rights reserved.
005: *
006: * $Id: BitMap.java,v 1.5.2.3 2008/01/07 15:14:18 cwl Exp $
007: */
008:
009: package com.sleepycat.je.utilint;
010:
011: import java.util.BitSet;
012: import java.util.HashMap;
013: import java.util.Iterator;
014: import java.util.Map;
015:
016: /**
017: * Bitmap which supports indexing with long arguments. java.util.BitSet
018: * provides all the functionality and performance we need, but requires integer
019: * indexing.
020: *
021: * Long indexing is implemented by keeping a Map of java.util.BitSets, where
022: * each bitset covers 2^16 bits worth of values. The Bitmap may be sparse, in
023: * that each segment is only instantiated when needed.
024: *
025: * Note that this class is currently not thread safe; adding a new bitset
026: * segment is not protected.
027: */
028: public class BitMap {
029:
030: private static final int SEGMENT_SIZE = 16;
031: private static final int SEGMENT_MASK = 0xffff;
032:
033: /*
034: * Map of segment value -> bitset, where the segment value is index >>16
035: */
036: private Map bitSegments;
037:
038: public BitMap() {
039: bitSegments = new HashMap();
040: }
041:
042: /*
043: * @throws IndexOutOfBoundsException if index is negative.
044: */
045: public void set(long index) throws IndexOutOfBoundsException {
046:
047: if (index < 0) {
048: throw new IndexOutOfBoundsException(index + " is negative.");
049: }
050:
051: BitSet bitset = getBitSet(index, true);
052: if (bitset == null) {
053: throw new IllegalArgumentException(index
054: + " is out of bounds");
055: }
056: int useIndex = getIntIndex(index);
057: bitset.set(useIndex);
058: }
059:
060: /*
061: * @throws IndexOutOfBoundsException if index is negative.
062: */
063: public boolean get(long index) throws IndexOutOfBoundsException {
064:
065: if (index < 0) {
066: throw new IndexOutOfBoundsException(index + " is negative.");
067: }
068:
069: BitSet bitset = getBitSet(index, false);
070: if (bitset == null) {
071: return false;
072: }
073:
074: int useIndex = getIntIndex(index);
075: return bitset.get(useIndex);
076: }
077:
078: /*
079: * Since the BitMap is implemented by a collection of BitSets, return
080: * the one which covers the numeric range for this index.
081: *
082: * @param index the bit we want to access
083: * @param allowCreate if true, return the BitSet that would hold this
084: * index even if it wasn't previously set. If false, return null
085: * if the bit has not been set.
086: */
087: private BitSet getBitSet(long index, boolean allowCreate) {
088:
089: Long segmentId = new Long(index >> SEGMENT_SIZE);
090:
091: BitSet bitset = (BitSet) bitSegments.get(segmentId);
092: if (allowCreate) {
093: if (bitset == null) {
094: bitset = new BitSet();
095: bitSegments.put(segmentId, bitset);
096: }
097: }
098:
099: return bitset;
100: }
101:
102: private int getIntIndex(long index) {
103: return (int) (index & SEGMENT_MASK);
104: }
105:
106: /* For unit testing. */
107: int getNumSegments() {
108: return bitSegments.size();
109: }
110:
111: /*
112: * Currently for unit testing, though note that java.util.BitSet does
113: * support cardinality().
114: */
115: int cardinality() {
116: int count = 0;
117: Iterator iter = bitSegments.values().iterator();
118: while (iter.hasNext()) {
119: BitSet b = (BitSet) iter.next();
120: count += b.cardinality();
121: }
122: return count;
123: }
124: }
|