1 // Jericho HTML Parser - Java based library for analysing and manipulating HTML 2 // Version 3.2 3 // Copyright (C) 2004-2009 Martin Jericho 4 // http://jericho.htmlparser.net/ 5 // 6 // This library is free software; you can redistribute it and/or 7 // modify it under the terms of either one of the following licences: 8 // 9 // 1. The Eclipse Public License (EPL) version 1.0, 10 // included in this distribution in the file licence-epl-1.0.html 11 // or available at http://www.eclipse.org/legal/epl-v10.html 12 // 13 // 2. The GNU Lesser General Public License (LGPL) version 2.1 or later, 14 // included in this distribution in the file licence-lgpl-2.1.txt 15 // or available at http://www.gnu.org/licenses/lgpl.txt 16 // 17 // This library is distributed on an "AS IS" basis, 18 // WITHOUT WARRANTY OF ANY KIND, either express or implied. 19 // See the individual licence texts for more details. 20 21 package net.htmlparser.jericho; 22 23 import java.util.*; 24 25 /** 26 * This is an internal class used to efficiently map integers to strings, which is used in the CharacterEntityReference class. 27 */ 28 final class IntStringHashMap { 29 private static final int DEFAULT_INITIAL_CAPACITY=15; 30 private static final float DEFAULT_LOAD_FACTOR=0.75f; 31 private transient Entry[] entries; // length must always be a power of 2. 32 private transient int size; 33 private int threshold; 34 private float loadFactor; 35 private int bitmask; // always entries.length-1 36 IntStringHashMap(int initialCapacity, final float loadFactor)37 public IntStringHashMap(int initialCapacity, final float loadFactor) { 38 this.loadFactor=loadFactor; 39 int capacity=1; 40 while (capacity<initialCapacity) capacity<<=1; 41 threshold=(int)(capacity*loadFactor); 42 entries=new Entry[capacity]; 43 bitmask=capacity-1; 44 } 45 IntStringHashMap(final int initialCapacity)46 public IntStringHashMap(final int initialCapacity) { 47 this(initialCapacity,DEFAULT_LOAD_FACTOR); 48 } 49 IntStringHashMap()50 public IntStringHashMap() { 51 this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR); 52 } 53 size()54 public int size() { 55 return size; 56 } 57 isEmpty()58 public boolean isEmpty() { 59 return size==0; 60 } 61 getIndex(final int key)62 private int getIndex(final int key) { 63 return key&bitmask; // equivalent to (key%entries.length) but more efficient. 64 } 65 get(final int key)66 public String get(final int key) { 67 Entry entry=entries[getIndex(key)]; 68 while (entry!=null) { 69 if (key==entry.key) return entry.value; 70 entry=entry.next; 71 } 72 return null; 73 } 74 getEntry(final int key)75 private Entry getEntry(final int key) { 76 Entry entry=entries[getIndex(key)]; 77 while (entry!=null && key!=entry.key) entry=entry.next; 78 return entry; 79 } 80 containsKey(final int key)81 public boolean containsKey(final int key) { 82 return getEntry(key)!=null; 83 } 84 put(final int key, final String value)85 public String put(final int key, final String value) { 86 final int index=getIndex(key); 87 for (Entry entry=entries[index]; entry!= null; entry=entry.next) { 88 if (key==entry.key) { 89 final String oldValue=entry.value; 90 entry.value=value; 91 return oldValue; 92 } 93 } 94 entries[index]=new Entry(key,value,entries[index]); 95 if (size++>=threshold) increaseCapacity(); 96 return null; 97 } 98 increaseCapacity()99 private void increaseCapacity() { 100 final int oldCapacity=entries.length; 101 final Entry[] oldEntries=entries; 102 entries=new Entry[oldCapacity<<1]; 103 bitmask=entries.length-1; 104 for (Entry entry : oldEntries) { 105 while (entry!=null) { 106 final Entry next=entry.next; 107 final int index=getIndex(entry.key); 108 entry.next=entries[index]; 109 entries[index]=entry; 110 entry=next; 111 } 112 } 113 threshold=(int)(entries.length*loadFactor); 114 } 115 remove(final int key)116 public String remove(final int key) { 117 final int index=getIndex(key); 118 Entry previous=null; 119 for (Entry entry=entries[index]; entry!=null; entry=(previous=entry).next) { 120 if (key==entry.key) { 121 if (previous==null) 122 entries[index]=entry.next; 123 else 124 previous.next=entry.next; 125 size--; 126 return entry.value; 127 } 128 } 129 return null; 130 } 131 clear()132 public void clear() { 133 for (int i=bitmask; i>=0; i--) entries[i]=null; 134 size=0; 135 } 136 containsValue(final String value)137 public boolean containsValue(final String value) { 138 if (value==null) { 139 for (int i=bitmask; i>=0; i--) 140 for (Entry entry=entries[i]; entry!=null; entry=entry.next) 141 if (entry.value==null) return true; 142 } else { 143 for (int i=bitmask; i>=0; i--) 144 for (Entry entry=entries[i]; entry!=null; entry=entry.next) 145 if (value.equals(entry.value)) return true; 146 } 147 return false; 148 } 149 150 private static final class Entry { 151 final int key; 152 String value; 153 Entry next; 154 Entry(final int key, final String value, final Entry next)155 public Entry(final int key, final String value, final Entry next) { 156 this.key=key; 157 this.value=value; 158 this.next=next; 159 } 160 } 161 } 162