Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 01 Sep 2011 21:58:27 -0500
Message-ID: <4E604653.7407@mindspring.com>
Date: Thu, 01 Sep 2011 22:58:27 -0400
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: My latest magnum opus!
References: <4E60142A.575D@mindspring.com> <j3palv$5tj$1@dont-email.me> <4E603F93.19F@mindspring.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 141
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.228.44
X-Trace: sv3-NKQ2o9TSG05lHSCpUxAwTd+USxZ4kGXXHOyx/pR6bRJXuNOUsOD5GB1figHpeHC9Z3IrrcNfs5G7kBS!h8mscxRURPianuxm3DxkQt2jJMzHKKxPlY/52IcdGps1kdozXLSH2dmqyUo31VqRG2dHfuqswgzo!yA1q2kd5XQ==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4997
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:9864

pete wrote:
> 
> Eric Sosman wrote:
> >
> > On 9/1/2011 7:24 PM, pete wrote:
> > > /* BEGIN block_swap_test.c */
> > > [...]
> >
> >      Jon Bentley tackled this problem in one of his "Programming
> > Pearls" columns in CACM, years and years ago.  IIRC, he reported
> > that he had seen manymanymany attempts to solve it "efficiently"
> > with clever analysis of which block was the larger, and by how much,
> > and so on and so forth.  He also reported that every such solution
> > he'd seen was either bug-ridden or actually slower than
> >
> >         Given an array A...FR...Z, to arrive at R...ZA...F:
> >         Reverse the A...F sequence byte for byte
> >         Reverse the R...Z sequence byte for byte
> >         Reverse the entire array byte for byte
> >
> >      I have not examined your code closely -- in truth, I have not
> > even examined it cursorily.  The very fact that it's longer than
> > Bentley's solution tells me it's almost certainly inferior; Bentley's
> > is certainly easier to analyze for correctness.
> 
> I'll look into it.
> Thank you.

Well, I've written it.
Now I have to time it.

I'm optimistic though.
The solution that you gave me, 
always does 
(lo_size - 1) / 2 + (hi_size - 1) / 2 + (lo_size + hi_size - 1) / 2 
swaps.
That's the worst case for the function that I wrote.

/* BEGIN block_swap_test.c */
/*
** block_swap swaps two contiguous subobjects.
** (base) is the address of the lower addressed subobject.
** (lo_size) is the size of the lower addressed subobject.
** (hi_size) is the size of the higher addressed subobject.
** If either (lo_size) or (hi_size) or both 
** compare equal to zero, then no swapping takes place.
*/
#include <stdio.h>

#define STRING  "0123456789A"

void block_swap(void *base, size_t lo_size, size_t hi_size);
void block_swap2(void *base, size_t lo_size, size_t hi_size);

int 
main(void)
{
    char string[] = STRING;
    size_t right = sizeof string;
    size_t left = 0;

    puts("/* BEGIN block_swap_test.c output */\n");
    do {
        --right;
        block_swap(string, left, right);
        puts(string);
        block_swap2(string, right, left);
        puts(string);
        putchar('\n');
    } while (++left != sizeof string);
    puts("/* END block_swap_test.c output */");
    return 0;
}

void 
block_swap(void *base, size_t lo_size, size_t hi_size)
{
    size_t mod;
    unsigned char *end, *middle, swap;

    mod = lo_size != 0 && hi_size != 0;
    while (mod != 0) {
        end = base;
        middle = end + lo_size;
        if (hi_size > lo_size) {
            mod = hi_size % lo_size;
            base = end + hi_size - mod;
            do {
                swap = *end;
                *end++ = *middle;
                *middle++ = swap;
            } while (--hi_size != mod);
        } else {
            mod = lo_size % hi_size;
            end = middle + hi_size;
            do {
                swap = *--middle;
                *middle = *--end;
                *end = swap;
            } while (--lo_size != mod);
        }
    }
}

void 
block_swap2(void *base, size_t lo_size, size_t hi_size)
{
    unsigned char *first, *middle, *after, swap;

    if (lo_size == 0 || hi_size == 0) {
        return;
    }
    first = base;
    middle = first + lo_size;
    while (--middle > first) {
        swap = *middle;
        *middle = *first;
        *first++ = swap;
    }
    first = base;
    middle = first + lo_size;
    after = middle + hi_size;
    while (--after > middle) {
        swap = *after;
        *after = *middle;
        *middle++ = swap;
    }
    first = base;
    after = first + lo_size + hi_size;
    while (--after > first) {
        swap = *after;
        *after = *first;
        *first++ = swap;
    }
}

/* END block_swap_test.c */


-- 
pete