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

Groups > comp.lang.c > #6958

Re: Array implementation of Stack

Show all headers | View raw

io_x wrote:
> 
> "io_x" <a@b.c.invalid> ha scritto nel messaggio
> news:4e058797$0$44207$4fafbaef@reader1.news.tin.it...
> >
> > "io_x" <a@b.c.invalid> ha scritto nel messaggio
> > news:4dfceef1$0$44207$4fafbaef@reader1.news.tin.it...
> >>
> >> "arnuld" <sunrise@invalid.address> ha scritto nel messaggio
> >> news:4df9d41f$0$308$14726298@news.sunsite.dk...
> >>> WANTED:  To write an array implementation of Stack.
> >>> WHAT I GOT:  It works fine.
> >>>
> >>> I think program is still little too complex. Any ideas to improve ?
> >
> > what about one stack of pointers?
> 
> i think at end could be better a stack of objects,
> than a stack of pointers...

Here's an array based stack of structures
which doesn't have any functions written for accessing the stack.

http://www.mindspring.com/~pfilandr/C/q_sort/pt_sort.c

#include <stddef.h>
#include <limits.h>

void 
q1sort(void *base, size_t nmemb, size_t size, 
       int (*compar)(const void *, const void *))
{
    unsigned char *left;
    size_t middle, last, right;
    struct {
        size_t bytes;
        void *base;
    } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;  
    unsigned char *p1, *p2, *end, swap;  
 
    stack -> bytes = nmemb * size;
    stack -> base  = base;
    stack_ptr = stack + 1;
    do {
        --stack_ptr;
        if (stack_ptr -> bytes > size) {
            right = stack_ptr -> bytes - size;
            left = stack_ptr -> base;
            last = middle = 0;
            do {
                middle += size;
                if (compar(left, left + middle) > 0) {
                    last += size;
                    p1 = left + middle;
                    p2 = left + last;
                    end = p2 + size;
                    do {
                        swap  = *p1;
                        *p1++ = *p2;
                        *p2++ = swap;
                    } while (p2 != end);
                }
            } while (middle != right);
            p1 = left;
            p2 = left + last;
            end = p2 + size;
            do {
                swap  = *p1;
                *p1++ = *p2;
                *p2++ = swap;
            } while (p2 != end);
            if (right - last > last) {
                stack_ptr   -> base  = last + size + left;
                stack_ptr++ -> bytes = right - last;
                stack_ptr   -> base  = left;
                stack_ptr++ -> bytes = last;
            } else {
                stack_ptr++ -> bytes = last;
                stack_ptr   -> base  = last + size + left;
                stack_ptr++ -> bytes = right - last;
            }
        }
    } while (stack_ptr != stack);
}

-- 
pete

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

Thread

Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-18 20:32 +0200
  Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-25 09:02 +0200
    Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-26 07:25 +0200
      Re: Array implementation of Stack pete <pfiland@mindspring.com> - 2011-06-26 02:11 -0400
        Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-26 19:08 +0200
      Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-07-07 06:59 +0200
        Re: Array implementation of Stack Shao Miller <sha0.miller@gmail.com> - 2011-07-07 19:25 -0400
          Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-07-08 20:06 +0200
  Re: Array implementation of Stack "io_x" <a@b.c.invalid> - 2011-06-25 11:29 +0200
    Re: Array implementation of Stack "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-25 03:04 -0700
      Re: Array implementation of Stack Ian Collins <ian-news@hotmail.com> - 2011-06-25 22:23 +1200
      Re: Array implementation of Stack Patrick Scheible <kkt@zipcon.net> - 2011-06-25 16:29 -0700

csiph-web