KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > org > apache > xerces > internal > util > SymbolHash


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 2001, 2002 The Apache Software Foundation. All rights
6  * reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Apache Software Foundation (http://www.apache.org/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Xerces" and "Apache Software Foundation" must
28  * not be used to endorse or promote products derived from this
29  * software without prior written permission. For written
30  * permission, please contact apache@apache.org.
31  *
32  * 5. Products derived from this software may not be called "Apache",
33  * nor may "Apache" appear in their name, without prior written
34  * permission of the Apache Software Foundation.
35  *
36  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
37  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
38  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
39  * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
43  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
44  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
45  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
46  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This software consists of voluntary contributions made by many
51  * individuals on behalf of the Apache Software Foundation and was
52  * originally based on software copyright (c) 2001, International
53  * Business Machines, Inc., http://www.apache.org. For more
54  * information on the Apache Software Foundation, please see
55  * <http://www.apache.org/>.
56  */
57
58 package com.sun.org.apache.xerces.internal.util;
59
60
61 /**
62  * This class is an unsynchronized hash table primary used for String
63  * to Object mapping.
64  * <p>
65  * The hash code uses the same algorithm as SymbolTable class.
66  *
67  * @author Elena Litani
68  * @version $Id: SymbolHash.java,v 1.7 2003/05/08 20:12:00 elena Exp $
69  */
70 public class SymbolHash {
71
72     //
73 // Constants
74 //
75
76     /** Default table size. */
77     protected int fTableSize = 101;
78
79     //
80 // Data
81 //
82
83     /** Buckets. */
84     protected Entry[] fBuckets;
85
86     /** Number of elements. */
87     protected int fNum = 0;
88
89     //
90 // Constructors
91 //
92
93     /** Constructs a key table with the default size. */
94     public SymbolHash() {
95         fBuckets = new Entry[fTableSize];
96     }
97
98     /**
99      * Constructs a key table with a given size.
100      *
101      * @param size the size of the key table.
102      */
103     public SymbolHash(int size) {
104         fTableSize = size;
105         fBuckets = new Entry[fTableSize];
106     }
107
108     //
109 // Public methods
110 //
111
112     /**
113      * Adds the key/value mapping to the key table. If the key already exists,
114      * the previous value associated with this key is overwritten by the new
115      * value.
116      *
117      * @param key
118      * @param value
119      */
120     public void put(Object JavaDoc key, Object JavaDoc value) {
121         int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
122         Entry entry = search(key, bucket);
123
124         // replace old value
125 if (entry != null) {
126             entry.value = value;
127         }
128         // create new entry
129 else {
130             entry = new Entry(key, value, fBuckets[bucket]);
131             fBuckets[bucket] = entry;
132             fNum++;
133         }
134     }
135
136     /**
137      * Get the value associated with the given key.
138      *
139      * @param key
140      * @return the value associated with the given key.
141      */
142     public Object JavaDoc get(Object JavaDoc key) {
143         int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
144         Entry entry = search(key, bucket);
145         if (entry != null) {
146             return entry.value;
147         }
148         return null;
149     }
150
151     /**
152      * Get the number of key/value pairs stored in this table.
153      *
154      * @return the number of key/value pairs stored in this table.
155      */
156     public int getLength() {
157         return fNum;
158     }
159     
160     /**
161      * Add all values to the given array. The array must have enough entry.
162      *
163      * @param elements the array to store the elements
164      * @param from where to start store element in the array
165      * @return number of elements copied to the array
166      */
167     public int getValues(Object JavaDoc[] elements, int from) {
168         for (int i=0, j=0; i<fTableSize && j<fNum; i++) {
169             for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
170                 elements[from+j] = entry.value;
171                 j++;
172             }
173         }
174         return fNum;
175     }
176     
177     /**
178      * Make a clone of this object.
179      */
180     public SymbolHash makeClone() {
181         SymbolHash newTable = new SymbolHash(fTableSize);
182         newTable.fNum = fNum;
183         for (int i = 0; i < fTableSize; i++) {
184             if (fBuckets[i] != null)
185                 newTable.fBuckets[i] = fBuckets[i].makeClone();
186         }
187         return newTable;
188     }
189     
190     /**
191      * Remove all key/value assocaition. This tries to save a bit of GC'ing
192      * by at least keeping the fBuckets array around.
193      */
194     public void clear() {
195         for (int i=0; i<fTableSize; i++) {
196             fBuckets[i] = null;
197         }
198         fNum = 0;
199     } // clear(): void
200
201     protected Entry search(Object JavaDoc key, int bucket) {
202         // search for identical key
203 for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
204             if (key.equals(entry.key))
205                 return entry;
206         }
207         return null;
208     }
209     
210     //
211 // Classes
212 //
213
214     /**
215      * This class is a key table entry. Each entry acts as a node
216      * in a linked list.
217      */
218     protected static final class Entry {
219         // key/value
220 public Object JavaDoc key;
221         public Object JavaDoc value;
222         /** The next entry. */
223         public Entry next;
224
225         public Entry() {
226             key = null;
227             value = null;
228             next = null;
229         }
230
231         public Entry(Object JavaDoc key, Object JavaDoc value, Entry next) {
232             this.key = key;
233             this.value = value;
234             this.next = next;
235         }
236         
237         public Entry makeClone() {
238             Entry entry = new Entry();
239             entry.key = key;
240             entry.value = value;
241             if (next != null)
242                 entry.next = next.makeClone();
243             return entry;
244         }
245     } // entry
246
247 } // class SymbolHash
248
249
Popular Tags