Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #9864

Re: My latest magnum opus!

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 19:24 -0400
  Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-01 21:13 -0400
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:29 -0400
      Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-01 22:58 -0400
        Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:41 -0400
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 00:53 -0400
    Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 05:39 +0000
      Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-02 02:59 -0400
      Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 08:21 -0400
        Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-02 13:39 +0000
          Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-02 20:53 -0400
            Re: My latest magnum opus! James Dow Allen <jdallen2000@yahoo.com> - 2011-09-03 03:18 -0700
            Re: My latest magnum opus! cri@tiac.net (Richard Harter) - 2011-09-03 17:16 +0000
    Re: My latest magnum opus! Andrey Tarasevich <andreytarasevich@hotmail.com> - 2011-09-02 09:21 -0700
  Re: My latest magnum opus! ImpalerCore <jadill33@gmail.com> - 2011-09-06 06:51 -0700
    Re: My latest magnum opus! pete <pfiland@mindspring.com> - 2011-09-06 18:36 -0400
    Re: My latest magnum opus! Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-06 21:04 -0400

csiph-web