Changeset 19539

Timestamp:

Sep 12, 2008, 12:36:29 PM (18 years ago)

Author:

Paul Price

Message:

Optimising psPixelsConcatenate: use of qsort took ages. Split into two functions: psPixelsConcatenate (joing two pixel lists) and psPixelsDuplicates (remove duplicates in a list; works nicely in-place), and using PSSORT instead of qsort. Much faster!

Location:

trunk/psLib

Files:

• src/types/psPixels.c (modified) (4 diffs)
• src/types/psPixels.h (modified) (3 diffs)
• src/types/psTree.h (modified) (1 diff)
• test/types/tap_psPixels_all.c (modified) (4 diffs)

trunk/psLib/src/types/psPixels.c

@@ -7 +7 @@
  *  @author Robert DeSonia, MHPCC
  *
- *  @version $Revision: 1.42 $ $Name: not supported by cvs2svn $
- *  @date $Date: 2008-08-27 22:29:48 $
+ *  @version $Revision: 1.43 $ $Name: not supported by cvs2svn $
+ *  @date $Date: 2008-09-12 22:36:29 $
  *
  *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
@@ -21 +21 @@
 
 #include "psAbort.h"
-#include "psPixels.h"
+#include "psSort.h"
 #include "psMemory.h"
 #include "psAssert.h"
 #include "psError.h"
 
+#include "psPixels.h"
+
 #define PIXELS_DEFAULT_ADD 10           // Default number to add, if not specified
 
@@ -35 +37 @@
     psFree(pixels->data);
 }
-
-// for use by qsort, etc.
-static int comparePixelCoord(psPixelCoord* coord1,
-                             psPixelCoord* coord2)
-{
-    // check row first
-    if (coord1->y < coord2->y) {
-        return -1;
-    }
-
-    if (coord1->y > coord2->y) {
-        return 1;
-    }
-
-    // rows are the same, so check column
-    if (coord1->x < coord2->x) {
-        return -1;
-    }
-
-    if (coord1->x > coord2->x) {
-        return 1;
-    }
-
-    return 0;
-}
-
 
 static psPixels *pixelsAlloc(const char *file,
@@ -254 +230 @@
     }
 
-    // sort the OUT array to help in searching for duplicates later
-    qsort(out->data, out->n, sizeof(psPixelCoord), (qsortCompareFunc)comparePixelCoord);
-
-    // add non-duplicate values in pixels to the end of the output list (unsorted!)
-    long numInPix = pixels->n;          // Number of input pixels
-    long numOutPix = out->n;            // (Original) number of output pixels
-    for (long i = 0; i < numInPix; i++) {
-        psPixelCoord pix = pixels->data[i]; // Coordinate of interest
-        if (!bsearch(&pix, out->data, numOutPix, sizeof(psPixelCoord), (qsortCompareFunc)comparePixelCoord)) {
-            psPixelsAdd(out, out->nalloc, pix.x, pix.y);
-        }
-    }
+    long numIn = pixels->n;             // Number of input pixels
+    long numOut = out->n;               // Number of (original) output pixels
+    out = psPixelsRealloc(out, numIn + numOut);
+    memcpy(&out->data[numOut], pixels->data, numIn * sizeof(psPixelCoord));
+    out->n = numIn + numOut;
+
+    return out;
+}
+
+// Macro functions for sorting a pixel list
+#define PSPIXELS_SORT_COMPARE(A,B) (data[A].y < data[B].y || data[A].x < data[B].x)
+#define PSPIXELS_SORT_SWAP(TYPE,A,B) { \
+    if (A != B) { \
+        TYPE temp = data[A]; \
+        data[A] = data[B]; \
+        data[B] = temp; \
+    } \
+}
+
+psPixels* psPixelsDuplicates(psPixels *out, const psPixels *pixels)
+{
+    PS_ASSERT_PIXELS_NON_NULL(pixels, NULL);
+    if (pixels->n <= 1) {
+        return psPixelsCopy(out, pixels);
+    }
+
+    long numIn = pixels->n;          // Number of input pixels
+    out = psPixelsRealloc(out, numIn);
+
+    psPixelCoord *data = pixels->data;  // Dereference input
+    PSSORT(numIn, PSPIXELS_SORT_COMPARE, PSPIXELS_SORT_SWAP, psPixelCoord);
+
+    long numOut = 0;                     // Number of output pixels
+    for (long i = 0; i < numIn; numOut++) {
+        psPixelCoord pix = data[i];     // Coordinates of interest
+        for (i++; i < numIn && data[i].x == pix.x && data[i].y == pix.y; i++); // No action
+        out->data[numOut] = pix;
+    }
+    out->n = numOut;
 
     return out;

trunk/psLib/src/types/psPixels.h

@@ -6 +6 @@
  *  @author Robert DeSonia, MHPCC
  *
- *  @version $Revision: 1.29 $ $Name: not supported by cvs2svn $
- *  @date $Date: 2008-08-14 03:18:41 $
+ *  @version $Revision: 1.30 $ $Name: not supported by cvs2svn $
+ *  @date $Date: 2008-09-12 22:36:29 $
  *
  *  Copyright 2004-2005 Maui High Performance Computing Center, University of Hawaii
@@ -214 +214 @@
  *  out is NULL, a new psPixels shall be allocated, and the contents of
  *  pixels simply copied in. If pixels is NULL, the function shall generate
- *  an error and return NULL. The function shall take care to ensure that
- *  there are no duplicate pixels in out.
+ *  an error and return NULL.
  *
  *  @return psPixels         Concatenated psPixel list
@@ -224 +223 @@
 );
 
+/// Remove duplicates in a list of pixels
+psPixels* psPixelsDuplicates(
+    psPixels *out, ///< Output list with duplicates removed, or NULL
+    const psPixels *pixels ///< Input list of pixels
+    );
 
 /** Prints a psPixels to specified destination.

trunk/psLib/src/types/psTree.h

@@ -3 +3 @@
 
 #include <psError.h>
+#include <psVector.h>
 
 /// An array of coordinates for the tree

trunk/psLib/test/types/tap_psPixels_all.c

@@ -51 +51 @@
     }
     //Make sure psMemCheckPixels works correctly - return false
-    // XXX EAM : disabled -- failing test causes segfault  
+    // XXX EAM : disabled -- failing test causes segfault
     if (0) {
         int j = 2;
@@ -349 +349 @@
     {
         psMemId id = psMemGetId();
-        psPixels *outPixels = psPixelsAlloc(5);
+        psPixels *outPixels = psPixelsAlloc(6);
         in.x = 1.0;
         in.y = 1.0;
@@ -360 +360 @@
         in.x = 2.0;
         psPixelsSet(outPixels, 4, in);  //2, 1
-        psPixels *testPixels = psPixelsAlloc(6);
+        in.y = 2.0;
+        psPixelsSet(outPixels, 5, in);  //2, 2
+        psPixels *testPixels = psPixelsAlloc(7);
         in.x = 1.0;
         in.y = 1.0;
@@ -370 +372 @@
         in.x = 2.0;
         psPixelsSet(testPixels, 3, in);  //2, 1
+        in.y = 2.0;
+        psPixelsSet(testPixels, 4, in);  //2, 2
         in.x = 1.0;
-        psPixelsSet(testPixels, 4, in);  //1, 1
+        psPixelsSet(testPixels, 5, in);  //1, 2
         in.x = 5.0;
         in.y = 3.0;
-        psPixelsSet(testPixels, 5, in);  //5, 3
+        psPixelsSet(testPixels, 6, in);  //5, 3
         outPixels = psPixelsConcatenate(outPixels, testPixels);
-        ok(outPixels->n == 6, "psPixelsConcatenate:  return properly concatenate pixel list for valid inputs.");
+        outPixels = psPixelsDuplicates(outPixels, outPixels);
+        // Should be 5 entries: (1,1) (2,1) (1,2) (2,2) (5,3)
+        ok(outPixels->n == 5, "psPixelsConcatenate:  return properly concatenate pixel list for valid inputs.");
         psFree(testPixels);
         psFree(outPixels);