Used the DAG algorithm given by Mike to re-implemented library constructor sorting...
authorjwang36 <jwang36@6f19259b-4bc3-4df7-8a09-765794883524>
Mon, 8 Jan 2007 09:41:20 +0000 (09:41 +0000)
committerjwang36 <jwang36@6f19259b-4bc3-4df7-8a09-765794883524>
Mon, 8 Jan 2007 09:41:20 +0000 (09:41 +0000)
git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@2193 6f19259b-4bc3-4df7-8a09-765794883524

Tools/Java/Source/GenBuild/org/tianocore/build/autogen/AutogenLibOrder.java
Tools/Java/Source/GenBuild/org/tianocore/build/id/ModuleIdentification.java

index 0ba6825..6d6794d 100644 (file)
@@ -40,18 +40,28 @@ public class AutogenLibOrder {
     ///\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
@@ -62,35 +72,40 @@ public class AutogenLibOrder {
       @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 = new ModuleIdentification[libraryList.length];\r
         for (int i = 0; i < libraryList.length; i++) {\r
+            libInstance = libraryList[i];\r
+            libInstanceList[i] = libInstance;\r
             //\r
             // Add libraryInstance in to libInstanceList.\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
+            // libInstanceConsumes.\r
             //\r
             libClassConsmList = saq.getLibraryClasses(CommonDefinition.ALWAYSCONSUMED, arch);\r
             if (libClassConsmList != null) {\r
+                /*\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
+                */\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
@@ -99,15 +114,33 @@ public class AutogenLibOrder {
             //\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
+        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
@@ -116,190 +149,83 @@ public class AutogenLibOrder {
 \r
     /**\r
       orderLibInstance\r
-      \r
+\r
       This function reorder the library instance according the library class \r
       dependency.\r
-      \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
+        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
-\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
+            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
-                //\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
-                    msg += lib1.getName();\r
-                    EdkLog.log(EdkLog.EDK_DEBUG, msg);\r
+                HashSet<ModuleIdentification> consumedBy = libInstanceConsumedBy.get(m);\r
+                consumedBy.remove(n);\r
+                if (consumedBy.size() == 0) {\r
+                    noConsumerList.addLast(m);\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
-        }\r
-        return false;\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
-    /**\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
+                    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
-/**\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
+        for (int i = 0; i < libInstanceList.length; ++i) {\r
+            if (!orderList.contains(libInstanceList[i])) {\r
+                orderList.add(libInstanceList[i]);\r
+            }\r
+        }\r
+        return orderList;\r
     }\r
 }\r
index c2d9acc..dfcbeae 100644 (file)
@@ -31,6 +31,10 @@ public class ModuleIdentification extends Identification {
     \r
     private boolean isLibrary = false;\r
 \r
+    private String constructor = "";\r
+\r
+    private String destructor = "";\r
+\r
     /**\r
       @param guid Guid\r
       @param version Version\r
@@ -189,4 +193,24 @@ public class ModuleIdentification extends Identification {
     public String getName() {\r
         return name;\r
     }\r
+\r
+    public boolean hasConstructor() {\r
+        return constructor != "";\r
+    }\r
+\r
+    public boolean hasDestructor() {\r
+        return destructor != "";\r
+    }\r
+\r
+    public void setConstructor(String name) {\r
+        if (name != null) {\r
+            constructor = name;\r
+        }\r
+    }\r
+\r
+    public void setDestructor(String name) {\r
+        if (name != null) {\r
+            destructor = name;\r
+        }\r
+    }\r
 }\r