View Javadoc
1   /*
2    * Copyright (c) 2001, 2007, 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   */
24  
25  package sun.jvm.hotspot.utilities;
26  
27  import sun.jvm.hotspot.debugger.*;
28  
29  /** Manages a bitmap of the specified bit size */
30  public class BitMap {
31    public BitMap(int sizeInBits) {
32      this.size = sizeInBits;
33      int nofWords = sizeInWords();
34      data = new int[nofWords];
35    }
36  
37    public int size() {
38      return size;
39    }
40  
41    // Accessors
42    public boolean at(int offset) {
43      if (Assert.ASSERTS_ENABLED) {
44        Assert.that(offset>=0 && offset < size(), "BitMap index out of bounds");
45      }
46      return Bits.isSetNthBit(wordFor(offset), offset % bitsPerWord);
47    }
48  
49    public void atPut(int offset, boolean value) {
50      int index = indexFor(offset);
51      int pos   = offset % bitsPerWord;
52      if (value) {
53        data[index] = Bits.setNthBit(data[index], pos);
54      } else {
55        data[index] = Bits.clearNthBit(data[index], pos);
56      }
57    }
58  
59    public void set_size(int value) {
60      size = value;
61    }
62  
63    public void set_map(Address addr) {
64      for (int i=0; i<sizeInWords(); i++) {
65        data[i] =  (int) addr.getCIntegerAt(0, bytesPerWord, true);
66        addr = addr.addOffsetTo(bytesPerWord);
67      }
68  
69    }
70  
71    public void clear() {
72      for (int i = 0; i < sizeInWords(); i++) {
73        data[i] = Bits.NoBits;
74      }
75    }
76  
77    public void iterate(BitMapClosure blk) {
78      for (int index = 0; index < sizeInWords(); index++) {
79        int rest = data[index];
80        for (int offset = index * bitsPerWord; rest != Bits.NoBits; offset++) {
81          if (rest % 2 == 1) {
82            if (offset < size()) {
83              blk.doBit(offset);
84            } else {
85              return; // Passed end of map
86            }
87          }
88          rest = rest >>> 1;
89        }
90      }
91    }
92  
93    /** Sets this bitmap to the logical union of it and the
94        argument. Both bitmaps must be the same size. Returns true if a
95        change was caused in this bitmap. */
96    public boolean setUnion(BitMap other) {
97      if (Assert.ASSERTS_ENABLED) {
98        Assert.that(size() == other.size(), "must have same size");
99      }
100     boolean changed = false;
101     for (int index = 0; index < sizeInWords(); index++) {
102       int temp = data[index] | other.data[index];
103       changed = changed || (temp != data[index]);
104       data[index] = temp;
105     }
106     return changed;
107   }
108 
109   /** Sets this bitmap to the logical intersection of it and the
110       argument. Both bitmaps must be the same size. */
111   public void setIntersection(BitMap other) {
112     if (Assert.ASSERTS_ENABLED) {
113       Assert.that(size() == other.size(), "must have same size");
114     }
115     for (int index = 0; index < sizeInWords(); index++) {
116       data[index] = data[index] & (other.data[index]);
117     }
118   }
119 
120   /** Sets this bitmap to the contents of the argument. Both bitmaps
121       must be the same size. */
122   public void setFrom(BitMap other) {
123     if (Assert.ASSERTS_ENABLED) {
124       Assert.that(size() == other.size(), "must have same size");
125     }
126     for (int index = 0; index < sizeInWords(); index++) {
127       data[index] = other.data[index];
128     }
129   }
130 
131   /** Sets this bitmap to the logical difference between it and the
132       argument; that is, any bits that are set in the argument are
133       cleared in this bitmap. Both bitmaps must be the same size.
134       Returns true if a change was caused in this bitmap. */
135   public boolean setDifference(BitMap other) {
136     if (Assert.ASSERTS_ENABLED) {
137       Assert.that(size() == other.size(), "must have same size");
138     }
139     boolean changed = false;
140     for (int index = 0; index < sizeInWords(); index++) {
141       int temp = data[index] & ~(other.data[index]);
142       changed = changed || (temp != data[index]);
143       data[index] = temp;
144     }
145     return changed;
146   }
147 
148   /** Both bitmaps must be the same size. */
149   public boolean isSame(BitMap other) {
150     if (Assert.ASSERTS_ENABLED) {
151       Assert.that(size() == other.size(), "must have same size");
152     }
153     for (int index = 0; index < sizeInWords(); index++) {
154       if (data[index] != (other.data[index])) return false;
155     }
156     return true;
157   }
158 
159   public int getNextOneOffset(int l_offset, int r_offset) {
160     if (l_offset == r_offset) {
161       return l_offset;
162     }
163 
164     int index = indexFor(l_offset);
165     int r_index = indexFor(r_offset);
166     int res_offset = l_offset;
167 
168     int pos = bitInWord(res_offset);
169     int res = data[index] >> pos;
170 
171     if (res != 0) {
172       // find the position of the 1-bit
173       for (; (res & 1) == 0; res_offset++) {
174         res = res >> 1;
175       }
176       return res_offset;
177     }
178     // skip over all word length 0-bit runs
179     for (index++; index < r_index; index++) {
180       res = data[index];
181       if (res != 0) {
182         // found a 1, return the offset
183         for (res_offset = index * bitsPerWord; (res & 1) == 0; res_offset++) {
184           res = res >> 1;
185         }
186         return res_offset;
187       }
188     }
189     return r_offset;
190   }
191 
192   //----------------------------------------------------------------------
193   // Internals only below this point
194   //
195   private int   size; // in bits
196   private int[] data;
197   private static final int bitsPerWord = 32;
198   private static final int bytesPerWord = 4;
199 
200   private int sizeInWords() {
201     return (size() + bitsPerWord - 1) / bitsPerWord;
202   }
203 
204   private int indexFor(int offset) {
205     return offset / bitsPerWord;
206   }
207 
208   private int wordFor(int offset) {
209     return data[offset / bitsPerWord];
210   }
211 
212   private int bitInWord(int offset) {
213     return offset & (bitsPerWord - 1);
214   }
215 }