SmallNumberedMap


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 2002 Ondrej Lhotak
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  package soot.util;
21  import java.util.*;
22  
23  /** A java.util.Map-like map with Numberable objects as the keys.
24   *
25   * @author Ondrej Lhotak
26   */
27  
28  public final class SmallNumberedMap {
29      public SmallNumberedMap( ArrayNumberer universe ) {
30          this.universe = universe;
31      }
32      /** Associates a value with a key. */
33      public boolean put( Numberable key, Object   value ) {
34          int pos = findPosition( key );
35          if( array[pos] == key ) {
36              if( values[pos] == value ) return false;
37              values[pos] = value;
38              return true;
39          }
40          size++;
41          if( size*3 > array.length*2 ) {
42              doubleSize();
43              pos = findPosition( key );
44          }
45          array[pos] = key;
46          values[pos] = value;
47          return true;
48      }
49      /** Returns the value associated with a given key. */
50      public Object   get( Numberable key ) {
51          return values[ findPosition(key) ];
52      }
53      /** Returns the number of non-null values in this map. */
54      public int nonNullSize() {
55          int ret = 0;
56          for( int i = 0; i < values.length; i++ ) {
57              if( values[i] != null ) ret++;
58          }
59          return ret;
60      }
61  
62      /** Returns an iterator over the keys with non-null values. */
63      public Iterator keyIterator() {
64          return new KeyIterator( this );
65      }
66  
67      /** Returns an iterator over the non-null values. */
68      public Iterator iterator() {
69          return new ValueIterator( this );
70      }
71  
72      abstract class SmallNumberedMapIterator implements Iterator {
73          SmallNumberedMap map;
74          int cur = 0;
75          SmallNumberedMapIterator( SmallNumberedMap map ) {
76              this.map = map;
77              seekNext();
78          }
79          protected final void seekNext() {
80              try {
81                  while( map.values[cur] == null ) {
82                      cur++;
83                  }
84              } catch( ArrayIndexOutOfBoundsException   e ) {
85                  cur = -1;
86              }
87          }
88          public final boolean hasNext() { return cur != -1; }
89          public abstract Object   next();
90          public void remove() {
91              throw new RuntimeException  ( "Not implemented." );
92          }
93      }
94  
95      class KeyIterator extends SmallNumberedMapIterator {
96          KeyIterator( SmallNumberedMap map ) { super(map); }
97          public final Object   next() {
98              Numberable ret = array[cur];
99              cur++;
100             seekNext();
101             return ret;
102         }
103     }
104 
105     class ValueIterator extends SmallNumberedMapIterator {
106         ValueIterator( SmallNumberedMap map ) { super(map); }
107         public final Object   next() {
108             Object   ret = values[cur];
109             cur++;
110             seekNext();
111             return ret;
112         }
113     }
114 
115     /* Private stuff. */
116 
117     private final int findPosition( Numberable o ) {
118         int number = o.getNumber();
119         if( number == 0 ) throw new RuntimeException  ( "unnumbered" );
120         number = number & (array.length-1);
121         while(true) {
122             if( array[number] == o ) return number;
123             if( array[number] == null ) return number;
124             number = (number+1) & (array.length-1);
125         }
126     }
127     private final void doubleSize() {
128         int uniSize = universe.size();
129         if( array.length*128 > uniSize ) {
130             bits = new long[ uniSize/64+2 ];
131         }
132         Numberable[] oldArray = array;
133         Object  [] oldValues = values;
134         int newLength = array.length*2;
135         values = new Object  [newLength];
136         array = new Numberable[newLength];
137         for( int i = 0; i < oldArray.length; i++ ) {
138             Numberable element = oldArray[i];
139             if( element != null ) {
140                 int pos = findPosition(element);
141                 array[pos] = element;
142                 values[pos] = oldValues[i];
143             }
144         }
145     }
146     private Numberable[] array = new Numberable[8];
147     private Object  [] values = new Object  [8];
148     private long[] bits;
149     private int size = 0;
150     private ArrayNumberer universe;
151 }
152
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags