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