summaryrefslogtreecommitdiffhomepage
path: root/ir/adt
diff options
context:
space:
mode:
authorMatthias Braun <matze@braunis.de>2016-06-27 03:54:04 +0200
committerMatthias Braun <matze@braunis.de>2016-06-27 09:17:15 +0200
commit7af7151a202833b5be1a2468e3864b9f09bff1cf (patch)
treea843ce1e49a97e18c5ebf658bf7f3ea09cb024d1 /ir/adt
parent6ae5546c0cfbd5b0ce0a371d9b16def3a46df88c (diff)
New double ended queue implementation
- The basic functions are written in a way to allow arbitrary sized objects in the queue. - Toplevel control structures are kept separate from the queue. This simplifies the implementation, frees 2 pointers for each data block and allows to free the initial block as soon as it is not needed anymore. - Implementation is no longer publicly exposed. We should get out of the business of exporting abstract data types. We had no outside users of pdeq as far as I can see. - Implement double ended queues with pointers with convenience functions. - deq_foreach_pointer() construct to iterate over all pointers in a deq_t. This was missing from pdeq and led some people to use the inefficient plist.
Diffstat (limited to 'ir/adt')
-rw-r--r--ir/adt/deq.c113
-rw-r--r--ir/adt/deq.h154
-rw-r--r--ir/adt/pdeq_new.h94
3 files changed, 361 insertions, 0 deletions
diff --git a/ir/adt/deq.c b/ir/adt/deq.c
new file mode 100644
index 0000000..a11fad1
--- /dev/null
+++ b/ir/adt/deq.c
@@ -0,0 +1,113 @@
+/*
+ * This file is part of libFirm.
+ * Copyright (C) 2016 Matthias Braun
+ */
+#include "deq.h"
+
+#include "xmalloc.h"
+#include <stdlib.h>
+#include <string.h>
+
+void deq_init(deq_t *deq)
+{
+ deq_block_t *block = XMALLOCF(deq_block_t, data, DEQ_BLOCK_DATA_SIZE);
+ memset(block, 0, sizeof(deq_block_t));
+ deq->left_end = block;
+ deq->right_end = block;
+}
+
+void deq_free(deq_t *deq)
+{
+ for (deq_block_t *block = deq->left_end, *next; block != NULL;
+ block = next) {
+ next = block->next_right;
+ free(block);
+ }
+#ifndef NDEBUG
+ deq->left_end = NULL;
+ deq->right_end = NULL;
+#endif
+}
+
+deq_block_t *deq_append_block_left_priv(deq_t *deq)
+{
+ deq_block_t *const left_end = deq->left_end;
+ /* Special case if left and right end are in the same block and
+ * the block is empty. Leaving the right pointer at 0 would be invalid. */
+ deq_block_t *newb;
+ if (left_end == deq->right_end && left_end->r == left_end->l) {
+ newb = left_end;
+ assert(newb->next_left == NULL);
+ assert(newb->next_right == NULL);
+ } else {
+ newb = XMALLOCF(deq_block_t, data, DEQ_BLOCK_DATA_SIZE);
+ newb->next_left = NULL;
+ newb->next_right = left_end;
+
+ left_end->next_left = newb;
+ deq->left_end = newb;
+ }
+ newb->l = DEQ_BLOCK_DATA_SIZE;
+ newb->r = DEQ_BLOCK_DATA_SIZE;
+ return newb;
+}
+
+deq_block_t *deq_append_block_right_priv(deq_t *deq)
+{
+ deq_block_t *const right_end = deq->right_end;
+ /* Special case if left and right end are in the same block and
+ * the block is empty. Leaving the right pointer at 0 would be invalid. */
+ deq_block_t *newb;
+ if (right_end == deq->left_end && right_end->r == right_end->l) {
+ newb = right_end;
+ assert(newb->next_left == NULL);
+ assert(newb->next_right == NULL);
+ } else {
+ newb = XMALLOCF(deq_block_t, data, DEQ_BLOCK_DATA_SIZE);
+ newb->next_left = right_end;
+ newb->next_right = NULL;
+
+ right_end->next_right = newb;
+ deq->right_end = newb;
+ }
+
+ newb->l = 0;
+ newb->r = 0;
+ return newb;
+}
+
+void deq_left_end_block_empty_priv(deq_t *deq)
+{
+ deq_block_t *const block = deq->left_end;
+ deq_block_t *const next_right = block->next_right;
+ assert(block->l == block->r);
+ if (next_right != NULL) {
+ assert(block != deq->right_end);
+ assert(next_right->next_left == block);
+ deq->left_end = next_right;
+ next_right->next_left = NULL;
+ free(block);
+ } else {
+ assert(block == deq->right_end);
+ block->l = 0;
+ block->r = 0;
+ }
+}
+
+void deq_right_end_block_empty_priv(deq_t *deq)
+{
+ deq_block_t *const block = deq->right_end;
+ deq_block_t *const next_left = block->next_left;
+ assert(block->r == block->l);
+ if (next_left != NULL) {
+ assert(block != deq->left_end);
+ assert(next_left->next_right == block);
+ deq->right_end = next_left;
+ next_left->next_right = NULL;
+ free(block);
+ } else {
+ assert(block == deq->left_end);
+ block->l = 0;
+ block->r = 0;
+ }
+}
diff --git a/ir/adt/deq.h b/ir/adt/deq.h
new file mode 100644
index 0000000..e5fcae2
--- /dev/null
+++ b/ir/adt/deq.h
@@ -0,0 +1,154 @@
+/*
+ * This file is part of libFirm.
+ * Copyright (C) 2016 Matthias Braun
+ */
+
+/**
+ * @file
+ * @brief Double Ended Queue.
+ */
+#ifndef FIRM_ADT_DEQ_H
+#define FIRM_ADT_DEQ_H
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+/**
+ * @ingroup adt
+ * @defgroup deq Double Ended Queue
+ * Double ended queue data structure. They allow efficient insertion and
+ * deletion on both ends.
+ * @{
+ */
+
+#define DEQ_BLOCK_SIZE 2048
+#define DEQ_BLOCK_DATA_SIZE DEQ_BLOCK_SIZE - sizeof(deq_block_t)
+
+typedef struct deq_block_t deq_block_t;
+struct deq_block_t {
+ unsigned l;
+ unsigned r;
+ deq_block_t *next_left;
+ deq_block_t *next_right;
+ char data[];
+};
+
+typedef struct deq_t {
+ deq_block_t *left_end;
+ deq_block_t *right_end;
+} deq_t;
+
+/** @cond PRIVATE */
+deq_block_t *deq_append_block_left_priv(deq_t *deq);
+deq_block_t *deq_append_block_right_priv(deq_t *deq);
+void deq_left_end_block_empty_priv(deq_t *deq);
+void deq_right_end_block_empty_priv(deq_t *deq);
+/** @endcond */
+
+/** Initialize double ended queue \p deq and allocate a first data block. */
+void deq_init(deq_t *deq);
+
+/**
+ * Free all data blocks allocated for double ended queue \p deq.
+ * Further use of the datastructure is undefined until deq_init() is called.
+ */
+void deq_free(deq_t *deq);
+
+/** Returns true if the double ended queue \p deq is empty, false otherwise. */
+static inline bool deq_empty(deq_t const *const deq)
+{
+ deq_block_t const *const left_end = deq->left_end;
+ return left_end == deq->right_end && left_end->l == left_end->r;
+}
+
+/** Return pointer to the object at the elft end of the double ended queue. */
+static inline void *deq_left_end(deq_t const *const deq)
+{
+ deq_block_t *const left_end = deq->left_end;
+ return left_end->data + left_end->l;
+}
+
+/** Return pointer to object at the right end of the double ended queue. */
+static inline void *deq_right_end_obj(deq_t const *const deq, unsigned size)
+{
+ deq_block_t *const right_end = deq->right_end;
+ return right_end->data + right_end->r - size;
+}
+
+/**
+ * Remove object of size \p size from the left end of double ended queue \p deq.
+ */
+static inline void deq_shrink_left(deq_t *const deq, unsigned size)
+{
+ deq_block_t *const left_end = deq->left_end;
+ left_end->l += size;
+ if (left_end->l >= left_end->r)
+ deq_left_end_block_empty_priv(deq);
+}
+
+/**
+ * Remove object of size \p size from the right end of double ended queue
+ * \p deq.
+ */
+static inline void deq_shrink_right(deq_t *const deq, unsigned size)
+{
+ deq_block_t *const right_end = deq->right_end;
+ assert(right_end->r >= size);
+ right_end->r -= size;
+ if (right_end->r <= right_end->l)
+ deq_right_end_block_empty_priv(deq);
+}
+
+/**
+ * Allocate space for object of size \p size on the left end of the double ended
+ * queue \p deq. Returns a pointer to the newly allocated space.
+ */
+static inline void *deq_alloc_left(deq_t *const deq, unsigned size)
+{
+ assert(size < DEQ_BLOCK_DATA_SIZE);
+ deq_block_t *left_end = deq->left_end;
+ if (left_end->l < size)
+ left_end = deq_append_block_left_priv(deq);
+ left_end->l -= size;
+ return left_end->data + left_end->l;
+}
+
+/**
+ * Allocate space for object of size \p size on the right end of the double
+ * ended queue \p deq. Returns a pointer to the newly allocated space.
+ */
+static inline void *deq_alloc_right(deq_t *const deq, unsigned size)
+{
+ assert(size < DEQ_BLOCK_DATA_SIZE);
+ deq_block_t *right_end = deq->right_end;
+ if (right_end->r + size > DEQ_BLOCK_DATA_SIZE)
+ right_end = deq_append_block_right_priv(deq);
+ void *result = right_end->data + right_end->r;
+ right_end->r += size;
+ return result;
+}
+
+static inline deq_block_t const *deq_get_left_end_block(deq_t const *const deq)
+{
+ return deq->left_end;
+}
+
+static inline deq_block_t *deq_block_next_right(deq_block_t const *const block)
+{
+ return block->next_right;
+}
+
+static inline const void *deq_block_data_begin(deq_block_t const *const block)
+{
+ return block->data + block->l;
+}
+
+static inline const void *deq_block_data_end(deq_block_t const *const block)
+{
+ return block->data + block->r;
+}
+
+/** @} */
+
+#endif
diff --git a/ir/adt/pdeq_new.h b/ir/adt/pdeq_new.h
new file mode 100644
index 0000000..4e051dc
--- /dev/null
+++ b/ir/adt/pdeq_new.h
@@ -0,0 +1,94 @@
+/*
+ * This file is part of libFirm.
+ * Copyright (C) 2016 Matthias Braun
+ */
+
+/**
+ * @file
+ * @brief Double Ended Pointer Queue.
+ *
+ * Convenience functions to maintain a double ended queue containing pointers.
+ */
+#ifndef FIRM_ADT_PDEQ_NEW_H
+#define FIRM_ADT_PDEQ_NEW_H
+
+#include "deq.h"
+
+static inline void deq_push_pointer_left(deq_t *deq, void *ptr)
+{
+ void **space = (void**)deq_alloc_left(deq, sizeof(void*));
+ *space = ptr;
+}
+
+static inline void deq_push_pointer_right(deq_t *deq, void *ptr)
+{
+ void **space = (void**)deq_alloc_right(deq, sizeof(void*));
+ *space = ptr;
+}
+
+static inline void *deq_pop_pointer_left(deq_t *deq)
+{
+ void *result = *((void**)deq_left_end(deq));
+ deq_shrink_left(deq, sizeof(void*));
+ return result;
+}
+
+#define deq_pop_pointer_left(type, deq) \
+ ((type*)deq_pop_pointer_left(deq))
+
+static inline void *deq_pop_pointer_right(deq_t *deq)
+{
+ void *result = *((void**)deq_right_end_obj(deq, sizeof(void*)));
+ deq_shrink_right(deq, sizeof(void*));
+ return result;
+}
+
+#define deq_pop_pointer_right(type, deq) \
+ ((type*)deq_pop_pointer_right(deq))
+
+
+typedef struct deq_pointer_iter_t {
+ deq_t const *deq;
+ deq_block_t const *block;
+ void const **block_p;
+ void const **block_end;
+} deq_pointer_iter_t;
+
+static inline void deq_pointer_iter_init(deq_pointer_iter_t *const iter,
+ deq_t const *const deq)
+{
+ deq_block_t const *const block = deq_get_left_end_block(deq);
+ iter->deq = deq;
+ iter->block = block;
+ iter->block_p = (void const**)deq_block_data_begin(block);
+ iter->block_end = (void const**)deq_block_data_end(block);
+}
+
+static inline bool deq_pointer_iter_at_end(deq_pointer_iter_t const *const iter)
+{
+ return iter->block_p == iter->block_end;
+}
+
+static inline void deq_pointer_iter_next(deq_pointer_iter_t *const iter)
+{
+ ++iter->block_p;
+ if (iter->block_p == iter->block_end) {
+ deq_block_t const *const next_right = deq_block_next_right(iter->block);
+ if (next_right != NULL) {
+ iter->block = next_right;
+ iter->block_p = (void const**)deq_block_data_begin(next_right);
+ iter->block_end = (void const**)deq_block_data_end(next_right);
+ }
+ }
+}
+
+#define deq_foreach_pointer(deq, type, pointer) \
+ for (bool pointer##__once = true; pointer##__once;) \
+ for (deq_pointer_iter_t pointer##__iter; pointer##__once;) \
+ for (type *pointer; pointer##__once; pointer##__once = false) \
+ for (deq_pointer_iter_init(&pointer##__iter, deq); \
+ (pointer = *((type**)pointer##__iter.block_p)), \
+ !deq_pointer_iter_at_end(&pointer##__iter); \
+ deq_pointer_iter_next(&pointer##__iter))
+
+#endif