Split autoconf.cfg

[libucw.git] / debug / sorter / retros.c

diff --git a/debug/sorter/retros.c b/debug/sorter/retros.c
index ea6de037ea0ddf662bd8e8d0123797e80f79f1f5..0d417bab48429488ef85494ab95ebb99588ab0f5 100644 (file)
--- a/debug/sorter/retros.c
+++ b/debug/sorter/retros.c
@@ -1,12 +1,13 @@
 /*
  *  Experiments with various sorting algorithms
  *
 /*
  *  Experiments with various sorting algorithms
  *

- *  (c) 2007 Martin Mares <mj@ucw.cz>
+ *  (c) 2007--2008 Martin Mares <mj@ucw.cz>

  */
 
 #include "sherlock/sherlock.h"
 #include "ucw/getopt.h"
 #include "ucw/md5.h"
  */
 
 #include "sherlock/sherlock.h"
 #include "ucw/getopt.h"
 #include "ucw/md5.h"

+#include "ucw/heap.h"

 
 #include <stdio.h>
 #include <stdlib.h>
 
 #include <stdio.h>
 #include <stdlib.h>


@@ -614,6 +615,28 @@ static void samplesort2(void)
   xfree(aux);
 }
 
   xfree(aux);
 }
 

+static void heapsort(void)
+{
+#define H_LESS(_a,_b) ((_a).key > (_b).key)
+  struct elt *heap = ary-1;
+  HEAP_INIT(struct elt, heap, n, H_LESS, HEAP_SWAP);
+  uns nn = n;
+  while (nn)
+    HEAP_DELMIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
+#undef H_LESS
+}
+
+static void heapsort_ind(void)
+{
+#define H_LESS(_a,_b) ((_a)->key > (_b)->key)
+  struct elt **heap = ind-1;
+  HEAP_INIT(struct elt *, heap, n, H_LESS, HEAP_SWAP);
+  uns nn = n;
+  while (nn)
+    HEAP_DELMIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
+#undef H_LESS
+}
+

 static void mk_ary(void)
 {
   ary = array0;
 static void mk_ary(void)
 {
   ary = array0;


@@ -696,6 +719,8 @@ int main(int argc, char **argv)
   for (uns i=0; i<n; i++)
     array0[i] = array1[i] = (struct elt) { 0 };
 
   for (uns i=0; i<n; i++)
     array0[i] = array1[i] = (struct elt) { 0 };
 

+  log(L_INFO, "Testing with %u elements", n);
+

   mk_ary();
   timestamp_t timer;
   init_timer(&timer);
   mk_ary();
   timestamp_t timer;
   init_timer(&timer);


@@ -715,20 +740,22 @@ int main(int argc, char **argv)
 
 #define BENCH(type, name, func) mk_##type(); init_timer(&timer); func; log(L_DEBUG, name ": %d", get_timer(&timer)); chk_##type()
 
 
 #define BENCH(type, name, func) mk_##type(); init_timer(&timer); func; log(L_DEBUG, name ": %d", get_timer(&timer)); chk_##type()
 

-  //BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
-  //BENCH(ary, "arraysort", as_sort(n, ary));
-  //BENCH(ind, "indirect qsort", qsort(ind, n, sizeof(struct elt *), comp_ind));
-  //BENCH(ind, "indirect arraysort", asi_sort(n));
-  //BENCH(ary, "radix1", r1_sort());
-  //BENCH(ary, "radix1b", r1b_sort());
+  BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
+  BENCH(ary, "arraysort", as_sort(n, ary));
+  BENCH(ind, "indirect qsort", qsort(ind, n, sizeof(struct elt *), comp_ind));
+  BENCH(ind, "indirect arraysort", asi_sort(n));
+  BENCH(ary, "radix1", r1_sort());
+  BENCH(ary, "radix1b", r1b_sort());

   BENCH(ary, "radix1c", r1c_sort());
   BENCH(ary, "radix1c", r1c_sort());

-  //BENCH(ary, "radix1c-sse", r1c_sse_sort());
-  //BENCH(ary, "radix1d", r1d_sort());
-  //BENCH(ary, "radix2", r2_sort());
+  BENCH(ary, "radix1c-sse", r1c_sse_sort());
+  BENCH(ary, "radix1d", r1d_sort());
+  BENCH(ary, "radix2", r2_sort());

   BENCH(ary, "radix3", r3_sort());
   BENCH(ary, "radix3", r3_sort());

-  //BENCH(ary, "mergesort", mergesort());
-  //BENCH(ary, "samplesort", samplesort());
-  //BENCH(ary, "samplesort2", samplesort2());
+  BENCH(ary, "mergesort", mergesort());
+  BENCH(ary, "samplesort", samplesort());
+  BENCH(ary, "samplesort2", samplesort2());
+  BENCH(ary, "heapsort", heapsort());
+  BENCH(ind, "indirect heapsort", heapsort_ind());

 
   free_elts(array0, n);
   free_elts(array1, n);
 
   free_elts(array0, n);
   free_elts(array1, n);