Groups > comp.lang.c > #6366 > unrolled thread

Re: Array implementation of Stack

Started by	"io_x" <a@b.c.invalid>
First post	2011-06-18 20:32 +0200
Last post	2011-06-25 16:29 -0700
Articles	12 — 6 participants

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

  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

#6366 — Re: Array implementation of Stack

From	"io_x" <a@b.c.invalid>
Date	2011-06-18 20:32 +0200
Subject	Re: Array implementation of Stack
Message-ID	<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 ?

too complex?

>
> /* Array implementation of Stack - Aho, Hopcraft and Ullman, page 68-70
> * section 2.3. We will add element at the bottom and we will grow the
> * stack to top. top_index will keep track of index where element was
> * added as latest. We will use top_index to push/pop elements.
> *
> * VERSION 0.0.
> *
> */
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> enum {
>  SIZE_NAME = 10, SIZE_ARR = 3,
>  VAL_SUCC = 0, VAL_ERR = 1
> };
>
> struct elm
> {
>  int num;
>  char name[SIZE_NAME+1];
> };
>
>
> struct elm_stack
> {
>  int top_index;
>  struct elm* arr[SIZE_ARR];
> };

disclaimer: i'm not one expert

if
struct elm_stack
{int       top_index;
 void* arr[SIZE_ARR];
};

stack could represent different objects

> int push(struct elm_stack* , struct elm* );
> void pop(struct elm_stack* );

each function can fail and has to return
the error value

> struct elm_stack* stack_init(void);
> void print_stack(struct elm_stack* );
> struct elm* get_element(const char* c, int n);
>
>
> int main(void)
> {
>  struct elm_stack* s = stack_init();
>
>  struct elm* e0 = get_element("comp", 2);
>  struct elm* e1 = get_element("lang", 1);
>  struct elm* e2 = get_element("c", 0);
>
>  int ret_elem = push(s, e0);
>  if(VAL_ERR == ret_elem)
>    {
>      printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
>      free(e0);
>    }
>
>  ret_elem = push(s, e1);
>  if(VAL_ERR == ret_elem)
>    {
>      printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
>      free(e1);
>    }
>
>  ret_elem = push(s, e2);
>  if(VAL_ERR == ret_elem)
>    {
>      printf("IN: %s @%d: Memory Full\n", __FILE__, __LINE__);
>      free(e2);
>    }
>
>  print_stack(s);
>
>
>  printf("-----------------------------------------\n\n");
>  pop(s);
>  print_stack(s);
>  printf("-----------------------------------------\n\n");
>
>  pop(s);
>  print_stack(s);
>  printf("-----------------------------------------\n\n");
>
>  pop(s);
>  print_stack(s);
>
>  return EXIT_SUCCESS;
> }
>
>
>
> int push(struct elm_stack* s, struct elm* e)
> {
>  int ret;
>
>  if(NULL == s || NULL == e)
>    {
>      printf("IN:%s @%d Invalid Args!\n", __FILE__, __LINE__);
>      ret = VAL_ERR;
>    }

if fail push has print nothing, is the fuction that use push
has  to print the error

>  else if(s->top_index == 0)
>    {
>      ret = VAL_ERR;
>    }
>  else
>    {
>      --(s->top_index);
>      /*      printf("s->top_index = %d\n", s->top_index); */
>      s->arr[s->top_index] = e;
>      /*      printf("%s = %d\n", e->name, e->num); */
>      ret = VAL_SUCC;
>    }
>
>  return ret;
> }
>
>
> void pop(struct elm_stack* s)
> {
>  if(NULL == s)
>    {
>      printf("IN:%s @%d: Invalid Args!\n", __FILE__, __LINE__);
>    }
>  else if(SIZE_ARR <= s->top_index)
>    {
>      printf("Nothing to pop()\n");
>    }
>  else
>    {
>      struct elm* e = s->arr[s->top_index];
>      free(e);

it is not in the fuction pop that the element has to be free;
pop has to return one value of error if for example
stack is void
this is only how i see the subject.

but this is only one type of stack,
the static one, the one that not change its size
than there is the dinamic one, the one that can change
its size.
if i remember well stack could be build on list and on doulble
list , dinamic and static

so one can write one[double list]
and find 3[list, stack, queue]

>      ++(s->top_index);
>    }
> }

[toc] | [next] | [standalone]

#6915

From	"io_x" <a@b.c.invalid>
Date	2011-06-25 09:02 +0200
Message-ID	<4e058797$0$44207$4fafbaef@reader1.news.tin.it>
In reply to	#6366

"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?

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

// macro for types
#define  u64  uint64_t
#define  u32  uint32_t
#define  u16  uint16_t
#define  u8    uint8_t
#define  uns  unsigned

// macro for function
#define  P  printf

// macro for keyWords
#define G  goto
#define R  return
#define W  while
#define F  for
#define T  template
#define TN typename

/* struct stack
  u32 stop, u32  ssize, u32*  sarr,  u32 not used
*/

typedef struct stackNode{
u32       top;
u32      size;
u8**      arr;
u32   notUsed;
}stack;

u32  IniStack(stack**  v, u32  sz)
{u32        t;
 stack    *vv;
 u8     **arr;

 if((int)sz<=0||v==0) R  -1;
 vv = malloc(sizeof(stack));
 if(vv==0)            R  -1;
 t=sz; t*=sizeof(u8*);
 if(t<sz ||(int)t<=0)
     {err: free(vv); *v=0; R  -1;}
 arr=malloc(t); if(t==0) G err;
 *v=vv; vv->top=-1; vv->size=sz;
 vv->arr=arr;  vv->notUsed=0;
 R  0;
}

u32 freeStack(stack**  v)
{u32  *arr, t;
 stack    *vv;

 if(v==0)  R  0;
 vv=*v; free(vv->arr); free(vv);
 *v=0; R  0;
}

u32  ApplyStack(stack**  v, u32 (*f)(u8*))
{u32  i, r;
 u8   **va;
 stack *vv;

 if(v==0||*v==0) R  -1;
 vv=*v;
 if(vv==0) {P("Stack NULL\n"); R  0;}
 if(vv->top==(u32)-1)
           {P("Stack void\n"); R  0;}
 va=vv->arr;
 if((int)vv->top<0||va==0)
           {P("Stack error\n"); R  0;}
 F(i=vv->top, r=0; i!=0; --i)
        r|=f(va[i]);
 r|=f(va[0]);
 R  r;
}

u32  push(stack** v, u8*  elm)
{u8     **va;
 stack   *vv;
 u32       i;

 if(v==0||*v==0) R  -1;
 vv=*v;
 if((int)vv->size<=0||vv->top==(vv->size-1))
                 R  -1;
 ++vv->top; va=vv->arr;
 va[vv->top]=elm;
 R  0;
}

u8*  pop(stack**   v)
{u8  **va, *r;
 stack    *vv;
 u32        i;

 if(v==0||*v==0) R  0;
 vv=*v;
 if((int)vv->size<=0||vv->top==(u32)-1)
                 R  0;
 va=vv->arr;
 r=va[vv->top];
 --vv->top;
 R  r;
}

// 0 means error
u8*  top(stack** v)
{u8      **va;
 stack    *vv;
 u32        i;

 if(v==0||*v==0) R  0;
 vv=*v;
 if((int)vv->size<=0||vv->top==(u32)-1)
                 R  0;
 va=vv->arr;
 R  va[vv->top];
}


u32  printu(u8*  a)
{u32   v, r;
 v=*(u32*)a;
 r=P("%u ", (uns) v);
 if((int)r<=0) R  -1;
 R  0;
}

u32  printd(u8*  a)
{double   v;
 u32      r;

 v=*(double*)a;
 r=P("%f ", v);
 if((int)r<=0) R  -1;
 R  0;
}

int main(void)
{double   d1, d2, d3, d4;
 u32      a1, a2, a3, a4, i, j, r, *rr;
 stack    *u32stack;
 stack      *dstack;

 r=IniStack(&u32stack, 10);
 if(r==(u32)-1)
    {err: P("Errore stack\n"); R  0;}
 r=IniStack(&dstack,   10); if(r==(u32)-1) G err;
 d1=1.123; d2=7.234;
 r=push( &dstack,(u8*) &d1);P("r=%u ", (uns) r);
 r=push( &dstack,(u8*) &d2);P("r=%u ", (uns) r);
 r=ApplyStack(&dstack, printd);P("r=%u ", (uns) r);
 P("\n");
 a1=123; a2=321;
 r=push( &u32stack,(u8*) &a1);P("r=%u ", (uns) r);
 r=push( &u32stack,(u8*) &a2);P("r=%u ", (uns) r);
 r=ApplyStack(&u32stack, printu);P("r=%u ", (uns) r);
 P("\n");

 a3=*(u32*)pop(&u32stack);
 a4=*(u32*)pop(&u32stack);
 P("a3=%u, a4=%u\n", (uns) a3, (uns) a4);
 r=ApplyStack(&u32stack, printu);P("r=%u ", (uns) r);
 P("\n");

 r=freeStack(&dstack);  P("r=%u ", (uns) r);
 r=freeStack(&u32stack);P("r=%u ", (uns) r);
 R  0;
}

-------------------------
r=0 r=0 7.234000 1.123000 r=0
r=0 r=0 321 123 r=0
a3=321, a4=123
Stack void
r=0
r=0 r=0
-------------------------

[toc] | [prev] | [next] | [standalone]

#6955

From	"io_x" <a@b.c.invalid>
Date	2011-06-26 07:25 +0200
Message-ID	<4e06c256$0$15665$4fafbaef@reader2.news.tin.it>
In reply to	#6915

"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...

#include <limits.h>
// CHAR_BIT
#include <stdlib.h>
#include <stdio.h>

// macro for types
#if  CHAR_BIT != 8
#error  "Non posso compilare con questo sistema"
#endif

#define  u8  unsigned char

#if   ULONG_MAX == 0xFFFFFFFF
#define  u32 unsigned long
#elif UINT_MAX  == 0xFFFFFFFF
#define  u32 unsigned int
#elif USHRT_MAX == 0xFFFFFFFF
#define  u32 unsigned short
#else
#error  "Non posso compilare con questo sistema"
#endif

#define  uns  unsigned

// macro for function
#define  P  printf

// macro for keyWords
#define G  goto
#define R  return
#define W  while
#define F  for
#define T  template
#define TN typename
#define S  sizeof

/* struct stack
  u32 stop, u32  ssize, u32*  sarr,  u32 not used
*/

typedef struct stackelem{
u32        sz;
u8*       arr;
}sele;


typedef struct stackNode{
u32       top;
u32      size;
sele*     arr;
u32   notUsed;
}stack;


u32  IniStack(stack**  v, u32  sz)
{u32       t;
 stack   *vv;
 sele   *arr;

 if(sz==0||v==0||sz>0xFFFFFF)
                      R  -1;
 vv = malloc(S(stack));
 if(vv==0)            R  -1;
 t=sz; t*=S(sele);
 if(t<sz ||t==0||t > 0xFFFFFF)
     {err: free(vv); *v=0; R  -1;}
 arr=malloc(t); if(t==0) G err;
 *v=vv; vv->top=-1; vv->size=sz;
 vv->arr=arr;  vv->notUsed=0;
 R  0;
}

u32 freeStack(stack**  v)
{u32        i;
 stack    *vv;

 if(v==0)  R  0;
 vv=*v;
 if(vv==0) R  0;
 F(i=0; i<=vv->top; ++i)
     free( (vv->arr)[i].arr );
 free(vv->arr); free(vv);
 *v=0; R  0;
}

u32  ApplyStack(stack**  v, u32 (*f)(sele*))
{u32   i, r;
 sele   *va;
 stack  *vv;

 if(v==0||*v==0) R  -1;
 vv=*v;
 if(vv==0) {P("Stack NULL\n"); R  0;}
 if(vv->top==(u32)-1)
           {P("Stack void\n"); R  0;}
 va=vv->arr;
 if(vv->top>0xFFFFFF||va==0)
           {P("Stack error\n"); R  0;}
 F(i=vv->top, r=0; i!=0; --i)
        r|=f(va+i);
 r|=f(va);
 R  r;
}

stack**   push(stack** v, u8*  elm, u32 elmsz)
{sele    *va;
 u8       *r;
 stack   *vv;
 u32    i, j;

 if(v==0||*v==0||elm==0||elmsz==0||elmsz>0xFFFFF)
                 R  0;
 vv=*v;
 if(vv->size==0|| vv->size>0xFFFFFF)
                 R  0;
 if(vv->top==(vv->size-1))
   {if(vv->size>0xFFFFF)  R  0;
    i=2*vv->size;
    j=i*S(sele);
    if(i>=j||j>0xFFFFF)   R  0;
    va=realloc(vv->arr, j);
    if(va==0)             R  0;
    vv->arr=va;
    vv->size=i;
   }
 r=malloc(elmsz);
 if(r==0)        R  0;

 ++vv->top; va=vv->arr;

 va[vv->top].sz=elmsz;
 F(i=0; i<elmsz; ++i)
     r[i]=elm[i];
 va[vv->top].arr=r;
 R  v;
}

/*
Se elm!=0 fa il pop dell'elemento
in ogni caso ritorna un puntatore all'elemento popped
 0 significa errore
*/
stack**  pop(u8*  elm, u32 elmsz, stack** v)
{sele     *va;
 u8        *r;
 stack    *vv;
 u32        i;

 if(v==0||*v==0) R  0;
 if(elm!=0&&(elmsz>0xFFFFFF||elmsz==0))
                 R  0;
 vv=*v;
 if(vv->size>0xFFFFFF||vv->top==(u32)-1)
                 R  0;
 va=vv->arr;
 if(elm!=0 && va[vv->top].sz!=elmsz)
                 R  0;
 r=va[vv->top].arr;
 if(elm!=0)
    F(i=0; i<elmsz; ++i)
        elm[i]=r[i];
 free(r);
 va[vv->top].arr=0;
 --vv->top;
 R  v;
}

// 0 means error
stack**  top(u8*  elm, u32 elmsz, stack** v)
{sele     *va;
 stack    *vv;
 u32        i;

 if(v==0||*v==0) R  0;
 if(elm!=0&&(elmsz>0xFFFFFF||elmsz==0))
                 R  0;
 vv=*v;
 if(vv->size>0||vv->top==(u32)-1)
                 R  0;
 va=vv->arr;
 if(va[vv->top].sz!=elmsz)
                 R  0;
 if(elm!=0)
   F(i=0; i<elmsz; ++i)
        elm[i]=va[vv->top].arr[i];
 R  v;
}


u32  printu(u8*  a)
{u32   v, r;
 v=*(u32*)a;
 r=P("%u ", (uns) v);
 if((int)r<=0) R  -1;
 R  0;
}

u32  printd(u8*  a)
{double   v;
 u32      r;

 v=*(double*)a;
 r=P("%f ", v);
 if((int)r<=0) R  -1;
 R  0;
}

u32  printE(sele *v)
{if(v==0)  R  -1;
      if(v->sz==S(double))
            R  printd(v->arr);
 else if(v->sz==S(u32))
            R  printu(v->arr);
 else       R  -1;
}

int test(void)
{double   a;
 stack  *ps;
 u32      b, r;

 IniStack( &ps, 10);

 push(&ps, (a=1.1, &a), S a);
 push(&ps, (a=1.2, &a), S a);
 push(&ps, (a=1.3, &a), S a);
 push(&ps, (b=1  , &b), S b);
 push(&ps, (b=2  , &b), S b);
 push(&ps, (b=3  , &b), S b);
 ApplyStack(&ps, printE);

 freeStack(&ps);
 R  0;
}

int main(void)
{double   d1, d2, d3, d4, *d5;
 u32      a1, a2, a3, a4, i, j, r;
 double   dd1, dd2, dd3, dd4;
 u32      aa1, aa2, aa3, aa4;
 stack   *dstack, **rr, **rs;

 IniStack( &dstack, 10);

 d1=1.1; d2=2.2; d3=3.3; d4=4.4;
 a1=1;   a2=2;   a3=3;   a4=4;

 rs=push( push(&dstack, &d1, S d1) , &d2, S d2);
 if(rs==0){errPush: P("Errore di push\n");
           freeStack(&dstack);  R  0;}

 ApplyStack(&dstack, printE);

 rr=pop(&d3, S d3, &dstack );
 if(rr==0){errPop: P("Errore di pop\n");
           freeStack(&dstack);  R  0;}

 rr=pop(&d4, S d4, &dstack );
 if(rr==0) G  errPop;

 P("d3=%f, d4=%f\n", d3, d4);
 d3=3.3; d4=4.4;
 rs=push( push(&dstack, &d1, S d1), &d2, S d2);
 if(rs==0) G  errPush;
 rs=push( push(&dstack, &d3, S d3), &d4, S d4);
 if(rs==0) G  errPush;

 d5=malloc(sizeof(double));   if(d5==0) G  errPush;
 *d5=123.456;
 rs=push(&dstack, d5, S *d5); if(rs==0) G  errPush;

 rs=push( push(&dstack, &a1, S  a1), &a2, S  a2);
 if(rs==0) G  errPush;
 rs=push( push(&dstack, &a3, S  a3), &a4, S  a4);
 if(rs==0) G  errPush;

 rr=pop(&aa4, S(u32), &dstack );
 if(rr==0) G  errPop;
 rr=pop(&aa3, S(u32), &dstack );
 if(rr==0) G  errPop;
 rr=pop(&aa2, S(u32), &dstack );
 if(rr==0) G  errPop;
 rr=pop(&aa1, S(u32), &dstack );
 if(rr==0) G  errPop;
 P("aa1,2,3,4= %u %u %u %u\n",
  (uns) aa1, (uns) aa2, (uns) aa3, (uns) aa4);

 r=ApplyStack(&dstack, printE);  P("r=%u\n", (uns) r);
 pop(0, 0, &dstack );
 ApplyStack(&dstack, printE);
 free(d5);
 r=freeStack(&dstack);  P("r=%u ", (uns) r);
 test();
 R  0;
}

/*
2.200000 1.100000 d3=2.200000, d4=1.100000
aa1,2,3,4= 1 2 3 4
123.456000 4.400000 3.300000 2.200000 1.100000 r=0
4.400000 3.300000 2.200000 1.100000 r=0 3 2 1 1.300000 1.200000 1.100000
*/

[toc] | [prev] | [next] | [standalone]

#6958

From	pete <pfiland@mindspring.com>
Date	2011-06-26 02:11 -0400
Message-ID	<4E06CDAB.2E20@mindspring.com>
In reply to	#6955

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

[toc] | [prev] | [next] | [standalone]

#6977

From	"io_x" <a@b.c.invalid>
Date	2011-06-26 19:08 +0200
Message-ID	<4e076738$0$44197$4fafbaef@reader1.news.tin.it>
In reply to	#6958

"pete" <pfiland@mindspring.com> ha scritto nel messaggio
news:4E06CDAB.2E20@mindspring.com...
> 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);
> }

i prefer order array of pointers
this is always O(nlog n) but here n is n pointers to void* or
(<=> pointers to unsigned char)
and not n: struct or type
some cpu i imagine handle better sizeof(void*) than sizeof(type)
[here sizeof(void*) == word of the cpu, basic register type len
 as int or unsigned]

[toc] | [prev] | [next] | [standalone]

#7807

From	"io_x" <a@b.c.invalid>
Date	2011-07-07 06:59 +0200
Message-ID	<4e153ccf$0$15663$4fafbaef@reader2.news.tin.it>
In reply to	#6955

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4e06c256$0$15665$4fafbaef@reader2.news.tin.it...
>
> u32  IniStack(stack**  v, u32  sz)
> {u32       t;
> stack   *vv;
> sele   *arr;
>
> if(sz==0||v==0||sz>0xFFFFFF)
>                      R  -1;
> vv = malloc(S(stack));
> if(vv==0)            R  -1;
> t=sz; t*=S(sele);
> if(t<sz ||t==0||t > 0xFFFFFF)
>     {err: free(vv); *v=0; R  -1;}
> arr=malloc(t); if(t==0) G err;
> *v=vv; vv->top=-1; vv->size=sz;
> vv->arr=arr;  vv->notUsed=0;
> R  0;
> }

the below is one much better language

<< top=0,  size=4,  arr=8, notUsed=12

;0k,4j,8i,12ra, 16P_v, 20P_sz
IniStack:
<i,j,k
    i=^16  |j=^20
    i==0#.e|j<=0?#.e|D*i=0|#.1
.e: a=-1|stc|#.z
.1: malloc<(16)|a==0#.e|k=a
    a=j|c=8    |mul   c|r#.2
    malloc<(a) |a==0!#.3
.2:    free<(k)|#.e
.3: *i=k
    D*k+top=-1|D*k+size   =j
    D*k+arr= a|D*k+notUsed=0
    a^=a  ; => CF==0
.z:
>i,j,k
ret  8
etc etc

>> top,  size,  arr, notUsed

[toc] | [prev] | [next] | [standalone]

#7906

From	Shao Miller <sha0.miller@gmail.com>
Date	2011-07-07 19:25 -0400
Message-ID	<iv5f5c$o8p$1@dont-email.me>
In reply to	#7807

On 7/7/2011 00:59, io_x wrote:
>
> the below is one much better language
>
> <<  top=0,  size=4,  arr=8, notUsed=12
>
> ;0k,4j,8i,12ra, 16P_v, 20P_sz
> IniStack:
> <i,j,k
>      i=^16  |j=^20
>      i==0#.e|j<=0?#.e|D*i=0|#.1
> .e: a=-1|stc|#.z
> .1: malloc<(16)|a==0#.e|k=a
>      a=j|c=8    |mul   c|r#.2
>      malloc<(a) |a==0!#.3
> .2:    free<(k)|#.e
> .3: *i=k
>      D*k+top=-1|D*k+size   =j
>      D*k+arr= a|D*k+notUsed=0
>      a^=a  ; =>  CF==0
> .z:
>> i,j,k
> ret  8
> etc etc
>

If you tilt your head sideways, it looks like a crab[1].

[1] http://en.wikipedia.org/wiki/File:Liocarcinus_vernalis.jpg

[toc] | [prev] | [next] | [standalone]

#7990

From	"io_x" <a@b.c.invalid>
Date	2011-07-08 20:06 +0200
Message-ID	<4e1746b2$0$44199$4fafbaef@reader1.news.tin.it>
In reply to	#7906

"Shao Miller" <sha0.miller@gmail.com> ha scritto nel messaggio
news:iv5f5c$o8p$1@dont-email.me...
> On 7/7/2011 00:59, io_x wrote:
>>
>> the below is one much better language
>>
>> <<  top=0,  size=4,  arr=8, notUsed=12
>>
>> ;0k,4j,8i,12ra, 16P_v, 20P_sz
>> IniStack:
>> <i,j,k
>>      i=^16  |j=^20
>>      i==0#.e|j<=0?#.e|D*i=0|#.1
>> .e: a=-1|stc|#.z
>> .1: malloc<(16)|a==0#.e|k=a
>>      a=j|c=8    |mul   c|r#.2
>>      malloc<(a) |a==0!#.3
>> .2:    free<(k)|#.e
>> .3: *i=k
>>      D*k+top=-1|D*k+size   =j
>>      D*k+arr= a|D*k+notUsed=0
>>      a^=a  ; =>  CF==0
>> .z:
>>> i,j,k
>> ret  8
>> etc etc
>>
>
> If you tilt your head sideways, it looks like a crab[1].
>
> [1] http://en.wikipedia.org/wiki/File:Liocarcinus_vernalis.jpg

that could be like a crab,
but if the ABI on what register has to be preserved are followed,
that has to run the same i.e. if someone enter to it the same input
it exit the same output to
each Os run the x86 cpu so no more UBs;

with that language, i can use stack in a not conventional way
possibly better of how all you use it, or imagine to use it;
it seem to me that came in mind
always idee on what to code; for example in this days i build a fixed array
of 5 bit, 12 element, content in the 2 registers ecx:edx
insert, delet, in that array etc etc

than i can see overflow of each single math operation
for example
a=j|c=8|mul  c|r#.2
would translate as
mov eax, edi|mov ecx, 8|mul ecx|cmp edx, 0|jne  .2
is a 32x32 bit to 64 bit multiplication
in this case is something as eax*ecx and the result
is in the couple of registers eax and edx (eax:edx);
if edx!=0 means the result overflow the 32 bit register
end eax is not sufficient to contain the number

i use the char '|' for separate instruction, a way better than ';'
the char '#' is perfect for jumps and goto;

the macro2d version is one line less than the one of C and it is
much more precise, compact, with a better way to handle errors
and much better to handle loop too, much more readable etc etc

at last for me; not that i'm a big programmer, but i like that
language

[toc] | [prev] | [next] | [standalone]

#6917

From	"io_x" <a@b.c.invalid>
Date	2011-06-25 11:29 +0200
Message-ID	<4e05aa11$0$15671$4fafbaef@reader2.news.tin.it>
In reply to	#6366

"io_x" <a@b.c.invalid> ha scritto nel messaggio
news:4dfceef1$0$44207$4fafbaef@reader1.news.tin.it...

what about one stack of pointers?

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

// macro for types
#define  u64  uint64_t
#define  u32  uint32_t
#define  u16  uint16_t
#define  u8    uint8_t
#define  uns  unsigned

// macro for function
#define  P  printf

// macro for keyWords
#define G  goto
#define R  return
#define W  while
#define F  for
#define T  template
#define TN typename

/* struct stack
  u32 stop, u32  ssize, u32*  sarr,  u32 not used
*/

typedef struct stackNode{
u32       top;
u32      size;
u8**      arr;
u32   notUsed;
}stack;

u32  IniStack(stack**  v, u32  sz)
{u32       t;
 stack   *vv;
 u8    **arr;

 if((int)sz<=0||v==0) R  -1;
 vv = malloc(sizeof(stack));
 if(vv==0)            R  -1;
 t=sz; t*=sizeof(u8*);
 if(t<sz ||(int)t<=0)
     {err: free(vv); *v=0; R  -1;}
 arr=malloc(t); if(t==0) G err;
 *v=vv; vv->top=-1; vv->size=sz;
 vv->arr=arr;  vv->notUsed=0;
 R  0;
}

u32 freeStack(stack**  v)
{u32  *arr, t;
 stack    *vv;

 if(v==0)  R  0;
 vv=*v; free(vv->arr); free(vv);
 *v=0; R  0;
}

u32  ApplyStack(stack**  v, u32 (*f)(u8*))
{u32   i, r;
 u8    **va;
 stack  *vv;

 if(v==0||*v==0) R  -1;
 vv=*v;
 if(vv==0) {P("Stack NULL\n"); R  0;}
 if(vv->top==(u32)-1)
           {P("Stack void\n"); R  0;}
 va=vv->arr;
 if((int)vv->top<0||va==0)
           {P("Stack error\n"); R  0;}
 F(i=vv->top, r=0; i!=0; --i)
        r|=f(va[i]);
 r|=f(va[0]);
 R  r;
}

stack**   push(stack** v, u8*  elm)
{u8     **va;
 stack   *vv;
 u32       i;

 if(v==0||*v==0) R  0;
 vv=*v;
 if((int)vv->size<=0||vv->top==(vv->size-1))
                 R  0;
 ++vv->top; va=vv->arr;
 va[vv->top]=elm;
 R  v;
}

/*
Se elm!=0 fa il pop dell'elemento
in ogni caso ritorna un puntatore all'elemento popped
 0 significa errore
*/
u8*  pop(u8*  elm, u32 elmsz, stack**   v)
{u8  **va, *r;
 stack    *vv;
 u32        i;

 if(v==0||*v==0) R  0;
 if(elm!=0&&(int)elmsz<=0)
                 R  0;
 vv=*v;
 if((int)vv->size<=0||vv->top==(u32)-1)
                 R  0;
 va=vv->arr;
 r=va[vv->top];
 if(elm!=0)
    F(i=0; i<elmsz; ++i)
        elm[i]=r[i];
 --vv->top;
 R  r;
}

// 0 means error
u8*  top(u8*  elm, u32 elmsz, stack** v)
{u8      **va;
 stack    *vv;
 u32        i;

 if(v==0||*v==0) R  0;
 if(elm!=0&&(int)elmsz<=0)
                 R  0;
 vv=*v;
 if((int)vv->size<=0||vv->top==(u32)-1)
                 R  0;
 va=vv->arr;
 if(elm!=0)
   F(i=0; i<elmsz; ++i)
        elm[i]=va[vv->top][i];
 R  va[vv->top];
}


u32  printu(u8*  a)
{u32   v, r;
 v=*(u32*)a;
 r=P("%u ", (uns) v);
 if((int)r<=0) R  -1;
 R  0;
}

u32  printd(u8*  a)
{double   v;
 u32      r;

 v=*(double*)a;
 r=P("%f ", v);
 if((int)r<=0) R  -1;
 R  0;
}

int main(void)
{double   d1, d2, d3, d4, *d5;
 u32      a1, a2, a3, a4, i, j, r;
 double   dd1, dd2, dd3, dd4, *dd5;
 u32      aa1, aa2, aa3, aa4;
 u8       *rr;
 stack    *dstack, **rs;

 IniStack( &dstack, 10);

 d1=1.1; d2=2.2; d3=3.3; d4=4.4;
 a1=1;   a2=2;   a3=3;   a4=4;

 rs=push( push(&dstack, (u8*) &d1), (u8*) &d2);
 if(rs==0){errPush: P("Errore di push\n");
           freeStack(&dstack);  R  0;}

 r=ApplyStack(&dstack, printd);

 rr=pop((u8*)&d3, sizeof(double), &dstack );
 if(rr==0){errPop: P("Errore di pop\n");
           freeStack(&dstack);  R  0;}

 rr=pop((u8*)&d4, sizeof(double), &dstack );
 if(rr==0) G  errPop;

 P("d3=%f, d4=%f\n", d3, d4);
 d3=3.3; d4=4.4;
 rs=push( push(&dstack, (u8*) &d1), (u8*) &d2);
 if(rs==0) G  errPush;
 rs=push( push(&dstack, (u8*) &d3), (u8*) &d4);
 if(rs==0) G  errPush;

 d5=malloc(sizeof(double));  if(d5==0) G  errPush;
 *d5=123.456;
 rs=push(&dstack, (u8*) d5); if(rs==0) G  errPush;

 rs=push( push(&dstack, (u8*) &a1), (u8*) &a2);
 if(rs==0) G  errPush;
 rs=push( push(&dstack, (u8*) &a3), (u8*) &a4);
 if(rs==0) G  errPush;

 rr=pop((u8*)&aa4, sizeof(u32), &dstack );
 if(rr==0) G  errPop;
 rr=pop((u8*)&aa3, sizeof(u32), &dstack );
 if(rr==0) G  errPop;
 rr=pop((u8*)&aa2, sizeof(u32), &dstack );
 if(rr==0) G  errPop;
 rr=pop((u8*)&aa1, sizeof(u32), &dstack );
 if(rr==0) G  errPop;
 P("aa1,2,3,4= %u %u %u %u\n",
  (uns) aa1, (uns) aa2, (uns) aa3, (uns) aa4);

 r=ApplyStack(&dstack, printd);  P("r=%u ", (uns) r);
 rr=pop(0, 0, &dstack );
 r=ApplyStack(&dstack, printd);
 if(rr!=(u8*)d5) P("Errore per mallocata area\n");
 free(d5);
 r=freeStack(&dstack);  P("r=%u ", (uns) r);
 R  0;
}
------------
2.200000 1.100000 d3=2.200000, d4=1.100000
aa1,2,3,4= 1 2 3 4
123.456000 4.400000 3.300000 2.200000 1.100000 r=0 4.400000 3.300000 2.200000
1.100000 r=0

[toc] | [prev] | [next] | [standalone]

#6919

From	"Kleuskes & Moos" <kleuske@xs4all.nl>
Date	2011-06-25 03:04 -0700
Message-ID	<627ecf99-e884-4bd5-804c-5b21f1d7422d@l9g2000yqk.googlegroups.com>
In reply to	#6917

On Jun 25, 11:29 am, "io_x" <a...@b.c.invalid> wrote:

> // macro for function
> #define  P  printf
>
> // macro for keyWords
> #define G  goto
> #define R  return
> #define W  while
> #define F  for
> #define T  template
> #define TN typename

The above macro's ought to be taken out and shot.

[toc] | [prev] | [next] | [standalone]

#6920

From	Ian Collins <ian-news@hotmail.com>
Date	2011-06-25 22:23 +1200
Message-ID	<96lra9Fli9U1@mid.individual.net>
In reply to	#6919

On 06/25/11 10:04 PM, Kleuskes & Moos wrote:
> On Jun 25, 11:29 am, "io_x"<a...@b.c.invalid>  wrote:
>
>> // macro for function
>> #define  P  printf
>>
>> // macro for keyWords
>> #define G  goto
>> #define R  return
>> #define W  while
>> #define F  for
>> #define T  template
>> #define TN typename
>
> The above macro's ought to be taken out and shot.

Twice!

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#6947

From	Patrick Scheible <kkt@zipcon.net>
Date	2011-06-25 16:29 -0700
Message-ID	<86mxh5v6au.fsf@zipcon.net>
In reply to	#6919

"Kleuskes & Moos" <kleuske@xs4all.nl> writes:

> On Jun 25, 11:29 am, "io_x" <a...@b.c.invalid> wrote:
>
>> // macro for function
>> #define  P  printf
>>
>> // macro for keyWords
>> #define G  goto
>> #define R  return
>> #define W  while
>> #define F  for
>> #define T  template
>> #define TN typename
>
> The above macro's ought to be taken out and shot.

Especially G for goto.  If you use gotos enough to need a macro for
them, you're doing something very, very wrong.

But all of them should go.  Too cryptic to expect third parties to read,
not cryptic enough to win the obfuscated C contest.

-- Patrick

[toc] | [prev] | [standalone]

csiph-web

Re: Array implementation of Stack

Contents

#6366 — Re: Array implementation of Stack

#6915

#6955

#6958

#6977

#7807

#7906

#7990

#6917

#6919

#6920

#6947