Stack Datastructure Implementation

[AceInfinity]

I think this is a pretty decent implementation and a good base for understanding stack functionality. It's entirely in C, but it supports all of the basic stack operations:

[NO-PARSE]#define ALLOCATE_ON_HEAP 1 // determine whether to call init() or init_from_ptr()
#define STACK_TYPE int

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

struct stack_t
{
  void *data;    // data buffer
  size_t offset; // offset of data
  size_t size;   // size of allocated memory buffer
};

/* description: initializes stack_t object referenced by p_stack pointer and
 * allocates internal stack buffer on heap
 * returns: 0 on success, -1 on failure (ex: malloc() failed) */
int init(struct stack_t *p_stack, size_t size)
{
  p_stack->offset = 0;
  p_stack->size = size;
  return (p_stack->data = malloc(size)) ? 0 : -1;
}

/* description: initializes stack_t object referenced by p_stack pointer and
 * points data pointer to pre-allocated buffer
 * returns: 0 on success, -1 on failure (ex: null pointer assigned) */
int init_from_ptr(struct stack_t *p_stack, void *buffer, size_t size)
{
  p_stack->offset = 0;
  p_stack->size = size;
  return (p_stack->data = buffer) ? 0 : -1;
}

/* description: free's stack internal buffer allocated on heap via init() call. */
#define stack_destroy(p_stack) free((p_stack)->data)

/* description: push data to the stack internal buffer by copying n_bytes bytes of
 * memory from src
 * returns: 0 on success, non-zero on failure (ex: stack overflow) */
int push(struct stack_t *p_stack, void *src, size_t n_bytes)
{
  if (!p_stack->data || p_stack->offset + n_bytes > p_stack->size) return -1;
  memcpy((unsigned char *)p_stack->data + p_stack->offset, src, n_bytes);
  p_stack->offset += n_bytes;
  return 0;
}

/* description: pop data to the stack internal buffer by copying n_bytes bytes of
 * memory to dst
 * returns: 0 on success, non-zero on failure (ex: stack overflow) */
int pop(struct stack_t *p_stack, void *dst, size_t n_bytes)
{
  if (!p_stack->data || n_bytes > p_stack->offset) return -1;
  p_stack->offset -= n_bytes;
  memcpy(dst, (unsigned char *)p_stack->data + p_stack->offset, n_bytes);
  return 0;
}

/* description: peek top-level data on stack internal buffer by copying n_bytes bytes of
 * memory to dst before offset
 * returns: 0 on success, non-zero on failure
 * (ex: num bytes requested to peek is too large resulting in stack underflow) */
int peek(struct stack_t *p_stack, void *dst, size_t n_bytes)
{
  if (!p_stack->data || n_bytes > p_stack->offset) return -1;
  memcpy(dst, (unsigned char *)p_stack->data + p_stack->offset - n_bytes,
         n_bytes);
  return 0;
}

/* stack helper macros for pointer arithmetic */
#ifdef STACK_TYPE
#define stack_init(ptr, n)       init(ptr, sizeof(STACK_TYPE) * n)
#define stack_push(ptr, src)     push(ptr, src, sizeof(STACK_TYPE) * 1)
#define stack_pop(ptr, dst)      pop(ptr, dst, sizeof(STACK_TYPE) * 1)
#define stack_peek(ptr, dst, n)  peek(ptr, dst, sizeof(STACK_TYPE) * n)
#endif


int main(void)
{
  const size_t stack_size = 10;
#if !ALLOCATE_ON_HEAP
  STACK_TYPE stack_data[stack_size];
#endif
  struct stack_t stack;

  // initialize stack with specified num elements
#if ALLOCATE_ON_HEAP
  if (stack_init(&stack, stack_size) != 0)
#else
  if (init_from_ptr(&stack, stack_data, stack_size * sizeof(stack_data[0])) != 0)
#endif
  {
    printf("stack initialization error.\n");
    exit(-1);
  }


  // push a bunch of data to stack
  for (size_t i = 0; i < stack_size; ++i)
  {
    STACK_TYPE tmp = (i + 1) * 13;
    printf("PUSH -> %d\n", tmp);
    if (stack_push(&stack, &tmp) != 0)
      printf("warning: stack push() failed.\n");
  }
  printf("\n");

  // peek at top element without updating offset
  STACK_TYPE peek_tmp;
  if (stack_peek(&stack, &peek_tmp, 1) == 0)
    printf("PEEK -> %d\n", peek_tmp);
  else
    printf("PEEK -> failed\n");
  printf("\n");

  // pop a bunch of data from the stack
  for (size_t i = 0; i < stack_size; ++i)
  {
    STACK_TYPE tmp;
    if (stack_pop(&stack, &tmp) != 0)
      printf("warning: stack pop() failed.\n");
    else
      printf("POP -> %d\n", tmp);
  }
  printf("\n");

#if ALLOCATE_ON_HEAP
  stack_destroy(&stack); // free internal buffer
#endif
}[/NO-PARSE]

Allocation can be done on the heap, or the stack object itself can be allocated on the stack and a pointer to that data can be passed in to the appropriate initialization function to initialize from that data. I've also got all of the basic boundary checks and null pointer checks for safety.

edit: Just noticed a problem ->

[NO-PARSE]#define stack_peek(ptr, dst, n)  (peek(ptr, dst, sizeof(STACK_TYPE) * n), *dst)[/NO-PARSE]

This macro is a bit different from the function because of the comma operator dereferencing the pointer which receives the data to peek from the stack. This works perfect in the case that the function call succeeds, but if it fails and returns -1, then that memcpy() never executes and probably shouldn't be dereferencing the destination buffer pointed to by dst. This is just a mention. I've now changed that line to:

[NO-PARSE]#define stack_peek(ptr, dst, n)  peek(ptr, dst, sizeof(STACK_TYPE) * n)[/NO-PARSE]

And modified the relevant code to work with the new macro definition

 

[blueelvis]

Ace, you should probably start a video training series :grin1:

 

[AceInfinity]

I wouldn't have any idea what kind of ground I would cover.