KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > batik > dom > util > DoublyIndexedTable


1 /*
2
3    Copyright 2001 The Apache Software Foundation
4
5    Licensed under the Apache License, Version 2.0 (the "License");
6    you may not use this file except in compliance with the License.
7    You may obtain a copy of the License at
8
9        http://www.apache.org/licenses/LICENSE-2.0
10
11    Unless required by applicable law or agreed to in writing, software
12    distributed under the License is distributed on an "AS IS" BASIS,
13    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14    See the License for the specific language governing permissions and
15    limitations under the License.
16
17  */
18 package org.apache.batik.dom.util;
19
20 /**
21  * This class represents a doubly indexed hash table.
22  *
23  * @author <a HREF="mailto:stephane@hillion.org">Stephane Hillion</a>
24  * @version $Id: DoublyIndexedTable.java,v 1.3 2004/08/18 07:13:37 vhardy Exp $
25  */
26 public class DoublyIndexedTable {
27     
28     /**
29      * The initial capacity
30      */
31     protected final static int INITIAL_CAPACITY = 11;
32
33     /**
34      * The underlying array
35      */
36     protected Entry[] table;
37         
38     /**
39      * The number of entries
40      */
41     protected int count;
42         
43     /**
44      * Creates a new DoublyIndexedTable.
45      */
46     public DoublyIndexedTable() {
47         table = new Entry[INITIAL_CAPACITY];
48     }
49
50     /**
51      * Creates a new DoublyIndexedTable.
52      * @param c The inital capacity.
53      */
54     public DoublyIndexedTable(int c) {
55         table = new Entry[c];
56     }
57
58     /**
59      * Returns the size of this table.
60      */
61     public int size() {
62     return count;
63     }
64     
65     /**
66      * Puts a value in the table.
67      * @return the old value or null
68      */
69     public Object JavaDoc put(Object JavaDoc o1, Object JavaDoc o2, Object JavaDoc value) {
70         int hash = hashCode(o1, o2) & 0x7FFFFFFF;
71         int index = hash % table.length;
72     
73         for (Entry e = table[index]; e != null; e = e.next) {
74             if ((e.hash == hash) && e.match(o1, o2)) {
75                 Object JavaDoc old = e.value;
76                 e.value = value;
77                 return old;
78             }
79         }
80     
81         // The key is not in the hash table
82 int len = table.length;
83         if (count++ >= (len * 3) >>> 2) {
84             rehash();
85             index = hash % table.length;
86         }
87             
88         Entry e = new Entry(hash, o1, o2, value, table[index]);
89         table[index] = e;
90         return null;
91     }
92
93     /**
94      * Gets the value of an entry
95      * @return the value or null
96      */
97     public Object JavaDoc get(Object JavaDoc o1, Object JavaDoc o2) {
98         int hash = hashCode(o1, o2) & 0x7FFFFFFF;
99         int index = hash % table.length;
100     
101         for (Entry e = table[index]; e != null; e = e.next) {
102             if ((e.hash == hash) && e.match(o1, o2)) {
103                 return e.value;
104             }
105         }
106         return null;
107     }
108     
109     /**
110      * Rehash the table
111      */
112     protected void rehash () {
113         Entry[] oldTable = table;
114     
115         table = new Entry[oldTable.length * 2 + 1];
116     
117         for (int i = oldTable.length-1; i >= 0; i--) {
118             for (Entry old = oldTable[i]; old != null;) {
119                 Entry e = old;
120                 old = old.next;
121                     
122                 int index = e.hash % table.length;
123                 e.next = table[index];
124                 table[index] = e;
125             }
126         }
127     }
128
129     /**
130      * Computes a hash code corresponding to the given objects.
131      */
132     protected int hashCode(Object JavaDoc o1, Object JavaDoc o2) {
133         int result = (o1 == null) ? 0 : o1.hashCode();
134         return result ^ ((o2 == null) ? 0 : o2.hashCode());
135     }
136
137     /**
138      * To manage collisions
139      */
140     protected static class Entry {
141     /**
142      * The hash code
143      */
144     public int hash;
145     
146     /**
147      * The first key
148      */
149     public Object JavaDoc key1;
150     
151     /**
152      * The second key
153      */
154     public Object JavaDoc key2;
155     
156     /**
157      * The value
158      */
159     public Object JavaDoc value;
160     
161     /**
162      * The next entry
163      */
164     public Entry next;
165     
166     /**
167      * Creates a new entry
168      */
169     public Entry(int hash, Object JavaDoc key1, Object JavaDoc key2, Object JavaDoc value, Entry next) {
170         this.hash = hash;
171         this.key1 = key1;
172         this.key2 = key2;
173         this.value = value;
174         this.next = next;
175     }
176
177         /**
178          * Whether this entry match the given keys.
179          */
180         public boolean match(Object JavaDoc o1, Object JavaDoc o2) {
181             if (key1 != null) {
182                 if (!key1.equals(o1)) {
183                     return false;
184                 }
185             } else if (o1 != null) {
186                 return false;
187             }
188             if (key2 != null) {
189                 return key2.equals(o2);
190             }
191             return o2 == null;
192         }
193     }
194 }
195
Popular Tags