WeakHashSet


1   /*
2    * The contents of this file are subject to the terms of the Common Development
3    * and Distribution License (the License). You may not use this file except in
4    * compliance with the License.
5    *
6    * You can obtain a copy of the License at http://www.netbeans.org/cddl.html
7    * or http://www.netbeans.org/cddl.txt.
8    *
9    * When distributing Covered Code, include this CDDL Header Notice in each file
10   * and include the License file at http://www.netbeans.org/cddl.txt.
11   * If applicable, add the following below the CDDL Header, with the fields
12   * enclosed by brackets [] replaced by your own identifying information:
13   * "Portions Copyrighted [year] [name of copyright owner]"
14   *
15   * The Original Software is NetBeans. The Initial Developer of the Original
16   * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
17   * Microsystems, Inc. All Rights Reserved.
18   */
19  
20  // XXX what is wrong with org.openide.util.WeakSet??
21  
22  package org.netbeans.editor.ext.html;
23  
24  import java.lang.ref.WeakReference  ;
25  
26  /** This is a special set-like (not java.util.Set-like) class.
27   * It holds a set of objects referenced only weakly, and which
28   * can be get() by an equivalent object. It can be used e.g.
29   * as a lightweight (gc()-able) intern() for String or as a temporal storage
30   * for an algorithm creating a lot of long-lasting equals() immutables.
31   *
32   * @author  Petr Nejedly
33   * @version 1.0
34   */
35  public class WeakHashSet {
36  
37      Entry[] data;
38      // count of (possibly) active Entries
39      int count = 0;
40      // Number of Entries at which we rehash
41      int treshold;
42      float loadFactor;
43      
44      
45      /** Creates new WeakHashSet */
46      public WeakHashSet( int capacity, float loadFactor ) {
47          this.loadFactor = loadFactor;
48          treshold = (int)(capacity * loadFactor);
49          data = new Entry[capacity];
50      }
51      
52      /** Return the object equals to this object */
53      public Object   get( Object   obj ) {
54          if( obj == null ) return null;
55  
56          Entry[] tab = data;
57          Entry prev = null; 
58          int hash = obj.hashCode();
59          int index = (hash & 0x7FFFFFFF) % tab.length;
60          
61          for( Entry e = tab[index]; e != null; prev = e, e = e.next )
62              if( e.hash == hash ) {
63                  Object   value = e.value.get();
64                  if( value == null ) {
65                      // remove this entry from chain
66                      count--;
67                      if( prev == null ) tab[index] = e.next;
68                      else prev.next = e.next;
69                  } else {
70                      if( value.equals( obj ) ) return value;
71                  }
72              }
73      return null;
74      }
75      
76      public Object   put( Object   obj ) {
77          if( obj == null ) return null;
78          
79      Entry[] tab = data;
80          Entry prev = null;
81          int hash = obj.hashCode();
82          int index = (hash & 0x7FFFFFFF) % tab.length;
83  
84          for( Entry e = tab[index] ; e != null ; prev = e, e = e.next )
85              if( e.hash == hash ) {
86                  Object   value = e.value.get();
87                  if( value == null ) {
88                      count--;
89                      if( prev == null ) tab[index] = e.next;
90                      else prev.next = e.next;
91                  } else {
92                      if( value.equals( obj ) ) return value;
93                  }
94              }
95  
96          
97          if( count >= treshold ) {
98              rehash();
99              tab = data;
100             index = (hash & 0x7FFFFFFF) % tab.length;
101         }
102 
103         Entry e = new Entry( hash, obj, tab[index] );
104         tab[index] = e;
105         count++;
106             
107         return obj;
108     }    
109 
110     private void rehash() {
111     int oldCapacity = data.length;
112     Entry oldMap[] = data;
113 
114     int newCapacity = oldCapacity * 2 + 1;
115     Entry newMap[] = new Entry[newCapacity];
116 
117     treshold = (int)(newCapacity * loadFactor);
118     data = newMap;
119 
120     for( int i = oldCapacity ; i-- > 0 ; ) {
121         for( Entry old = oldMap[i] ; old != null ; ) {
122         Entry e = old;
123         old = old.next;
124 
125         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
126         e.next = newMap[index];
127         newMap[index] = e;
128         }
129     }
130     }
131 
132     
133     
134     
135     /**
136      * WeakHashSet collision list entry.
137      */
138     private static class Entry {
139     int hash;
140         WeakReference   value;
141     Entry next;
142 
143     Entry(int hash, Object   value, Entry next) {
144         this.hash = hash;
145         this.value = new WeakReference  ( value );
146         this.next = next;
147     }
148     }
149 
150 }
151
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags