Begin adding some C code

diff --git a/c/queue.c b/c/queue.c
new file mode 100644 (file)
index 0000000..cc5b2e3
--- /dev/null
+++ b/c/queue.c
@@ -0,0 +1,100 @@
+/*
+This is an adaptation of Michael and Scott's lock-free queue.
+
+Whitepaper containing pseudocode can be found here:
+https://www.liblfds.org/downloads/white%20papers/[Queue]%20-%20[Michael,%20Scott]%20-%20Simple,%20Fast,%20and%20Practical%20Non-Blocking%20and%20Blocking%20Concurrent%20Queue%20Algorithms.pdf
+*/
+#ifndef QUEUE_C
+#define QUEUE_C
+
+#include<stdbool.h>
+#include<stdint.h>
+#include<stdlib.h>
+#include"queue.h">
+
+struct QueueNodeTaggedPointer;
+struct QueueNode;
+
+typedef struct QueueNodeTaggedPointer QueueNodeTaggedPointer;
+typedef struct QueueNode QueueNode;
+
+struct QueueNodeTaggedPointer {
+  QueueNode* ptr;
+  uint64_t count;
+};
+
+QueueNodeTaggedPointer QueueNodeTaggedPointer_create(QueueNode* ptr, uint64_t count) {
+  QueueNodeTaggedPointer result = { ptr, count };
+  return result;
+}
+
+struct QueueNode {
+  void* value;
+  volatile QueueNodeTaggedPointer next;
+};
+
+volatile struct Queue {
+  QueueNodeTaggedPointer nose;
+  QueueNodeTaggedPointer tail;
+};
+
+Queue* Queue_construct() {
+  QueueNode* dummy = malloc(sizeof(QueueNode));
+  dummy->next = NULL;
+
+  Queue* result = malloc(sizeof(Queue));
+  result->nose.ptr = dummy;
+  result->tail.ptr = dummy;
+  return result;
+}
+
+void Queue_enqueue(Queue* self, void* value) {
+  QueueNode* node = malloc(sizeof(QueueNode));
+  node->value = value;
+  node->next.ptr = NULL;
+
+  while(true) {
+    QueueNodeTaggedPointer tail = self->tail;
+    QueueNodeTaggedPointer next = tail.ptr->next;
+
+    if(tail == self->tail) {
+      if(next.ptr == NULL) {
+        if(__sync_bool_compare_and_swap(&(tail.ptr->next), next, QueueNodeTaggedPointer_create(node, next.count + 1))) {
+          __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(node, tail.count + 1));
+          return;
+        }
+        else {
+          __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(next.ptr, tail.count + 1));
+        }
+      }
+    }
+  }
+}
+
+void* Queue_dequeue(Queue* self, void* defaultValue) {
+  while(true) {
+    QueueNodeTaggedPointer nose = self->nose;
+    QueueNodeTaggedPointer tail = self->tail;
+    QueueNodeTaggedPointer head = nose.ptr->next;
+
+    if(nose == self->nose) {
+      if(nose.ptr == tail.ptr) {
+        if(head.ptr == NULL) {
+          return defaultValue;
+        }
+        else {
+          __sync_bool_compare_and_swap(&(self->tail), tail, QueueNodeTaggedPointer_create(head.ptr, tail.count + 1));
+        }
+      }
+      else {
+        void* result = head.ptr->value;
+        if(__sync_bool_compare_and_swap(&(self->nose), nose, QueueNodeTaggedPointer_create(head.ptr, nose.count + 1))) {
+          free(nose.ptr);
+          return result;
+        }
+      }
+    }
+  }
+}
+
+#endif

diff --git a/c/queue.h b/c/queue.h
new file mode 100644 (file)
index 0000000..01ba40c
--- /dev/null
+++ b/c/queue.h
@@ -0,0 +1,12 @@
+#ifndef QUEUE_H
+#define QUEUE_H
+
+struct Queue;
+typedef struct Queue Queue;
+
+Queue* Queue_construct();
+
+void Queue_enqueue(Queue*, void*);
+void* Queue_dequeue(Queue*, void* defaultValue);
+
+#endif

diff --git a/c/rope.c b/c/rope.c
new file mode 100644 (file)
index 0000000..716a5af
--- /dev/null
+++ b/c/rope.c
@@ -0,0 +1,90 @@
+#ifndef ROPE_C
+#define ROPE_C
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+enum RopeType;
+typedef enum RopeType RopeType;
+enum RopeType {
+  ROPETYPE_CONCATENATION,
+  ROPETYPE_STRING
+};
+
+struct Concatenation;
+typedef struct Concatenation Concatenation;
+struct Concatenation {
+  Rope* r0;
+  Rope* r1;
+};
+
+struct String;
+typedef struct String String;
+struct String {
+  size_t length;
+  uint32_t* characters;
+};
+
+union RopeInstance;
+typedef union RopeInstance RopeInstance;
+union RopeInstance {
+  Concatenation concatenation;
+  String string;
+};
+
+struct Rope {
+  volatile size_t referenceCount;
+  RopeType type;
+  RopeInstance instance;
+};
+
+Rope* Rope_rereference(Rope* self) {
+  __sync_add_and_fetch(&(self->referenceCount), 1);
+  return self;
+}
+
+void Rope_destruct(Rope* self) {
+  size_t referenceCount = __sync_sub_and_fetch(&(self->referenceCount), 1);
+
+  if(referenceCount == 0) {
+    switch(self->type) {
+      case ROPETYPE_CONCATENATION:
+        Rope_destruct(self->instance.concatenation.r0);
+        Rope_destruct(self->instance.concatenation.r1);
+        break;
+
+      case ROPETYPE_STRING:
+        free(self->instance.string.characters);
+        break;
+
+      default:
+        assert(false);
+    }
+
+    free(self);
+  }
+}
+
+void Rope_write(Rope*, Encoding, FILE) {
+  // TODO Implement
+  printf("Not implemented");
+}
+
+Rope* Rope_read(Encoding, FILE) {
+  // TODO Implement
+  printf("Not implemented");
+  return NULL;
+}
+
+Rope* Rope_concatenate(Rope* r0, Rope* r1) {
+  Rope* result = malloc(sizeof(Rope));
+  result->referenceCount = 0;
+  result->type = ROPETYPE_CONCATENATION;
+  result->instance.concatenation.r0 = Rope_rereference(r0);
+  result->instance.concatenation.r1 = Rope_rereference(r1);
+  return result;
+}
+
+#endif

diff --git a/c/rope.h b/c/rope.h
new file mode 100644 (file)
index 0000000..33319e7
--- /dev/null
+++ b/c/rope.h
@@ -0,0 +1,24 @@
+#ifndef ROPE_H
+#define ROPE H
+
+struct Rope;
+typedef struct Rope Rope;
+
+enum Encoding {
+  ASCII,
+  UTF_8,
+  UTF_16,
+  UTF_32
+};
+
+typedef enum Encoding Encoding;
+
+Rope* Rope_rereference(Rope*);
+void Rope_destruct(Rope*);
+
+void Rope_write(Rope*, Encoding, FILE);
+Rope* Rope_read(Encoding, FILE);
+
+Rope* Rope_concatenate(Rope* r0, Rope* r1);
+
+#endif