Anonymous

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

#define BUFFER_SIZE 1024

// Represents an area of memory being used to store part of the stack.
struct frame
{
  // Pointer to the previous stack frame.
  struct frame *previous;

  // The buffer for storing data.
  char buffer[BUFFER_SIZE];
};

// Current frame of the stack.
// This will be NULL initially and in future will only be nulled when the last element is pushed off the stack.
struct frame *currentFrame;

/* The first free index within the buffer of the current frame.
 * This lies in [0, BUFFER_SIZE], with BUFFER_SIZE corresponding to the first element of the next (currently 
 * unallocated) frame.
 */
int bufferIndex = 0;

// Number of frames in the stack. Only used for reporting purposes.
int frameCount = 0;

/** Allocate a new frame of the stack. This is intended to only be called when the
 *  current stack frame is full, and the results are undefined if called otherwise.
 */
int newFrame()
{
  struct frame *oldFrame = currentFrame;
  struct frame *nextFrame;

  nextFrame = malloc(sizeof(struct frame));
  
  if (nextFrame == NULL) return -1; 
  else currentFrame = nextFrame;

  currentFrame->previous = oldFrame;

  bufferIndex = 0;
  frameCount++;

  return 0;
}

/** Free the memory used by the current frame and reset the head of the stack to the 
 *  end of the previous frame.
 */
void clearFrame()
{
  if (currentFrame != NULL)
  {
    struct frame *oldFrame = currentFrame->previous;
    free(currentFrame);
    currentFrame = oldFrame;
    
    bufferIndex = BUFFER_SIZE - 1;
    frameCount--;
  }
}

/**
 * The number of characters currently on the stack.
 */ 
int stackSize()
{
  return (currentFrame == NULL) ? 0 : (frameCount - 1) * BUFFER_SIZE + bufferIndex;
}

/**
 * Push a character onto the stack. This returns -1 if it fails to push, or 0 otherwise.
 */
int push(char i)
{
  int error = 0;

  if ((bufferIndex >= BUFFER_SIZE) || (currentFrame == NULL))
  {
    error = newFrame();
  }

  if (error == -1) return -1;

  currentFrame->buffer[bufferIndex++] = i;
  
}

/**
 * Pops the character at the head of the stack and returns it, or returns -1 if the stack is
 * empty.
 */
int pop()
{
  // This will reset bufferIndex to BUFFER_SIZE - 1 if it is currently < 0.
  if (bufferIndex <= 0) clearFrame();

  if (currentFrame == NULL) return EOF;

  return currentFrame->buffer[--bufferIndex];
}

/**
 * Returns the current head of the stack without popping it. 
 */ 
char head()
{
  if (currentFrame == NULL) return EOF;
  else if ((bufferIndex == 0) && (currentFrame->previous == NULL)) return EOF;
  else if (bufferIndex > 0) return currentFrame->buffer[bufferIndex - 1];
  else return currentFrame->previous->buffer[BUFFER_SIZE - 1];
}

/**
 * Duplicates the current head of the stack.
 */
void dup()
{
  char h;

  if ( (h = head()) != EOF ) push(h);
}

int main()
{
  int val;

  while ( (val = getchar()) != EOF )
  {
    if (push(val) == -1)
    {
      printf("Failed to push ");
      putchar(val);

      printf(". Exiting.");
      return -1;
    }
  }

  printf("Stack size %d \n", stackSize());


  // Abuse the stack a bit to make sure it won't segfault when we do something naughty.
  dup();

  while ( (val = pop()) != -1 ) putchar(val);

  putchar('\n');

  printf("Stack size %d \n", stackSize());

  pop();
  head();
  dup();

  return 0;
}