Mercurial > hg > graal-jvmci-8

comparison graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java @ 3733:e233f5660da4

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