Mercurial > sos > sos

changeset 24:45a80ea314ae

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
The stack now theroretically is a properly working stack! I added the free function I converted the code for the stack so that it uses a linked list to store the stack values. TODO: create a way to destroy stacks.
author Jonathan Pevarnek <pevarnj@gmail.com>
date Wed, 16 Mar 2011 12:00:43 -0400
parents f68b59af5ea6
children 2b19746a4e97
files include/operations.h include/stack.h include/std.h src/init.c src/operations.c src/stack.c src/std.c
diffstat 7 files changed, 115 insertions(+), 81 deletions(-) [+]
line wrap: on
line diff
--- a/include/operations.h	Wed Mar 16 00:47:21 2011 -0400
+++ b/include/operations.h	Wed Mar 16 12:00:43 2011 -0400
@@ -6,20 +6,20 @@
 
 enum Operation {PRINT, ADD, SUB, MULT, DIV, POW, DUP, DROP, LOG, EXP, MAXOP};
 extern const char operationNames[MAXOP][10];
-extern void (*operation[MAXOP])(struct Stack*);
+extern void (*operation[MAXOP])(Stack*);
 
-void op_math1(struct Stack *stack, eltType (*mathop)(eltType));
-void op_math2(struct Stack *stack, eltType (*mathop)(eltType, eltType));
+void op_math1(Stack *stack, eltType (*mathop)(eltType));
+void op_math2(Stack *stack, eltType (*mathop)(eltType, eltType));
 
-void op_print(struct Stack *stack);
-void op_add(struct Stack *stack);
-void op_sub(struct Stack *stack);
-void op_mult(struct Stack *stack);
-void op_div(struct Stack *stack);
-void op_pow(struct Stack *stack);
-void op_dup(struct Stack *stack);
-void op_drop(struct Stack *stack);
-void op_log(struct Stack *stack);
-void op_exp(struct Stack *stack);
+void op_print(Stack *stack);
+void op_add(Stack *stack);
+void op_sub(Stack *stack);
+void op_mult(Stack *stack);
+void op_div(Stack *stack);
+void op_pow(Stack *stack);
+void op_dup(Stack *stack);
+void op_drop(Stack *stack);
+void op_log(Stack *stack);
+void op_exp(Stack *stack);
 
 #endif //__OPERATIONS_H
--- a/include/stack.h	Wed Mar 16 00:47:21 2011 -0400
+++ b/include/stack.h	Wed Mar 16 12:00:43 2011 -0400
@@ -2,20 +2,27 @@
 #define __STACK_H
 
 typedef double eltType;
-typedef struct eltTypeCon eltCon;
+
+struct STACKELT {
+	eltType elt;
+	struct STACKELT *next;
+};
+typedef struct STACKELT StackElt;
 
-struct Stack {
-	int top;
-	eltType values[100];
+struct STACK {
+	StackElt* top;
 };
+typedef struct STACK Stack;
 
-struct eltTypeCon { //contains an eltType and an error value
+struct ELTCON { //contains an eltType and an error value
 	eltType val;
 	short error;
 };
+typedef struct ELTCON eltCon;
 
-eltCon pop(struct Stack *stack);
-void push(struct Stack *stack, eltType val);
-void initStack(struct Stack *stack);
+eltCon pop(Stack *stack);
+void push(Stack *stack, eltType val);
+Stack* stack_init();
+//void stack_destroy(Stack *stack); //TODO
 
 #endif //__STACK_H
--- a/include/std.h	Wed Mar 16 00:47:21 2011 -0400
+++ b/include/std.h	Wed Mar 16 12:00:43 2011 -0400
@@ -19,14 +19,16 @@
 
 //MALLOC CODE
 
-struct block{
-	struct block *next;
-	unsigned int size;
+struct header{
+	struct header *next;
+	size_t size;
 };
-typedef struct block Block;
+typedef struct header Header;
+
+typedef Header blockUnit;
 
 void malloc_init(size_t memSize);
 void* malloc(size_t size);
-//void free(void *ptr);
+void free(void *ptr);
 
 #endif
--- a/src/init.c	Wed Mar 16 00:47:21 2011 -0400
+++ b/src/init.c	Wed Mar 16 12:00:43 2011 -0400
@@ -21,10 +21,11 @@
 
 void start(u64 __memsize)
 {
+	malloc_init(__memsize - HEAP_START);
+	/*
   int i, n;
   char *buffer;
 	char input[30];
-	malloc_init(__memsize - HEAP_START); //20MB memory
 
 	while(1) {
 		sPrint("How long do you want the string? ");
@@ -36,19 +37,19 @@
 			break;
 		}
 
-		for (i = 0; i < n; i++)
-			buffer[i]='a'; //I need to make rand...
-		buffer[n]='\0';
+//		for (i = 0; i < n - 1; i++)
+//			buffer[i]='a'; //I need to make rand...
+//		buffer[n - 1]='\0';
 
+//		sPrint(buffer), sPrint("\n");
 //		dumpBuffer(buffer, n);
 
 		sPrint(append(itoa((unsigned long)buffer, input), "\n"));
-		sPrint(buffer), sPrint("\n");
+		free(buffer);
 	}
-/*
-	struct Stack theStack;
-	struct Stack *stack = &theStack;
-	initStack(stack);
+*/
+
+	Stack *stack = stack_init();
 	while(1) {
 		int opVal;
 		char input[30];
@@ -60,7 +61,8 @@
 			push(stack, atof(input));
 		}
 	}
-*/
+
 	for(;;)
 		;
+//	stack_destroy(stack);
 }
--- a/src/operations.c	Wed Mar 16 00:47:21 2011 -0400
+++ b/src/operations.c	Wed Mar 16 12:00:43 2011 -0400
@@ -4,34 +4,28 @@
 #include <math.h>
 
 const char operationNames[MAXOP][10] = {".", "+", "-", "*", "/", "**", "dup", "drop", "log", "exp"};
-void (*operation[MAXOP])(struct Stack*) = {op_print, op_add, op_sub, op_mult,
+void (*operation[MAXOP])(Stack*) = {op_print, op_add, op_sub, op_mult,
 	op_div, op_pow, op_dup, op_drop, op_log, op_exp};
 
-void op_math1(struct Stack *stack, eltType (*mathop)(eltType))
+void op_math1(Stack *stack, eltType (*mathop)(eltType))
 {
-	if(stack->top < 0) sPrint("ERROR\n");
-	else {
-		eltCon con = pop(stack);
-		if(con.error) sPrint("ERROR\n");
-		else push(stack, mathop(con.val));
-	}
+	eltCon con = pop(stack);
+	if(con.error) sPrint("ERROR, no values on stack\n");
+	else push(stack, mathop(con.val));
 }
 
-void op_math2(struct Stack *stack, eltType (*mathop)(eltType, eltType))
+void op_math2(Stack *stack, eltType (*mathop)(eltType, eltType))
 {
-	if(stack->top < 1) sPrint("ERROR\n");
-	else {
-		eltCon con2 = pop(stack);
-		eltCon con1 = pop(stack);
-		if(con1.error || con2.error) sPrint("ERROR\n");
-		else push(stack, mathop(con1.val, con2.val));
-	}
+	eltCon con2 = pop(stack);
+	eltCon con1 = pop(stack);
+	if(con1.error || con2.error) sPrint("ERROR, stack not large enough\n");
+	else push(stack, mathop(con1.val, con2.val));
 }
 
-void op_print(struct Stack *stack)
+void op_print(Stack *stack)
 {
 	eltCon con = pop(stack);
-	if(con.error) sPrint("ERROR\n");
+	if(con.error) sPrint("ERROR, no values on stack\n");
 	else {
 		eltType val = con.val;
 		char output[30];
@@ -39,35 +33,35 @@
 	}
 }
 
-void op_add(struct Stack *stack)
+void op_add(Stack *stack)
 {
 	op_math2(stack, math_add);
 }
 
-void op_sub(struct Stack *stack)
+void op_sub(Stack *stack)
 {
 	op_math2(stack, math_sub);
 }
 
-void op_mult(struct Stack *stack)
+void op_mult(Stack *stack)
 {
 	op_math2(stack, math_mult);
 }
 
-void op_div(struct Stack *stack)
+void op_div(Stack *stack)
 {
 	op_math2(stack, math_div);
 }
 
-void op_pow(struct Stack *stack)
+void op_pow(Stack *stack)
 {
 	op_math2(stack, math_pow);
 }
 
-void op_dup(struct Stack *stack)
+void op_dup(Stack *stack)
 {
 	eltCon con = pop(stack);
-	if(con.error) sPrint("ERROR\n");
+	if(con.error) sPrint("ERROR, no values on stack\n");
 	else {
 		eltType val = con.val;
 		push(stack, val);
@@ -75,17 +69,17 @@
 	}
 }
 
-void op_drop(struct Stack *stack)
+void op_drop(Stack *stack)
 {
 	pop(stack);
 }
 
-void op_log(struct Stack *stack)
+void op_log(Stack *stack)
 {
 	op_math1(stack, math_log);
 }
 
-void op_exp(struct Stack *stack)
+void op_exp(Stack *stack)
 {
 	op_math1(stack, math_exp);
 }
--- a/src/stack.c	Wed Mar 16 00:47:21 2011 -0400
+++ b/src/stack.c	Wed Mar 16 12:00:43 2011 -0400
@@ -1,24 +1,32 @@
 #include <stack.h>
 #include <std.h>
 
-eltCon pop(struct Stack *stack)
+eltCon pop(Stack *stack)
 {
 	eltCon ret;
-	if(stack->top == -1) {
+	if(stack->top == NULL) {
 		ret.error = 1;
 	} else {
 		ret.error = 0;
-		ret.val = stack->values[stack->top--];
+		StackElt *top = stack->top;
+		ret.val = top->elt;
+		stack->top = top->next;
+		free(top);
 	}
 	return ret;
 }
 
-void push(struct Stack *stack, eltType val)
+void push(Stack *stack, eltType val)
 {
-	if(stack->top < (100 - 1)) stack->values[++stack->top] = val;
+	StackElt *new = malloc(sizeof(StackElt));
+	new->elt = val;
+	new->next = stack->top;
+	stack->top = new;
 }
 
-void initStack(struct Stack *stack)
+Stack* stack_init()
 {
-	stack->top = -1;
+	Stack *new = malloc(sizeof(Stack));
+	new->top = NULL;
+	return new;
 }
--- a/src/std.c	Wed Mar 16 00:47:21 2011 -0400
+++ b/src/std.c	Wed Mar 16 12:00:43 2011 -0400
@@ -126,27 +126,35 @@
 	return ret;
 }
 
-static Block *allocp = NULL; //the location of the last item allocated by malloc
+static Header base;
+static Header *allocp = NULL; //the location of the last known free block
 
 void malloc_init(size_t memSize)
 {
-	allocp = (void*)HEAP_START;
-	allocp->next = allocp;
-	allocp->size = memSize/sizeof(u64);
+	allocp = &base;
+	allocp->size = 0;
+	allocp->next = (void*)HEAP_START;
+	allocp->next->next = &base;
+	allocp->next->size = memSize/sizeof(blockUnit);
+	if((sizeof(blockUnit)%sizeof(u64))) {
+		sPrint("WARNING: MEMORY NOT 8-BYTE ALIGNED\n");
+		char foo[40];
+		sPrint(append("MEMORY BLOCK SIZE IS: ", append(itoa(sizeof(Header), foo), "\n")));
+	}
 }
 
 void* malloc(size_t size)
 {
-	unsigned int nUnits = ((size + sizeof(Block)) + sizeof(u64) - 1)/sizeof(u64);
-	Block *cur, *prev, *temp;
 	if(allocp == NULL) return NULL;
-	prev = allocp;
+	size_t nUnits = ((size + sizeof(Header)) + sizeof(blockUnit) - 1)/sizeof(blockUnit);
+	Header *prev = allocp;
+	Header *cur, *temp;
 	for(cur = prev->next;; prev = cur, cur = cur->next) {
 		if(cur->size >= nUnits) {
 			if(cur->size == nUnits) {
 				prev->next = cur->next;
 			} else {
-				temp = cur + nUnits;
+				temp = cur + nUnits; //This requires sizeof(blockUnit) == sizeof(Header).  TODO fix
 				temp->size = cur->size - nUnits;
 				temp->next = cur->next;
 				prev->next = temp;
@@ -160,8 +168,21 @@
 	}
 }
 
-/*
 void free(void *ptr)
 {
+	Header *toFree = (Header *)ptr - 1;
+	Header *scan;
+	for(scan = allocp; !(toFree > scan && toFree < scan->next); scan = scan->next)
+		if(scan->next < scan && (toFree > scan || toFree < scan->next)) break;
+	toFree->next = scan->next;
+	scan->next = toFree;
+	if(scan + toFree->size == toFree) {
+		scan->size += toFree->size;
+		scan->next = toFree->next;
+		toFree = scan;
+	}
+	if(toFree + toFree->size == toFree->next) {
+		toFree->size += toFree->next->size;
+		toFree->next = toFree->next->next;
+	}
 }
-*/