001: /* Copyright (c) 2001-2005, The HSQL Development Group
002: * All rights reserved.
003: *
004: * Redistribution and use in source and binary forms, with or without
005: * modification, are permitted provided that the following conditions are met:
006: *
007: * Redistributions of source code must retain the above copyright notice, this
008: * list of conditions and the following disclaimer.
009: *
010: * Redistributions in binary form must reproduce the above copyright notice,
011: * this list of conditions and the following disclaimer in the documentation
012: * and/or other materials provided with the distribution.
013: *
014: * Neither the name of the HSQL Development Group nor the names of its
015: * contributors may be used to endorse or promote products derived from this
016: * software without specific prior written permission.
017: *
018: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
019: * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
020: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
021: * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
022: * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
023: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
024: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
026: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028: * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029: */
030:
031: package org.hsqldb.store;
032:
033: /**
034: * Implementation of a bit map of any size, together with static methods to
035: * manipulate int values as bit maps.
036: *
037: * @author fredt@users
038: * @version 1.8.0
039: * @since 1.8.0
040: */
041: public class BitMap {
042:
043: int defaultCapacity;
044: int capacity;
045: int[] map;
046:
047: public BitMap(int initialCapacity) {
048:
049: int words = initialCapacity / 32;
050:
051: if (initialCapacity % 32 != 0) {
052: words++;
053: }
054:
055: defaultCapacity = capacity = words * 32;
056: map = new int[words];
057: }
058:
059: /**
060: * Resets to blank with original capacity
061: */
062: public void reset() {
063: map = new int[defaultCapacity / 32];
064: capacity = defaultCapacity;
065: }
066:
067: /**
068: * Sets pos and returns old value
069: */
070: public int set(int pos) {
071:
072: while (pos >= capacity) {
073: doubleCapacity();
074: }
075:
076: int windex = pos >> 5;
077: int mask = 0x80000000 >>> (pos & 0x1F);
078: int word = map[windex];
079: int result = (word & mask) == 0 ? 0 : 1;
080:
081: map[windex] = (word | mask);
082:
083: return result;
084: }
085:
086: /**
087: * Unsets pos and returns old value
088: */
089: public int unset(int pos) {
090:
091: if (pos >= capacity) {
092: return 0;
093: }
094:
095: int windex = pos >> 5;
096: int mask = 0x80000000 >>> (pos & 0x1F);
097: int word = map[windex];
098: int result = (word & mask) == 0 ? 0 : 1;
099:
100: mask = ~mask;
101: map[windex] = (word & mask);
102:
103: return result;
104: }
105:
106: public int get(int pos) {
107:
108: while (pos >= capacity) {
109: doubleCapacity();
110: }
111:
112: int windex = pos >> 5;
113: int mask = 0x80000000 >>> (pos & 0x1F);
114: int word = map[windex];
115:
116: return (word & mask) == 0 ? 0 : 1;
117: }
118:
119: public static int set(int map, int pos) {
120:
121: int mask = 0x80000000 >>> pos;
122:
123: return (map | mask);
124: }
125:
126: public static int unset(int map, int pos) {
127:
128: int mask = 0x80000000 >>> pos;
129:
130: mask = ~mask;
131:
132: return (map & mask);
133: }
134:
135: public static boolean isSet(int map, int pos) {
136:
137: int mask = 0x80000000 >>> pos;
138:
139: return (map & mask) == 0 ? false : true;
140: }
141:
142: private void doubleCapacity() {
143:
144: int[] newmap = new int[map.length * 2];
145:
146: capacity *= 2;
147:
148: System.arraycopy(map, 0, newmap, 0, map.length);
149:
150: map = newmap;
151: }
152: }
|