1 /*
2 * reserved comment block
3 * DO NOT REMOVE OR ALTER!
4 */
5 /*
6 * Copyright 1999-2004 The Apache Software Foundation.
7 *
8 * Licensed under the Apache License, Version 2.0 (the "License");
9 * you may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing, software
15 * distributed under the License is distributed on an "AS IS" BASIS,
16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17 * See the License for the specific language governing permissions and
18 * limitations under the License.
19 *
20 */
21 package com.sun.org.apache.xml.internal.security.c14n.implementations;
22
23 import java.util.ArrayList;
24 import java.util.Collection;
25 import java.util.Iterator;
26 import java.util.List;
27
28
29 import org.w3c.dom.Attr;
30 import org.w3c.dom.Node;
31
32
33
34 /**
35 * A stack based Symble Table.
36 *<br>For speed reasons all the symbols are introduced in the same map,
37 * and at the same time in a list so it can be removed when the frame is pop back.
38 * @author Raul Benito
39 **/
40 public class NameSpaceSymbTable {
41
42 /**The map betwen prefix-> entry table. */
43 SymbMap symb;
44 /**The level of nameSpaces (for Inclusive visibility).*/
45 int nameSpaces=0;
46 /**The stacks for removing the definitions when doing pop.*/
47 List<SymbMap> level;
48 boolean cloned=true;
49 static final String XMLNS="xmlns";
50 final static SymbMap initialMap=new SymbMap();
51 static {
52 NameSpaceSymbEntry ne=new NameSpaceSymbEntry("",null,true,XMLNS);
53 ne.lastrendered="";
54 initialMap.put(XMLNS,ne);
55 }
56 /**
57 * Default constractor
58 **/
59 public NameSpaceSymbTable() {
60 level = new ArrayList<SymbMap>(10);
61 //Insert the default binding for xmlns.
62 symb=(SymbMap) initialMap.clone();
63 }
64
65 /**
66 * Get all the unrendered nodes in the name space.
67 * For Inclusive rendering
68 * @param result the list where to fill the unrendered xmlns definitions.
69 **/
70 public void getUnrenderedNodes(Collection<Attr> result) {
71 //List result=new ArrayList();
72 Iterator<NameSpaceSymbEntry> it=symb.entrySet().iterator();
73 while (it.hasNext()) {
74 NameSpaceSymbEntry n= it.next();
75 //put them rendered?
76 if ((!n.rendered) && (n.n!=null)) {
77 n=(NameSpaceSymbEntry) n.clone();
78 needsClone();
79 symb.put(n.prefix,n);
80 n.lastrendered=n.uri;
81 n.rendered=true;
82
83 result.add(n.n);
84
85 }
86 }
87 }
88
89 /**
90 * Push a frame for visible namespace.
91 * For Inclusive rendering.
92 **/
93 public void outputNodePush() {
94 nameSpaces++;
95 push();
96 }
97
98 /**
99 * Pop a frame for visible namespace.
100 **/
101 public void outputNodePop() {
102 nameSpaces--;
103 pop();
104 }
105
106 /**
107 * Push a frame for a node.
108 * Inclusive or Exclusive.
109 **/
110 public void push() {
111 //Put the number of namespace definitions in the stack.
112 level.add(null);
113 cloned=false;
114 }
115
116 /**
117 * Pop a frame.
118 * Inclusive or Exclusive.
119 **/
120 public void pop() {
121 int size=level.size()-1;
122 Object ob= level.remove(size);
123 if (ob!=null) {
124 symb=(SymbMap)ob;
125 if (size==0) {
126 cloned=false;
127 } else
128 cloned=(level.get(size-1)!=symb);
129 } else {
130 cloned=false;
131 }
132
133
134 }
135
136 final void needsClone() {
137 if (!cloned) {
138 level.set(level.size()-1,symb);
139 symb=(SymbMap) symb.clone();
140 cloned=true;
141 }
142 }
143
144
145 /**
146 * Gets the attribute node that defines the binding for the prefix.
147 * @param prefix the prefix to obtain the attribute.
148 * @return null if there is no need to render the prefix. Otherwise the node of
149 * definition.
150 **/
151 public Attr getMapping(String prefix) {
152 NameSpaceSymbEntry entry=symb.get(prefix);
153 if (entry==null) {
154 //There is no definition for the prefix(a bug?).
155 return null;
156 }
157 if (entry.rendered) {
158 //No need to render an entry already rendered.
159 return null;
160 }
161 // Mark this entry as render.
162 entry=(NameSpaceSymbEntry) entry.clone();
163 needsClone();
164 symb.put(prefix,entry);
165 entry.rendered=true;
166 entry.level=nameSpaces;
167 entry.lastrendered=entry.uri;
168 // Return the node for outputing.
169 return entry.n;
170 }
171
172 /**
173 * Gets a definition without mark it as render.
174 * For render in exclusive c14n the namespaces in the include prefixes.
175 * @param prefix The prefix whose definition is neaded.
176 * @return the attr to render, null if there is no need to render
177 **/
178 public Attr getMappingWithoutRendered(String prefix) {
179 NameSpaceSymbEntry entry= symb.get(prefix);
180 if (entry==null) {
181 return null;
182 }
183 if (entry.rendered) {
184 return null;
185 }
186 return entry.n;
187 }
188
189 /**
190 * Adds the mapping for a prefix.
191 * @param prefix the prefix of definition
192 * @param uri the Uri of the definition
193 * @param n the attribute that have the definition
194 * @return true if there is already defined.
195 **/
196 public boolean addMapping(String prefix, String uri,Attr n) {
197 NameSpaceSymbEntry ob = symb.get(prefix);
198 if ((ob!=null) && uri.equals(ob.uri)) {
199 //If we have it previously defined. Don't keep working.
200 return false;
201 }
202 //Creates and entry in the table for this new definition.
203 NameSpaceSymbEntry ne=new NameSpaceSymbEntry(uri,n,false,prefix);
204 needsClone();
205 symb.put(prefix, ne);
206 if (ob != null) {
207 //We have a previous definition store it for the pop.
208 //Check if a previous definition(not the inmidiatly one) has been rendered.
209 ne.lastrendered=ob.lastrendered;
210 if ((ob.lastrendered!=null)&& (ob.lastrendered.equals(uri))) {
211 //Yes it is. Mark as rendered.
212 ne.rendered=true;
213 }
214 }
215 return true;
216 }
217
218 /**
219 * Adds a definition and mark it as render.
220 * For inclusive c14n.
221 * @param prefix the prefix of definition
222 * @param uri the Uri of the definition
223 * @param n the attribute that have the definition
224 * @return the attr to render, null if there is no need to render
225 **/
226 public Node addMappingAndRender(String prefix, String uri,Attr n) {
227 NameSpaceSymbEntry ob = symb.get(prefix);
228
229 if ((ob!=null) && uri.equals(ob.uri)) {
230 if (!ob.rendered) {
231 ob=(NameSpaceSymbEntry) ob.clone();
232 needsClone();
233 symb.put(prefix,ob);
234 ob.lastrendered=uri;
235 ob.rendered=true;
236 return ob.n;
237 }
238 return null;
239 }
240
241 NameSpaceSymbEntry ne=new NameSpaceSymbEntry(uri,n,true,prefix);
242 ne.lastrendered=uri;
243 needsClone();
244 symb.put(prefix, ne);
245 if (ob != null) {
246
247 if ((ob.lastrendered!=null)&& (ob.lastrendered.equals(uri))) {
248 ne.rendered=true;
249 return null;
250 }
251 }
252 return ne.n;
253 }
254
255 public int getLevel() {
256 // TODO Auto-generated method stub
257 return level.size();
258 }
259
260 public void removeMapping(String prefix) {
261 NameSpaceSymbEntry ob = symb.get(prefix);
262
263 if (ob!=null) {
264 needsClone();
265 symb.put(prefix,null);
266 }
267 }
268
269 public void removeMappingIfNotRender(String prefix) {
270 NameSpaceSymbEntry ob = symb.get(prefix);
271
272 if (ob!=null && !ob.rendered) {
273 needsClone();
274 symb.put(prefix,null);
275 }
276 }
277
278 public boolean removeMappingIfRender(String prefix) {
279 NameSpaceSymbEntry ob = symb.get(prefix);
280
281 if (ob!=null && ob.rendered) {
282 needsClone();
283 symb.put(prefix,null);
284 }
285 return false;
286 }
287 }
288
289 /**
290 * The internal structure of NameSpaceSymbTable.
291 **/
292 class NameSpaceSymbEntry implements Cloneable {
293 NameSpaceSymbEntry(String name,Attr n,boolean rendered,String prefix) {
294 this.uri=name;
295 this.rendered=rendered;
296 this.n=n;
297 this.prefix=prefix;
298 }
299 /** @inheritDoc */
300 public Object clone() {
301 try {
302 return super.clone();
303 } catch (CloneNotSupportedException e) {
304 return null;
305 }
306 }
307 /** The level where the definition was rendered(Only for inclusive) */
308 int level=0;
309 String prefix;
310 /**The URI that the prefix defines */
311 String uri;
312 /**The last output in the URI for this prefix (This for speed reason).*/
313 String lastrendered=null;
314 /**This prefix-URI has been already render or not.*/
315 boolean rendered=false;
316 /**The attribute to include.*/
317 Attr n;
318 };
319
320 class SymbMap implements Cloneable {
321 int free=23;
322 NameSpaceSymbEntry[] entries;
323 String[] keys;
324 SymbMap() {
325 entries=new NameSpaceSymbEntry[free];
326 keys=new String[free];
327 }
328 void put(String key, NameSpaceSymbEntry value) {
329 int index = index(key);
330 Object oldKey = keys[index];
331 keys[index] = key;
332 entries[index] = value;
333 if (oldKey==null || !oldKey.equals(key)) {
334 if (--free == 0) {
335 free=entries.length;
336 int newCapacity = free<<2;
337 rehash(newCapacity);
338 }
339 }
340 }
341
342 List<NameSpaceSymbEntry> entrySet() {
343 List<NameSpaceSymbEntry> a=new ArrayList<NameSpaceSymbEntry>();
344 for (int i=0;i<entries.length;i++) {
345 if ((entries[i]!=null) && !("".equals(entries[i].uri))) {
346 a.add(entries[i]);
347 }
348 }
349 return a;
350 }
351
352 protected int index(Object obj) {
353 Object[] set = keys;
354 int length = set.length;
355 //abs of index
356 int index = (obj.hashCode() & 0x7fffffff) % length;
357 Object cur = set[index];
358
359 if (cur == null || (cur.equals( obj))) {
360 return index;
361 }
362 length=length-1;
363 do {
364 index=index==length? 0:++index;
365 cur = set[index];
366 } while (cur != null && (!cur.equals(obj)));
367 return index;
368 }
369
370 /**
371 * rehashes the map to the new capacity.
372 *
373 * @param newCapacity an <code>int</code> value
374 */
375 protected void rehash(int newCapacity) {
376 int oldCapacity = keys.length;
377 String oldKeys[] = keys;
378 NameSpaceSymbEntry oldVals[] = entries;
379
380 keys = new String[newCapacity];
381 entries = new NameSpaceSymbEntry[newCapacity];
382
383 for (int i = oldCapacity; i-- > 0;) {
384 if(oldKeys[i] != null) {
385 String o = oldKeys[i];
386 int index = index(o);
387 keys[index] = o;
388 entries[index] = oldVals[i];
389 }
390 }
391 }
392
393 NameSpaceSymbEntry get(String key) {
394 return entries[index(key)];
395 }
396
397 protected Object clone() {
398 try {
399 SymbMap copy=(SymbMap) super.clone();
400 copy.entries=new NameSpaceSymbEntry[entries.length];
401 System.arraycopy(entries,0,copy.entries,0,entries.length);
402 copy.keys=new String[keys.length];
403 System.arraycopy(keys,0,copy.keys,0,keys.length);
404
405 return copy;
406 } catch (CloneNotSupportedException e) {
407 // TODO Auto-generated catch block
408 e.printStackTrace();
409 }
410 return null;
411 }
412 }