init

6 files changed, 292 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..0c9949e
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+arraylist.o
+apptest
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..587a191
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,3 @@
+build:
+	gcc -c arraylist.c -std=c99 -o arraylist.o -Wall
+	gcc test.c arraylist.o -std=c99 -o apptest -Wall
diff --git a/Readme.mdown b/Readme.mdown
new file mode 100644
index 0000000..f5019b3
--- /dev/null
+++ b/Readme.mdown
@@ -0,0 +1,3 @@
+# Arraylist
+
+Generic arraylist implementation in C. WIP.
diff --git a/arraylist.c b/arraylist.c
new file mode 100644
index 0000000..048299f
--- /dev/null
+++ b/arraylist.c
@@ -0,0 +1,136 @@
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include "arraylist.h"
+
+#define PUBLIC /* nothing */
+#define PRIVATE static
+
+// size doubles whenever it is exceeded
+#define ARRAYLIST_DEFAULT_SIZE 4
+//#define ARRAYLIST_DEBUG
+
+struct array_list_type {
+	void* data; // the arraylist data
+	int element_size;
+	int max_num_elements;
+	int num_elements;
+};
+
+PRIVATE bool al_grow(Arraylist* al) {
+	void* result = realloc(
+			al->data,
+			al->max_num_elements * al->element_size * 2
+			);
+	if(result != NULL) {
+		al->data = result;
+		al->max_num_elements *= 2;
+		return true;
+	} else {
+		return false;
+	}
+}
+
+void al_delete_last(Arraylist *al) {
+	if(al->num_elements > 0)
+		al->num_elements -= 1;
+}
+
+bool al_delete_at(Arraylist *al, int position) {
+	if(position == (al->num_elements - 1)) {
+		al_delete_last(al);
+		return true;
+	}
+	else if((position >= 0) && (position < al->num_elements)) {
+		memcpy(
+				al->data + (position * al->element_size),
+				al->data + ((position + 1) * al->element_size),
+				al->element_size * (al->num_elements - position)
+			  );
+		al->num_elements -= 1;
+		return true;
+	}
+	printf("Error: deletion out of bounds\n");
+	return false;
+}
+
+int al_len(Arraylist* al) {
+	return al->num_elements;
+}
+
+bool al_allocate_at_least(Arraylist* al, int size) {
+	if(al->max_num_elements >= size) return true;
+	void* result = realloc(
+			al->data,
+			size * al->element_size
+			);
+	if(result != NULL) {
+		al->data = result;
+		al->max_num_elements = size;
+#ifdef ARRAYLIST_DEBUG
+		printf("Grew arraylist to %i\n", al->max_num_elements);
+#endif
+		return true;
+	} else {
+		return false;
+	}
+}
+
+
+Arraylist* al_create(int type_size) {
+	Arraylist* al = malloc(sizeof(Arraylist));
+
+	al->data = malloc(sizeof(type_size) * ARRAYLIST_DEFAULT_SIZE);
+	al->element_size = type_size;
+	al->num_elements = 0;
+	al->max_num_elements = ARRAYLIST_DEFAULT_SIZE;
+
+	return al;
+}
+
+void al_free(Arraylist* al) {
+	free(al->data);
+	free(al);
+}
+
+bool al_push(Arraylist* al, void* item) {
+	if(al->num_elements >= al->max_num_elements) {
+		if(!al_grow(al)) {
+			printf("Error: Failed to grow arraylist to %i\n", al->max_num_elements);
+			return false;
+		}
+#ifdef ARRAYLIST_DEBUG
+		printf("Grew arraylist to %i\n", al->max_num_elements);
+#endif
+	}
+	memcpy(
+			al->data + (al->num_elements * al->element_size),
+			item,
+			al->element_size
+		  );
+	al->num_elements += 1;
+	return true;
+}
+
+void* al_access(Arraylist* al, int position) {
+	if((position >= al->num_elements) || (position < 0))
+		return NULL;
+	return al->data + (al->element_size * position);
+}
+
+bool al_overwrite_and_delete(Arraylist* al, int source, int target) {
+	if(source == target) return true;
+	else if((source >= al->num_elements) || (target >= al->num_elements) || (source < 0) || (target < 0)) {
+		printf("Error, out of bounds");
+		return false;
+	}
+	memcpy(
+			al->data + (target * al->element_size),
+			al->data + (source * al->element_size),
+			al->element_size
+			);
+	return al_delete_at(al, source);
+}
+
+
diff --git a/arraylist.h b/arraylist.h
new file mode 100644
index 0000000..7a1f08e
--- /dev/null
+++ b/arraylist.h
@@ -0,0 +1,20 @@
+#ifndef ARRAYLIST_H
+#define ARRAYLIST_H
+
+#include <stdbool.h>
+
+typedef struct array_list_type Arraylist;
+
+Arraylist* al_create(int type_size);
+void al_free(Arraylist* al);
+void* al_access(Arraylist* al, int position);
+bool al_push(Arraylist* al, void* item);
+void al_delete_last(Arraylist* al);
+bool al_delete_at(Arraylist *al, int position);
+bool al_allocate_at_least(Arraylist* al, int size);
+int al_len(Arraylist* al);
+
+// give 2 indexes, moves source to overwrite the target
+bool al_overwrite_and_delete(Arraylist* al, int source, int target);
+
+#endif
diff --git a/test.c b/test.c
new file mode 100644
index 0000000..6216586
--- /dev/null
+++ b/test.c
@@ -0,0 +1,128 @@
+#include <stdio.h>
+
+#include "arraylist.h"
+
+bool test_match(Arraylist* al, int answer_key[], int answer_key_size) {
+	if(al_len(al) != answer_key_size) {
+		printf("test failed\n");
+		printf("unexpected array size\n");
+		printf("Expected: %d\n", answer_key_size);
+		printf("Got:      %d\n", al_len(al));
+		
+		return false;
+	}
+	for(int i = 0; i < al_len(al); i += 1) {
+		printf("%d == %d\n", answer_key[i], *(int*)al_access(al, i));	
+		if(answer_key[i] != *(int*)al_access(al, i)){
+			printf("test failed\n");
+			printf("Expected: %d\n", answer_key[i]);
+			printf("Got:      %d\n", *(int*)al_access(al, i));
+			return false;
+		}
+	}
+	return true;
+}
+
+int main() {
+	Arraylist* test_list = al_create(sizeof(int));
+
+	int a = 0;
+
+	printf("testing 1025 integer elements\n");
+	for(int i = 0; i < 1025; i += 1) {
+		a += 3;
+		al_push(test_list, &a);
+		/*printf("pushed element %i\n", a);
+		  printf(
+		  "read element %i\n",
+		 *(int*)al_access(test_list,i)
+		 );*/
+	}
+	a = 0;
+	for(int i = 0; i < 1025; i += 1) {
+		a += 3;
+		if(a != *(int*)al_access(test_list, i)){
+			printf("failed\n");
+			return 1;
+		}
+	}
+	printf("test passed\n");
+
+	printf("testing resizing arraylist\n");
+	al_allocate_at_least(test_list, 4096);
+	printf("test passed\n");
+
+	printf("testing deallocating arraylist\n");
+	al_free(test_list);
+	printf("test passed\n");
+
+	printf("testing deletion\n");
+	test_list = al_create(sizeof(int));
+	a = 0;
+	for(int i = 0; i < 5; i += 1) {
+		a += 1;
+		al_push(test_list, &a);
+	}
+	printf("delete middle element:\n");
+	al_delete_at(test_list, 2);
+	{
+		int answer_key[] = { 1, 2, 4, 5 };
+		if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key)))
+			return false;
+	}
+	printf("passed\n");
+	printf("delete first element:\n");
+	al_delete_at(test_list, 0);
+	{
+		int answer_key[] = { 2, 4, 5 };
+		if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key)))
+			return false;
+	}
+	printf("passed\n");
+	printf("delete last element:\n");
+	al_delete_at(test_list, 2);
+	{
+		int answer_key[] = { 2, 4 };
+		if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key)))
+			return false;
+	}
+	printf("passed\n");
+	printf("try to delete out of bounds\n");
+	if(al_delete_at(test_list, 64)){
+		printf("Should of errored but did not\n");
+	}
+	printf("passed\n");
+
+	a = 3;
+	al_push(test_list, &a);
+	printf("test editing existing element\n");
+	*(int*)al_access(test_list, 1) = 7;
+	{
+		int answer_key[] = { 2, 7, 3 };
+		if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key)))
+			return false;
+	}
+
+	a = 20;
+	al_push(test_list, &a);
+	printf("test overwrite and delete\n");
+	al_overwrite_and_delete(test_list, al_len(test_list)-1, 1);
+	{
+		int answer_key[] = { 2, 20, 3 };
+		if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key)))
+			return false;
+	}
+	al_overwrite_and_delete(test_list, 1, 0);
+	{
+		int answer_key[] = { 20, 3 };
+		if(!test_match(test_list, answer_key, sizeof(answer_key)/sizeof(*answer_key)))
+			return false;
+	}
+
+
+
+	printf("test passed\n");
+
+	printf("all tests passed\n");
+	return 0;
+}