Mercurial > hg > graal-compiler

comparison graal/com.oracle.max.cri/src/com/oracle/max/cri/ci/CiBitMap.java @ 4199:aaac4894175c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Renamed cri packages from sun to oracle.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Tue, 03 Jan 2012 16:29:28 +0100
parents graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java@f5328dda9714
children
comparison
equal deleted inserted replaced
4198:8c9c0e1eaab1 4199:aaac4894175c
1 /*
2 * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23 package com.oracle.max.cri.ci;
24
25 import java.io.*;
26 import java.util.*;
27
28 /**
29 * Implements a bitmap that stores a single bit for a range of integers (0-n).
30 */
31 public final class CiBitMap implements Serializable {
32
33 private static final long serialVersionUID = 2471441272241401105L;
34 private static final int ADDRESS_BITS_PER_WORD = 6;
35 private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
36 private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1;
37
38 public static final int DEFAULT_LENGTH = BITS_PER_WORD;
39
40 public static int roundUpLength(int length) {
41 return ((length + (BITS_PER_WORD - 1)) >> ADDRESS_BITS_PER_WORD) << ADDRESS_BITS_PER_WORD;
42 }
43
44 private int size;
45 private long low;
46 private long[] extra;
47
48 /**
49 * Constructs a new bit map with the {@linkplain #DEFAULT_LENGTH default length}.
50 */
51 public CiBitMap() {
52 this(DEFAULT_LENGTH);
53 }
54
55 /**
56 * Constructs a new bit map from a byte array encoded bit map.
57 *
58 * @param bitmap the bit map to convert
59 */
60 public CiBitMap(byte[] bitmap) {
61 this(bitmap, 0, bitmap.length);
62 }
63
64 /**
65 * Constructs a copy of the given bit map.
66 *
67 * @param bitmap the bit map to copy.
68 */
69 public CiBitMap(CiBitMap bitmap) {
70 this.size = bitmap.size;
71 this.low = bitmap.low;
72 if (bitmap.extra != null) {
73 this.extra = Arrays.copyOf(bitmap.extra, bitmap.extra.length);
74 }
75 }
76
77 /**
78 * Constructs a new bit map from a byte array encoded bit map.
79 *
80 * @param arr the byte array containing the bit map to convert
81 * @param off the byte index in {@code arr} at which the bit map starts
82 * @param numberOfBytes the number of bytes worth of bits to copy from {@code arr}
83 */
84 public CiBitMap(byte[] arr, int off, int numberOfBytes) {
85 this(numberOfBytes * 8);
86 int byteIndex = off;
87 int end = off + numberOfBytes;
88 assert end <= arr.length;
89 while (byteIndex < end && (byteIndex - off) < 8) {
90 long bite = (long) arr[byteIndex] & 0xff;
91 low |= bite << ((byteIndex - off) * 8);
92 byteIndex++;
93 }
94 if (byteIndex < end) {
95 assert (byteIndex - off) == 8;
96 int remBytes = end - byteIndex;
97 int remWords = (remBytes + 7) / 8;
98 for (int word = 0; word < remWords; word++) {
99 long w = 0L;
100 for (int i = 0; i < 8 && byteIndex < end; i++) {
101 long bite = (long) arr[byteIndex] & 0xff;
102 w |= bite << (i * 8);
103 byteIndex++;
104 }
105 extra[word] = w;
106 }
107 }
108 }
109
110 /**
111 * Converts a {@code long} to a {@link CiBitMap}.
112 */
113 public static CiBitMap fromLong(long bitmap) {
114 CiBitMap bm = new CiBitMap(64);
115 bm.low = bitmap;
116 return bm;
117 }
118
119 /**
120 * Constructs a new bit map with the specified length.
121 *
122 * @param length the length of the bitmap
123 */
124 public CiBitMap(int length) {
125 assert length >= 0;
126 this.size = length;
127 if (length > BITS_PER_WORD) {
128 extra = new long[length >> ADDRESS_BITS_PER_WORD];
129 }
130 }
131
132 /**
133 * Sets the bit at the specified index.
134 *
135 * @param i the index of the bit to set
136 */
137 public void set(int i) {
138 if (checkIndex(i) < BITS_PER_WORD) {
139 low |= 1L << i;
140 } else {
141 int pos = wordIndex(i);
142 int index = bitInWord(i);
143 extra[pos] |= 1L << index;
144 }
145 }
146
147 /**
148 * Grows this bitmap to a new size, appending necessary zero bits.
149 *
150 * @param newLength the new length of the bitmap
151 */
152 public void grow(int newLength) {
153 if (newLength > size) {
154 // grow this bitmap to the new length
155 int newSize = newLength >> ADDRESS_BITS_PER_WORD;
156 if (newLength > 0) {
157 if (extra == null) {
158 // extra just needs to be allocated now
159 extra = new long[newSize];
160 } else {
161 if (extra.length < newSize) {
162 // extra needs to be copied
163 long[] newExtra = new long[newSize];
164 for (int i = 0; i < extra.length; i++) {
165 newExtra[i] = extra[i];
166 }
167 extra = newExtra;
168 } else {
169 // nothing to do, extra is already the right size
170 }
171 }
172 }
173 size = newLength;
174 }
175 }
176
177 private static int bitInWord(int i) {
178 return i & BIT_INDEX_MASK;
179 }
180
181 private static int wordIndex(int i) {
182 return (i >> ADDRESS_BITS_PER_WORD) - 1;
183 }
184
185 /**
186 * Clears the bit at the specified index.
187 * @param i the index of the bit to clear
188 */
189 public void clear(int i) {
190 if (checkIndex(i) < BITS_PER_WORD) {
191 low &= ~(1L << i);
192 } else {
193 int pos = wordIndex(i);
194 int index = bitInWord(i);
195 extra[pos] &= ~(1L << index);
196 }
197 }
198
199 /**
200 * Sets all the bits in this bitmap.
201 */
202 public void setAll() {
203 low = -1;
204 if (extra != null) {
205 for (int i = 0; i < extra.length; i++) {
206 extra[i] = -1;
207 }
208 }
209 }
210
211 /**
212 * Clears all the bits in this bitmap.
213 */
214 public void clearAll() {
215 low = 0;
216 if (extra != null) {
217 for (int i = 0; i < extra.length; i++) {
218 extra[i] = 0;
219 }
220 }
221 }
222
223 /**
224 * Gets the value of the bit at the specified index.
225 *
226 * @param i the index of the bit to get
227 * @return {@code true} if the bit at the specified position is {@code 1}
228 */
229 public boolean get(int i) {
230 if (checkIndex(i) < BITS_PER_WORD) {
231 return ((low >> i) & 1) != 0;
232 }
233 int pos = wordIndex(i);
234 int index = bitInWord(i);
235 long bits = extra[pos];
236 return ((bits >> index) & 1) != 0;
237 }
238
239 /**
240 * Gets the value of the bit at the specified index, returning {@code false} if the
241 * bitmap does not cover the specified index.
242 *
243 * @param i the index of the bit to get
244 * @return {@code true} if the bit at the specified position is {@code 1}
245 */
246 public boolean getDefault(int i) {
247 if (i < 0 || i >= size) {
248 return false;
249 }
250 if (i < BITS_PER_WORD) {
251 return ((low >> i) & 1) != 0;
252 }
253 int pos = wordIndex(i);
254 int index = bitInWord(i);
255 long bits = extra[pos];
256 return ((bits >> index) & 1) != 0;
257 }
258
259 /**
260 * Performs the union operation on this bitmap with the specified bitmap. That is, all bits set in either of the two
261 * bitmaps will be set in this bitmap following this operation.
262 *
263 * @param other the other bitmap for the union operation
264 */
265 public void setUnion(CiBitMap other) {
266 low |= other.low;
267 if (extra != null && other.extra != null) {
268 for (int i = 0; i < extra.length && i < other.extra.length; i++) {
269 extra[i] |= other.extra[i];
270 }
271 }
272 }
273
274 /**
275 * Performs the union operation on this bitmap with the specified bitmap. That is, a bit is set in this
276 * bitmap if and only if it is set in both this bitmap and the specified bitmap.
277 *
278 * @param other the other bitmap for this operation
279 * @return {@code true} if any bits were cleared as a result of this operation
280 */
281 public boolean setIntersect(CiBitMap other) {
282 boolean same = true;
283 long intx = low & other.low;
284 if (low != intx) {
285 same = false;
286 low = intx;
287 }
288 long[] oxtra = other.extra;
289 if (extra != null && oxtra != null) {
290 for (int i = 0; i < extra.length; i++) {
291 long a = extra[i];
292 if (i < oxtra.length) {
293 // zero bits out of this map
294 long ax = a & oxtra[i];
295 if (a != ax) {
296 same = false;
297 extra[i] = ax;
298 }
299 } else {
300 // this bitmap is larger than the specified bitmap; zero remaining bits
301 if (a != 0) {
302 same = false;
303 extra[i] = 0;
304 }
305 }
306 }
307 }
308 return !same;
309 }
310
311 /**
312 * Gets the number of addressable bits in this bitmap.
313 *
314 * @return the size of this bitmap
315 */
316 public int size() {
317 return size;
318 }
319
320 private int checkIndex(int i) {
321 if (i < 0 || i >= size) {
322 throw new IndexOutOfBoundsException();
323 }
324 return i;
325 }
326
327 public void setFrom(CiBitMap other) {
328 assert this.size == other.size : "must have same size";
329
330 low = other.low;
331 if (extra != null) {
332 for (int i = 0; i < extra.length; i++) {
333 extra[i] = other.extra[i];
334 }
335 }
336 }
337
338 public void setDifference(CiBitMap other) {
339 assert this.size == other.size : "must have same size";
340
341 low &= ~other.low;
342 if (extra != null) {
343 for (int i = 0; i < extra.length; i++) {
344 extra[i] &= ~other.extra[i];
345 }
346 }
347 }
348
349 public boolean isSame(CiBitMap other) {
350 if (this.size != other.size || this.low != other.low) {
351 return false;
352 }
353
354 if (extra != null) {
355 for (int i = 0; i < extra.length; i++) {
356 if (extra[i] != other.extra[i]) {
357 return false;
358 }
359 }
360 }
361
362 return true;
363 }
364
365 /**
366 * Returns the index of the first set bit that occurs on or after a specified start index.
367 * If no such bit exists then -1 is returned.
368 * <p>
369 * To iterate over the set bits in a {@code BitMap}, use the following loop:
370 *
371 * <pre>
372 * for (int i = bitMap.nextSetBit(0); i &gt;= 0; i = bitMap.nextSetBit(i + 1)) {
373 * // operate on index i here
374 * }
375 * </pre>
376 *
377 * @param fromIndex the index to start checking from (inclusive)
378 * @return the index of the lowest set bit between {@code [fromIndex .. size())} or -1 if there is no set bit in this range
379 * @throws IndexOutOfBoundsException if the specified index is negative.
380 */
381 public int nextSetBit(int fromIndex) {
382 return nextSetBit(fromIndex, size());
383 }
384
385 /**
386 * Returns the index of the first set bit that occurs on or after a specified start index
387 * and before a specified end index. If no such bit exists then -1 is returned.
388 * <p>
389 * To iterate over the set bits in a {@code BitMap}, use the following loop:
390 *
391 * <pre>
392 * for (int i = bitMap.nextSetBit(0, bitMap.size()); i &gt;= 0; i = bitMap.nextSetBit(i + 1, bitMap.size())) {
393 * // operate on index i here
394 * }
395 * </pre>
396 *
397 * @param fromIndex the index to start checking from (inclusive)
398 * @param toIndex the index at which to stop checking (exclusive)
399 * @return the index of the lowest set bit between {@code [fromIndex .. toIndex)} or -1 if there is no set bit in this range
400 * @throws IndexOutOfBoundsException if the specified index is negative.
401 */
402 public int nextSetBit(int fromIndex, int toIndex) {
403 assert fromIndex <= size() : "index out of bounds";
404 assert toIndex <= size() : "index out of bounds";
405 assert fromIndex <= toIndex : "fromIndex > toIndex";
406
407 if (fromIndex == toIndex) {
408 return -1;
409 }
410 int fromWordIndex = wordIndex(fromIndex);
411 int toWordIndex = wordIndex(toIndex - 1) + 1;
412 int resultIndex = fromIndex;
413
414 // check bits including and to the left_ of offset's position
415 int pos = bitInWord(resultIndex);
416 long res = map(fromWordIndex) >> pos;
417 if (res != 0) {
418 resultIndex += Long.numberOfTrailingZeros(res);
419 assert resultIndex >= fromIndex && resultIndex < toIndex : "just checking";
420 if (resultIndex < toIndex) {
421 return resultIndex;
422 }
423 return -1;
424 }
425 // skip over all word length 0-bit runs
426 for (fromWordIndex++; fromWordIndex < toWordIndex; fromWordIndex++) {
427 res = map(fromWordIndex);
428 if (res != 0) {
429 // found a 1, return the offset
430 resultIndex = bitIndex(fromWordIndex) + Long.numberOfTrailingZeros(res);
431 assert resultIndex >= fromIndex : "just checking";
432 if (resultIndex < toIndex) {
433 return resultIndex;
434 }
435 return -1;
436 }
437 }
438 return -1;
439 }
440
441 private static int bitIndex(int index) {
442 return (index + 1) << ADDRESS_BITS_PER_WORD;
443 }
444
445 private long map(int index) {
446 if (index == -1) {
447 return low;
448 }
449 return extra[index];
450 }
451
452 private static boolean allZeros(int start, long[] arr) {
453 for (int i = start; i < arr.length; i++) {
454 if (arr[i] != 0) {
455 return false;
456 }
457 }
458 return true;
459 }
460
461 /**
462 * Compares this object against the specified object.
463 * The result is {@code true} if and only if {@code obj} is
464 * not {@code null} and is a {@code CiBitMap} object that has
465 * exactly the same set of bits set to {@code true} as this bit
466 * set.
467 *
468 * @param obj the object to compare with.
469 */
470 @Override
471 public boolean equals(Object obj) {
472 if (obj instanceof CiBitMap) {
473 CiBitMap bm = (CiBitMap) obj;
474 if (bm.low == low) {
475 if (bm.extra == null) {
476 if (extra == null) {
477 // Common case
478 return true;
479 }
480 return allZeros(0, extra);
481 }
482 if (extra == null) {
483 return allZeros(0, bm.extra);
484 }
485 // both 'extra' array non null:
486 int i = 0;
487 int length = Math.min(extra.length, bm.extra.length);
488 while (i < length) {
489 if (extra[i] != bm.extra[i]) {
490 return false;
491 }
492 i++;
493 }
494 if (extra.length > bm.extra.length) {
495 return allZeros(length, extra);
496 }
497 if (extra.length < bm.extra.length) {
498 return allZeros(length, bm.extra);
499 }
500 return true;
501 }
502 }
503 return false;
504 }
505
506 @Override
507 public int hashCode() {
508 return (int) low ^ size;
509 }
510
511 /**
512 * Returns a string representation of this bit map
513 * that is the same as the string returned by {@link BitSet#toString()}
514 * for a bit set with the same bits set as this bit map.
515 */
516 @Override
517 public String toString() {
518 StringBuilder sb = new StringBuilder(size * 2);
519 sb.append('{');
520
521 int bit = nextSetBit(0);
522 if (bit != -1) {
523 sb.append(bit);
524 for (bit = nextSetBit(bit + 1); bit >= 0; bit = nextSetBit(bit + 1)) {
525 sb.append(", ").append(bit);
526 }
527 }
528
529 sb.append('}');
530 return sb.toString();
531 }
532
533 public static int highestOneBitIndex(long value) {
534 int bit = Long.numberOfTrailingZeros(Long.highestOneBit(value));
535 if (bit == 64) {
536 return -1;
537 }
538 return bit;
539 }
540
541 /**
542 * Returns the number of bits set to {@code true} in this bit map.
543 */
544 public int cardinality() {
545 int sum = Long.bitCount(low);
546 if (extra != null) {
547 for (long word : extra) {
548 sum += Long.bitCount(word);
549 }
550 }
551 return sum;
552 }
553
554 /**
555 * Returns the "logical size" of this bit map: the index of
556 * the highest set bit in the bit map plus one. Returns zero
557 * if the bit map contains no set bits.
558 *
559 * @return the logical size of this bit map
560 */
561 public int length() {
562 if (extra != null) {
563 for (int i = extra.length - 1; i >= 0; i--) {
564 if (extra[i] != 0) {
565 return (highestOneBitIndex(extra[i]) + ((i + 1) * 64)) + 1;
566 }
567 }
568 }
569 return highestOneBitIndex(low) + 1;
570 }
571
572 /**
573 * Returns a string representation of this bit map with every set bit represented as {@code '1'}
574 * and every unset bit represented as {@code '0'}. The first character in the returned string represents
575 * bit 0 in this bit map.
576 *
577 * @param length the number of bits represented in the returned string. If {@code length < 0 || length > size()},
578 * then the value of {@link #length()} is used.
579 */
580 public String toBinaryString() {
581 int length = length();
582 if (length == 0) {
583 return "";
584 }
585 StringBuilder sb = new StringBuilder(length);
586 for (int i = 0; i < length; ++i) {
587 sb.append(get(i) ? '1' : '0');
588 }
589 return sb.toString();
590 }
591
592 static final char[] hexDigits = {
593 '0', '1', '2', '3', '4', '5', '6', '7',
594 '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
595 };
596
597 /**
598 * Returns a string representation of this bit map in hex.
599 */
600 public String toHexString() {
601 if (size == 0) {
602 return "";
603 }
604 int hexSize = CiUtil.align(this.size, 4);
605 StringBuilder sb = new StringBuilder(hexSize / 4);
606 for (int i = 0; i < hexSize; i += 4) {
607 int nibble = get(i) ? 1 : 0;
608 if (get(i + 1)) {
609 nibble |= 2;
610 }
611 if (get(i + 2)) {
612 nibble |= 4;
613 }
614 if (get(i + 3)) {
615 nibble |= 8;
616 }
617
618 sb.append(hexDigits[nibble]);
619 }
620 return sb.toString();
621 }
622
623 public CiBitMap copy() {
624 CiBitMap n = new CiBitMap(BITS_PER_WORD);
625 n.low = low;
626 if (extra != null) {
627 n.extra = Arrays.copyOf(extra, extra.length);
628 }
629 n.size = size;
630 return n;
631 }
632
633 /**
634 * Copies this bit map into a given byte array.
635 *
636 * @param arr the destination
637 * @param off the byte index in {@code arr} at which to start writing
638 * @param numberOfBytes the number of bytes worth of bits to copy from this bit map.
639 * The number of bits copied is {@code numberOfBytes * 8}. If {@code numberOfBytes}
640 * is -1, then {@code ((size() + 7) / 8)} is used instead.
641 * @return the number of bytes written to {@code arr}
642 */
643 public int copyTo(byte[] arr, int off, int numberOfBytes) {
644 for (int i = 0; i < numberOfBytes; ++i) {
645 long word = low;
646 int byteInWord;
647 if (i >= 8) {
648 int wordIndex = (i - 8) / 8;
649 word = extra[wordIndex];
650 byteInWord = i & 0x7;
651 } else {
652 byteInWord = i;
653 }
654 assert byteInWord < 8;
655 byte b = (byte) (word >> (byteInWord * 8));
656 arr[off + i] = b;
657 }
658 return numberOfBytes;
659 }
660
661 /**
662 * Converts this bit map to a byte array. The length of the returned
663 * byte array is {@code ((size() + 7) / 8)}.
664 */
665 public byte[] toByteArray() {
666 byte[] arr = new byte[(size + 7) / 8];
667 copyTo(arr, 0, arr.length);
668 return arr;
669 }
670
671 /**
672 * Converts this bit map to a long.
673 *
674 * @throws IllegalArgumentException if {@code (size() > 64)}
675 */
676 public long toLong() {
677 if (size > 64) {
678 throw new IllegalArgumentException("bit map of size " + size + " cannot be converted to long");
679 }
680 return low;
681 }
682 }