286N/A/*
286N/A * reserved comment block
286N/A * DO NOT REMOVE OR ALTER!
286N/A */
286N/A/*
286N/A * Copyright 2001, 2002,2004 The Apache Software Foundation.
286N/A *
286N/A * Licensed under the Apache License, Version 2.0 (the "License");
286N/A * you may not use this file except in compliance with the License.
286N/A * You may obtain a copy of the License at
286N/A *
286N/A * http://www.apache.org/licenses/LICENSE-2.0
286N/A *
286N/A * Unless required by applicable law or agreed to in writing, software
286N/A * distributed under the License is distributed on an "AS IS" BASIS,
286N/A * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
286N/A * See the License for the specific language governing permissions and
286N/A * limitations under the License.
286N/A */
286N/A
286N/Apackage com.sun.org.apache.xerces.internal.util;
286N/A
286N/A
286N/A/**
286N/A * This class is an unsynchronized hash table primary used for String
286N/A * to Object mapping.
286N/A * <p>
286N/A * The hash code uses the same algorithm as SymbolTable class.
286N/A *
286N/A * @author Elena Litani
286N/A * @version $Id: SymbolHash.java,v 1.7 2010-11-01 04:40:14 joehw Exp $
286N/A */
286N/Apublic class SymbolHash {
286N/A
286N/A //
286N/A // Constants
286N/A //
286N/A
286N/A /** Default table size. */
286N/A protected int fTableSize = 101;
286N/A
286N/A //
286N/A // Data
286N/A //
286N/A
286N/A /** Buckets. */
286N/A protected Entry[] fBuckets;
286N/A
286N/A /** Number of elements. */
286N/A protected int fNum = 0;
286N/A
286N/A //
286N/A // Constructors
286N/A //
286N/A
286N/A /** Constructs a key table with the default size. */
286N/A public SymbolHash() {
286N/A fBuckets = new Entry[fTableSize];
286N/A }
286N/A
286N/A /**
286N/A * Constructs a key table with a given size.
286N/A *
286N/A * @param size the size of the key table.
286N/A */
286N/A public SymbolHash(int size) {
286N/A fTableSize = size;
286N/A fBuckets = new Entry[fTableSize];
286N/A }
286N/A
286N/A //
286N/A // Public methods
286N/A //
286N/A
286N/A /**
286N/A * Adds the key/value mapping to the key table. If the key already exists,
286N/A * the previous value associated with this key is overwritten by the new
286N/A * value.
286N/A *
286N/A * @param key
286N/A * @param value
286N/A */
286N/A public void put(Object key, Object value) {
286N/A int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
286N/A Entry entry = search(key, bucket);
286N/A
286N/A // replace old value
286N/A if (entry != null) {
286N/A entry.value = value;
286N/A }
286N/A // create new entry
286N/A else {
286N/A entry = new Entry(key, value, fBuckets[bucket]);
286N/A fBuckets[bucket] = entry;
286N/A fNum++;
286N/A }
286N/A }
286N/A
286N/A /**
286N/A * Get the value associated with the given key.
286N/A *
286N/A * @param key
286N/A * @return the value associated with the given key.
286N/A */
286N/A public Object get(Object key) {
286N/A int bucket = (key.hashCode() & 0x7FFFFFFF) % fTableSize;
286N/A Entry entry = search(key, bucket);
286N/A if (entry != null) {
286N/A return entry.value;
286N/A }
286N/A return null;
286N/A }
286N/A
286N/A /**
286N/A * Get the number of key/value pairs stored in this table.
286N/A *
286N/A * @return the number of key/value pairs stored in this table.
286N/A */
286N/A public int getLength() {
286N/A return fNum;
286N/A }
286N/A
286N/A /**
286N/A * Add all values to the given array. The array must have enough entry.
286N/A *
286N/A * @param elements the array to store the elements
286N/A * @param from where to start store element in the array
286N/A * @return number of elements copied to the array
286N/A */
286N/A public int getValues(Object[] elements, int from) {
286N/A for (int i=0, j=0; i<fTableSize && j<fNum; i++) {
286N/A for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
286N/A elements[from+j] = entry.value;
286N/A j++;
286N/A }
286N/A }
286N/A return fNum;
286N/A }
286N/A
286N/A /**
286N/A * Return key/value pairs of all entries in the map
286N/A */
286N/A public Object[] getEntries() {
286N/A Object[] entries = new Object[fNum << 1];
286N/A for (int i=0, j=0; i<fTableSize && j<fNum << 1; i++) {
286N/A for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) {
286N/A entries[j] = entry.key;
286N/A entries[++j] = entry.value;
286N/A j++;
286N/A }
286N/A }
286N/A return entries;
286N/A }
286N/A
286N/A /**
286N/A * Make a clone of this object.
286N/A */
286N/A public SymbolHash makeClone() {
286N/A SymbolHash newTable = new SymbolHash(fTableSize);
286N/A newTable.fNum = fNum;
286N/A for (int i = 0; i < fTableSize; i++) {
286N/A if (fBuckets[i] != null)
286N/A newTable.fBuckets[i] = fBuckets[i].makeClone();
286N/A }
286N/A return newTable;
286N/A }
286N/A
286N/A /**
286N/A * Remove all key/value assocaition. This tries to save a bit of GC'ing
286N/A * by at least keeping the fBuckets array around.
286N/A */
286N/A public void clear() {
286N/A for (int i=0; i<fTableSize; i++) {
286N/A fBuckets[i] = null;
286N/A }
286N/A fNum = 0;
286N/A } // clear(): void
286N/A
286N/A protected Entry search(Object key, int bucket) {
286N/A // search for identical key
286N/A for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
286N/A if (key.equals(entry.key))
286N/A return entry;
286N/A }
286N/A return null;
286N/A }
286N/A
286N/A //
286N/A // Classes
286N/A //
286N/A
286N/A /**
286N/A * This class is a key table entry. Each entry acts as a node
286N/A * in a linked list.
286N/A */
286N/A protected static final class Entry {
286N/A // key/value
286N/A public Object key;
286N/A public Object value;
286N/A /** The next entry. */
286N/A public Entry next;
286N/A
286N/A public Entry() {
286N/A key = null;
286N/A value = null;
286N/A next = null;
286N/A }
286N/A
286N/A public Entry(Object key, Object value, Entry next) {
286N/A this.key = key;
286N/A this.value = value;
286N/A this.next = next;
286N/A }
286N/A
286N/A public Entry makeClone() {
286N/A Entry entry = new Entry();
286N/A entry.key = key;
286N/A entry.value = value;
286N/A if (next != null)
286N/A entry.next = next.makeClone();
286N/A return entry;
286N/A }
286N/A } // entry
286N/A
286N/A} // class SymbolHash