Laboratory Solutions

test_stack.c

////////////////////////////////////////////////////////////////////////
// COMP2521 19T0 -- Test a Stack ADT implementation.
//
// 2018-11-29	Jashank Jeremy <jashankj@cse.unsw.edu.au>

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

#include "item.h"
#include "stack.h"
#include "testable.h"

static void test_empty_stack (void);
static void test_one_item_stack (void);
static void test_two_item_stack (void);
static void test_twenty_item_stack (void);
static void test_rolling_stack (void);

int main (void)
{
	white_box_tests ();
	puts ("");

	test_empty_stack ();
	test_one_item_stack ();
	test_two_item_stack ();
	test_twenty_item_stack ();
	test_rolling_stack ();

	puts ("\nAll tests passed. You are awesome!");
	return EXIT_SUCCESS;
}

static void test_empty_stack (void)
{
	puts ("Test 1: testing an empty stack.");
	Stack s = stack_new ();
	assert (stack_size (s) == 0);
	stack_drop (s);
}

static void test_one_item_stack (void)
{
	puts ("Test 2: testing a stack with one item.");
	Stack s = stack_new ();
	stack_push (s, 1);

	assert (stack_size (s) == 1);

	assert (stack_pop (s) == 1);
	assert (stack_size (s) == 0);

	stack_drop (s);
}

static void test_two_item_stack (void)
{
	puts ("Test 3: testing a stack with two items.");
	Stack s = stack_new ();
	stack_push (s, 'a');
	stack_push (s, 'b');

	assert (stack_size (s) == 2);

	assert (stack_pop (s) == 'b');
	assert (stack_size (s) == 1);

	assert (stack_pop (s) == 'a');
	assert (stack_size (s) == 0);

	stack_drop (s);
}

static void test_twenty_item_stack (void)
{
	puts ("Test 4: testing a stack with twenty items.");
	Stack s = stack_new ();

	for (size_t i = 0; i < 20; i++)
		stack_push (s, (Item) i);
	assert (stack_size (s) == 20);

	for (size_t i = 20; i > 0; i--) {
		assert (stack_pop (s) == (Item) i - 1);
		assert (stack_size (s) == i - 1);
	}

	stack_drop (s);
}

static void test_rolling_stack (void)
{
	puts ("Test 5: testing a stack with churn.");
	Stack s = stack_new ();

	for (size_t n = 0; n < 5; n++) {
		for (size_t i = 0; i < 80; i++)
			stack_push (s, (Item) i);

		assert (stack_size (s) == 80);

		for (size_t i = 80; i > 0; i--) {
			assert (stack_pop (s) == (Item) i - 1);
			assert (stack_size (s) == i - 1);
		}
	}

	stack_drop (s);
}

(download)
(back to top)

stack_array.c

////////////////////////////////////////////////////////////////////////
// COMP2521 19T0 -- A Stack ADT implementation, using arrays.
//
// 2018-11-29	Jashank Jeremy <jashankj@cse.unsw.edu.au>
// YYYY-mm-dd   Your Name Here <zNNNNNNN@student.unsw.edu.au>

#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sysexits.h>

#include "item.h"
#include "stack.h"
#include "test1511.h"
#include "testable.h"

#define DEFAULT_SIZE 10

typedef struct stack stack;

struct stack {
	size_t n_items;
	size_t capacity;
	Item *items;
};

static Item *stack_realloc_items (Item *its, size_t new_cap);

static bool stack_should_grow_p (stack *s);
static bool stack_should_shrink_p (stack *s);


/** Create a new, empty Stack. */
stack *stack_new (void)
{
	stack *new = malloc (sizeof *new);
	if (new == NULL)
		err (EX_OSERR, "couldn't allocate stack");
	(*new) = (stack) { .n_items = 0, .capacity = DEFAULT_SIZE };

	new->items = calloc (DEFAULT_SIZE, sizeof(Item));
	if (new->items == NULL)
		err (EX_OSERR, "couldn't allocate stack items");

	return new;
}

/** Destroy a Stack. */
void stack_drop (stack *s)
{
	assert (s != NULL);
	free (s->items);
	free (s);
}

/** Add an item to the top of a Stack. */
void stack_push (stack *s, Item it)
{
	assert (s != NULL);

	if (stack_should_grow_p (s))
		s->items = stack_realloc_items (s->items, s->capacity *= 2);

	s->items[s->n_items] = it;
	s->n_items++;
	return;
}

/** Remove an item from the top of a Stack. */
Item stack_pop (stack *s)
{
	assert (s != NULL);

	Item it = s->items[s->n_items - 1];
	s->n_items--;

	if (stack_should_shrink_p (s))
		s->items = stack_realloc_items (s->items, s->capacity /= 2);

	return it;
}

/** Get the number of items in a Stack. */
size_t stack_size (stack *s)
{
	assert (s != NULL);
	return s->n_items;
}


/** Reallocate the items array, checking for _realloc(3)_ failure. */
static Item *stack_realloc_items (Item *its, size_t new_cap)
{
#ifdef DEBUG_STACK_ARRAY
	warnx ("stack: realloc_items to %zu", new_cap);
#endif
	Item *xs = realloc (its, new_cap * sizeof (Item));
	if (xs == NULL) err (EX_OSERR, "couldn't realloc stack items");
	return xs;
}

/** Should the stack grow? */
static bool stack_should_grow_p (stack *s)
{
	return s->n_items == s->capacity
		;
}

/** Should the stack shrink? */
static bool stack_should_shrink_p (stack *s)
{
	return s->capacity >= s->n_items * 4
		&& s->capacity >= 2 * DEFAULT_SIZE
		;
}

#ifndef nitems
#define nitems(x) (sizeof((x))/(sizeof((x)[0])))
#endif
#define VT_INVERSE "\033[7m"
#define VT_NORMAL  "\033[0m"

static inline void test_header (const char *, const char *);

static void wbt_stack_new (void);
static void wbt_stack_push (void);
static void wbt_stack_pop (void);
static void wbt_stack_size (void);

void white_box_tests (void)
{
	wbt_stack_new ();
	wbt_stack_push ();
	wbt_stack_pop ();
	wbt_stack_size ();
}

static inline void test_header (const char *n, const char *descr)
{
	printf ("%s%s%s: %s\n", VT_INVERSE, n, VT_NORMAL, descr);
}

/** Test that `stack_new' and `stack_drop' work. */
static void wbt_stack_new (void)
{
	test_header ("Test 1", "`stack_new', `stack_drop'");

	stack *s = stack_new ();

	assert (s != NULL);
	assert (s->items != NULL);
	assert (s->n_items == 0);
	assert (s->capacity == DEFAULT_SIZE);

#ifdef IN_ASAN
	assert (! mem_address_is_poisoned (s));
	assert (! mem_region_is_poisoned (s, sizeof (stack)));
	assert (! mem_address_is_poisoned (s->items));
	assert (! mem_region_is_poisoned (
		s->items, sizeof (Item) * DEFAULT_SIZE));
#endif

	stack_drop (s);

#ifdef IN_ASAN
	assert (mem_address_is_poisoned (s));
	assert (mem_region_is_poisoned (s, sizeof (stack)));
#endif
}

/** Test that `stack_push' works. */
static void wbt_stack_push (void)
{
	test_header ("Test 2", "`stack_push'");

	stack s_ = (struct stack){
		.n_items  = 0,
		.capacity = DEFAULT_SIZE,
		.items    = calloc (DEFAULT_SIZE, sizeof (Item))
	};
	stack *s = &s_;
	assert (s->items != NULL);

	Item items[] = {
		0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
		0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f
	};

	for (size_t i = 0; i < nitems (items); i++) {
		stack_push (s, items[i]);
		assert (s->n_items == i + 1);
		assert (
			s->capacity ==
			((s->n_items > DEFAULT_SIZE) ? 2 : 1) * DEFAULT_SIZE
		);

		for (size_t j = 0; j <= i; j++) {
			assert (s->items[j] == items[j]);
		}
	}

	free (s->items);
}

/** Test that `stack_pop' works. */
static void wbt_stack_pop (void)
{
	test_header ("Test 3", "`stack_pop'");

	Item items[] = {
		0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47,
		0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f
	};
	stack s_ = (struct stack){
		.n_items  = nitems (items),
		.capacity = 2 * DEFAULT_SIZE,
		.items    = calloc (2 * DEFAULT_SIZE, sizeof (Item))
	};
	stack *s = &s_;
	assert (s->items != NULL);
	memcpy (s->items, items, sizeof (items));

	for (size_t i = 0; i < nitems (items); i++) {
		Item it = stack_pop (s);
		assert (it == s->items[nitems(items) - i - 1]);
		assert (s->n_items == nitems(items) - i - 1);
		assert (
			s->capacity ==
			((s->n_items <= DEFAULT_SIZE / 2) ? 1 : 2) * DEFAULT_SIZE
		);
	}

	free (s->items);
}

/** Test that stack size functions (`stack_size', `stack_should_grow_p'
 * and `stack_should_shrink_p') all work. */
static void wbt_stack_size (void)
{
	test_header ("Test 4", "stack size functions");
	stack s_ = (struct stack){
		.n_items  = 0,
		.capacity = 10,
		.items    = NULL
	};
	stack *s = &s_;

	assert (stack_size (s) == 0);
	s->n_items = 10;
	assert (stack_size (s) == 10);
	assert (stack_should_grow_p (s) == true);
	assert (stack_should_shrink_p (s) == false);
	s->capacity = 20;
	assert (stack_should_grow_p (s) == false);
	assert (stack_should_shrink_p (s) == false);

	s->capacity = 20;
	s->n_items = 10;
	assert (stack_should_grow_p (s) == false);
	assert (stack_should_shrink_p (s) == false);
	s->n_items = 5;
	assert (stack_size (s) == 5);
	assert (stack_should_grow_p (s) == false);
	assert (stack_should_shrink_p (s) == true);
}

(download)
(back to top)

test_queue.c

////////////////////////////////////////////////////////////////////////
// COMP2521 19T0 -- Test a Queue ADT implementation.
//
// 2018-12-01	Jashank Jeremy <jashankj@cse.unsw.edu.au>

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

#include "item.h"
#include "queue.h"
#include "testable.h"

static void test_empty_queue (void);
static void test_one_item_queue (void);
static void test_two_item_queue (void);
static void test_ten_item_queue (void);
static void test_rolling_queue (void);
static void test_webcms3_2714021 (void);

int main (void)
{
	white_box_tests ();
	puts ("");

	test_empty_queue ();
	test_one_item_queue ();
	test_two_item_queue ();
	test_ten_item_queue ();
	test_rolling_queue ();
	test_webcms3_2714021 ();

	puts ("\nAll tests passed. You are awesome!");
	return EXIT_SUCCESS;
}

static void test_empty_queue (void)
{
	puts ("Test 1: testing an empty queue.");
	Queue q = queue_new ();
	assert (queue_size (q) == 0);
	queue_drop (q);
}

static void test_one_item_queue (void)
{
	puts ("Test 2: testing a queue with one item.");
	Queue q = queue_new ();
	queue_en (q, 1);

	assert (queue_size (q) == 1);

	assert (queue_de (q) == 1);
	assert (queue_size (q) == 0);

	queue_drop (q);
}

static void test_two_item_queue (void)
{
	puts ("Test 3: testing a queue with two items.");
	Queue q = queue_new ();
	queue_en (q, 'a');
	queue_en (q, 'b');

	assert (queue_size (q) == 2);

	assert (queue_de (q) == 'a');
	assert (queue_size (q) == 1);

	assert (queue_de (q) == 'b');
	assert (queue_size (q) == 0);

	queue_drop (q);
}

static void test_ten_item_queue (void)
{
	puts ("Test 4: testing a queue with ten items.");
	Queue q = queue_new ();

	for (size_t i = 0; i < 10; i++)
		queue_en (q, (Item) i);
	assert (queue_size (q) == 10);

	for (size_t i = 0; i < 10; i++) {
		assert (queue_de (q) == (Item) i);
		assert (queue_size (q) == 10 - i - 1);
	}

	queue_drop (q);
}

static void test_rolling_queue (void)
{
	puts ("Test 5: testing a queue with churn.");
	Queue q = queue_new ();
	assert (q != NULL);
	assert (queue_size (q) == 0);

	for (int i = 0; i < 10; i++)
		queue_en (q, i);
	assert (queue_size (q) == 10);

	for (int i = 10; i < 100; i++) {
		Item qv = queue_de (q);   // get a value out
		// printf ("%d ", qv);
		assert (qv == i - 10);   // make sure it's what we expect
		assert (queue_size (q) == 9);
		queue_en (q, i);         // put another value in
		assert (queue_size (q) == 10);
	}

	queue_drop (q);
}

static void test_webcms3_2714021 (void)
{
	puts ("Test 6: /forums/2714016 fix");
	Queue q = queue_new();
	queue_en (q, 2);
	assert (queue_de(q) == 2);
	queue_en (q, 3); // fails here
	assert (queue_de(q) == 3);
	queue_drop (q);
}

(download)
(back to top)

queue_array.c

////////////////////////////////////////////////////////////////////////
// COMP2521 19T0 -- A Queue ADT implementation, using arrays.
//
// 2018-12-01	Jashank Jeremy <jashankj@cse.unsw.edu.au>
// YYYY-mm-dd   Your Name Here <zNNNNNNN@student.unsw.edu.au>

#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sysexits.h>

#include "item.h"
#include "queue.h"
#include "testable.h"

#define DEFAULT_SIZE 10

typedef struct queue queue;

struct queue {
	size_t n_items;
	size_t capacity;
	Item *items;
};

/** Create a new, empty Stack.  $ O(1) $. */
queue *queue_new (void)
{
	queue *new = malloc (sizeof *new);
	if (new == NULL) err (EX_OSERR, "couldn't allocate queue");
	(*new) = (queue) { .n_items = 0, .capacity = DEFAULT_SIZE };

	new->items = calloc (DEFAULT_SIZE, sizeof(Item));
	if (new->items == NULL)
		err (EX_OSERR, "couldn't allocate queue items");

	return new;
}

/** Destroy a Queue.  $ O(1) $. */
void queue_drop (queue *q)
{
	assert (q != NULL);
	free (q->items);
	free (q);
}


/** Add an item to the end of a Queue.  $ O(1) $.
 * Sometimes referred to as "enqueue" or "unshift". */
void queue_en (queue *q, Item it)
{
	assert (q != NULL);
	assert (q->n_items < q->capacity);
	q->items[q->n_items++] = it;
}

/** Remove an item from the front of a Queue.  $ O(n) $.
 * Sometimes referred to as "dequeue" or "shift". */
Item queue_de (queue *q)
{
	assert (q != NULL);
	if (q->n_items == 0) {
		fprintf (stderr, "queue underflow!\n");
		abort();
	}

	Item it = q->items[0];
	q->n_items--;

	// shift the elements across; still O(n) but faster?
	memmove (&q->items[0], &q->items[1], q->n_items * sizeof (Item));

	return it;
}

/** Get the number of items in a Queue.  $ O(1) $. */
size_t queue_size (queue *q)
{
	assert (q != NULL);
	return q->n_items;
}

void white_box_tests (void)
{
	// ... you need to write these!
}

(download)
(back to top)

queue_list.c

////////////////////////////////////////////////////////////////////////
// COMP2521 19T0 -- A Queue ADT implementation, using linked lists.
//
// 2018-12-01	Jashank Jeremy <jashankj@cse.unsw.edu.au>

#include <assert.h>
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <sysexits.h>

#include "item.h"
#include "queue.h"
#include "testable.h"

typedef struct queue queue;
typedef struct queue_node queue_node;

struct queue {
	size_t n_items;
	queue_node *head, *tail;
};

struct queue_node {
	Item item;
	queue_node *next;
};

static queue_node *queue_node_new (Item);

/** Create a new, empty Queue. */
queue *queue_new (void)
{
	queue *new = malloc (sizeof *new);
	if (new == NULL) err (EX_OSERR, "couldn't allocate queue");
	(*new) = (queue) { .n_items = 0, .head = NULL, .tail = NULL };
	return new;
}

/** Destroy a Queue, releasing all resources associated with it. */
void queue_drop (queue *q)
{
	assert (q != NULL);

	queue_node *curr = q->head;
	while (curr != NULL) {
		queue_node *tmp = curr->next;
		free (curr);
		curr = tmp;
	}

	free (q);
}

/** Add an item to the end of a Queue.
 * Sometimes referred to as "enqueue" or "unshift". */
void queue_en (queue *q, Item it)
{
	assert (q != NULL);

	queue_node *node = queue_node_new (it);
	if (q->head == NULL) {
		assert (q->head == NULL && q->tail == NULL && q->n_items == 0);
		q->head = node;
	} else {
		assert (q->head != NULL && q->tail != NULL && q->n_items != 0);
		q->tail->next = node;
	}

	q->tail = node;
	q->n_items++;
	return;
}

/** Remove an item from the front of a Queue.
 * Sometimes referred to as "dequeue" or "shift". */
Item queue_de (queue *q)
{
	assert (q != NULL);
	if (q->head == NULL) {
		fprintf (stderr, "queue underflow!\n");
		assert (q->n_items == 0);
		abort();
	}

	queue_node *del = q->head;
	Item it = del->item;
	q->head = del->next;
	if (q->head == NULL)
		q->tail = NULL;
	q->n_items--;

	free (del);
	return it;
}

/** Get the number of items in a Queue. */
size_t queue_size (queue *q)
{
	assert (q != NULL);
	return q->n_items;
}

static queue_node *queue_node_new (Item it)
{
	queue_node *new = malloc (sizeof *new);
	if (new == NULL) err (EX_OSERR, "couldn't allocate queue_node");
	(*new) = (queue_node) { .item = it, .next = NULL };
	return new;
}

void white_box_tests (void)
{
	// ... you need to write these!
}