content: /*
   *  This file is part of AndroidIDE.
   *
   *  AndroidIDE is free software: you can redistribute it and/or modify
   *  it under the terms of the GNU General Public License as published by
   *  the Free Software Foundation, either version 3 of the License, or
   *  (at your option) any later version.
   *
   *  AndroidIDE is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *   along with AndroidIDE.  If not, see <https://www.gnu.org/licenses/>.
   */
  
  /*
   * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
   */
  
  /*
   * Copyright 2005 The Apache Software Foundation.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package jaxp.sun.org.apache.xerces.internal.util;
  
  /**
   * This class is a symbol table implementation that guarantees that
   * strings used as identifiers are unique references. Multiple calls
   * to <code>addSymbol</code> will always return the same string
   * reference.
   * <p>
   * The symbol table performs the same task as <code>String.intern()</code>
   * with the following differences:
   * <ul>
   *  <li>
   *   A new string object does not need to be created in order to
   *   retrieve a unique reference. Symbols can be added by using
   *   a series of characters in a character array.
   *  </li>
   *  <li>
   *   Users of the symbol table can provide their own symbol hashing
   *   implementation. For example, a simple string hashing algorithm
   *   may fail to produce a balanced set of hashcodes for symbols
   *   that are <em>mostly</em> unique. Strings with similar leading
   *   characters are especially prone to this poor hashing behavior.
   *  </li>
   * </ul>
   *
   * @see SymbolHash
   *
   * @author Andy Clark
   *
   */
  public class SymbolTable {
  
      //
      // Constants
      //
  
      /** Default table size. */
      protected static final int TABLE_SIZE = 173;
  
  
      /** Buckets. */
      protected Entry[] fBuckets = null;
  
      // actual table size
      protected int fTableSize;
  
      //
      // Constructors
      //
  
      /** Constructs a symbol table with a default number of buckets. */
      public SymbolTable() {
          this(TABLE_SIZE);
      }
  
      /** Constructs a symbol table with a specified number of buckets. */
      public SymbolTable(int tableSize) {
          fTableSize = tableSize;
          fBuckets = new Entry[fTableSize];
      }
  
      //
      // Public methods
      //
  
      /**
       * Adds the specified symbol to the symbol table and returns a
       * reference to the unique symbol. If the symbol already exists,
       * the previous symbol reference is returned instead, in order
       * guarantee that symbol references remain unique.
       *
       * @param symbol The new symbol.
       */
      public String addSymbol(String symbol) {
  
          // search for identical symbol
          final int hash = hash(symbol);
          final int bucket = hash % fTableSize;
          final int length = symbol.length();
          OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
              if (length == entry.characters.length && hash == entry.hashCode) {
                  if(symbol.regionMatches(0,entry.symbol,0,length)){
                      return entry.symbol;
                  }
                  else{
                      continue OUTER;
                  }
                  /**
                  for (int i = 0; i < length; i++) {
                      if (symbol.charAt(i) != entry.characters[i]) {
                          continue OUTER;
                      }
                  }
                  symbolAsArray = entry.characters;
                  return entry.symbol;
                   */
              }
          }
  
          // create new entry
          Entry entry = new Entry(symbol, fBuckets[bucket]);
          entry.hashCode = hash;
          fBuckets[bucket] = entry;
          return entry.symbol;
  
      } // addSymbol(String):String
  
      /**
       * Adds the specified symbol to the symbol table and returns a
       * reference to the unique symbol. If the symbol already exists,
       * the previous symbol reference is returned instead, in order
       * guarantee that symbol references remain unique.
       *
       * @param buffer The buffer containing the new symbol.
       * @param offset The offset into the buffer of the new symbol.
       * @param length The length of the new symbol in the buffer.
       */
      public String addSymbol(char[] buffer, int offset, int length) {
          // search for identical symbol
          int hash = hash(buffer, offset, length);
          int bucket = hash % fTableSize;
          OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
              if (length == entry.characters.length && hash ==entry.hashCode) {
                  for (int i = 0; i < length; i++) {
                      if (buffer[offset + i] != entry.characters[i]) {
                          continue OUTER;
                      }
                  }
                  return entry.symbol;
              }
          }
  
          // add new entry
          Entry entry = new Entry(buffer, offset, length, fBuckets[bucket]);
          fBuckets[bucket] = entry;
          entry.hashCode = hash;
          return entry.symbol;
  
      } // addSymbol(char[],int,int):String
  
      /**
       * Returns a hashcode value for the specified symbol. The value
       * returned by this method must be identical to the value returned
       * by the <code>hash(char[],int,int)</code> method when called
       * with the character array that comprises the symbol string.
       *
       * @param symbol The symbol to hash.
       */
      public int hash(String symbol) {
  
          int code = 0;
          int length = symbol.length();
          for (int i = 0; i < length; i++) {
              code = code * 37 + symbol.charAt(i);
          }
          return code & 0x7FFFFFFF;
  
      } // hash(String):int
  
      /**
       * Returns a hashcode value for the specified symbol information.
       * The value returned by this method must be identical to the value
       * returned by the <code>hash(String)</code> method when called
       * with the string object created from the symbol information.
       *
       * @param buffer The character buffer containing the symbol.
       * @param offset The offset into the character buffer of the start
       *               of the symbol.
       * @param length The length of the symbol.
       */
      public int hash(char[] buffer, int offset, int length) {
  
          int code = 0;
          for (int i = 0; i < length; i++) {
              code = code * 37 + buffer[offset + i];
          }
          return code & 0x7FFFFFFF;
  
      } // hash(char[],int,int):int
  
      /**
       * Returns true if the symbol table already contains the specified
       * symbol.
       *
       * @param symbol The symbol to look for.
       */
      public boolean containsSymbol(String symbol) {
  
          // search for identical symbol
          int hash = hash(symbol);
          int bucket = hash % fTableSize;
          int length = symbol.length();
          OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
              if (length == entry.characters.length && hash == entry.hashCode) {
                  if(symbol.regionMatches(0,entry.symbol,0,length)){
                      return true;
                  }
                  else {
                      continue OUTER;
                  }
                  /**
                  for (int i = 0; i < length; i++) {
                      if (symbol.charAt(i) != entry.characters[i]) {
                          continue OUTER;
                      }
                  }
                   return true;
                   */
              }
          }
  
          return false;
  
      } // containsSymbol(String):boolean
  
      /**
       * Returns true if the symbol table already contains the specified
       * symbol.
       *
       * @param buffer The buffer containing the symbol to look for.
       * @param offset The offset into the buffer.
       * @param length The length of the symbol in the buffer.
       */
      public boolean containsSymbol(char[] buffer, int offset, int length) {
  
          // search for identical symbol
          int hash = hash(buffer, offset, length) ;
          int bucket = hash % fTableSize;
          OUTER: for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) {
              if (length == entry.characters.length && hash == entry.hashCode) {
                  for (int i = 0; i < length; i++) {
                      if (buffer[offset + i] != entry.characters[i]) {
                          continue OUTER;
                      }
                  }
                  return true;
              }
          }
  
          return false;
  
      } // containsSymbol(char[],int,int):boolean
  
  
      //
      // Classes
      //
  
      /**
       * This class is a symbol table entry. Each entry acts as a node
       * in a linked list.
       */
      protected static final class Entry {
  
          //
          // Data
          //
  
          /** Symbol. */
          public String symbol;
          int hashCode = 0;
  
          /**
           * Symbol characters. This information is duplicated here for
           * comparison performance.
           */
          public char[] characters;
  
          /** The next entry. */
          public Entry next;
  
          //
          // Constructors
          //
  
          /**
           * Constructs a new entry from the specified symbol and next entry
           * reference.
           */
          public Entry(String symbol, Entry next) {
              this.symbol = symbol.intern();
              characters = new char[symbol.length()];
              symbol.getChars(0, characters.length, characters, 0);
              this.next = next;
          }
  
          /**
           * Constructs a new entry from the specified symbol information and
           * next entry reference.
           */
          public Entry(char[] ch, int offset, int length, Entry next) {
              characters = new char[length];
              System.arraycopy(ch, offset, characters, 0, length);
              symbol = new String(characters).intern();
              this.next = next;
          }
  
      } // class Entry
  
  } // class SymbolTable
  