001 /*
002 * Copyright 1999-2005 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025
026 package com.sun.tools.javac.util;
027
028 /** A class for extensible, mutable bit sets.
029 *
030 * <p><b>This is NOT part of any API supported by Sun Microsystems. If
031 * you write code that depends on this, you do so at your own risk.
032 * This code and its internal interfaces are subject to change or
033 * deletion without notice.</b>
034 */
035 public class Bits {
036
037
038 private final static int wordlen = 32;
039 private final static int wordshift = 5;
040 private final static int wordmask = wordlen - 1;
041
042 private int[] bits;
043
044 /** Construct an initially empty set.
045 */
046 public Bits() {
047 this(new int[1]);
048 }
049
050 /** Construct a set consisting initially of given bit vector.
051 */
052 public Bits(int[] bits) {
053 this.bits = bits;
054 }
055
056 /** Construct a set consisting initially of given range.
057 */
058 public Bits(int start, int limit) {
059 this();
060 inclRange(start, limit);
061 }
062
063 private void sizeTo(int len) {
064 if (bits.length < len) {
065 int[] newbits = new int[len];
066 System.arraycopy(bits, 0, newbits, 0, bits.length);
067 bits = newbits;
068 }
069 }
070
071 /** This set = {}.
072 */
073 public void clear() {
074 for (int i = 0; i < bits.length; i++) bits[i] = 0;
075 }
076
077 /** Return a copy of this set.
078 */
079 public Bits dup() {
080 int[] newbits = new int[bits.length];
081 System.arraycopy(bits, 0, newbits, 0, bits.length);
082 return new Bits(newbits);
083 }
084
085 /** Include x in this set.
086 */
087 public void incl(int x) {
088 assert x >= 0;
089 sizeTo((x >>> wordshift) + 1);
090 bits[x >>> wordshift] = bits[x >>> wordshift] |
091 (1 << (x & wordmask));
092 }
093
094
095 /** Include [start..limit) in this set.
096 */
097 public void inclRange(int start, int limit) {
098 sizeTo((limit >>> wordshift) + 1);
099 for (int x = start; x < limit; x++)
100 bits[x >>> wordshift] = bits[x >>> wordshift] |
101 (1 << (x & wordmask));
102 }
103
104 /** Exclude x from this set.
105 */
106 public void excl(int x) {
107 assert x >= 0;
108 sizeTo((x >>> wordshift) + 1);
109 bits[x >>> wordshift] = bits[x >>> wordshift] &
110 ~(1 << (x & wordmask));
111 }
112
113 /** Is x an element of this set?
114 */
115 public boolean isMember(int x) {
116 return
117 0 <= x && x < (bits.length << wordshift) &&
118 (bits[x >>> wordshift] & (1 << (x & wordmask))) != 0;
119 }
120
121 /** this set = this set & xs.
122 */
123 public Bits andSet(Bits xs) {
124 sizeTo(xs.bits.length);
125 for (int i = 0; i < xs.bits.length; i++)
126 bits[i] = bits[i] & xs.bits[i];
127 return this;
128 }
129
130 /** this set = this set | xs.
131 */
132 public Bits orSet(Bits xs) {
133 sizeTo(xs.bits.length);
134 for (int i = 0; i < xs.bits.length; i++)
135 bits[i] = bits[i] | xs.bits[i];
136 return this;
137 }
138
139 /** this set = this set \ xs.
140 */
141 public Bits diffSet(Bits xs) {
142 for (int i = 0; i < bits.length; i++) {
143 if (i < xs.bits.length) {
144 bits[i] = bits[i] & ~xs.bits[i];
145 }
146 }
147 return this;
148 }
149
150 /** this set = this set ^ xs.
151 */
152 public Bits xorSet(Bits xs) {
153 sizeTo(xs.bits.length);
154 for (int i = 0; i < xs.bits.length; i++)
155 bits[i] = bits[i] ^ xs.bits[i];
156 return this;
157 }
158
159 /** Count trailing zero bits in an int. Algorithm from "Hacker's
160 * Delight" by Henry S. Warren Jr. (figure 5-13)
161 */
162 private static int trailingZeroBits(int x) {
163 assert wordlen == 32;
164 if (x == 0) return 32;
165 int n = 1;
166 if ((x & 0xffff) == 0) { n += 16; x >>>= 16; }
167 if ((x & 0x00ff) == 0) { n += 8; x >>>= 8; }
168 if ((x & 0x000f) == 0) { n += 4; x >>>= 4; }
169 if ((x & 0x0003) == 0) { n += 2; x >>>= 2; }
170 return n - (x&1);
171 }
172
173 /** Return the index of the least bit position >= x that is set.
174 * If none are set, returns -1. This provides a nice way to iterate
175 * over the members of a bit set:
176 * <pre>
177 * for (int i = bits.nextBit(0); i>=0; i = bits.nextBit(i+1)) ...
178 * </pre>
179 */
180 public int nextBit(int x) {
181 int windex = x >>> wordshift;
182 if (windex >= bits.length) return -1;
183 int word = bits[windex] & ~((1 << (x & wordmask))-1);
184 while (true) {
185 if (word != 0)
186 return (windex << wordshift) + trailingZeroBits(word);
187 windex++;
188 if (windex >= bits.length) return -1;
189 word = bits[windex];
190 }
191 }
192
193 /** a string representation of this set.
194 */
195 public String toString() {
196 char[] digits = new char[bits.length * wordlen];
197 for (int i = 0; i < bits.length * wordlen; i++)
198 digits[i] = isMember(i) ? '1' : '0';
199 return new String(digits);
200 }
201
202 /** Test Bits.nextBit(int). */
203 public static void main(String[] args) {
204 java.util.Random r = new java.util.Random();
205 Bits bits = new Bits();
206 int dupCount = 0;
207 for (int i=0; i<125; i++) {
208 int k;
209 do {
210 k = r.nextInt(250);
211 } while (bits.isMember(k));
212 System.out.println("adding " + k);
213 bits.incl(k);
214 }
215 int count = 0;
216 for (int i = bits.nextBit(0); i >= 0; i = bits.nextBit(i+1)) {
217 System.out.println("found " + i);
218 count ++;
219 }
220 if (count != 125) throw new Error();
221 }
222 }