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