1 files changed, 705 insertions, 0 deletions
diff --git a/libparc/parc/algol/parc_LinkedList.c b/libparc/parc/algol/parc_LinkedList.c
new file mode 100644
index 00000000..d220e223
--- /dev/null
+++ b/libparc/parc/algol/parc_LinkedList.c
@@ -0,0 +1,705 @@
+/*
+ * Copyright (c) 2017 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/**
+ */
+#include <config.h>
+
+#include <LongBow/runtime.h>
+
+#include <stdio.h>
+#include <sys/queue.h>
+
+#include <parc/algol/parc_LinkedList.h>
+
+#include <parc/algol/parc_DisplayIndented.h>
+#include <parc/algol/parc_Object.h>
+#include <parc/algol/parc_Memory.h>
+
+static PARCListInterface *PARCLinkedListAsPARCList = &(PARCListInterface) {
+    .Add = (bool (*)(void *, void *))parcLinkedList_Append,
+    .AddAtIndex = (void (*)(void *, int index, PARCObject *))parcLinkedList_InsertAtIndex,
+    .AddCollection = (bool (*)(void *, PARCCollection *))NULL,
+    .AddCollectionAtIndex = (bool (*)(void *, int index, PARCCollection *))NULL,
+    .Clear = (void (*)(void *))NULL,
+    .Contains = (bool (*)(const void *, const PARCObject *))parcLinkedList_Contains,
+    .ContainsCollection = (bool (*)(const void *, const PARCCollection *))NULL,
+    .Copy = (void *    (*)(const PARCList *))parcLinkedList_Copy,
+    .Destroy = (void (*)(void **))parcLinkedList_Release,
+    .Equals = (bool (*)(const void *, const void *))parcLinkedList_Equals,
+    .GetAtIndex = (PARCObject * (*)(const void *, size_t))parcLinkedList_GetAtIndex,
+    .HashCode = (PARCHashCode (*)(const void *))parcLinkedList_HashCode,
+    .IndexOf = (size_t (*)(const void *, const PARCObject *element))NULL,
+    .IsEmpty = (bool (*)(const void *))parcLinkedList_IsEmpty,
+    .LastIndexOf = (size_t (*)(void *, const PARCObject *element))NULL,
+    .Remove = (bool (*)(void *, const PARCObject *element))parcLinkedList_Remove,
+    .RemoveAtIndex = (PARCObject * (*)(PARCList *, size_t))parcLinkedList_RemoveAtIndex,
+    .RemoveCollection = (bool (*)(void *, const PARCCollection *))NULL,
+    .RetainCollection = (bool (*)(void *, const PARCCollection *))NULL,
+    .SetAtIndex = (PARCObject * (*)(void *, size_t index, PARCObject *))parcLinkedList_SetAtIndex,
+    .Size = (size_t (*)(const void *))parcLinkedList_Size,
+    .SubList = (PARCList * (*)(const void *, size_t, size_t))NULL,
+    .ToArray = (void**      (*)(const void *))NULL,
+};
+
+typedef struct parc_linkedlist_node {
+    PARCObject *object;
+    struct parc_linkedlist_node *previous;
+    struct parc_linkedlist_node *next;
+} _PARCLinkedListNode;
+
+struct parc_linkedlist {
+    _PARCLinkedListNode *head;
+    _PARCLinkedListNode *tail;
+    size_t size;
+};
+
+static inline _PARCLinkedListNode *
+_parcLinkedListNode_getByIndex(const PARCLinkedList *list, size_t index)
+{
+    _PARCLinkedListNode *node = list->head;
+    while (index-- && node != NULL) {
+        node = node->next;
+    }
+    return node;
+}
+
+static inline _PARCLinkedListNode *
+_parcLinkedListNode_getByValue(const PARCLinkedList *list, const PARCObject *value)
+{
+    _PARCLinkedListNode *node = list->head;
+    while (node != NULL && parcObject_Equals(node->object, value) == false) {
+        node = node->next;
+    }
+    return node;
+}
+
+static bool
+_parcLinkedListNode_IsValid(const _PARCLinkedListNode *node)
+{
+    bool result = false;
+
+    if (node != NULL) {
+        if (node->object != NULL) {
+            if (parcObject_IsValid(node->object)) {
+                if (node->previous) {
+                    if (node->previous->next == node) {
+                        if (parcObject_IsValid(node->previous->object)) {
+                            result = true;
+                        }
+                    }
+                } else {
+                    result = true;
+                }
+                if (node->next != NULL) {
+                    if (node->next->previous == node) {
+                        if (parcObject_IsValid(node->next->object)) {
+                            result = true;
+                        }
+                    }
+                } else {
+                    result = true;
+                }
+            }
+        }
+    }
+
+    return result;
+}
+
+static inline _PARCLinkedListNode *
+_parcLinkedListNode_Create(const PARCObject *object, _PARCLinkedListNode *previous, _PARCLinkedListNode *next)
+{
+    _PARCLinkedListNode *result = parcMemory_Allocate(sizeof(_PARCLinkedListNode));
+    if (result != NULL) {
+        result->object = parcObject_Acquire(object);
+        result->next = next;
+        result->previous = previous;
+    }
+
+    return result;
+}
+
+static void
+_parcLinkedListIterator_IsValid(const _PARCLinkedListNode *node)
+{
+    if (node != NULL) {
+        assertTrue(_parcLinkedListNode_IsValid(node), "node is invalid");
+    }
+}
+
+static void
+_parcLinkedListNode_Destroy(PARCLinkedList *list __attribute__((unused)), _PARCLinkedListNode **nodePtr)
+{
+    _PARCLinkedListNode *node = *nodePtr;
+
+    parcObject_Release(&node->object);
+    parcMemory_Deallocate((void **) nodePtr);
+}
+
+static bool
+_parcLinkedList_Destructor(PARCLinkedList **listPtr)
+{
+    PARCLinkedList *list = *listPtr;
+
+    _PARCLinkedListNode *next = NULL;
+
+    for (_PARCLinkedListNode *node = list->head; node != NULL; node = next) {
+        next = node->next;
+        _parcLinkedListNode_Destroy(list, &node);
+    }
+    return true;
+}
+
+static _PARCLinkedListNode *
+_parcLinkedIterator_Init(PARCLinkedList *list __attribute__((unused)))
+{
+    return NULL;
+}
+
+static bool
+_parcLinkedListNode_Fini(PARCLinkedList *list __attribute__((unused)), const _PARCLinkedListNode *node __attribute__((unused)))
+{
+    return true;
+}
+
+static struct parc_linkedlist_node *
+_parcLinkedListNode_Next(PARCLinkedList *list __attribute__((unused)), const _PARCLinkedListNode *node)
+{
+    struct parc_linkedlist_node *result = NULL;
+
+    if (node == NULL) {
+        result = list->head;
+    } else {
+        assertTrue(_parcLinkedListNode_IsValid(node), "node is invalid");
+        trapOutOfBoundsIf(node->next == NULL, "No more elements.");
+        result = node->next;
+    }
+
+    assertTrue(_parcLinkedListNode_IsValid(result), "result is invalid");
+    parcObject_OptionalAssertValid(result->object);
+
+    return result;
+}
+
+static inline PARCObject *
+_parcLinkedListNode_Delete(PARCLinkedList *list, _PARCLinkedListNode *node)
+{
+    PARCObject *result = node->object;
+
+    list->size--;
+
+    if (node == list->head) {
+        list->head = node->next;
+    }
+    if (node == list->tail) {
+        list->tail = node->previous;
+    }
+    if (node->previous) {
+        node->previous->next = node->next;
+    }
+    if (node->next) {
+        node->next->previous = node->previous;
+    }
+
+    parcMemory_Deallocate((void **) &node);
+
+    return result;
+}
+
+static void
+_parcLinkedListNode_Remove(PARCLinkedList *list, _PARCLinkedListNode **nodePtr)
+{
+    parcLinkedList_OptionalAssertValid(list);
+
+    _PARCLinkedListNode *node = *nodePtr;
+
+    if (node != NULL) {
+        *nodePtr = node->previous;
+
+        PARCObject *object = _parcLinkedListNode_Delete(list, node);
+        parcObject_Release(&object);
+
+        parcLinkedList_OptionalAssertValid(list);
+    }
+}
+
+static bool
+_parcLinkedListNode_HasNext(PARCLinkedList *list, const _PARCLinkedListNode *node)
+{
+    bool result = false;
+
+    if (node == NULL) {
+        result = (list->head != NULL);
+        if (result) {
+            assertTrue(_parcLinkedListNode_IsValid(list->head), "node is invalid");
+        }
+    } else {
+        result = node->next != NULL;
+        if (result) {
+            assertTrue(_parcLinkedListNode_IsValid(node->next), "node is invalid");
+        }
+    }
+
+
+    return result;
+}
+
+static void *
+_parcLinkedListNode_Element(PARCLinkedList *list __attribute__((unused)), const _PARCLinkedListNode *node)
+{
+    return node->object;
+}
+
+parcObject_Override(PARCLinkedList, PARCObject,
+                    .destructor = (PARCObjectDestructor *) _parcLinkedList_Destructor,
+                    .copy = (PARCObjectCopy *) parcLinkedList_Copy,
+                    .equals = (PARCObjectEquals *) parcLinkedList_Equals,
+                    .hashCode = (PARCObjectHashCode *) parcLinkedList_HashCode,
+                    .display = (PARCObjectDisplay *) parcLinkedList_Display);
+
+PARCIterator *
+parcLinkedList_CreateIterator(PARCLinkedList *list)
+{
+    PARCIterator *iterator = parcIterator_Create(list,
+                                                 (void *(*)(PARCObject *))_parcLinkedIterator_Init,
+                                                 (bool (*)(PARCObject *, void *))_parcLinkedListNode_HasNext,
+                                                 (void *(*)(PARCObject *, void *))_parcLinkedListNode_Next,
+                                                 (void (*)(PARCObject *, void **))_parcLinkedListNode_Remove,
+                                                 (void *(*)(PARCObject *, void *))_parcLinkedListNode_Element,
+                                                 (void (*)(PARCObject *, void *))_parcLinkedListNode_Fini,
+                                                 (void (*)(const void *))_parcLinkedListIterator_IsValid);
+
+    return iterator;
+}
+
+PARCLinkedList *
+parcLinkedList_Create(void)
+{
+    PARCLinkedList *result = parcObject_CreateInstance(PARCLinkedList);
+
+    if (result != NULL) {
+        result->head = NULL;
+        result->tail = NULL;
+        result->size = 0;
+    }
+    return result;
+}
+
+bool
+parcLinkedList_IsValid(const PARCLinkedList *list)
+{
+    bool result = false;
+
+    if (list != NULL) {
+        if (parcObject_IsValid(list)) {
+            if (list->size > 0) {
+                if (list->head != NULL) {
+                    if (list->tail != NULL) {
+                        result = true;
+                        for (_PARCLinkedListNode *node = list->head; node != NULL; node = node->next) {
+                            if (_parcLinkedListNode_IsValid(node) == false) {
+                                result = false;
+                                break;
+                            }
+                        }
+                    }
+                }
+            } else {
+                if (list->head == NULL) {
+                    if (list->tail == NULL) {
+                        result = true;
+                    }
+                }
+            }
+        }
+    }
+
+    return result;
+}
+
+void
+parcLinkedList_AssertValid(const PARCLinkedList *instance)
+{
+    assertTrue(parcLinkedList_IsValid(instance),
+               "PARCLinkedList is not valid.");
+}
+
+parcObject_ImplementAcquire(parcLinkedList, PARCLinkedList);
+
+parcObject_ImplementRelease(parcLinkedList, PARCLinkedList);
+
+PARCLinkedList *
+parcLinkedList_Copy(const PARCLinkedList *list)
+{
+    PARCLinkedList *result = parcLinkedList_Create();
+
+    struct parc_linkedlist_node *node = list->head;
+
+    while (node != NULL) {
+        parcLinkedList_Append(result, node->object);
+        node = node->next;
+    }
+
+    return result;
+}
+
+bool
+parcLinkedList_Contains(const PARCLinkedList *list, const PARCObject *element)
+{
+    bool result = false;
+
+    struct parc_linkedlist_node *node = list->head;
+
+    while (node != NULL) {
+        if (parcObject_Equals(node->object, element)) {
+            result = true;
+            break;
+        }
+        node = node->next;
+    }
+
+    return result;
+}
+
+PARCLinkedList *
+parcLinkedList_Append(PARCLinkedList *list, const PARCObject *element)
+{
+    _PARCLinkedListNode *node = _parcLinkedListNode_Create(element, list->tail, NULL);
+
+    if (list->tail == NULL) {
+        list->tail = node;
+    } else {
+        list->tail->next = node;
+        list->tail = node;
+    }
+
+    if (list->head == NULL) {
+        list->head = list->tail;
+    }
+
+    list->size++;
+
+    return list;
+}
+
+PARCLinkedList *
+parcLinkedList_AppendAll(PARCLinkedList *list, const PARCLinkedList *other)
+{
+    PARCIterator *iterator = parcLinkedList_CreateIterator((PARCLinkedList *) other);
+    while (parcIterator_HasNext(iterator)) {
+        PARCObject *object = parcIterator_Next(iterator);
+        parcLinkedList_Append(list, object);
+    }
+    parcIterator_Release(&iterator);
+
+    return list;
+}
+
+PARCLinkedList *
+parcLinkedList_Prepend(PARCLinkedList *list, const PARCObject *element)
+{
+    _PARCLinkedListNode *node = _parcLinkedListNode_Create(element, NULL, list->head);
+
+    if (list->head == NULL) {
+        list->head = node;
+    } else {
+        list->head->previous = node;
+        list->head = node;
+    }
+
+    if (list->tail == NULL) {
+        list->tail = list->head;
+    }
+    list->size++;
+
+    parcLinkedList_OptionalAssertValid(list);
+
+    return list;
+}
+
+PARCObject *
+parcLinkedList_RemoveFirst(PARCLinkedList *list)
+{
+    PARCObject *result = NULL;
+
+    if (list->head != NULL) {
+        _PARCLinkedListNode *node = list->head;
+        result = _parcLinkedListNode_Delete(list, node);
+    }
+
+    parcLinkedList_OptionalAssertValid(list);
+
+    return result;
+}
+
+PARCObject *
+parcLinkedList_RemoveLast(PARCLinkedList *list)
+{
+    PARCObject *result = NULL;
+
+    if (list->tail != NULL) {
+        _PARCLinkedListNode *node = list->tail;
+        result = _parcLinkedListNode_Delete(list, node);
+    }
+
+    parcLinkedList_OptionalAssertValid(list);
+    return result;
+}
+
+bool
+parcLinkedList_Remove(PARCLinkedList *list, const PARCObject *element)
+{
+    assertTrue(element != NULL, "Element must not be NULL");
+    bool result = false;
+
+    _PARCLinkedListNode *node = _parcLinkedListNode_getByValue(list, element);
+    if (node != NULL) {
+        PARCObject *e = _parcLinkedListNode_Delete(list, node);
+        parcObject_Release(&e);
+        result = true;
+    }
+
+    parcLinkedList_OptionalAssertValid(list);
+
+    return result;
+}
+
+PARCObject *
+parcLinkedList_RemoveAtIndex(PARCLinkedList *list, size_t index)
+{
+    PARCObject *result = NULL;
+
+    _PARCLinkedListNode *node = _parcLinkedListNode_getByIndex(list, index);
+    if (node != NULL) {
+        result = _parcLinkedListNode_Delete(list, node);
+    }
+
+    return result;
+}
+
+PARCObject *
+parcLinkedList_GetFirst(const PARCLinkedList *list)
+{
+    PARCObject *result = NULL;
+
+    if (list->head != NULL) {
+        _PARCLinkedListNode *node = list->head;
+        result = node->object;
+    }
+    return result;
+}
+
+PARCObject *
+parcLinkedList_GetLast(const PARCLinkedList *list)
+{
+    PARCObject *result = NULL;
+
+    if (list->tail != NULL) {
+        _PARCLinkedListNode *node = list->tail;
+        result = node->object;
+    }
+    return result;
+}
+
+PARCHashCode
+parcLinkedList_HashCode(const PARCLinkedList *list)
+{
+    PARCHashCode result = 0;
+
+    _PARCLinkedListNode *node = list->head;
+    if (node != NULL) {
+        while (node != NULL) {
+            result += parcObject_HashCode(node->object);
+            node = node->next;
+        }
+    }
+
+    return result;
+}
+
+size_t
+parcLinkedList_Size(const PARCLinkedList *list)
+{
+    return list->size;
+}
+
+bool
+parcLinkedList_IsEmpty(const PARCLinkedList *list)
+{
+    return (parcLinkedList_Size(list) == 0);
+}
+
+static void
+_parcLinkedList_InsertInitialNode(PARCLinkedList *list, const PARCObject *element)
+{
+    _PARCLinkedListNode *newNode = _parcLinkedListNode_Create(element, NULL, NULL);
+    list->head = newNode;
+    list->tail = newNode;
+}
+
+PARCLinkedList *
+parcLinkedList_InsertAtIndex(PARCLinkedList *list, size_t index, const PARCObject *element)
+{
+    if (index == 0) {
+        if (list->head == NULL) {
+            _parcLinkedList_InsertInitialNode(list, element);
+        } else {
+            _PARCLinkedListNode *newNode = _parcLinkedListNode_Create(element, NULL, list->head);
+
+            list->head->previous = newNode;
+            list->tail = list->head;
+            list->head = newNode;
+        }
+
+        list->size++;
+    } else if (index == list->size) {
+        _PARCLinkedListNode *node = list->tail;
+        node->next = _parcLinkedListNode_Create(element, node, NULL);
+        list->tail = node->next;
+        list->size++;
+    } else {
+        _PARCLinkedListNode *node = list->head;
+        while (index-- && node->next != NULL) {
+            node = node->next;
+        }
+        _PARCLinkedListNode *newNode = _parcLinkedListNode_Create(element, node->previous, node);
+
+        node->previous->next = newNode;
+        node->previous = newNode;
+        list->size++;
+    }
+
+    parcLinkedList_OptionalAssertValid(list);
+    return list;
+}
+
+PARCObject *
+parcLinkedList_SetAtIndex(PARCLinkedList *list, size_t index, PARCObject *element)
+{
+    PARCObject *result = NULL;
+
+    if (index > (parcLinkedList_Size(list) - 1)) {
+        trapOutOfBounds(index, "[0, %zd]", parcLinkedList_Size(list) - 1);
+    }
+
+    _PARCLinkedListNode *node = _parcLinkedListNode_getByIndex(list, index);
+    if (node != NULL) {
+        result = node->object;
+        node->object = parcObject_Acquire(element);
+    }
+    return result;
+}
+
+PARCObject *
+parcLinkedList_GetAtIndex(const PARCLinkedList *list, size_t index)
+{
+    if (index > (parcLinkedList_Size(list) - 1)) {
+        trapOutOfBounds(index, "[0, %zd]", parcLinkedList_Size(list) - 1);
+    }
+
+    _PARCLinkedListNode *node = _parcLinkedListNode_getByIndex(list, index);
+    return (node == NULL) ? NULL : node->object;
+}
+
+bool
+parcLinkedList_Equals(const PARCLinkedList *x, const PARCLinkedList *y)
+{
+    if (x == y) {
+        return true;
+    }
+    if (x == NULL || y == NULL) {
+        return false;
+    }
+
+    if (x->size == y->size) {
+        _PARCLinkedListNode *xNode = x->head;
+        _PARCLinkedListNode *yNode = y->head;
+
+        while (xNode != NULL) {
+            if (parcObject_Equals(xNode->object, yNode->object) == false) {
+                return false;
+            }
+            xNode = xNode->next;
+            yNode = yNode->next;
+        }
+        return true;
+    }
+    return false;
+}
+
+void
+parcLinkedList_Display(const PARCLinkedList *list, const int indentation)
+{
+    if (list == NULL) {
+        parcDisplayIndented_PrintLine(indentation, "PARCLinkedList@NULL");
+    } else {
+        parcDisplayIndented_PrintLine(indentation, "PARCLinkedList@%p { .size=%016zp, .head=%016zp, .tail=%016zp",
+                                      (void *) list, list->size, list->head, list->tail);
+
+        _PARCLinkedListNode *node = list->head;
+
+        while (node != NULL) {
+            parcDisplayIndented_PrintLine(indentation + 1,
+                                          "%016zp { .previous=%016zp, %016zp, .next=%016zp }",
+                                          node, node->previous, node->object, node->next);
+            parcObject_Display(node->object, indentation + 2);
+            node = node->next;
+        }
+
+        parcDisplayIndented_PrintLine(indentation, "}\n");
+    }
+}
+
+bool
+parcLinkedList_SetEquals(const PARCLinkedList *x, const PARCLinkedList *y)
+{
+    bool result = false;
+
+    if (x->size == y->size) {
+        for (size_t i = 0; i < x->size; i++) {
+            PARCObject *xObject = parcLinkedList_GetAtIndex(x, i);
+            for (size_t j = 0; j < x->size; j++) {
+                PARCObject *yObject = parcLinkedList_GetAtIndex(y, j);
+                if (parcObject_Equals(xObject, yObject) == false) {
+                    break;
+                }
+            }
+        }
+        result = true;
+    }
+
+    return result;
+}
+
+PARCList *
+parcLinkedList_AsPARCList(PARCLinkedList *list)
+{
+    PARCList *result = parcList_Create(list, PARCLinkedListAsPARCList);
+    return result;
+}
+
+void
+parcLinkedList_ApplyImpl(PARCLinkedList *list, void (*function)(PARCObject *, const void *), const void *parameter)
+{
+    PARCIterator *iterator = parcLinkedList_CreateIterator(list);
+
+    while (parcIterator_HasNext(iterator)) {
+        PARCObject *object = parcIterator_Next(iterator);
+        function(object, parameter);
+    }
+
+    parcIterator_Release(&iterator);
+}