KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > modules > javacore > scanning > IntSet


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 package org.netbeans.modules.javacore.scanning;
21
22 import org.netbeans.modules.javacore.JMManager;
23
24 /**
25  * Fast set class for ints, loosely based java.util.HashTable, HashSet,
26  * and the discussion of hashtables from "Data Structures & Algorithms
27  * in Java" by Robert Lafore.
28  *
29  * @author Tom Ball
30  */
31 final class IntSet {
32     static class Entry {
33     int value;
34     int hash;
35     Entry next;
36
37     Entry(int v, int h, Entry n) {
38         value = v;
39         hash = h;
40         next = n;
41     }
42     }
43
44     private Entry[] table;
45     private int size;
46
47     private static final int LOAD_FACTOR = 2;
48     private static final int GROWTH_FACTOR = 2;
49
50     public IntSet() {
51     // 2048 is the max used by all of the JDK sources.
52 // Use fewer only if the set is referenced longer than
53 // the body of makeIndexes() above.
54 this(2048);
55     }
56
57     public IntSet(int capacity) {
58     table = new Entry[capacity];
59     }
60
61     public boolean add(int x) {
62     if (contains(x))
63         return false;
64
65     if (size > table.length / LOAD_FACTOR)
66         resize();
67
68     int h = hash(x);
69     int idx = indexFor(h, table.length);
70     Entry e = new Entry(x, h, table[idx]);
71     table[idx] = e;
72     size++;
73     return true;
74     }
75
76     public boolean contains(int x) {
77     int h = hash(x);
78     Entry e = table[indexFor(h, table.length)];
79     while (e != null) {
80         if (e.value == x)
81         return true;
82         e = e.next;
83     }
84     return false;
85     }
86
87     public int[] toArray() {
88     int[] arr = new int[size];
89     int n = 0;
90     Entry eNext;
91     for (int i = 0; i < table.length; i++)
92         for(Entry e = table[i]; e != null; e = e.next)
93         arr[n++] = e.value;
94     assert n == size;
95     return arr;
96     }
97
98     private void resize() {
99     Entry[] newt = new Entry[table.length * GROWTH_FACTOR];
100
101     Entry eNext;
102     for(int i = 0; i < table.length; i++)
103         for(Entry e = table[i]; e != null; e = eNext) {
104         int idx = indexFor(e.hash, newt.length);
105         eNext = e.next;
106         e.next = newt[idx];
107         newt[idx] = e;
108         }
109     table = newt;
110     JMManager.getLog().log("IntSet: table doubled to " + table.length);
111     }
112
113     // hash(), forIndex() from java.util.HashMap
114
115     /**
116      * Returns a hash value for the specified object. In addition to
117      * the object's own hashCode, this method applies a "supplemental
118      * hash function," which defends against poor quality hash functions.
119      * This is critical because HashMap uses power-of two length
120      * hash tables.<p>
121      *
122      * The shift distances in this function were chosen as the result
123      * of an automated search over the entire four-dimensional search space.
124      */
125     private static int hash(int h) {
126     h += ~(h << 9);
127     h ^= (h >>> 14);
128     h += (h << 4);
129     h ^= (h >>> 10);
130     return h;
131     }
132
133     /**
134      * Returns index for hash code h.
135      */
136     private static int indexFor(int h, int length) {
137     return h & (length-1);
138     }
139 }
140
Popular Tags