KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xerces > util > SymbolHash


1 /*
2  * Copyright 2001, 2002,2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.apache.xerces.util;
18
19
20 /**
21  * This class is an unsynchronized hash table primary used for String
22  * to Object mapping.
23  * <p>
24  * The hash code uses the same algorithm as SymbolTable class.
25  *
26  * @author Elena Litani
27  * @version $Id: SymbolHash.java,v 1.8 2004/02/24 23:15:53 mrglavas Exp $
28  */
29 public class SymbolHash {
30
31     //
32 // Constants
33 //
34
35     /** Default table size. */
36     protected int fTableSize = 101;
37
38     //
39 // Data
40 //
41
42     /** Buckets. */
43     protected Entry[] fBuckets;
44
45     /** Number of elements. */
46     protected int fNum = 0;
47
48     //
49 // Constructors
50 //
51
52     /** Constructs a key table with the default size. */
53     public SymbolHash() {
54         fBuckets = new Entry[fTableSize];
55     }
56
57     /**
58      * Constructs a key table with a given size.
59      *
60      * @param size the size of the key table.
61      */
62     public SymbolHash(int size) {
63         fTableSize = size;
64         fBuckets = new Entry[fTableSize];
65     }
66
67     //
68 // Public methods
69 //
70
71     /**
72      * Adds the key/value mapping to the key table. If the key already exists,
73      * the previous value associated with this key is overwritten by the new
74      * value.
75      *
76      * @param key
77      * @param value
78      */
79     public void put(Object JavaDoc key, Object JavaDoc value) {
80         int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
81         Entry entry = search(key, bucket);
82
83         // replace old value
84 if (entry != null) {
85             entry.value = value;
86         }
87         // create new entry
88 else {
89             entry = new Entry(key, value, fBuckets[bucket]);
90             fBuckets[bucket] = entry;
91             fNum++;
92         }
93     }
94
95     /**
96      * Get the value associated with the given key.
97      *
98      * @param key
99      * @return the value associated with the given key.
100      */
101     public Object JavaDoc get(Object JavaDoc key) {
102         int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
103         Entry entry = search(key, bucket);
104         if (entry != null) {
105             return entry.value;
106         }
107         return null;
108     }
109
110     /**
111      * Get the number of key/value pairs stored in this table.
112      *
113      * @return the number of key/value pairs stored in this table.
114      */
115     public int getLength() {
116         return fNum;
117     }
118     
119     /**
120      * Add all values to the given array. The array must have enough entry.
121      *
122      * @param elements the array to store the elements
123      * @param from where to start store element in the array
124      * @return number of elements copied to the array
125      */
126     public int getValues(Object JavaDoc[] elements, int from) {
127         for (int i=0, j=0; i<fTableSize && j<fNum; i++) {
128             for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
129                 elements[from+j] = entry.value;
130                 j++;
131             }
132         }
133         return fNum;
134     }
135     
136     /**
137      * Make a clone of this object.
138      */
139     public SymbolHash makeClone() {
140         SymbolHash newTable = new SymbolHash(fTableSize);
141         newTable.fNum = fNum;
142         for (int i = 0; i < fTableSize; i++) {
143             if (fBuckets[i] != null)
144                 newTable.fBuckets[i] = fBuckets[i].makeClone();
145         }
146         return newTable;
147     }
148     
149     /**
150      * Remove all key/value assocaition. This tries to save a bit of GC'ing
151      * by at least keeping the fBuckets array around.
152      */
153     public void clear() {
154         for (int i=0; i<fTableSize; i++) {
155             fBuckets[i] = null;
156         }
157         fNum = 0;
158     } // clear(): void
159
160     protected Entry search(Object JavaDoc key, int bucket) {
161         // search for identical key
162 for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
163             if (key.equals(entry.key))
164                 return entry;
165         }
166         return null;
167     }
168     
169     //
170 // Classes
171 //
172
173     /**
174      * This class is a key table entry. Each entry acts as a node
175      * in a linked list.
176      */
177     protected static final class Entry {
178         // key/value
179 public Object JavaDoc key;
180         public Object JavaDoc value;
181         /** The next entry. */
182         public Entry next;
183
184         public Entry() {
185             key = null;
186             value = null;
187             next = null;
188         }
189
190         public Entry(Object JavaDoc key, Object JavaDoc value, Entry next) {
191             this.key = key;
192             this.value = value;
193             this.next = next;
194         }
195         
196         public Entry makeClone() {
197             Entry entry = new Entry();
198             entry.key = key;
199             entry.value = value;
200             if (next != null)
201                 entry.next = next.makeClone();
202             return entry;
203         }
204     } // entry
205
206 } // class SymbolHash
207
208
Popular Tags