Homework #4 – Stacks

format.h

#if -0


// ----------------------------------------------------------------------------
// SYNOPSYS
// ----------------------------------------------------------------------------
char* format(const char* format, ...);
int   fmtlen(const char*    ptr, ...);

// ----------------------------------------------------------------------------
// EXAMPLE
// ----------------------------------------------------------------------------
{
	errno = 0;

	const char* buffer = format("%i", 42);
	const int   lenght = fmtlen(buffer);

	if (errno != 0)
	{
		assert(strcmp(buffer, "42") == 0 && strlen("42") == lenght);
	}
}


#endif
#pragma once
#include <alloca.h>
#include <stdio.h>

#define format_size_t            int
#define format_size_offset     ( 0 - sizeof(format_size_t)                )
#define format_size_address(M) ( (format_size_t*)(M + format_size_offset) )
#define fmtlen(M)              ( *(format_size_address(M))                )
#define format(...)                                                            	\
({                                                                             	\
	const format_size_t  count = snprintf(NULL, 0, __VA_ARGS__);           	\
	void*               memory = alloca( sizeof(format_size_t)             	\
	                                   + sizeof(char) * count              	\
	                                   + sizeof('\0')         );           	\
	format_size_t*      lenght = format_size_address(memory);              	\
	                   *lenght = count;                                    	\
                                                                               	\
	assert(snprintf(memory,count, __VA_ARGS__) == count);                  	\
	memory;                                                                	\
})

hw4.c

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

#include "new.h"
#include "format.h"
#include "stack.h"

int to_int(const char digit)
{
	return digit - '0';
}

int addDigits(const char left, const char right)
{
	return to_int(left) + to_int(right);
}

void faddLargeNumbers(FILE* stream, const char* Lnumber, const char* Rnumber)
{
	stack*   left = new(stack, Lnumber);
	stack*  right = new(stack, Rnumber);
	stack* result = new(stack, "");

	int carry = 0;

	// while at least one stack is not empty
	while (stack_empty(left) == false || stack_empty(right) == false)
	{
		char* buffer;
		char  unit;

		//  pop a numeral from each nonempty stack and add them to result
		const char  l = stack_empty(left)  ? '0' : stack_pop(left);
		const char  r = stack_empty(right) ? '0' : stack_pop(right);
		const int res = addDigits(l, r) + carry;

		//  push the unit part of addition onto a new stack called the result stack
		buffer = format("%i", res);
		unit   = buffer[fmtlen(buffer) -1];
		stack_push(result, unit);

		//  store the carry
		buffer[fmtlen(buffer) -1] = '\0';
		carry = atoi(buffer);
	}

	if (carry)
	{
		fprintf(stream, "%i", carry);
	}

	//  pop numbers from the result stack and display them
	while (stack_empty(result) == false)
	{
		fprintf(stream, "%c", stack_pop(result));
	}

	delete(stack,   left);
	delete(stack,  right);
	delete(stack, result);
}

void addLargeNumbers(const char* left, const char* right)
{
	faddLargeNumbers(stdout, left, right);
}

bool test_faddLargeNumbers(const char* left, const char* right,
                           const char* reference)
{
	char* buffer = NULL;
	size_t  size = 0;
	FILE* stream = open_memstream(&buffer, &size);

	faddLargeNumbers(stream, left, right);
	fclose(stream);
	const bool test = strcmp(buffer, reference) == 0;
	free(buffer);
	return test;
}

int main(void)
{
	// Implement a test program that demonstrates adding at least three pairs of large
	// numbers (numbers larger than can be represented by a long). 

	// Assuming a long is difined as : unsigned long ← 0 to 4294967295
	assert(test_faddLargeNumbers("099999999999",            "1",  "100000000000"));
	assert(test_faddLargeNumbers("000000000000",            "1",  "000000000001"));
	assert(test_faddLargeNumbers("685696514687", "854688321354", "1540384836041"));
	return EXIT_SUCCESS;
}

new.h

#if -0


// ----------------------------------------------------------------------------
// SYNOPSYS
// ----------------------------------------------------------------------------
typename new(typename, constructor arguments...);
void  delete(typename, typename* pointer);

// ----------------------------------------------------------------------------
// EXAMPLE
// ----------------------------------------------------------------------------

{
	string* ptr = new(string, "content");

	...
	delete(string, ptr);
}


#endif
#pragma once
#include <stdlib.h>
#include <assert.h>

#define new(type, ...)								\
({										\
	type* ptr = malloc(sizeof(type));					\
										\
	assert(ptr);								\
	if (ptr)								\
	{									\
		type##_constructor(ptr, __VA_ARGS__);				\
	}									\
	ptr;             							\
})

#define delete(type, ptr)							\
({										\
	if (ptr)								\
	{									\
		type##_destructor(ptr);						\
	}									\
	free(ptr);								\
})

stack.c

#include <stdlib.h>
#include <string.h>
#include "stack.h"

void stack_constructor(stack* this, const char* content)
{
	this->size = strlen(content);
	this->data = strdup(content);
}

void stack_destructor(stack* this)
{
	free(this->data);
}

char stack_pop(stack* this)
{
	const char element = this->data[--this->size];

	char* allocated = realloc(this->data, sizeof(element) * this->size);

	if (allocated)
	{
		this->data = allocated;
	}

	return element;
}

void stack_push(stack* this, const char element)
{
	char* allocated = realloc(this->data, sizeof(element) * (this->size + 1) );

	if (allocated)
	{
		this->data = allocated;
		this->data[this->size++] = element;
	}
}

bool stack_empty(const stack* this)
{
	return this->size == 0;
}

stack.h

#pragma once
#include <stddef.h>
#include <stdbool.h>

typedef struct
{
	char*  data;
	size_t size;
} stack;

void stack_constructor(stack*, const char* elements);
void stack_destructor(stack*);
char stack_pop(stack*);
void stack_push(stack*, const char element);
bool stack_empty(const stack*);