|
1
57
58 package org.xquark.xpath.datamodel.xerces.utils;
59
60
64 public final class SymbolCache {
65 public static final int CHAR_OFFSET = 0;
69 public static final int INDEX_OFFSET = 1;
70 public static final int NEXT_OFFSET = 2;
71 public static final int CACHE_RECORD_SIZE = 3;
72 public static final int INITIAL_CACHE_RECORD_COUNT = 4; public char[] fSymbolChars = new char[8192];
76 public int fSymbolCharsOffset = 0;
77 public int[][] fCacheLines = new int[8][];
78 public int fCacheLineCount = 0;
79 public SymbolCache() {
83 fCacheLines[fCacheLineCount++] = new int[1+(INITIAL_CACHE_RECORD_COUNT*CACHE_RECORD_SIZE)];
84 }
85 public void reset() {
86 fSymbolCharsOffset = 0;
87 fCacheLineCount = 0;
88 fCacheLines[fCacheLineCount++] = new int[1+(INITIAL_CACHE_RECORD_COUNT*CACHE_RECORD_SIZE)];
89 }
90 public char[] getSymbolChars() {
94 return fSymbolChars;
95 }
96 public String  createSymbol(int symbolHandle, int startOffset, int entry, int[] entries, int offset) {
100 int slen = fSymbolCharsOffset - startOffset;
101 String str = new String (fSymbolChars, startOffset, slen);
102 try {
103 entries[offset + SymbolCache.INDEX_OFFSET] = symbolHandle;
104 } catch (ArrayIndexOutOfBoundsException ex) {
105 throw new RuntimeException ("UTL001 untested");
106 }
107 return str;
108 }
109 public int addSymbolToCache(String str, int slen, int symbolHandle) {
110 int charsOffset = fSymbolCharsOffset;
111 if (slen == 0) return charsOffset;
113 int strIndex = 0;
114 char ch = str.charAt(strIndex++);
115 try {
116 fSymbolChars[fSymbolCharsOffset] = ch;
117 } catch (ArrayIndexOutOfBoundsException ex) {
118 char[] newChars = new char[fSymbolChars.length * 2];
119 System.arraycopy(fSymbolChars, 0, newChars, 0, fSymbolChars.length);
120 fSymbolChars = newChars;
121 fSymbolChars[fSymbolCharsOffset] = ch;
122 }
123 fSymbolCharsOffset++;
124 int entry = 0;
125 int[] entries = fCacheLines[entry];
126 int count = entries[0];
127 int i = 0;
128 int offset = 1;
129 while (true) {
130 if (i == count)
131 break;
132 if (entries[offset + CHAR_OFFSET] != ch) {
133 i++;
134 offset += CACHE_RECORD_SIZE;
135 continue;
136 }
137 if (strIndex == slen) {
138 if (entries[offset + INDEX_OFFSET] != -1) {
139 throw new RuntimeException ("addSymbolToCache");
141 }
142 entries[offset + INDEX_OFFSET] = symbolHandle;
143 return charsOffset;
144 }
145 ch = str.charAt(strIndex++);
146 try {
147 fSymbolChars[fSymbolCharsOffset] = ch;
148 } catch (ArrayIndexOutOfBoundsException ex) {
149 char[] newChars = new char[fSymbolChars.length * 2];
150 System.arraycopy(fSymbolChars, 0, newChars, 0, fSymbolChars.length);
151 fSymbolChars = newChars;
152 fSymbolChars[fSymbolCharsOffset] = ch;
153 }
154 fSymbolCharsOffset++;
155 entry = entries[offset + NEXT_OFFSET];
156 try {
157 entries = fCacheLines[entry];
158 } catch (ArrayIndexOutOfBoundsException ex) {
159 if (entry == -1) {
160 entry = fCacheLineCount++;
161 entries[offset + NEXT_OFFSET] = entry;
162 entries = new int[1+(INITIAL_CACHE_RECORD_COUNT*CACHE_RECORD_SIZE)];
163 try {
164 fCacheLines[entry] = entries;
165 } catch (ArrayIndexOutOfBoundsException ex2) {
166 int[][] newCache = new int[entry * 2][];
167 System.arraycopy(fCacheLines, 0, newCache, 0, entry);
168 fCacheLines = newCache;
169 fCacheLines[entry] = entries;
170 }
171 } else {
172 entries = fCacheLines[entry];
173 throw new RuntimeException ("UTL001 untested");
174 }
175 }
176 count = entries[0];
177 i = 0;
178 offset = 1;
179 }
180 while (true) {
181 entries[0]++;
182 try {
183 entries[offset + CHAR_OFFSET] = ch;
184 } catch (ArrayIndexOutOfBoundsException ex) {
185 int newSize = 1 + ((offset - 1) * 2);
186 int[] newEntries = new int[newSize];
187 System.arraycopy(entries, 0, newEntries, 0, offset);
188 fCacheLines[entry] = entries = newEntries;
189 entries[offset + CHAR_OFFSET] = ch;
190 }
191 if (strIndex == slen) {
192 entries[offset + INDEX_OFFSET] = symbolHandle;
193 entries[offset + NEXT_OFFSET] = -1;
194 break;
195 }
196 entry = fCacheLineCount++;
197 entries[offset + INDEX_OFFSET] = -1;
198 entries[offset + NEXT_OFFSET] = entry;
199 entries = new int[1+(INITIAL_CACHE_RECORD_COUNT*CACHE_RECORD_SIZE)];
200 try {
201 fCacheLines[entry] = entries;
202 } catch (ArrayIndexOutOfBoundsException ex) {
203 int[][] newCache = new int[entry * 2][];
204 System.arraycopy(fCacheLines, 0, newCache, 0, entry);
205 fCacheLines = newCache;
206 fCacheLines[entry] = entries;
207 }
208 offset = 1;
209 ch = str.charAt(strIndex++);
210 try {
211 fSymbolChars[fSymbolCharsOffset] = ch;
212 } catch (ArrayIndexOutOfBoundsException ex) {
213 char[] newChars = new char[fSymbolChars.length * 2];
214 System.arraycopy(fSymbolChars, 0, newChars, 0, fSymbolChars.length);
215 fSymbolChars = newChars;
216 fSymbolChars[fSymbolCharsOffset] = ch;
217 }
218 fSymbolCharsOffset++;
219 }
220 return charsOffset;
221 }
222 public void updateCacheLine(int charsOffset, int totalMisses, int length) {
223 int entry = 0;
225 int[] entries = fCacheLines[0];
226 int ch = fSymbolChars[charsOffset++];
227 int count = entries[0];
228 int offset = 1 + ((count - 1) * CACHE_RECORD_SIZE);
229 int misses = 0;
230 while (true) {
231 if (ch != entries[offset + CHAR_OFFSET]) {
232 offset -= CACHE_RECORD_SIZE;
233 misses++;
234 continue;
235 }
236 if (misses > 4) {
237 int symIndex = entries[offset + INDEX_OFFSET];
238 int nextIndex = entries[offset + NEXT_OFFSET];
239 System.arraycopy(entries, offset + CACHE_RECORD_SIZE, entries, offset, misses * CACHE_RECORD_SIZE);
240 offset = 1 + ((count - 1) * CACHE_RECORD_SIZE);
241 entries[offset + CHAR_OFFSET] = ch;
242 entries[offset + INDEX_OFFSET] = symIndex;
243 entries[offset + NEXT_OFFSET] = nextIndex;
244 }
245 if (--length == 0)
246 break;
247 entry = entries[offset + NEXT_OFFSET];
248 entries = fCacheLines[entry];
249 ch = fSymbolChars[charsOffset++];
250 count = entries[0];
251 offset = 1 + ((count - 1) * CACHE_RECORD_SIZE);
252 misses = 0;
253 }
254 }
255 }
256 |
Popular Tags |
Java API By Example, From Geeks To Geeks.