/**@file\r
AutogenLibOrder class.\r
\r
- This class is to reorder library instance sequence according to library \r
+ This class is to reorder library instance sequence according to library\r
dependence.\r
- \r
+\r
Copyright (c) 2006, Intel Corporation\r
All rights reserved. This program and the accompanying materials\r
are licensed and made available under the terms and conditions of the BSD License\r
which accompanies this distribution. The full text of the license may be found at\r
http://opensource.org/licenses/bsd-license.php\r
- \r
+\r
THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
\r
///\r
/// The map of library class and its library instance.\r
///\r
- private Map<String, ModuleIdentification> libClassMap = new HashMap<String, ModuleIdentification>();\r
+ private Map<String, ModuleIdentification> libClassProducer = new HashMap<String, ModuleIdentification>();\r
+\r
+ ///\r
+ /// The map of library instance and its consumed Library Classes.\r
+ ///\r
+ private Map<ModuleIdentification, String[]> libInstanceConsumes = new HashMap<ModuleIdentification, String[]>();\r
+\r
+ ///\r
+ /// The map of library instance and its implemeted Library Classes.\r
+ ///\r
+ private Map<ModuleIdentification, String[]> libInstanceProduces = new HashMap<ModuleIdentification, String[]>();\r
\r
///\r
- /// The map of library instance and its implemet libraryClass.\r
+ /// The map of library instance and its consumers.\r
///\r
- private Map<ModuleIdentification, String[]> libInstanceMap = new HashMap<ModuleIdentification, String[]>();\r
+ private Map<ModuleIdentification, HashSet<ModuleIdentification>> libInstanceConsumedBy = new HashMap<ModuleIdentification, HashSet<ModuleIdentification>>();\r
\r
///\r
/// List of library instance. It is String[3] list, String[0] is libraryName,\r
/// String[1] is libraryConstructor name, String[2] is libDestructor name.\r
///\r
- private List<LibraryInstanceNode> libInstanceList = new ArrayList<LibraryInstanceNode>();\r
- \r
+ private ModuleIdentification[] libInstanceList = null;\r
+\r
/**\r
Constructor function\r
- \r
+\r
This function mainly initialize some member variable.\r
- \r
+\r
@param libraryList List of the library instance.\r
@throws Exception\r
**/\r
AutogenLibOrder(ModuleIdentification[] libraryList, String arch) throws EdkException {\r
- LibraryInstanceNode libInstanceNode;\r
+ ModuleIdentification libInstance;\r
String[] libClassDeclList = null;\r
String[] libClassConsmList = null;\r
- \r
+\r
+ libInstanceList = libraryList;\r
for (int i = 0; i < libraryList.length; i++) {\r
+ libInstance = libraryList[i];\r
//\r
- // Add libraryInstance in to libInstanceList.\r
- // \r
- Map<String, XmlObject> libDoc = GlobalData.getDoc(libraryList[i], arch);\r
+ // Fetch the constructor & destructor.\r
+ //\r
+ Map<String, XmlObject> libDoc = GlobalData.getDoc(libInstance, arch);\r
SurfaceAreaQuery saq = new SurfaceAreaQuery(libDoc);\r
- libInstanceNode = new LibraryInstanceNode (libraryList[i],saq.getLibConstructorName(), saq.getLibDestructorName());\r
- libInstanceList.add(libInstanceNode);\r
- \r
+ libInstance.setConstructor(saq.getLibConstructorName());\r
+ libInstance.setDestructor(saq.getLibDestructorName());\r
+\r
//\r
- // Add library instance and consumed library class list to\r
- // libInstanceMap.\r
+ // Create library class consume database.\r
//\r
libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
if (libClassConsmList != null) {\r
- String[] classStr = new String[libClassConsmList.length];\r
- for (int k = 0; k < libClassConsmList.length; k++) {\r
- classStr[k] = libClassConsmList[k];\r
- }\r
- if (this.libInstanceMap.containsKey(libraryList[i])) {\r
+ if (this.libInstanceConsumes.containsKey(libInstance)) {\r
throw new AutoGenException(\r
libraryList[i].getName()\r
+ "-- this library instance already exists, please check the library instance list!");\r
} else {\r
- this.libInstanceMap.put(libraryList[i], classStr);\r
+ this.libInstanceConsumes.put(libInstance, libClassConsmList);\r
}\r
}\r
\r
//\r
- // Add library class and library instance map.\r
+ // Create library class implementer database\r
//\r
libClassDeclList = saq.getLibraryClasses(CommonDefinition.ALWAYSPRODUCED, arch);\r
if (libClassDeclList != null) {\r
+ this.libInstanceProduces.put(libInstance, libClassDeclList);\r
for (int j = 0; j < libClassDeclList.length; j++) {\r
- if (this.libClassMap.containsKey(libClassDeclList[j])) {\r
+ if (this.libClassProducer.containsKey(libClassDeclList[j])) {\r
EdkLog.log(EdkLog.EDK_ERROR,libClassDeclList[j]\r
- + " class is already implement by "\r
- + this.libClassMap.get(libClassDeclList[j]));\r
+ + " class is already implemented by "\r
+ + this.libClassProducer.get(libClassDeclList[j]));\r
throw new AutoGenException("Library Class: " + libClassDeclList\r
+ " already has a library instance!");\r
} else {\r
- this.libClassMap.put(libClassDeclList[j], libraryList[i]);\r
+ this.libClassProducer.put(libClassDeclList[j], libInstance);\r
+ }\r
+ }\r
+ }\r
+ }\r
+\r
+ //\r
+ // Create a consumed-by database\r
+ //\r
+ for (Iterator it = libClassProducer.keySet().iterator(); it.hasNext();) {\r
+ String className = (String)it.next();\r
+ libInstance = libClassProducer.get(className);\r
+ libInstanceConsumedBy.put(libInstance, new HashSet<ModuleIdentification>());\r
+\r
+ for (int k = 0; k < libraryList.length; ++k) {\r
+ ModuleIdentification consumer = libraryList[k];\r
+ String[] consumedClassList = libInstanceConsumes.get(consumer);\r
+\r
+ for (int l = 0; l < consumedClassList.length; ++l) {\r
+ if (consumedClassList[l].equals(className)) {\r
+ libInstanceConsumedBy.get(libInstance).add(consumer);\r
}\r
}\r
}\r
\r
/**\r
orderLibInstance\r
- \r
- This function reorder the library instance according the library class \r
- dependency.\r
- \r
+\r
+ This function reorder the library instance according the library class\r
+ dependency, using DAG anaylysis algothim\r
+\r
@return List which content the ordered library instance.\r
**/\r
- List<ModuleIdentification> orderLibInstance() {\r
+ List<ModuleIdentification> orderLibInstance() throws EdkException {\r
LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
- for (int i = 0; i < libInstanceList.size(); ++i) {\r
- ModuleIdentification current = libInstanceList.get(i).libId;\r
- int insertPoint = orderList.size();\r
- //\r
- // check current library instance against orderred ones in orderList\r
- // \r
- for (int j = 0; j < orderList.size(); ++j) {\r
- ModuleIdentification old = orderList.get(j);\r
- if (consumes(current, old)) {\r
- //\r
- // if current library instance consumes the one in orderList\r
- // it must be put after\r
- // \r
- insertPoint = j + 1;\r
- } else if (consumes(old, current)) {\r
- //\r
- // if current library instance is consumed by the one in orderList\r
- // it must be put before. And no further check is needed.\r
- // \r
- insertPoint = j;\r
- break;\r
- }\r
+ LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
+\r
+ //\r
+ // First, add the library instance without consumers to the Q\r
+ //\r
+ for (int i = 0; i < libInstanceList.length; ++i) {\r
+ if (libInstanceConsumedBy.get(libInstanceList[i]).size() == 0) {\r
+ noConsumerList.add(libInstanceList[i]);\r
}\r
- orderList.add(insertPoint, current);\r
}\r
\r
- return orderList;\r
- }\r
+ while (noConsumerList.size() > 0) {\r
+ ModuleIdentification n = noConsumerList.poll();\r
+ orderList.addFirst(n);\r
\r
- //\r
- // Test if one library consumes another library\r
- // \r
- private boolean consumes(ModuleIdentification lib1, ModuleIdentification lib2) {\r
- LinkedList<ModuleIdentification> stack = new LinkedList<ModuleIdentification>();\r
+ String[] consumedClassList = libInstanceConsumes.get(n);\r
+ for (int i = 0; i < consumedClassList.length; ++i) {\r
+ ModuleIdentification m = libClassProducer.get(consumedClassList[i]);\r
+ if (m == null) {\r
+ continue;\r
+ }\r
+ HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
+ if (consumedBy.size() == 0) {\r
+ continue;\r
+ }\r
\r
- stack.add(lib1);\r
- int j = 0;\r
- while (j < stack.size()) {\r
- //\r
- // get the last library instance in stack, which hasn't been checked\r
- // \r
- ModuleIdentification lib = stack.get(j++);\r
- //\r
- // get the library classes consumed by it\r
- // \r
- String[] consumedClasses = libInstanceMap.get(lib);\r
- for (int i = 0; i < consumedClasses.length; ++i) {\r
- //\r
- // for each library class, find its corresponding library instance\r
- // \r
- ModuleIdentification consumedLib = libClassMap.get(consumedClasses[i]);\r
- //\r
- // if the corresponding instance is the "lib2", we can say that\r
- // "lib1" consumes "lib2"\r
- // \r
- if (consumedLib == lib2) {\r
- EdkLog.log(EdkLog.EDK_DEBUG, lib1 + "\n consumes\n" + lib2 + "\n");\r
- return true;\r
+ consumedBy.remove(n);\r
+ if (consumedBy.size() == 0) {\r
+ noConsumerList.addLast(m);\r
}\r
- //\r
- // otherwise, we put it back into the stack to check it later\r
- // to see if it consumes "lib2" or not. If the library instance\r
- // consumed by "lib1" consumes "lib2", we can also say that "lib1"\r
- // consumes "lib2"\r
- // \r
- if (consumedLib != null && !stack.contains(consumedLib)) {\r
- stack.offer(consumedLib);\r
- } else if (consumedLib == lib1) {\r
- //\r
- // found circular consume, do nothing now but just print\r
- // out message for debugging\r
- // \r
- String msg = "!!! Library consumes circularly: ";\r
- for (int k = 0; k < j; k++) {\r
- msg += stack.get(k).getName() + "->";\r
+ }\r
+\r
+ boolean circularlyConsumed = false;\r
+ while (noConsumerList.size() == 0 && !circularlyConsumed) {\r
+ circularlyConsumed = true;\r
+ for (int i = 0; i < libInstanceList.length; ++i) {\r
+ ModuleIdentification libInstance = libInstanceList[i];\r
+ if (!libInstance.hasConstructor()) {\r
+ continue;\r
+ }\r
+\r
+ HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(libInstance);\r
+ if (consumedBy.size() == 0) {\r
+ continue;\r
+ }\r
+\r
+ ModuleIdentification[] consumedByList = consumedBy.toArray(new ModuleIdentification[consumedBy.size()]);\r
+ for (int j = 0; j < consumedByList.length; ++j) {\r
+ ModuleIdentification consumer = consumedByList[j];\r
+ if (consumer.hasConstructor()) {\r
+ continue;\r
+ }\r
+\r
+ //\r
+ // if there's no constructor in the library instance's consumer,\r
+ // remove it from the consumer list\r
+ //\r
+ consumedBy.remove(consumer);\r
+ circularlyConsumed = false;\r
+ if (consumedBy.size() == 0) {\r
+ noConsumerList.addLast(libInstance);\r
+ break;\r
+ }\r
+ }\r
+\r
+ if (noConsumerList.size() > 0) {\r
+ break;\r
}\r
- msg += lib1.getName();\r
- EdkLog.log(EdkLog.EDK_DEBUG, msg);\r
}\r
- }\r
- }\r
- return false;\r
- }\r
\r
- /**\r
- isInLibInstance\r
- \r
- This function check does the library instance already in the list.\r
- \r
- @param list List of the library instance.\r
- @param instanceName Name of library instance.\r
- @return "true" the library instance in list |\r
- "false" the library instance is not in list.\r
- **/\r
- private boolean isInLibInstance(List<ModuleIdentification> list, ModuleIdentification instanceId) {\r
- for (int i = 0; i < list.size(); i++) {\r
- \r
- if (instanceId.equals(list.get(i))) {\r
- return true;\r
+ if (noConsumerList.size() == 0 && !circularlyConsumed) {\r
+ break;\r
+ }\r
}\r
}\r
- return false;\r
- }\r
\r
- /**\r
- isInStackList \r
- \r
- This function check if the node already in the stack.\r
- \r
- @param list Stack.\r
- @param nodeName Name of node.\r
- @return "true" if node have in stack |\r
- "false" if node don't in stack.\r
- **/ \r
- private boolean isInStackList(List<Node> list, ModuleIdentification instanceId) {\r
- for (int i = 0; i < list.size(); i++) {\r
- if (instanceId.equals(list.get(i).nodeId)) {\r
- return true;\r
+ //\r
+ // Append the remaining library instance to the end of sorted list\r
+ //\r
+ for (int i = 0; i < libInstanceList.length; ++i) {\r
+ if (libInstanceConsumedBy.get(libInstanceList[i]).size() > 0 && libInstanceList[i].hasConstructor()) {\r
+ EdkLog.log(EdkLog.EDK_ERROR, libInstanceList[i].getName()\r
+ + " with constructor has a circular dependency!");\r
+ throw new AutoGenException("Circular dependency in library instances is found!");\r
}\r
- }\r
- return false;\r
- }\r
- \r
- /**\r
- isHaveConsDestructor\r
- \r
- This function check if the library have constructor or destructor \r
- function.\r
- \r
- @param libName Name of library\r
- @return "true" if library have constructor or desconstructor |\r
- "false" if library don't have constructor \r
- and desconstructor.\r
- **/\r
- private boolean isHaveConsDestructor (ModuleIdentification libNode){\r
- for (int i = 0; i < libInstanceList.size(); i++){\r
- if (libInstanceList.get(i).libId.equals(libNode)){\r
- if (libInstanceList.get(i).constructorName != null || libInstanceList.get(i).deconstructorName != null){\r
- return true;\r
- }\r
+\r
+ if (!orderList.contains(libInstanceList[i])) {\r
+ orderList.add(libInstanceList[i]);\r
}\r
}\r
- return false;\r
- }\r
-}\r
-\r
-/**\r
- Node \r
- \r
- This class is used as stack node.\r
- \r
- **/\r
-class Node {\r
- ModuleIdentification nodeId;\r
-\r
- boolean isVisit;\r
-\r
- Node(ModuleIdentification nodeId, boolean isVisit) {\r
- this.nodeId = nodeId;\r
- this.isVisit = false;\r
- }\r
-} \r
-/**\r
- LibraryInstance Node \r
- \r
- This class is used to store LibrayInstance and it's deconstructor and constructor\r
-**/\r
- \r
-class LibraryInstanceNode {\r
- ModuleIdentification libId;\r
- String deconstructorName;\r
- String constructorName;\r
- \r
- LibraryInstanceNode (ModuleIdentification libId, String deconstructor, String constructor){\r
- this.libId = libId;\r
- this.deconstructorName = deconstructor;\r
- this.constructorName = constructor;\r
+ return orderList;\r
}\r
}\r
projects / mirror_edk2.git / blobdiff