///\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 implemet libraryClass.\r
+ /// The map of library instance and its consumed Library Classes.\r
///\r
- private Map<ModuleIdentification, String[]> libInstanceMap = new HashMap<ModuleIdentification, String[]>();\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 consumers.\r
+ ///\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
+ private ModuleIdentification[] libInstanceList = null;\r
\r
/**\r
Constructor function\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
+ // Fetch the constructor & destructor.\r
// \r
- Map<String, XmlObject> libDoc = GlobalData.getDoc(libraryList[i], arch);\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
+ 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
- // Check is the library instance list meet the require;\r
- //\r
- //for (int s = 0; s < this.libInstanceList.size(); s++) {\r
- // String[] libClass = this.libInstanceMap.get(this.libInstanceList\r
- // .get(s));\r
- // if (libClass != null) {\r
- // for (int t = 0; t < libClass.length; t++) {\r
- // if (this.libClassMap.get(libClass[t]) == null) {\r
- //\r
- // Note: There exist a kind of module which depend on \r
- // library class with no instance or whose instance will\r
- // never be linked into the module. \r
- // For this satuation, the module has the description of \r
- // library class in MSA file but no description of \r
- // corresponding library instance in MBD file. There \r
- // will be a warnig message given here after a standard \r
- // log way has been decided.\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
\r
/**\r
orderLibInstance\r
- \r
+\r
This function reorder the library instance according the library class \r
- dependency.\r
- \r
+ dependency, using DAG anaylysis algothim\r
+\r
@return List which content the ordered library instance.\r
**/\r
- List<ModuleIdentification> orderLibInstance1() {\r
- List<ModuleIdentification> orderList = new ArrayList<ModuleIdentification>();\r
- //\r
- // Stack of node which track the library instance name ant its visiting\r
- // flag.\r
- //\r
- List<Node> stackList = new ArrayList<Node>();\r
- int stackSize = 0;\r
- ModuleIdentification libInstanceId = null;\r
- if (libInstanceList.size() < 0) {\r
- return null;\r
- }\r
+ List<ModuleIdentification> orderLibInstance() throws EdkException {\r
+ LinkedList<ModuleIdentification> orderList = new LinkedList<ModuleIdentification>();\r
+ LinkedList<ModuleIdentification> noConsumerList = new LinkedList<ModuleIdentification>();\r
\r
//\r
- // Reorder the library instance.\r
- //\r
- for (int i = 0; i < libInstanceList.size(); i++) {\r
- //\r
- // If library instance is already in the order list skip it.\r
- //\r
- if (isInLibInstance(orderList, libInstanceList.get(i).libId)) {\r
- continue;\r
- }\r
- \r
- Node node = new Node(libInstanceList.get(i).libId, false);\r
- //\r
- // Use stack to reorder library instance.\r
- // Push node to stack.\r
- //\r
- stackList.add(node);\r
- while (stackList.size() > 0) {\r
- stackSize = stackList.size() - 1;\r
- //\r
- // Pop the first node in stack. If the node flag has been visited\r
- // add this node to orderlist and remove it from stack.\r
- //\r
- if (stackList.get(stackSize).isVisit) {\r
- if (!isInLibInstance(orderList,\r
- stackList.get(stackSize).nodeId)) {\r
- orderList.add(stackList.get(stackSize).nodeId);\r
- stackList.remove(stackSize);\r
- }\r
- \r
- } else {\r
- //\r
- // Get the node value and set visit flag as true.\r
- //\r
- stackList.get(stackList.size() - 1).isVisit = true;\r
- String[] libClassList = this.libInstanceMap.get(stackList\r
- .get(stackSize).nodeId);\r
- //\r
- // Push the node dependence library instance to the stack.\r
- //\r
- if (libClassList != null) {\r
- for (int j = 0; j < libClassList.length; j++) {\r
- libInstanceId = this.libClassMap.get(libClassList[j]);\r
- if (libInstanceId != null\r
- && !isInLibInstance(orderList, libInstanceId)) {\r
- //\r
- // If and only if the currently library instance\r
- // is not in stack and it have constructor or \r
- // destructor function, push this library \r
- // instacne in stack.\r
- //\r
- if (!isInStackList(stackList, this.libClassMap\r
- .get(libClassList[j])) /* && isHaveConsDestructor(libInstanceId) */) {\r
- stackList.add(new Node(this.libClassMap\r
- .get(libClassList[j]), false));\r
- }\r
- }\r
- }\r
- }\r
- }\r
- System.out.println("################################################");\r
- for (int ii = 0; ii < orderList.size(); ++ii) {\r
- System.out.println(" " + orderList.get(ii));\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
}\r
- return orderList;\r
- }\r
\r
- List<ModuleIdentification> orderLibInstance() {\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
- for (int j = 0; j < orderList.size(); ++j) {\r
- ModuleIdentification old = orderList.get(j);\r
- //System.out.println("### old = " + old);\r
- if (consumes(current, old)) {\r
- insertPoint = j + 1;\r
- } else if (consumes(old, current)) {\r
- insertPoint = j;\r
- break;\r
+ while (noConsumerList.size() > 0) {\r
+ ModuleIdentification n = noConsumerList.poll();\r
+ orderList.addFirst(n);\r
+\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
+ consumedBy.remove(n);\r
+ if (consumedBy.size() == 0) {\r
+ noConsumerList.addLast(m);\r
}\r
}\r
- orderList.add(insertPoint, current);\r
-// System.out.println("################################################");\r
-// for (int ii = 0; ii < orderList.size(); ++ii) {\r
-// System.out.println(" " + orderList.get(ii));\r
-// }\r
- }\r
\r
- return orderList;\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
- boolean consumes(ModuleIdentification lib1, ModuleIdentification lib2) {\r
- //System.out.println("$$$ lib1 = " + lib1);\r
- LinkedList<ModuleIdentification> stack = new LinkedList<ModuleIdentification>();\r
- stack.add(lib1);\r
- int j = 0;\r
- while (j < stack.size()) {\r
- ModuleIdentification lib = stack.get(j++);\r
- String[] consumedClasses = libInstanceMap.get(lib);\r
- for (int i = 0; i < consumedClasses.length; ++i) {\r
- ModuleIdentification consumedLib = libClassMap.get(consumedClasses[i]);\r
- //System.out.println("$$$ class = " + consumedClasses[i]);\r
- //System.out.println("$$$ insta = " + consumedLib);\r
- if (consumedLib == lib2) {\r
- //System.out.println(lib1 + "\n consumes\n" + lib2 + "\n");\r
- return true;\r
- }\r
- if (consumedLib != null && !stack.contains(consumedLib)) {\r
- stack.offer(consumedLib);\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
+ // 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
}\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
+ //\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
- 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
- }\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
+ 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