aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorErik Liodden <eriklio@stud.ntnu.no>2017-11-15 13:48:48 +0100
committerErik Liodden <eriklio@stud.ntnu.no>2017-11-15 16:01:28 +0100
commit9c38aae5127a9e8679999d8981eaa5b63d328216 (patch)
treeb31e57e6c9dafc1121bed1b75e5e62ccf35c1d4c
parent4d428d5536f5905a8c2ea17797f7d7bb020a9393 (diff)
downloadalgdat-9c38aae5127a9e8679999d8981eaa5b63d328216.tar.gz
add queue data structure
struct queue is a generic queue capable of holding an arbitrary number of elements of size elem_size. (all elements in the queue must be of the same size, but it could be pointers, so it is quite flexible). queue_init initializes a queue (preferably created by the caller on the stack). The queue is initially able to hold op to 4 elements in the queue at the same time. The elements in the queue are stored on the heap, and queue_dispose takes care of the free() calls if there is elements left on the queue. For this to work, the queue must be inititalized with a free-function accepting a void * as argument. The caller must provide this function. (note that is can, and probably should, be decleared as a statuc function at the caller). queue_enqueue takes in an adress of the variable to be put in the queue. If the queue is full, queue_enqueue will double the memory allocated to the queue. This is an expensice task, so by doubleing it, it will not happen that often. queue_dequeue expects an adress to a block of memory capable of storing the size of one element in the queue. This memory location should be provided by the caller. (initialize a variable on the stack and pass the adress of it to queue_dequeue). queue_length return the number of elements in the queue. This can also be accessed directly by the log_length field in the queue struct.
-rw-r--r--include/list.h23
-rw-r--r--src/misc/list.c61
2 files changed, 84 insertions, 0 deletions
diff --git a/include/list.h b/include/list.h
index 3fa535c..73ed377 100644
--- a/include/list.h
+++ b/include/list.h
@@ -27,6 +27,29 @@ void stack_pop(struct stack *s, void *elem_addr);
void stack_peek(struct stack *s, void *elem_addr);
int stack_length(struct stack *s);
+/****************************************************************************
+ * Queue *
+ ****************************************************************************/
+
+struct queue {
+ void *elems;
+ size_t elem_size;
+ int head;
+ int tail;
+ int log_length;
+ int alloc_length;
+ void (*freefn)(void *);
+};
+
+void queue_init(struct queue *q, size_t elem_size, void (*freefn)(void *));
+void queue_dispose(struct queue *q);
+void queue_enqueue(struct queue *q, void *elem_addr);
+void queue_dequeue(struct queue *q, void *elem_addr);
+int queue_length(struct queue *q);
+
+
+
+
/* linked lists */
struct llist {
struct llist_node *head;
diff --git a/src/misc/list.c b/src/misc/list.c
index d16f939..fc7ae7f 100644
--- a/src/misc/list.c
+++ b/src/misc/list.c
@@ -71,7 +71,68 @@ int stack_length(struct stack *s)
}
+/****************************************************************************
+ * Queue *
+ ****************************************************************************/
+
+static void grow_queue(struct queue *q)
+{
+ void *middle = (char *)q->elems + q->head * q->elem_size;
+ void *end = (char *)q->elems + q->log_length * q->elem_size;
+ q->head = 0;
+ q->tail = q->log_length;
+ q->alloc_length *= 2;
+ if (q->head != 0)
+ rotate(q->elems, middle, end);
+ q->elems = realloc(q->elems, q->alloc_length * q->elem_size);
+ assert(q->elems != NULL);
+}
+void queue_init(struct queue *q, size_t elem_size, void (*freefn)(void *))
+{
+ q->elem_size = elem_size;
+ q->head = 0;
+ q->tail = 0;
+ q->log_length = 0;
+ q->alloc_length = 4;
+ q->elems = allocate(q->alloc_length * elem_size);
+ q->freefn = freefn;
+}
+
+void queue_dispose(struct queue *q)
+{
+ int i;
+ if (q->freefn) {
+ for (i = 0; i < q->log_length; i++)
+ q->freefn((char *)q->elems + (((q->head + i) %
+ q->alloc_length) * q->elem_size));
+ }
+ free(q->elems);
+}
+
+void queue_enqueue(struct queue *q, void *elem_addr)
+{
+ if (q->log_length == q->alloc_length)
+ grow_queue(q);
+ void *target = (char *)q->elems + (q->tail * q->elem_size);
+ memcpy(target, elem_addr, q->elem_size);
+ q->tail = (q->tail + 1) % q->alloc_length;
+ q->log_length++;
+}
+
+void queue_dequeue(struct queue *q, void *elem_addr)
+{
+ assert(q->log_length != 0);
+ void *source = (char *)q->elems + (q->head * q->elem_size);
+ memcpy(elem_addr, source, q->elem_size);
+ q->head = (q->head + 1) % q->alloc_length;
+ q->log_length--;
+}
+
+int queue_length(struct queue *q)
+{
+ return q->log_length;
+}
static struct llist_node *create_node(void *data)
{