KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > jasper > xmlparser > SymbolTable


1 /*
2  * Licensed to the Apache Software Foundation (ASF) under one or more
3  * contributor license agreements. See the NOTICE file distributed with
4  * this work for additional information regarding copyright ownership.
5  * The ASF licenses this file to You under the Apache License, Version 2.0
6  * (the "License"); you may not use this file except in compliance with
7  * the License. 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  * This software consists of voluntary contributions made by many
19  * individuals on behalf of the Apache Software Foundation and was
20  * originally based on software copyright (c) 1999, International
21  * Business Machines, Inc., http://www.apache.org. For more
22  * information on the Apache Software Foundation, please see
23  * <http://www.apache.org/>.
24  */
25
26 package org.apache.jasper.xmlparser;
27
28 /**
29  * This class is a symbol table implementation that guarantees that
30  * strings used as identifiers are unique references. Multiple calls
31  * to <code>addSymbol</code> will always return the same string
32  * reference.
33  * <p>
34  * The symbol table performs the same task as <code>String.intern()</code>
35  * with the following differences:
36  * <ul>
37  * <li>
38  * A new string object does not need to be created in order to
39  * retrieve a unique reference. Symbols can be added by using
40  * a series of characters in a character array.
41  * </li>
42  * <li>
43  * Users of the symbol table can provide their own symbol hashing
44  * implementation. For example, a simple string hashing algorithm
45  * may fail to produce a balanced set of hashcodes for symbols
46  * that are <em>mostly</em> unique. Strings with similar leading
47  * characters are especially prone to this poor hashing behavior.
48  * </li>
49  * </ul>
50  *
51  * @author Andy Clark
52  * @version $Id: SymbolTable.java 467222 2006-10-24 03:17:11Z markt $
53  */
54 public class SymbolTable {
55
56     //
57 // Constants
58 //
59
60     /** Default table size. */
61     protected static final int TABLE_SIZE = 101;
62
63     //
64 // Data
65 //
66
67     /** Buckets. */
68     protected Entry[] fBuckets = null;
69
70     // actual table size
71 protected int fTableSize;
72
73     //
74 // Constructors
75 //
76
77     /** Constructs a symbol table with a default number of buckets. */
78     public SymbolTable() {
79         this(TABLE_SIZE);
80     }
81
82     /** Constructs a symbol table with a specified number of buckets. */
83     public SymbolTable(int tableSize) {
84         fTableSize = tableSize;
85         fBuckets = new Entry[fTableSize];
86     }
87
88     //
89 // Public methods
90 //
91
92     /**
93      * Adds the specified symbol to the symbol table and returns a
94      * reference to the unique symbol. If the symbol already exists,
95      * the previous symbol reference is returned instead, in order
96      * guarantee that symbol references remain unique.
97      *
98      * @param symbol The new symbol.
99      */
100     public String JavaDoc addSymbol(String JavaDoc symbol) {
101
102         // search for identical symbol
103 int bucket = hash(symbol) % fTableSize;
104         int length = symbol.length();
105         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
106             if (length == entry.characters.length) {
107                 for (int i = 0; i < length; i++) {
108                     if (symbol.charAt(i) != entry.characters[i]) {
109                         continue OUTER;
110                     }
111                 }
112                 return entry.symbol;
113             }
114         }
115
116         // create new entry
117 Entry entry = new Entry(symbol, fBuckets[bucket]);
118         fBuckets[bucket] = entry;
119         return entry.symbol;
120
121     } // addSymbol(String):String
122
123     /**
124      * Adds the specified symbol to the symbol table and returns a
125      * reference to the unique symbol. If the symbol already exists,
126      * the previous symbol reference is returned instead, in order
127      * guarantee that symbol references remain unique.
128      *
129      * @param buffer The buffer containing the new symbol.
130      * @param offset The offset into the buffer of the new symbol.
131      * @param length The length of the new symbol in the buffer.
132      */
133     public String JavaDoc addSymbol(char[] buffer, int offset, int length) {
134
135         // search for identical symbol
136 int bucket = hash(buffer, offset, length) % fTableSize;
137         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
138             if (length == entry.characters.length) {
139                 for (int i = 0; i < length; i++) {
140                     if (buffer[offset + i] != entry.characters[i]) {
141                         continue OUTER;
142                     }
143                 }
144                 return entry.symbol;
145             }
146         }
147
148         // add new entry
149 Entry entry = new Entry(buffer, offset, length, fBuckets[bucket]);
150         fBuckets[bucket] = entry;
151         return entry.symbol;
152
153     } // addSymbol(char[],int,int):String
154
155     /**
156      * Returns a hashcode value for the specified symbol. The value
157      * returned by this method must be identical to the value returned
158      * by the <code>hash(char[],int,int)</code> method when called
159      * with the character array that comprises the symbol string.
160      *
161      * @param symbol The symbol to hash.
162      */
163     public int hash(String JavaDoc symbol) {
164
165         int code = 0;
166         int length = symbol.length();
167         for (int i = 0; i < length; i++) {
168             code = code * 37 + symbol.charAt(i);
169         }
170         return code & 0x7FFFFFF;
171
172     } // hash(String):int
173
174     /**
175      * Returns a hashcode value for the specified symbol information.
176      * The value returned by this method must be identical to the value
177      * returned by the <code>hash(String)</code> method when called
178      * with the string object created from the symbol information.
179      *
180      * @param buffer The character buffer containing the symbol.
181      * @param offset The offset into the character buffer of the start
182      * of the symbol.
183      * @param length The length of the symbol.
184      */
185     public int hash(char[] buffer, int offset, int length) {
186
187         int code = 0;
188         for (int i = 0; i < length; i++) {
189             code = code * 37 + buffer[offset + i];
190         }
191         return code & 0x7FFFFFF;
192
193     } // hash(char[],int,int):int
194
195     /**
196      * Returns true if the symbol table already contains the specified
197      * symbol.
198      *
199      * @param symbol The symbol to look for.
200      */
201     public boolean containsSymbol(String JavaDoc symbol) {
202
203         // search for identical symbol
204 int bucket = hash(symbol) % fTableSize;
205         int length = symbol.length();
206         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
207             if (length == entry.characters.length) {
208                 for (int i = 0; i < length; i++) {
209                     if (symbol.charAt(i) != entry.characters[i]) {
210                         continue OUTER;
211                     }
212                 }
213                 return true;
214             }
215         }
216
217         return false;
218
219     } // containsSymbol(String):boolean
220
221     /**
222      * Returns true if the symbol table already contains the specified
223      * symbol.
224      *
225      * @param buffer The buffer containing the symbol to look for.
226      * @param offset The offset into the buffer.
227      * @param length The length of the symbol in the buffer.
228      */
229     public boolean containsSymbol(char[] buffer, int offset, int length) {
230
231         // search for identical symbol
232 int bucket = hash(buffer, offset, length) % fTableSize;
233         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
234             if (length == entry.characters.length) {
235                 for (int i = 0; i < length; i++) {
236                     if (buffer[offset + i] != entry.characters[i]) {
237                         continue OUTER;
238                     }
239                 }
240                 return true;
241             }
242         }
243
244         return false;
245
246     } // containsSymbol(char[],int,int):boolean
247
248     //
249 // Classes
250 //
251
252     /**
253      * This class is a symbol table entry. Each entry acts as a node
254      * in a linked list.
255      */
256     protected static final class Entry {
257
258         //
259 // Data
260 //
261
262         /** Symbol. */
263         public String JavaDoc symbol;
264
265         /**
266          * Symbol characters. This information is duplicated here for
267          * comparison performance.
268          */
269         public char[] characters;
270
271         /** The next entry. */
272         public Entry next;
273
274         //
275 // Constructors
276 //
277
278         /**
279          * Constructs a new entry from the specified symbol and next entry
280          * reference.
281          */
282         public Entry(String JavaDoc symbol, Entry next) {
283             this.symbol = symbol.intern();
284             characters = new char[symbol.length()];
285             symbol.getChars(0, characters.length, characters, 0);
286             this.next = next;
287         }
288
289         /**
290          * Constructs a new entry from the specified symbol information and
291          * next entry reference.
292          */
293         public Entry(char[] ch, int offset, int length, Entry next) {
294             characters = new char[length];
295             System.arraycopy(ch, offset, characters, 0, length);
296             symbol = new String JavaDoc(characters).intern();
297             this.next = next;
298         }
299
300     } // class Entry
301
302 } // class SymbolTable
303
Popular Tags