Replace Stack List internal usage by a Vector (lighter)
authorBenjamin Auder <benjamin.a@mailoo.org>
Sat, 31 Jan 2015 19:01:05 +0000 (20:01 +0100)
committerBenjamin Auder <benjamin.a@mailoo.org>
Sat, 31 Jan 2015 19:01:05 +0000 (20:01 +0100)
src/Stack.c
src/Stack.h
test/t.Stack.c

index c37b775..545e83d 100644 (file)
@@ -6,9 +6,8 @@
 
 void _stack_init(Stack* stack, size_t dataSize)
 {
-       stack->size = 0;
        stack->dataSize = dataSize;
-       stack->top = NULL;
+       _vector_init(stack->array, dataSize);
 }
 
 Stack* _stack_new(size_t dataSize)
@@ -20,61 +19,41 @@ Stack* _stack_new(size_t dataSize)
 
 Stack* stack_copy(Stack* stack)
 {
-       // since a stack is a single-linked list, an auxiliary storage is required
-       void** tmpStorage = (void**) malloc(stack->size * sizeof (void*));
-       StackCell* stackCell = stack->top;
-       for (UInt i = 0; i < stack->size; i++)
-       {
-               tmpStorage[stack->size - 1 - i] = stackCell->data;
-               stackCell = stackCell->previous;
-       }
-       // now transfer tmpStorage contents (pushed in right order) in a new stack
-       Stack* stackCopy = _stack_new(stack->dataSize);
-       for (UInt i = 0; i < stack->size; i++)
-               _stack_push(stackCopy, tmpStorage[i]);
-       free(tmpStorage);
+       Stack* stackCopy = (Stack*) safe_malloc(sizeof (Stack));
+       stackCopy->dataSize = stack->dataSize;
+       Vector* arrayCopy = vector_copy(stack->array);
+       stackCopy->array = arrayCopy;
        return stackCopy;
 }
 
 Bool stack_empty(Stack* stack)
 {
-       return (stack->size == 0);
+       return vector_empty(stack->array);
 }
 
 UInt stack_size(Stack* stack)
 {
-       return stack->size;
+       return vector_size(stack->array);
 }
 
 void _stack_push(Stack* stack, void* data)
 {
-       StackCell* newStackTop = (StackCell*) safe_malloc(sizeof (StackCell));
-       newStackTop->data = safe_malloc(stack->dataSize);
-       memcpy(newStackTop->data, data, stack->dataSize);
-       newStackTop->previous = stack->top;
-       stack->top = newStackTop;
-       stack->size++;
+       _vector_push(stack->array, data);
 }
 
 void* _stack_top(Stack* stack)
 {
-       return stack->top->data;
+       return _vector_get(stack->array, vector_size(stack->array)-1);
 }
 
 void stack_pop(Stack* stack)
 {
-       StackCell* toTrash = stack->top;
-       stack->top = stack->top->previous;
-       safe_free(toTrash->data);
-       safe_free(toTrash);
-       stack->size--;
+       vector_pop(stack->array);
 }
 
 void stack_clear(Stack* stack)
 {
-       while (stack->size > 0) 
-               stack_pop(stack);
-       _stack_init(stack, stack->dataSize);
+       vector_clear(stack->array);
 }
 
 void stack_destroy(Stack* stack)
index d246107..c314c28 100644 (file)
@@ -9,22 +9,14 @@
 #include <string.h>
 #include "cgds/types.h"
 #include "cgds/safe_alloc.h"
-
-/**
- * @brief Generic internal stack cell.
- */
-typedef struct StackCell {
-       void* data; ///< Generic data contained in the cell.
-       struct StackCell* previous; ///< Previous cell in the internal single-linked list.
-} StackCell;
+#include "cgds/Vector.h"
 
 /**
  * @brief Stack containing generic data.
  */
 typedef struct Stack {
-       UInt size; ///< Count elements in the stack.
        size_t dataSize; ///< Size in bytes of a stack element.
-       StackCell* top; ///< Last added element, on top of the stack.
+       Vector* array; ///< Internal data structure: resizeable array.
 } Stack;
 
 /**
index 364c344..db5a0d5 100644 (file)
@@ -116,7 +116,7 @@ void t_stack_copy() //FTEST
                stack_push(s, rand() % 42);
        Stack* sc = stack_copy(s);
 
-       lu_assert_int_eq(s->size, sc->size);
+       lu_assert_int_eq(stack_size(s), stack_size(sc));
        int a, b;
        for (int i = 0; i < n; i++)
        {