From 64ef22e135f7c790f0cd80956d8bdf7fa0268148 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Mon, 19 Aug 2019 02:34:59 -0400 Subject: [PATCH] Begin adding some C code --- c/queue.c | 100 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ c/queue.h | 12 +++++++ c/rope.c | 90 ++++++++++++++++++++++++++++++++++++++++++++++++ c/rope.h | 24 +++++++++++++ 4 files changed, 226 insertions(+) create mode 100644 c/queue.c create mode 100644 c/queue.h create mode 100644 c/rope.c create mode 100644 c/rope.h diff --git a/c/queue.c b/c/queue.c new file mode 100644 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 +#include +#include +#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 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 index 0000000..716a5af --- /dev/null +++ b/c/rope.c @@ -0,0 +1,90 @@ +#ifndef ROPE_C +#define ROPE_C + +#include +#include +#include +#include + +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 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 -- 2.20.1