commit 8524813dc34e1b596f903ecd0dd64411b1447aab
parent 99774ad7b054418a996772088e686c34065b4768
Author: Christian Ermann <christianermann@gmail.com>
Date: Sat, 30 Jul 2022 14:05:27 -0700
Added support for iterating through a queue
Diffstat:
4 files changed, 250 insertions(+), 31 deletions(-)
diff --git a/include/memory.h b/include/memory.h
@@ -7,6 +7,7 @@ typedef enum memory_tag {
MEMORY_TAG_RENDER,
MEMORY_TAG_STRING,
MEMORY_TAG_JOB,
+ MEMORY_TAG_QUEUE,
MEMORY_TAG_MAX_TAGS
} memory_tag;
diff --git a/include/queue.h b/include/queue.h
@@ -2,20 +2,76 @@
#include "types.h"
+/*
+ * A FIFO-ish queue.
+ */
typedef struct Queue {
+
+ // The current number of elements in the queue.
u32 length;
+
+ // The size in bytes of an element.
u32 stride;
+
+ // The size in bytes of a QueueItem.
+ u32 stride_padded;
+
+ // The maximum number of elements in the queue.
u32 capacity;
- i32 head;
- i32 tail;
- void *data;
+
+ // The current element being accessed during iteration.
+ struct QueueItem *cursor;
+
+ // The front of the queue.
+ struct QueueItem *head;
+
+ // The end of the queue.
+ struct QueueItem *tail;
+
+ // Block of memory holding all QueueItems.
+ struct QueueItem *data;
+
} Queue;
+/*
+ * Initialize a queue which can hold a maximum of `capacity` elements of
+ * `stride` bytes in size.
+ */
b8 Queue_init(Queue *queue, u32 stride, u32 capacity);
-void Queue_free(Queue *queue);
+/*
+ * Internal clean-up of a queue.
+ */
+b8 Queue_free(Queue *queue);
+/*
+ * Add an element to the end of the queue.
+ */
b8 Queue_enqueue(Queue *queue, void *value);
+
+/*
+ * Remove an element from the front of the queue.
+ */
b8 Queue_dequeue(Queue *queue, void *value);
+
+/*
+ * Retrieve the element at the front of the queue without removing it.
+ */
b8 Queue_peek(const Queue *queue, void *value);
+/*
+ * Iterate through the elements of a queue. Starts at the first element in the
+ * queue. Returns false when the end of the queue is reached.
+ */
+b8 Queue_peekNext(Queue *queue, void *value);
+
+/*
+ * Called when iteration of a queue is stopped before reaching the end.
+ */
+b8 Queue_peekDone(Queue *queue);
+
+/*
+ * Removes the current element of a queue during iteration.
+ */
+b8 Queue_yank(Queue *queue, void *value);
+
diff --git a/include/types.h b/include/types.h
@@ -24,3 +24,5 @@ typedef int8_t b8;
#define true 1
#define false 0
+#define NULL 0
+
diff --git a/src/queue.c b/src/queue.c
@@ -1,33 +1,50 @@
#include "queue.h"
-#include "memory.h"
#include "logger.h"
+#include "memory.h"
+
+typedef struct QueueItem {
+ struct QueueItem *next;
+ struct QueueItem *prev;
+ void *data;
+} QueueItem;
b8 Queue_init(Queue *queue, u32 stride, u32 capacity)
{
if (!queue)
{
- LOGE("Queue_init: Unitialized queue pointer.");
+ LOGE("Queue_init: Invalid queue pointer");
return false;
}
- queue->length = 0;
- queue->stride = stride;
+ queue->length = 0;
+ queue->stride = stride;
+ queue->stride_padded = 2 * sizeof(QueueItem *) + stride;
queue->capacity = capacity;
- queue->head = 0;
- queue->tail = -1;
-
- queue->data = s_alloc(capacity * stride, MEMORY_TAG_QUEUE);
+ queue->cursor = NULL;
+ queue->head = NULL;
+ queue->tail = NULL;
+ queue->data = s_alloc(queue->stride_padded * capacity, MEMORY_TAG_QUEUE);
return true;
}
-void Queue_free(Queue *queue)
+b8 Queue_free(Queue *queue)
{
if (queue)
{
- s_free(queue->data, queue->capacity * queue->stride, MEMORY_TAG_QUEUE);
+ s_free(
+ queue->data,
+ queue->stride_padded * queue->capacity,
+ MEMORY_TAG_QUEUE
+ );
}
+ return true;
+}
+
+b8 Queue_empty(const Queue *queue)
+{
+ return queue->length == 0;
}
b8 Queue_enqueue(Queue *queue, void *value)
@@ -43,18 +60,43 @@ b8 Queue_enqueue(Queue *queue, void *value)
return false;
}
+ // Check queue is not full
if (queue->length == queue->capacity)
{
LOGE("Queue_enqueue: Can't enqueue value in full queue");
return false;
}
- queue->tail = (queue->tail + 1) % queue->capacity;
+ // Find empty slot in queue memory
+ QueueItem *empty = NULL;
+ for (u32 i = 0; i < queue->capacity; i++)
+ {
+ if (queue->data + i * queue->stride_padded) continue;
+
+ empty = queue->data + i * queue->stride_padded;
+ }
+
+ // Fill empty slot
+ empty->next = NULL;
+ empty->prev = queue->tail;
s_copyMemory(
- (char *)queue->data + (queue->tail * queue->stride),
+ empty->data,
value,
queue->stride
);
+
+ // Add to end of queue
+ if (queue->length == 0)
+ {
+ queue->head = empty;
+ queue->tail = empty;
+ }
+ else
+ {
+ queue->tail->next = empty;
+ queue->tail = empty;
+ }
+
queue->length += 1;
return true;
@@ -73,20 +115,34 @@ b8 Queue_dequeue(Queue *queue, void *value)
return false;
}
+ // Check queue is not empty
if (queue->length == 0)
{
LOGE("Queue_dequeue: Can't dequeue value from empty queue");
return false;
}
- s_copyMemory(
- value,
- (char *)queue->data + (queue->head * queue->stride),
- queue->stride
- );
- queue->head = (queue->head + 1) % queue->capacity;
+ // Set value
+ s_copyMemory(value, queue->head->data, queue->stride);
+
+ // Save reference for later
+ QueueItem *removed = queue->head;
+
+ // Remove from front of queue
+ if (queue->length == 1)
+ {
+ queue->head = NULL;
+ queue->tail = NULL;
+ }
+ else
+ {
+ queue->head = queue->head->next;
+ }
queue->length -= 1;
+ // Free memory used by item
+ s_zeroMemory(removed, queue->stride_padded);
+
return true;
}
@@ -95,26 +151,130 @@ b8 Queue_peek(const Queue *queue, void *value)
if (!queue)
{
LOGE("Queue_peek: Invalid queue pointer");
- return 0;
+ return false;
}
if (!value)
{
LOGE("Queue_peek: Invalid value pointer");
- return 0;
+ return false;
}
+ // Check queue is not empty
if (queue->length == 0)
{
LOGE("Queue_peek: Can't peek value from empty queue");
- return 0;
+ return false;
}
- s_copyMemory(
- value,
- (char *)queue->data + (queue->head * queue->stride),
- queue->stride
- );
+ // Set value
+ s_copyMemory(value, queue->head->data, queue->stride);
+
+ return true;
+}
- return 1;
+b8 Queue_peekNext(Queue *queue, void *value)
+{
+ if (!queue)
+ {
+ LOGE("Queue_peekNext: Invalid queue pointer");
+ return false;
+ }
+ if (!value)
+ {
+ LOGE("Queue_peekNext: Invalid value pointer");
+ return false;
+ }
+
+ if (queue->length == 0)
+ {
+ LOGE("Queue_peekNext: Can't peek value from empty queue");
+ return false;
+ }
+
+ // At beginning of queue
+ if (!queue->cursor)
+ {
+ queue->cursor = queue->head;
+ s_copyMemory(value, queue->cursor->data, queue->stride);
+ return true;
+ }
+
+ // In middle of queue
+ if (queue->cursor->next)
+ {
+ queue->cursor = queue->cursor->next;
+ s_copyMemory(value, queue->cursor->data, queue->stride);
+ return true;
+ }
+
+ // At end of queue
+ queue->cursor = NULL;
+ return false;
+}
+
+b8 Queue_peekDone(Queue *queue)
+{
+ if (!queue)
+ {
+ LOGE("Queue_peekDone: Invalid queue pointer");
+ return false;
+ }
+
+ queue->cursor = NULL;
+
+ return true;
+}
+
+b8 Queue_yank(Queue *queue, void *value)
+{
+ if (!queue)
+ {
+ LOGE("Queue_yank: Invalid queue pointer");
+ return false;
+ }
+ if (!value)
+ {
+ LOGE("Queue_yank: Invalid value pointer");
+ return false;
+ }
+
+ // Check we're iterating through the queue
+ if (!queue->cursor)
+ {
+ LOGE("Queue_yank: Queue cursor is not set");
+ return false;
+ }
+
+ // Set value
+ s_copyMemory(value, queue->cursor->data, queue->stride);
+
+ // Remove item from queue
+ if (queue->cursor->prev)
+ {
+ queue->cursor->prev->next = queue->cursor->next;
+ }
+ else
+ {
+ queue->head = queue->cursor->next;
+ }
+
+ if (queue->cursor->next)
+
+ {
+ queue->cursor->next->prev = queue->cursor->prev;
+ }
+ else
+ {
+ queue->tail = queue->cursor->prev;
+ }
+ queue->length -= 1;
+
+ // Free memory used by item
+ s_zeroMemory(queue->cursor, queue->stride_padded);
+
+ // Move cursor forward
+ queue->cursor = queue->cursor->next;
+
+ return true;
}
