X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=ucw%2Fsorter%2Fdebug%2Fretros.c;h=d48280ee4ab95178fb27a63029c11cb049cac691;hb=c8ffd6e3b4fc8fd6437c04282c357b2dc290bbbd;hp=7bb692f6bead3094d3d3b06a6ea8a9088d3a0042;hpb=44feaeb65636c36e71fa1fd79710aa746867c17e;p=libucw.git

diff --git a/ucw/sorter/debug/retros.c b/ucw/sorter/debug/retros.c
index 7bb692f6..d48280ee 100644
--- a/ucw/sorter/debug/retros.c
+++ b/ucw/sorter/debug/retros.c
@@ -4,10 +4,11 @@
  *  (c) 2007--2008 Martin Mares <mj@ucw.cz>
  */
 
-#include "sherlock/sherlock.h"
-#include "ucw/getopt.h"
-#include "ucw/md5.h"
-#include "ucw/heap.h"
+#include <ucw/lib.h>
+#include <ucw/getopt.h>
+#include <ucw/md5.h>
+#include <ucw/heap.h>
+#include <ucw/time.h>
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -21,15 +22,15 @@ struct elt {
 };
 
 static struct elt *ary, *alt, **ind, *array0, *array1;
-static uns n = 10000000;
+static uint n = 10000000;
 static u32 sum;
 
-static struct elt *alloc_elts(uns n)
+static struct elt *alloc_elts(uint n)
 {
   return big_alloc(n * sizeof(struct elt));
 }
 
-static void free_elts(struct elt *a, uns n)
+static void free_elts(struct elt *a, uint n)
 {
   big_free(a, n * sizeof(struct elt));
 }
@@ -51,33 +52,33 @@ static int comp_ind(const void *x, const void *y)
 #define ASORT_ELT(i) a[i].key
 #define ASORT_SWAP(i,j) do { struct elt t=a[i]; a[i]=a[j]; a[j]=t; } while (0)
 #define ASORT_EXTRA_ARGS , struct elt *a
-#include "ucw/sorter/array-simple.h"
+#include <ucw/sorter/array-simple.h>
 
 #define ASORT_PREFIX(x) asi_##x
 #define ASORT_KEY_TYPE u32
 #define ASORT_ELT(i) ind[i]->key
 #define ASORT_SWAP(i,j) do { struct elt *t=ind[i]; ind[i]=ind[j]; ind[j]=t; } while (0)
-#include "ucw/sorter/array-simple.h"
+#include <ucw/sorter/array-simple.h>
 
 static void r1_sort(void)
 {
   struct elt *from = ary, *to = alt, *tmp;
 #define BITS 8
-  uns cnt[1 << BITS];
-  for (uns sh=0; sh<32; sh+=BITS)
+  uint cnt[1 << BITS];
+  for (uint sh=0; sh<32; sh+=BITS)
     {
       bzero(cnt, sizeof(cnt));
-      for (uns i=0; i<n; i++)
+      for (uint i=0; i<n; i++)
 	cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
-      uns pos = 0;
-      for (uns i=0; i<(1<<BITS); i++)
+      uint pos = 0;
+      for (uint i=0; i<(1<<BITS); i++)
 	{
-	  uns c = cnt[i];
+	  uint c = cnt[i];
 	  cnt[i] = pos;
 	  pos += c;
 	}
       ASSERT(pos == n);
-      for (uns i=0; i<n; i++)
+      for (uint i=0; i<n; i++)
 	to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
       ASSERT(cnt[(1 << BITS)-1] == n);
       tmp=from, from=to, to=tmp;
@@ -90,27 +91,27 @@ static void r1b_sort(void)
 {
   struct elt *from = ary, *to = alt, *tmp;
 #define BITS 8
-  uns cnt[1 << BITS], cnt2[1 << BITS];
-  for (uns sh=0; sh<32; sh+=BITS)
+  uint cnt[1 << BITS], cnt2[1 << BITS];
+  for (uint sh=0; sh<32; sh+=BITS)
     {
       if (sh)
 	memcpy(cnt, cnt2, sizeof(cnt));
       else
 	{
 	  bzero(cnt, sizeof(cnt));
-	  for (uns i=0; i<n; i++)
+	  for (uint i=0; i<n; i++)
 	    cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
 	}
-      uns pos = 0;
-      for (uns i=0; i<(1<<BITS); i++)
+      uint pos = 0;
+      for (uint i=0; i<(1<<BITS); i++)
 	{
-	  uns c = cnt[i];
+	  uint c = cnt[i];
 	  cnt[i] = pos;
 	  pos += c;
 	}
       ASSERT(pos == n);
       bzero(cnt2, sizeof(cnt2));
-      for (uns i=0; i<n; i++)
+      for (uint i=0; i<n; i++)
 	{
 	  cnt2[(from[i].key >> (sh + BITS)) & ((1 << BITS) - 1)]++;
 	  to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
@@ -124,7 +125,7 @@ static void r1b_sort(void)
 
 static void r1c_sort(void)
 {
-  uns cnt[256];
+  uint cnt[256];
   struct elt *ptrs[256], *x, *lim;
 
   x = ary; lim = ary + n;
@@ -132,7 +133,7 @@ static void r1c_sort(void)
   while (x < lim)
     cnt[x++->key & 255]++;
 
-#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
+#define PTRS(start) x=start; for (uint i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 
   PTRS(alt);
   x = ary; lim = ary + n;
@@ -184,7 +185,7 @@ static inline void sse_copy_elt(struct elt *to, struct elt *from)
 
 static void r1c_sse_sort(void)
 {
-  uns cnt[256];
+  uint cnt[256];
   struct elt *ptrs[256], *x, *lim;
 
   ASSERT(sizeof(struct elt) == 16);
@@ -196,7 +197,7 @@ static void r1c_sse_sort(void)
   while (x < lim)
     cnt[x++->key & 255]++;
 
-#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
+#define PTRS(start) x=start; for (uint i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 
   PTRS(alt);
   x = ary; lim = ary + n;
@@ -240,7 +241,7 @@ static void r1c_sse_sort(void)
 
 static void r1d_sort(void)
 {
-  uns cnt[256];
+  uint cnt[256];
   struct elt *ptrs[256], *x, *y, *lim;
 
   ASSERT(!(n % 4));
@@ -255,7 +256,7 @@ static void r1d_sort(void)
       cnt[x++->key & 255]++;
     }
 
-#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
+#define PTRS(start) x=start; for (uint i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
 
   PTRS(alt);
   x = ary; y = ary+n/2; lim = ary + n/2;
@@ -316,24 +317,24 @@ static void r2_sort(void)
 {
   struct elt *from = ary, *to = alt;
 #define BITS 14
-  uns cnt[1 << BITS];
+  uint cnt[1 << BITS];
   bzero(cnt, sizeof(cnt));
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++;
-  uns pos = 0;
-  for (uns i=0; i<(1<<BITS); i++)
+  uint pos = 0;
+  for (uint i=0; i<(1<<BITS); i++)
     {
-      uns c = cnt[i];
+      uint c = cnt[i];
       cnt[i] = pos;
       pos += c;
     }
   ASSERT(pos == n);
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     to[cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++] = from[i];
   ASSERT(cnt[(1 << BITS)-1] == n);
 
   pos = 0;
-  for (uns i=0; i<(1 << BITS); i++)
+  for (uint i=0; i<(1 << BITS); i++)
     {
       as_sort(cnt[i] - pos, alt+pos);
       pos = cnt[i];
@@ -350,32 +351,32 @@ static void r3_sort(void)
 #define THRESHOLD 5000
 #define ODDEVEN 0
 
-  auto void r3(struct elt *from, struct elt *to, uns n, uns lev);
-  void r3(struct elt *from, struct elt *to, uns n, uns lev)
+  auto void r3(struct elt *from, struct elt *to, uint n, uint lev);
+  void r3(struct elt *from, struct elt *to, uint n, uint lev)
   {
-    uns sh = 32 - lev*BITS;
-    uns cnt[BUCKS];
+    uint sh = 32 - lev*BITS;
+    uint cnt[BUCKS];
     bzero(cnt, sizeof(cnt));
-    for (uns i=0; i<n; i++)
+    for (uint i=0; i<n; i++)
       cnt[(from[i].key >> sh) & (BUCKS - 1)]++;
-    uns pos = 0;
-    for (uns i=0; i<BUCKS; i++)
+    uint pos = 0;
+    for (uint i=0; i<BUCKS; i++)
       {
-	uns c = cnt[i];
+	uint c = cnt[i];
 	cnt[i] = pos;
 	pos += c;
       }
     ASSERT(pos == n);
-    for (uns i=0; i<n; i++)
+    for (uint i=0; i<n; i++)
 #if 1
       to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++] = from[i];
 #else
       sse_copy_elt(&to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++], &from[i]);
 #endif
     pos = 0;
-    for (uns i=0; i<BUCKS; i++)
+    for (uint i=0; i<BUCKS; i++)
       {
-	uns l = cnt[i]-pos;
+	uint l = cnt[i]-pos;
 	if (lev >= LEVELS || l <= THRESHOLD)
 	  {
 	    as_sort(l, to+pos);
@@ -431,7 +432,7 @@ static inline struct elt *mrg(struct elt *x, struct elt *xl, struct elt *y, stru
 static void mergesort(void)
 {
   struct elt *from, *to;
-  uns lev = 0;
+  uint lev = 0;
   if (1)
     {
       struct elt *x = ary, *z = alt, *last = ary + (n & ~1U);
@@ -460,7 +461,7 @@ static void mergesort(void)
       x = from;
       z = to;
       last = from + n;
-      uns step = 1 << lev;
+      uint step = 1 << lev;
       while (x + 2*step <= last)
 	{
 	  z = mrg(x, x+step, x+step, x+2*step, z);
@@ -475,18 +476,18 @@ static void mergesort(void)
     ary = alt;
 }
 
-static void sampsort(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
+static void sampsort(uint n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
 {
 #define WAYS 256
   struct elt k[WAYS];
-  uns cnt[WAYS];
+  uint cnt[WAYS];
   bzero(cnt, sizeof(cnt));
-  for (uns i=0; i<WAYS; i++)
+  for (uint i=0; i<WAYS; i++)
     k[i] = ar[random() % n];
   as_sort(WAYS, k);
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     {
-      uns w = 0;
+      uint w = 0;
 #define FW(delta) if (ar[i].key > k[w+delta].key) w += delta
       FW(128);
       FW(64);
@@ -500,20 +501,20 @@ static void sampsort(uns n, struct elt *ar, struct elt *al, struct elt *dest, by
       cnt[w]++;
     }
   struct elt *y = al, *way[WAYS], *z;
-  for (uns i=0; i<WAYS; i++)
+  for (uint i=0; i<WAYS; i++)
     {
       way[i] = y;
       y += cnt[i];
     }
   ASSERT(y == al+n);
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     {
-      uns w = wbuf[i];
+      uint w = wbuf[i];
       *way[w]++ = ar[i];
     }
   y = al;
   z = ar;
-  for (uns i=0; i<WAYS; i++)
+  for (uint i=0; i<WAYS; i++)
     {
       if (cnt[i] >= 1000)
 	sampsort(cnt[i], y, z, dest, wbuf);
@@ -537,20 +538,20 @@ static void samplesort(void)
   xfree(aux);
 }
 
-static void sampsort2(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
+static void sampsort2(uint n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
 {
 #define WAYS 256
   struct elt k[WAYS];
-  uns cnt[WAYS];
+  uint cnt[WAYS];
   bzero(cnt, sizeof(cnt));
-  for (uns i=0; i<WAYS; i++)
+  for (uint i=0; i<WAYS; i++)
     k[i] = ar[random() % n];
   as_sort(WAYS, k);
   struct elt *k1 = ar, *k2 = ar+1, *kend = ar+n;
   byte *ww = wbuf;
   while (k2 < kend)
     {
-      uns w1 = 0, w2 = 0;
+      uint w1 = 0, w2 = 0;
 #define FW1(delta) if (k1->key > k[w1+delta].key) w1 += delta
 #define FW2(delta) if (k2->key > k[w2+delta].key) w2 += delta
       FW1(128); FW2(128);
@@ -570,27 +571,27 @@ static void sampsort2(uns n, struct elt *ar, struct elt *al, struct elt *dest, b
     }
   if (k1 < kend)
     {
-      uns w1 = 0;
+      uint w1 = 0;
       FW1(128); FW1(64); FW1(32); FW1(16);
       FW1(8); FW1(4); FW1(2); FW1(1);
       *ww++ = w1;
       cnt[w1]++;
     }
   struct elt *y = al, *way[WAYS], *z;
-  for (uns i=0; i<WAYS; i++)
+  for (uint i=0; i<WAYS; i++)
     {
       way[i] = y;
       y += cnt[i];
     }
   ASSERT(y == al+n);
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     {
-      uns w = wbuf[i];
+      uint w = wbuf[i];
       *way[w]++ = ar[i];
     }
   y = al;
   z = ar;
-  for (uns i=0; i<WAYS; i++)
+  for (uint i=0; i<WAYS; i++)
     {
       if (cnt[i] >= 1000)
 	sampsort2(cnt[i], y, z, dest, wbuf);
@@ -620,9 +621,9 @@ 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;
+  uint nn = n;
   while (nn)
-    HEAP_DELMIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
+    HEAP_DELETE_MIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
 #undef H_LESS
 }
 
@@ -631,9 +632,9 @@ 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;
+  uint nn = n;
   while (nn)
-    HEAP_DELMIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
+    HEAP_DELETE_MIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
 #undef H_LESS
 }
 
@@ -647,7 +648,7 @@ static void mk_ary(void)
   bzero(block, sizeof(block));
 
   sum = 0;
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     {
 #if 1
       if (!(i % 4))
@@ -659,7 +660,7 @@ static void mk_ary(void)
 #else
       ary[i].key = i*(~0U/(n-1));
 #endif
-      for (uns j=1; j<sizeof(struct elt)/4; j++)
+      for (uint j=1; j<sizeof(struct elt)/4; j++)
 	((u32*)&ary[i])[j] = ROL(ary[i].key, 3*j);
       sum ^= ary[i].key;
     }
@@ -668,7 +669,7 @@ static void mk_ary(void)
 static void chk_ary(void)
 {
   u32 s = ary[0].key;
-  for (uns i=1; i<n; i++)
+  for (uint i=1; i<n; i++)
     if (ary[i].key < ary[i-1].key)
       die("Missorted at %d", i);
     else
@@ -681,14 +682,14 @@ static void mk_ind(void)
 {
   mk_ary();
   ind = xmalloc(sizeof(struct elt *) * n);
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     ind[i] = &ary[i];
 }
 
 static void chk_ind(void)
 {
   u32 s = ind[0]->key;
-  for (uns i=1; i<n; i++)
+  for (uint i=1; i<n; i++)
     if (ind[i]->key < ind[i-1]->key)
       die("Missorted at %d", i);
     else
@@ -703,7 +704,7 @@ int main(int argc, char **argv)
   log_init(argv[0]);
 
   int opt;
-  uns op = 0;
+  uint op = 0;
   while ((opt = cf_getopt(argc, argv, CF_SHORT_OPTS "1", CF_NO_LONG_OPTS, NULL)) >= 0)
     switch (opt)
       {
@@ -716,29 +717,29 @@ int main(int argc, char **argv)
 
   array0 = alloc_elts(n);
   array1 = alloc_elts(n);
-  for (uns i=0; i<n; i++)
+  for (uint i=0; i<n; i++)
     array0[i] = array1[i] = (struct elt) { 0 };
 
-  log(L_INFO, "Testing with %u elements", n);
+  msg(L_INFO, "Testing with %u elements", n);
 
   mk_ary();
   timestamp_t timer;
   init_timer(&timer);
-  for (uns i=0; i<5; i++)
+  for (uint i=0; i<5; i++)
     {
 #if 1
       memcpy(alt, ary, sizeof(struct elt) * n);
       memcpy(ary, alt, sizeof(struct elt) * n);
 #else
-      for (uns j=0; j<n; j++)
+      for (uint j=0; j<n; j++)
 	alt[j] = ary[j];
-      for (uns j=0; j<n; j++)
+      for (uint j=0; j<n; j++)
 	ary[j] = alt[j];
 #endif
     }
-  log(L_DEBUG, "memcpy: %d", get_timer(&timer)/10);
+  msg(L_DEBUG, "memcpy: %d", get_timer(&timer)/10);
 
-#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; msg(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));