BuildMethodMappings


1   /*
2    * Enhydra Java Application Server Project
3    * 
4    * The contents of this file are subject to the Enhydra Public License
5    * Version 1.1 (the "License"); you may not use this file except in
6    * compliance with the License. You may obtain a copy of the License on
7    * the Enhydra web site ( http://www.enhydra.org/ ).
8    * 
9    * Software distributed under the License is distributed on an "AS IS"
10   * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 
11   * the License for the specific terms governing rights and limitations
12   * under the License.
13   * 
14   * The Initial Developer of the Enhydra Application Server is Lutris
15   * Technologies, Inc. The Enhydra Application Server and portions created
16   * by Lutris Technologies, Inc. are Copyright Lutris Technologies, Inc.
17   * All Rights Reserved.
18   * 
19   * Contributor(s):
20   * 
21   * $Id: BuildMethodMappings.java,v 1.2 2005/01/26 08:29:24 jkjome Exp $
22   */
23  
24  package org.enhydra.xml.xmlc.dom.generic;
25  
26  import java.util.ArrayList  ;
27  import java.util.Collections  ;
28  import java.util.Comparator  ;
29  import java.util.HashMap  ;
30  
31  import org.enhydra.xml.xmlc.XMLCError;
32  import org.enhydra.xml.xmlc.codegen.JavaLang;
33  import org.w3c.dom.Document  ;
34  import org.w3c.dom.Element  ;
35  import org.w3c.dom.Node  ;
36  
37  /**
38   * Class to calculate which node are to have build methods created for
39   * them based on trying to optimize the amount of code (create-cost) in each
40   * build methods without overflowing the maximum create-cost.
41   * <P> 
42   * Build methods are normally rooted at a subtree.  Costs are adjusted by
43   * moving the creation of children into sub-build methods. This leaves just
44   * the cost of calling the build method.  If the build cost is till too high
45   * after moving all children into build methods, the methods are chained
46   * together to handle creating the children.
47   * <P> 
48   * Note that the tree is a bit more comple than just the child nodes.
49   * Elements have attributes and DocumentTypes have lists of nodes.
50   * Collectively, these are refered to as contained nodes.
51   * <P> 
52   * The advantage of this object determining where build methods are created in
53   * a seperate traversal from creating the build methods is that the
54   * determination is best down from the bottom up, while creating the methods
55   * is done top-down.  The seperation also keeps the code cleaner and easier to
56   * understand.  The cost is building an intermediate table.
57   */
58  final class BuildMethodMappings {
59      /**
60       * Create-cost to call a build-method.
61       */
62      public static final int BUILD_METHOD_CALL_CREATE_COST = 1;
63  
64      /**
65       * Create-cost to create an element node.  Slightly higher due
66       * to possibility of initializing access methods.
67       */
68      public static final int CREATE_ELEMENT_CREATE_COST = 2;
69  
70      /**
71       * Create-cost to create other nodes.
72       */
73      public static final int CREATE_NODE_CREATE_COST = 1;
74  
75      /**
76       * Document we are associated with.
77       */
78      private Document   fDocument;
79  
80      /**
81       * Maximum creation-cost that a single build method can handle.
82       */
83      private int fMaxCreateCostPerBuildMethod;
84  
85      /*
86       * Table of node record.
87       */
88      private HashMap   fNodeRecordTable = new HashMap  ();
89  
90      /**
91       * Node record.
92       */
93      private class Record {
94          /** The node we are associated with. */
95          private Node   fNode;
96  
97          /**
98           * The total cost to create this node and its children in this build
99           * method.  It includes calls to other build methods, but not the cost
100          * in other build methods.
101          */
102         private int fCreateCost;
103         
104         /**
105          * The cost to the parent to create this node.  If the create cost is
106          * rooted at a method, then this is simply the cost to call the build
107          * method.  If the node is not rooted at a method, the is the total
108          * cost to create the node.
109          */
110         private int fParentCreateCost;
111 
112         /** Should this node be at the root of a build method? */
113         private boolean fMethodRoot;
114 
115         /** Should the children be created in a chained method? */
116         private boolean fChainedChildrenMethods;
117 
118         /**
119          * Constructor.  Initialize base costs.
120          */
121         public Record(Node   node) {
122             fNode = node;
123             fCreateCost = getNodeTypeCost(node);
124             fParentCreateCost = fCreateCost;
125 
126             // Add self to table
127             fNodeRecordTable.put(node, this);
128         }
129 
130         /* Mark this as a method root */
131         public void makeMethodRoot() {
132             fParentCreateCost = BUILD_METHOD_CALL_CREATE_COST;
133             fMethodRoot = true;
134         }
135 
136         /* Mark this as a having it's children created in chained methods */
137         public void makeChainedChildrenMethods () {
138             fChainedChildrenMethods = true;
139         }
140 
141         /** Determine if this can be a method root */
142         public boolean canBeMethodRoot() {
143             return BuildMethodMappings.this.canBeMethodRoot(fNode);
144         }
145 
146         /**
147          * Adjust the creation cost, this also changes the parent cost
148          * if it's not a method root. It doesn't change the parent record,
149          * as this is down during the bottom-up build of the tree.
150          */
151         public void adjustCreateCost(int amount) {
152             fCreateCost += amount;
153             if (!fMethodRoot) {
154                 fParentCreateCost += amount;
155             }
156         }
157 
158         /** Get the node */
159         public Node   getNode() {
160             return fNode;
161         }
162 
163         /** Get the create cost */
164         public int getCreateCost() {
165             return fCreateCost;
166         }
167 
168         /** Get the cost to the parent to create this node */
169         public int getParentCreateCost() {
170             return fParentCreateCost;
171         }
172 
173         /** Is the node the root of a build method? */
174         public boolean isMethodRoot() {
175             return fMethodRoot;
176         }
177 
178         /** Should the children be created in a chained method? */
179         public boolean useChainedChildrenMethods() {
180             return fChainedChildrenMethods;
181         }
182 
183         /** Get string description for debugging. */
184         public String   toString() {
185             return JavaLang.simpleClassName(fNode)
186                 + " method=" + fMethodRoot
187                 + " chained=" + fChainedChildrenMethods
188                 + " cost=" + fCreateCost
189                 + " parentCost=" + fParentCreateCost;
190         }
191     }
192 
193     /**
194      * Constructor.
195      */
196     public BuildMethodMappings(int maxCreateCostPerBuildMethod,
197                                Document   document) {
198         fDocument = document;
199         fMaxCreateCostPerBuildMethod = maxCreateCostPerBuildMethod;
200         calculateTreeCosts(document);
201     }
202 
203     /**
204      * Policy control: Determine if a node can be the root of a build method.
205      * Change the logic here maybe useful in getting better packing.
206      */
207     boolean canBeMethodRoot(Node   node) {
208         //FIXME: revisit
209         switch (node.getNodeType()) {
210         case Node.DOCUMENT_NODE:
211         case Node.DOCUMENT_TYPE_NODE:
212         case Node.ELEMENT_NODE:
213             return true;
214         default:
215             return false;
216         }
217     }
218 
219     /**
220      * Policy control: Get the cost of creating a single node based on its
221      * type.  This does not provide cumulative costs, its based on type only.
222      */
223     public int getNodeTypeCost(Node   node) {
224         //FIXME: need costs for DocType, maybe attr
225         if (node instanceof Element  ) {
226             return CREATE_ELEMENT_CREATE_COST;
227         } else {
228             return CREATE_NODE_CREATE_COST;
229         }
230     }
231 
232     /**
233      * Get a record.
234      */
235     private Record getRecord(Node   node) {
236         Record rec = (Record)fNodeRecordTable.get(node);
237         if (rec == null) {
238             throw new XMLCError("BUG: record not found: " + node);
239         }
240         return rec;
241     }
242 
243     /**
244      * Traverse the tree, calculating costs and determining where build methods
245      * should be created.  Depth-first traversal, build records from the
246      * bottom-up.  This builds the table of node records.
247      * @return The node record.
248      */
249     private Record calculateTreeCosts(Node   node) {
250         Record rec = new Record(node);
251         if (node instanceof Document  ) {
252             rec.makeMethodRoot();
253         }
254         
255         // depth-fist traversal, summing cost of contained nodes
256         ContainedNodeEnum nodes = new ContainedNodeEnum(rec.fNode);
257         while (nodes.hasMoreElements()) {
258             Record child = calculateTreeCosts(nodes.nextNode());
259             rec.adjustCreateCost(child.getParentCreateCost());
260         }
261         adjustRecord(rec);
262         return rec;
263     }
264 
265     /**
266      * Convert a child to being build in another method, adjust the size of
267      * the parent.
268      */
269     private void moveChildIntoMethod(Record parent,
270                                      Record child) {
271         parent.adjustCreateCost(-child.getParentCreateCost());
272         child.makeMethodRoot();
273         parent.adjustCreateCost(child.getParentCreateCost());
274     }
275 
276     /**
277      * Convert a child to being build in another method, if this will reduce
278      * the cost of building the parent.  Adjust the size of the parent.
279      */
280     private void minimizeChildCreateCost(Record parent,
281                                          Record child) {
282         if (!child.isMethodRoot() &&  child.canBeMethodRoot()
283             && (child.getParentCreateCost() > BUILD_METHOD_CALL_CREATE_COST)) {
284             moveChildIntoMethod(parent, child);
285         }
286     }
287 
288     /**
289      * Build a descending sorted list of children to potentially move to their
290      * own build methods, based to their parent create cost.
291      */
292     private ArrayList   buildSortedBuildMethodCandidates(Record rec) {
293         ArrayList   list = new ArrayList  ();
294         
295         ContainedNodeEnum children = new ContainedNodeEnum(rec.fNode);
296         while (children.hasMoreElements()) {
297             Record child = getRecord(children.nextNode());
298             if (child.canBeMethodRoot()) {
299                 list.add(child);
300             }
301         }
302 
303         Comparator   cmp
304             = new Comparator  () {
305                     public int compare(Object   o1,
306                                        Object   o2) {
307                         int cost1 =  ((Record)o1).getParentCreateCost();
308                         int cost2 = ((Record)o2).getParentCreateCost();
309                         return ((cost1 > cost2) ? -1 : ((cost1 < cost2) ? 1 : 0));
310                     }
311                 };
312 
313         Collections.sort(list, cmp);
314         return list;
315     }
316 
317     /**
318      * Move children into other build methods until the cost of this method
319      * is below the maximum.  Sorting to move largest first results in fewer
320      * methods being created.
321      */
322     private void adjustBuildMethod(Record rec) {
323         ArrayList   list = buildSortedBuildMethodCandidates(rec);
324 
325         // Move largest-first into their own build methods until this method
326         // is no longer full.
327         int numChildren = list.size();
328         for (int idx = 0; 
329              (idx < numChildren)
330                  && (rec.getCreateCost() >= fMaxCreateCostPerBuildMethod);
331              idx++) {
332             minimizeChildCreateCost(rec, (Record)list.get(idx));
333         }
334     }
335 
336     /**
337      * Adjust an node record, if nececssary, to keep it from overflowing
338      * the maximum build method create-cost.  This must be called *before* the
339      * parent record is created.
340      */
341     private void adjustRecord(Record rec) {
342         if (rec.getCreateCost() >= fMaxCreateCostPerBuildMethod) {
343             // Split children into other build methods until this one fits
344             adjustBuildMethod(rec);
345         }
346        if (rec.getCreateCost() > fMaxCreateCostPerBuildMethod) {
347             // Not enough, create a chained method.
348             rec.makeChainedChildrenMethods();
349        }
350     }
351 
352     /**
353      * Should a new method be created at the root of this node.
354      */
355     public boolean isMethodRoot(Node   node) {
356         return getRecord(node).isMethodRoot();
357     }
358 
359     /**
360      * Should the children be created in a chained method?
361      */
362     public boolean useChainedChildrenMethods(Node   node) {
363         return getRecord(node).useChainedChildrenMethods();
364     }
365 
366     /**
367      * Get the create cost of a node in it's method.
368      */
369     public int getCreateCost(Node   node) {
370         return getRecord(node).getCreateCost();
371     }
372 
373     /**
374      * Get a string repersentation of an entry for debugging.
375      */
376     public String   toString(Node   node) {
377         return getRecord(node).toString(); 
378     }
379 }
380
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags