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

index 5b24a3d..7921f29 100644 (file)
@@ -6,10 +6,8 @@
 
 void _queue_init(Queue* queue, size_t dataSize)
 {
 
 void _queue_init(Queue* queue, size_t dataSize)
 {
-       queue->size = 0;
        queue->dataSize = dataSize;
        queue->dataSize = dataSize;
-       queue->front = NULL;
-       queue->back = NULL;
+       _vector_init(queue->array, dataSize);
 }
 
 Queue* _queue_new(size_t dataSize)
 }
 
 Queue* _queue_new(size_t dataSize)
@@ -21,61 +19,46 @@ Queue* _queue_new(size_t dataSize)
 
 Queue* queue_copy(Queue* queue)
 {
 
 Queue* queue_copy(Queue* queue)
 {
-       Queue* queueCopy = _queue_new(queue->dataSize);
-       QueueCell* queueCell = queue->front;
-       while (queueCell != NULL)
-       {
-               _queue_push(queueCopy, queueCell->data);
-               queueCell = queueCell->next;
-       }
+       Queue* queueCopy = (Queue*) safe_malloc(sizeof (Queue));
+       queueCopy->dataSize = queue->dataSize;
+       Vector* arrayCopy = vector_copy(queue->array);
+       queueCopy->array = arrayCopy;
        return queueCopy;
 }
 
 Bool queue_empty(Queue* queue)
 {
        return queueCopy;
 }
 
 Bool queue_empty(Queue* queue)
 {
-       return (queue->size == 0);
+       return vector_empty(queue->array);
 }
 
 UInt queue_size(Queue* queue)
 {
 }
 
 UInt queue_size(Queue* queue)
 {
-       return queue->size;
+       return vector_size(queue->array);
 }
 
 void _queue_push(Queue* queue, void* data)
 {
 }
 
 void _queue_push(Queue* queue, void* data)
 {
-       QueueCell* newQueueBack = (QueueCell*) safe_malloc(sizeof (QueueCell));
-       newQueueBack->data = safe_malloc(queue->dataSize);
-       memcpy(newQueueBack->data, data, queue->dataSize);
-       newQueueBack->next = NULL;
-       if (queue->size > 0) 
-               queue->back->next = newQueueBack;
-       queue->back = newQueueBack;
-       if (queue->size == 0) 
-               queue->front = newQueueBack;
-       queue->size++;
+       _vector_push(queue->array, data);
 }
 
 void* _queue_peek(Queue* queue)
 {
 }
 
 void* _queue_peek(Queue* queue)
 {
-       return queue->front->data;
+       return vector_get(queue->array, 0);
 }
 
 void queue_pop(Queue* queue)
 {
 }
 
 void queue_pop(Queue* queue)
 {
-       QueueCell* toTrash = queue->front;
-       queue->front = queue->front->next;
-       if (queue->front == NULL) 
-               queue->back = NULL;
-       safe_free(toTrash->data);
-       safe_free(toTrash);
-       queue->size--;
+       //remove first vector element and shift its internal array
+       safe_free(queue->array->datas[0]);
+       queue->array->datas++;
+       //NOTE: we remove first element, so capacity decrease too
+       queue->array->size--;
+       queue->array->capacity--;
 }
 
 void queue_clear(Queue* queue)
 {
 }
 
 void queue_clear(Queue* queue)
 {
-       while (queue->size > 0) 
-               queue_pop(queue);
-       _queue_init(queue, queue->dataSize);
+       vector_clear(queue->array);
 }
 
 void queue_destroy(Queue* queue)
 }
 
 void queue_destroy(Queue* queue)
index db71579..619ae4a 100644 (file)
@@ -9,24 +9,15 @@
 #include <string.h>
 #include "cgds/types.h"
 #include "cgds/safe_alloc.h"
 #include <string.h>
 #include "cgds/types.h"
 #include "cgds/safe_alloc.h"
-
-/**
- * @brief Generic internal queue cell.
- */
-typedef struct QueueCell {
-       void* data; ///< Generic data contained in the cell.
-       struct QueueCell* next; ///< Next cell in the internal single-linked list.
-} QueueCell;
+#include "cgds/Vector.h"
 
 /**
  * @brief Queue containing generic data.
  * @param dataSize Size in bytes of a queue element.
  */
 typedef struct Queue {
 
 /**
  * @brief Queue containing generic data.
  * @param dataSize Size in bytes of a queue element.
  */
 typedef struct Queue {
-       UInt size; ///< Count elements in the queue.
        size_t dataSize; ///< Size in bytes of a queue element.
        size_t dataSize; ///< Size in bytes of a queue element.
-       QueueCell* front; ///< Pointer to the next dequeued element.
-       QueueCell* back; ///< Pointer to the last enqueued element.
+       Vector* array; ///< Internal vector representation
 } Queue;
 
 /**
 } Queue;
 
 /**
index 6141dd0..0b368f1 100644 (file)
@@ -115,7 +115,7 @@ void t_queue_copy() //FTEST
                queue_push(q, rand() % 42);
        Queue* qc = queue_copy(q);
 
                queue_push(q, rand() % 42);
        Queue* qc = queue_copy(q);
 
-       lu_assert_int_eq(q->size, qc->size);
+       lu_assert_int_eq(queue_size(q), queue_size(qc));
        int a, b;
        for (int i = 0; i < n; i++)
        {
        int a, b;
        for (int i = 0; i < n; i++)
        {