KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 2000-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) 1999, 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  * This class is a symbol table implementation that guarantees that
62  * strings used as identifiers are unique references. Multiple calls
63  * to <code>addSymbol</code> will always return the same string
64  * reference.
65  * <p>
66  * The symbol table performs the same task as <code>String.intern()</code>
67  * with the following differences:
68  * <ul>
69  * <li>
70  * A new string object does not need to be created in order to
71  * retrieve a unique reference. Symbols can be added by using
72  * a series of characters in a character array.
73  * </li>
74  * <li>
75  * Users of the symbol table can provide their own symbol hashing
76  * implementation. For example, a simple string hashing algorithm
77  * may fail to produce a balanced set of hashcodes for symbols
78  * that are <em>mostly</em> unique. Strings with similar leading
79  * characters are especially prone to this poor hashing behavior.
80  * </li>
81  * </ul>
82  *
83  * @see SymbolHash
84  *
85  * @author Andy Clark
86  *
87  * @version $Id: SymbolTable.java,v 1.7 2002/02/07 22:15:09 neilg Exp $
88  */
89 public class SymbolTable {
90
91     //
92 // Constants
93 //
94
95     /** Default table size. */
96     protected static final int TABLE_SIZE = 101;
97
98     //
99 // Data
100 //
101
102     /** Buckets. */
103     protected Entry[] fBuckets = null;
104
105     // actual table size
106 protected int fTableSize;
107
108     //
109 // Constructors
110 //
111
112     /** Constructs a symbol table with a default number of buckets. */
113     public SymbolTable() {
114         this(TABLE_SIZE);
115     }
116
117     /** Constructs a symbol table with a specified number of buckets. */
118     public SymbolTable(int tableSize) {
119         fTableSize = tableSize;
120         fBuckets = new Entry[fTableSize];
121     }
122
123     //
124 // Public methods
125 //
126
127     /**
128      * Adds the specified symbol to the symbol table and returns a
129      * reference to the unique symbol. If the symbol already exists,
130      * the previous symbol reference is returned instead, in order
131      * guarantee that symbol references remain unique.
132      *
133      * @param symbol The new symbol.
134      */
135     public String JavaDoc addSymbol(String JavaDoc symbol) {
136
137         // search for identical symbol
138 int bucket = hash(symbol) % fTableSize;
139         int length = symbol.length();
140         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
141             if (length == entry.characters.length) {
142                 for (int i = 0; i < length; i++) {
143                     if (symbol.charAt(i) != entry.characters[i]) {
144                         continue OUTER;
145                     }
146                 }
147                 return entry.symbol;
148             }
149         }
150
151         // create new entry
152 Entry entry = new Entry(symbol, fBuckets[bucket]);
153         fBuckets[bucket] = entry;
154         return entry.symbol;
155
156     } // addSymbol(String):String
157
158     /**
159      * Adds the specified symbol to the symbol table and returns a
160      * reference to the unique symbol. If the symbol already exists,
161      * the previous symbol reference is returned instead, in order
162      * guarantee that symbol references remain unique.
163      *
164      * @param buffer The buffer containing the new symbol.
165      * @param offset The offset into the buffer of the new symbol.
166      * @param length The length of the new symbol in the buffer.
167      */
168     public String JavaDoc addSymbol(char[] buffer, int offset, int length) {
169
170         // search for identical symbol
171 int bucket = hash(buffer, offset, length) % fTableSize;
172         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
173             if (length == entry.characters.length) {
174                 for (int i = 0; i < length; i++) {
175                     if (buffer[offset + i] != entry.characters[i]) {
176                         continue OUTER;
177                     }
178                 }
179                 return entry.symbol;
180             }
181         }
182
183         // add new entry
184 Entry entry = new Entry(buffer, offset, length, fBuckets[bucket]);
185         fBuckets[bucket] = entry;
186         return entry.symbol;
187
188     } // addSymbol(char[],int,int):String
189
190     /**
191      * Returns a hashcode value for the specified symbol. The value
192      * returned by this method must be identical to the value returned
193      * by the <code>hash(char[],int,int)</code> method when called
194      * with the character array that comprises the symbol string.
195      *
196      * @param symbol The symbol to hash.
197      */
198     public int hash(String JavaDoc symbol) {
199
200         int code = 0;
201         int length = symbol.length();
202         for (int i = 0; i < length; i++) {
203             code = code * 37 + symbol.charAt(i);
204         }
205         return code & 0x7FFFFFF;
206
207     } // hash(String):int
208
209     /**
210      * Returns a hashcode value for the specified symbol information.
211      * The value returned by this method must be identical to the value
212      * returned by the <code>hash(String)</code> method when called
213      * with the string object created from the symbol information.
214      *
215      * @param buffer The character buffer containing the symbol.
216      * @param offset The offset into the character buffer of the start
217      * of the symbol.
218      * @param length The length of the symbol.
219      */
220     public int hash(char[] buffer, int offset, int length) {
221
222         int code = 0;
223         for (int i = 0; i < length; i++) {
224             code = code * 37 + buffer[offset + i];
225         }
226         return code & 0x7FFFFFF;
227
228     } // hash(char[],int,int):int
229
230     /**
231      * Returns true if the symbol table already contains the specified
232      * symbol.
233      *
234      * @param symbol The symbol to look for.
235      */
236     public boolean containsSymbol(String JavaDoc symbol) {
237
238         // search for identical symbol
239 int bucket = hash(symbol) % fTableSize;
240         int length = symbol.length();
241         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
242             if (length == entry.characters.length) {
243                 for (int i = 0; i < length; i++) {
244                     if (symbol.charAt(i) != entry.characters[i]) {
245                         continue OUTER;
246                     }
247                 }
248                 return true;
249             }
250         }
251
252         return false;
253
254     } // containsSymbol(String):boolean
255
256     /**
257      * Returns true if the symbol table already contains the specified
258      * symbol.
259      *
260      * @param buffer The buffer containing the symbol to look for.
261      * @param offset The offset into the buffer.
262      * @param length The length of the symbol in the buffer.
263      */
264     public boolean containsSymbol(char[] buffer, int offset, int length) {
265
266         // search for identical symbol
267 int bucket = hash(buffer, offset, length) % fTableSize;
268         OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
269             if (length == entry.characters.length) {
270                 for (int i = 0; i < length; i++) {
271                     if (buffer[offset + i] != entry.characters[i]) {
272                         continue OUTER;
273                     }
274                 }
275                 return true;
276             }
277         }
278
279         return false;
280
281     } // containsSymbol(char[],int,int):boolean
282
283     //
284 // Classes
285 //
286
287     /**
288      * This class is a symbol table entry. Each entry acts as a node
289      * in a linked list.
290      */
291     protected static final class Entry {
292
293         //
294 // Data
295 //
296
297         /** Symbol. */
298         public String JavaDoc symbol;
299
300         /**
301          * Symbol characters. This information is duplicated here for
302          * comparison performance.
303          */
304         public char[] characters;
305
306         /** The next entry. */
307         public Entry next;
308
309         //
310 // Constructors
311 //
312
313         /**
314          * Constructs a new entry from the specified symbol and next entry
315          * reference.
316          */
317         public Entry(String JavaDoc symbol, Entry next) {
318             this.symbol = symbol.intern();
319             characters = new char[symbol.length()];
320             symbol.getChars(0, characters.length, characters, 0);
321             this.next = next;
322         }
323
324         /**
325          * Constructs a new entry from the specified symbol information and
326          * next entry reference.
327          */
328         public Entry(char[] ch, int offset, int length, Entry next) {
329             characters = new char[length];
330             System.arraycopy(ch, offset, characters, 0, length);
331             symbol = new String JavaDoc(characters).intern();
332             this.next = next;
333         }
334
335     } // class Entry
336
337 } // class SymbolTable
338
Popular Tags