From d96baa7c425f10bf407ca83ec7acca5ec27a8179 Mon Sep 17 00:00:00 2001
From: cuz <cuz@b7a2c559-68d2-44c3-8de9-860c34a00d81>
Date: Wed, 23 May 2001 22:02:19 +0000
Subject: [PATCH] Use a collections for the line info and sort them by
 file/line.

git-svn-id: svn://svn.cc65.org/cc65/trunk@751 b7a2c559-68d2-44c3-8de9-860c34a00d81
---
 src/ca65/lineinfo.c | 93 +++++++++++++++++++++++++++------------------
 src/ca65/lineinfo.h |  8 ++--
 2 files changed, 59 insertions(+), 42 deletions(-)

diff --git a/src/ca65/lineinfo.c b/src/ca65/lineinfo.c
index 26e12fff5..3abfd6e3f 100644
--- a/src/ca65/lineinfo.c
+++ b/src/ca65/lineinfo.c
@@ -59,10 +59,8 @@
 
 
 
-/* Linked list of all line infos */
-LineInfo* LineInfoRoot  = 0;
-LineInfo* LineInfoLast  = 0;
-unsigned  LineInfoCount = 0;
+/* Collection containing all line infos */
+Collection LineInfoColl = STATIC_COLLECTION_INITIALIZER;
 unsigned  LineInfoValid = 0;              /* Valid, that is, used entries */
 
 /* Static pointer to last line info or NULL if not active */
@@ -71,7 +69,7 @@ LineInfo* CurLineInfo   = 0;
 
 
 /*****************************************************************************/
-/*     	       	      	      	     Code			     	     */
+/*     	       	       	      	     Code			     	     */
 /*****************************************************************************/
 
 
@@ -83,23 +81,14 @@ static LineInfo* NewLineInfo (unsigned FileIndex, unsigned long LineNum)
     LineInfo* LI = xmalloc (sizeof (LineInfo));
 
     /* Initialize the fields */
-    LI->Next     = 0;
     LI->Usage    = 0;
     LI->Index    = 0;           /* Currently invalid */
     LI->Pos.Line = LineNum;
     LI->Pos.Col  = 0;
     LI->Pos.Name = FileIndex;
 
-    /* Insert this structure into the line info list */
-    if (LineInfoLast == 0) {
-	LineInfoRoot = LI;
-    } else {
-	LineInfoLast->Next = LI;
-    }
-    LineInfoLast = LI;
-
-    /* Count the line infos */
-    ++LineInfoCount;
+    /* Insert this structure into the collection */
+    CollAppend (&LineInfoColl, LI);
 
     /* Return the new struct */
     return LI;
@@ -113,7 +102,10 @@ LineInfo* UseLineInfo (LineInfo* LI)
  */
 {
     if (LI) {
-	++LI->Usage;
+	if (LI->Usage++ == 0) {
+	    /* One more valid line info */
+	    ++LineInfoValid;
+	}
     }
     return LI;
 }
@@ -137,45 +129,72 @@ void ClearLineInfo (void)
 
 
 
-void MakeLineInfoIndex (void)
-/* Walk over the line info list and make an index of all entries ignoring
- * those with a usage count of zero.
- */
+static int CmpLineInfo (void* Data, const void* LI1_, const void* LI2_)
+/* Compare function for the sort */
 {
-    LineInfo* LI  = LineInfoRoot;
-    LineInfoValid = 0;
-    while (LI) {
-	if (LI->Usage) {
-	    LI->Index = LineInfoValid++;
+    /* Cast the pointers */
+    const LineInfo* LI1 = LI1_;
+    const LineInfo* LI2 = LI2_;
+
+    /* Unreferenced line infos are always larger, otherwise sort by file,
+     * then by line.
+     */
+    if ((LI1->Usage == 0) == (LI2->Usage == 0)) {
+	/* Both are either referenced or unreferenced */
+       	if (LI1->Pos.Name< LI2->Pos.Name) {
+	    return -1;
+	} else if (LI1->Pos.Name > LI2->Pos.Name) {
+	    return 1;
+	} else if (LI1->Pos.Line < LI2->Pos.Line) {
+	    return -1;
+	} else if (LI1->Pos.Line > LI2->Pos.Line) {
+	    return 1;
+	} else {
+	    return 0;
+	}
+    } else {
+	if (LI1->Usage > 0) {
+	    return -1;
+	} else {
+	    return 1;
 	}
-	LI = LI->Next;
     }
 }
 
 
 
+void MakeLineInfoIndex (void)
+/* Sort the line infos and drop all unreferenced ones */
+{
+    /* Sort the collection */
+    CollSort (&LineInfoColl, CmpLineInfo, 0);
+}
+
+
+
 void WriteLineInfo (void)
 /* Write a list of all line infos to the object file. */
 {
-    LineInfo* LI;
-
     /* Tell the object file module that we're about to write line infos */
     ObjStartLineInfos ();
 
     /* Check if debug info is requested */
     if (DbgSyms) {
 
+	unsigned I;
+
 	/* Write the line info count to the list */
        	ObjWriteVar (LineInfoValid);
 
-       	/* Walk through list and write all line infos that have references */
-	LI = LineInfoRoot;
-	while (LI) {
-	    if (LI->Usage) {
-		/* Write the source file position */
-		ObjWritePos (&LI->Pos);
-	    }
-	    LI = LI->Next;
+       	/* Walk through list and write all line infos that have references.
+	 * Because of the sort, this are exactly the first LineInfoValid
+	 * ones.
+	 */
+	for (I = 0; I < LineInfoValid; ++I) {
+	    /* Get a pointer to this line info */
+	    LineInfo* LI = CollAtUnchecked (&LineInfoColl, I);
+	    /* Write the source file position */
+	    ObjWritePos (&LI->Pos);
 	}
 
     } else {
diff --git a/src/ca65/lineinfo.h b/src/ca65/lineinfo.h
index faf69f284..1414fe364 100644
--- a/src/ca65/lineinfo.h
+++ b/src/ca65/lineinfo.h
@@ -49,6 +49,7 @@
 
 
 /* common */
+#include "coll.h"
 #include "filepos.h"
 
 /* ca65 */
@@ -67,16 +68,13 @@
  */
 typedef struct LineInfo LineInfo;
 struct LineInfo {
-    LineInfo*       Next;                 /* Pointer to next info in list */
     unsigned   	    Usage;                /* Usage counter */
     unsigned        Index;                /* Index */
     FilePos         Pos;                  /* File position */
 };
 
-/* Linked list of all line infos */
-extern LineInfo* LineInfoRoot;
-extern LineInfo* LineInfoLast;
-extern unsigned  LineInfoCount;
+/* Collection containing all line infos */
+extern Collection LineInfoColl;
 extern unsigned  LineInfoValid;           /* Valid, that is, used entries */
 
 /* Global pointer to last line info or NULL if not active */
-- 
2.39.5