[Mndiff-dev] [mndiff]: r41 - trunk/mnzip/mnzip.c

[michael]

Author: michael
Date: Thu Jun 21 18:23:05 2007
New Revision: 41

Log:
get rid of the bentley sedgewick bwt, this thing has a too creepy worst case behavior
even under #if 0 ;)


Modified:
   trunk/mnzip/mnzip.c

Modified: trunk/mnzip/mnzip.c
==============================================================================
--- trunk/mnzip/mnzip.c	(original)
+++ trunk/mnzip/mnzip.c	Thu Jun 21 18:23:05 2007
@@ -268,53 +268,6 @@ static void qsort2(uint8_t **ptr, int *i
 
 #define read(p) ((p)>=end ? (p)[in - end] : *(p))
 
-static void bssort(const uint8_t **p, int len, int skip, uint8_t *in, uint8_t *end){
-    int pivot;
-    int i=0;
-    int j=0;
-    int k=len-1;
-
-    assert(len>1);
-
-retry:
-    pivot= read(p[len>>1] + skip);
-    for(i=0; i<len; i++)
-        if(read(p[i]+skip) != pivot)
-            break;
-    if(i==len){
-        skip++;
-        goto retry;
-    }
-
-    i=0;
-    while(j<=k){
-        uint8_t *pj= p[j];
-        int v= read(pj + skip);
-        if(v == pivot)
-            j++;
-        else if(v<pivot){
-            p[j]= p[i]; p[i]= pj;
-            j++;
-            i++;
-        }else{
-            p[j]= p[k]; p[k]= pj;
-            do{
-                k--;
-            }while(read(p[k] + skip) > pivot);
-        }
-    }
-    assert(i>=0);
-    assert(i<=j);
-    assert(j<=k+1);
-    assert(k<=len-1);
-    if(i>1)
-        bssort(p  , i      , skip  , in, end);
-    if(j-i>1)
-        bssort(p+i, j-i    , skip+1, in, end);
-    if(len-k>2)
-        bssort(p+j, len-1-k, skip  , in, end);
-}
-
 static unsigned int bwt(uint8_t *out, uint8_t *in, unsigned int len){
     unsigned int i, j, ret;
     uint8_t **ptr = malloc(len*sizeof(uint8_t*));
@@ -361,7 +314,7 @@ static unsigned int bwt(uint8_t *out, ui
         ptr[ histogram[ptr2[i][1]]++ ]= ptr2[i];
     }
 fprintf(stderr, "radix sort done\n");
-#if 1
+
     idx2= malloc(len*sizeof(int));
     for(i=len-1; (int)i>=0; i--){
         if(ptr[last][1] != ptr[i][1] || ptr[last][2] != ptr[i][2] ||
@@ -444,17 +397,6 @@ fprintf(stderr, "idx init done\n");
         out[idx[i]]= in[i];
     }
     ret= idx[0];
-#else
-    for(i=1; i<len; i++){
-        if(memcmp(ptr[last]+1, ptr[i]+1, RADIX_PASSES)){
-            if(i-last>1)
-                bssort(ptr + last, i-last, RADIX_PASSES+1, in, in+len);
-            last= i;
-        }
-    }
-    if(i-last>1)
-        bssort(ptr + last, i-last, RADIX_PASSES+1, in, in+len);
-#endif
 
     free(ptr);
     free(ptr2);