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