15 files changed, 760 insertions, 0 deletions

diff --git a/libcnary/CMakeLists.txt b/libcnary/CMakeLists.txt
new file mode 100644
index 0000000..bbbe8ce
--- /dev/null
+++ b/libcnary/CMakeLists.txt
@@ -0,0 +1,16 @@
+cmake_minimum_required(VERSION 2.6)
+
+SET(libcnary_SRC
+        iterator.c
+        list.c
+        node.c
+        node_iterator.c
+        node_list.c )
+
+INCLUDE_DIRECTORIES(${CMAKE_CURRENT_SOURCE_DIR}/include)
+
+SET(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -fPIC")
+ADD_LIBRARY(libcnary STATIC ${libcnary_SRC})
+
+SET_TARGET_PROPERTIES(libcnary PROPERTIES OUTPUT_NAME cnary)
+
diff --git a/libcnary/Makefile b/libcnary/Makefile
new file mode 100644
index 0000000..bdd165d
--- /dev/null
+++ b/libcnary/Makefile
@@ -0,0 +1,21 @@
+TARGET = cnary
+LIBRARY = libcnary.a
+OBJECTS = cnary.o libcnary.a
+LIBRARY_OBJECTS = node.o list.o iterator.o node_list.o node_iterator.o
+CFLAGS=-g -I./include -I/opt/local/include -mmacosx-version-min=10.5 -arch i386 -isysroot /Developer/SDKs/MacOSX10.5.sdk
+LDFLAGS=-L/opt/local/lib -framework CoreFoundation -mmacosx-version-min=10.5 -arch i386 -isysroot /Developer/SDKs/MacOSX10.5.sdk -Wl,-no_compact_linkedit
+
+
+%.o: %.c
+        $(CC) -o $(@) -c $(^) $(CFLAGS)
+
+$(LIBRARY): $(LIBRARY_OBJECTS)
+        $(AR) rs $(@) $(^)
+        
+$(TARGET): $(OBJECTS)
+        $(CC) -o $(@) $(^) $(CFLAGS) $(LDFLAGS)
+
+all: $(TARGET)
+
+clean:
+        rm -rf $(TARGET) $(LIBRARY) $(OBJECTS) $(LIBRARY_OBJECTS)
\ No newline at end of file
diff --git a/libcnary/README b/libcnary/README
new file mode 100644
index 0000000..5472b4e
--- /dev/null
+++ b/libcnary/README
@@ -0,0 +1,5 @@
+Project Name:
+        libcnary
+
+Project Description:
+        A small N-ary (Tree) library written in C.
\ No newline at end of file
diff --git a/libcnary/cnary.c b/libcnary/cnary.c
new file mode 100644
index 0000000..3e55fce
--- /dev/null
+++ b/libcnary/cnary.c
@@ -0,0 +1,30 @@
+/*
+ * cnary.c
+ *
+ *  Created on: Mar 9, 2011
+ *      Author: posixninja
+ */
+
+#include <stdio.h>
+
+#include "node.h"
+
+int main(int argc, char* argv[]) {
+        puts("Creating root node");
+        node_t* root = node_create(NULL, NULL);
+
+        puts("Creating child 1 node");
+        node_t* one = node_create(root, NULL);
+        puts("Creating child 2 node");
+        node_t* two = node_create(root, NULL);
+
+        puts("Creating child 3 node");
+        node_t* three = node_create(one, NULL);
+
+        puts("Debugging root node");
+        node_debug(root);
+
+        puts("Destroying root node");
+        node_destroy(root);
+        return 0;
+}
diff --git a/libcnary/include/iterator.h b/libcnary/include/iterator.h
new file mode 100644
index 0000000..debc1c5
--- /dev/null
+++ b/libcnary/include/iterator.h
@@ -0,0 +1,33 @@
+/*
+ * iterator.h
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#ifndef ITERATOR_H_
+#define ITERATOR_H_
+
+struct list_t;
+struct object_t;
+
+typedef struct iterator_t {
+        struct object_t*(*next)(struct iterator_t* iterator);
+        int(*bind)(struct iterator_t* iterator, struct list_t* list);
+
+        unsigned int count;
+        unsigned int position;
+
+        struct list_t* list;
+        struct object_t* end;
+        struct object_t* begin;
+        struct object_t* value;
+} iterator_t;
+
+void iterator_destroy(struct iterator_t* iterator);
+struct iterator_t* iterator_create(struct list_t* list);
+
+struct object_t* iterator_next(struct iterator_t* iterator);
+int iterator_bind(struct iterator_t* iterator, struct list_t* list);
+
+#endif /* ITERATOR_H_ */
diff --git a/libcnary/include/list.h b/libcnary/include/list.h
new file mode 100644
index 0000000..237aba0
--- /dev/null
+++ b/libcnary/include/list.h
@@ -0,0 +1,24 @@
+/*
+ * list.h
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#ifndef LIST_H_
+#define LIST_H_
+
+#include "object.h"
+
+typedef struct list_t {
+        void* next;
+        void* prev;
+} list_t;
+
+void list_init(struct list_t* list);
+void list_destroy(struct list_t* list);
+
+int list_add(struct list_t* list, struct object_t* object);
+int list_remove(struct list_t* list, struct object_t* object);
+
+#endif /* LIST_H_ */
diff --git a/libcnary/include/node.h b/libcnary/include/node.h
new file mode 100644
index 0000000..35f6333
--- /dev/null
+++ b/libcnary/include/node.h
@@ -0,0 +1,59 @@
+/*
+ * node.h
+ *
+ *  Created on: Mar 7, 2011
+ *      Author: posixninja
+ */
+
+#ifndef NODE_H_
+#define NODE_H_
+
+#include "object.h"
+
+#define NODE_TYPE 1;
+
+struct node_list_t;
+
+// This class implements the abstract iterator class
+typedef struct node_t {
+        // Super class
+        struct node_t* next;
+        struct node_t* prev;
+        unsigned int count;
+
+        // Local Properties
+        int isRoot;
+        int isLeaf;
+
+        // Local Members
+        void *data;
+        unsigned int depth;
+        struct node_t* parent;
+        struct node_list_t* children;
+
+        // Virtual Functions
+        int(*attach)(struct node_t* parent, struct node_t* child);
+        int(*detach)(struct node_t* parent, struct node_t* child);
+
+} node_t;
+
+void node_destroy(struct node_t* node);
+struct node_t* node_create(struct node_t* parent, void* data);
+
+int node_attach(struct node_t* parent, struct node_t* child);
+int node_detach(struct node_t* parent, struct node_t* child);
+int node_insert(struct node_t* parent, unsigned int index, struct node_t* child);
+
+unsigned int node_n_children(struct node_t* node);
+node_t* node_nth_child(struct node_t* node, unsigned int n);
+node_t* node_first_child(struct node_t* node);
+node_t* node_prev_sibling(struct node_t* node);
+node_t* node_next_sibling(struct node_t* node);
+int node_child_position(struct node_t* parent, node_t* child);
+
+typedef void* (*copy_func_t)(const void *src);
+node_t* node_copy_deep(node_t* node, copy_func_t copy_func);
+
+void node_debug(struct node_t* node);
+
+#endif /* NODE_H_ */
diff --git a/libcnary/include/node_iterator.h b/libcnary/include/node_iterator.h
new file mode 100644
index 0000000..8f39ceb
--- /dev/null
+++ b/libcnary/include/node_iterator.h
@@ -0,0 +1,39 @@
+/*
+ * node_iterator.h
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#ifndef NODE_ITERATOR_H_
+#define NODE_ITERATOR_H_
+
+#include "iterator.h"
+#include "node_list.h"
+
+// This class implements the abstract iterator class
+typedef struct node_iterator_t {
+        // Super class
+        struct iterator_t super;
+
+        // Local members
+        struct node_t*(*next)(struct node_iterator_t* iterator);
+        int(*bind)(struct node_iterator_t* iterator, struct node_list_t* list);
+
+        unsigned int count;
+        unsigned int position;
+
+        struct node_list_t* list;
+        struct node_t* end;
+        struct node_t* begin;
+        struct node_t* value;
+
+} node_iterator_t;
+
+void node_iterator_destroy(node_iterator_t* iterator);
+node_iterator_t* node_iterator_create(node_list_t* list);
+
+struct node_t* node_iterator_next(struct node_iterator_t* iterator);
+int node_iterator_bind(struct node_iterator_t* iterator, struct node_list_t* list);
+
+#endif /* NODE_ITERATOR_H_ */
diff --git a/libcnary/include/node_list.h b/libcnary/include/node_list.h
new file mode 100644
index 0000000..bb9fcae
--- /dev/null
+++ b/libcnary/include/node_list.h
@@ -0,0 +1,31 @@
+/*
+ * node_list.h
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#ifndef NODE_LIST_H_
+#define NODE_LIST_H_
+
+struct node_t;
+
+// This class implements the list_t abstract class
+typedef struct node_list_t {
+        // list_t members
+        struct node_t* begin;
+        struct node_t* end;
+
+        // node_list_t members
+        unsigned int count;
+
+} node_list_t;
+
+void node_list_destroy(struct node_list_t* list);
+struct node_list_t* node_list_create(struct node_t* node);
+
+int node_list_add(node_list_t* list, node_t* node);
+int node_list_insert(node_list_t* list, unsigned int index, node_t* node);
+int node_list_remove(node_list_t* list, node_t* node);
+
+#endif /* NODE_LIST_H_ */
diff --git a/libcnary/include/object.h b/libcnary/include/object.h
new file mode 100644
index 0000000..adf1891
--- /dev/null
+++ b/libcnary/include/object.h
@@ -0,0 +1,25 @@
+/*
+ * object.h
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#ifndef OBJECT_H_
+#define OBJECT_H_
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+typedef struct object_t {
+        void* value;
+        unsigned int type;
+        unsigned int size;
+} object_t;
+
+#endif /* OBJECT_H_ */
diff --git a/libcnary/iterator.c b/libcnary/iterator.c
new file mode 100644
index 0000000..f4897f9
--- /dev/null
+++ b/libcnary/iterator.c
@@ -0,0 +1,45 @@
+/*
+ * iterator.c
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "list.h"
+#include "object.h"
+#include "iterator.h"
+
+void iterator_destroy(iterator_t* iterator) {
+        if(iterator) {
+                free(iterator);
+        }
+}
+
+iterator_t* iterator_create(list_t* list) {
+        iterator_t* iterator = (iterator_t*) malloc(sizeof(iterator_t));
+        if(iterator == NULL) {
+                return NULL;
+        }
+        memset(iterator, '\0', sizeof(iterator_t));
+
+        if(list != NULL) {
+                // Create and bind to list
+
+        } else {
+                // Empty Iterator
+        }
+
+        return iterator;
+}
+
+object_t* iterator_next(iterator_t* iterator) {
+        return NULL;
+}
+
+int iterator_bind(iterator_t* iterator, list_t* list) {
+        return -1;
+}
diff --git a/libcnary/list.c b/libcnary/list.c
new file mode 100644
index 0000000..b98cde8
--- /dev/null
+++ b/libcnary/list.c
@@ -0,0 +1,31 @@
+/*
+ * list.c
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+void list_init(list_t* list) {
+        list->next = NULL;
+        list->prev = list;
+}
+
+
+void list_destroy(list_t* list) {
+        if(list) {
+                free(list);
+        }
+}
+
+int list_add(list_t* list, object_t* object) {
+        return -1;
+}
+
+int list_remove(list_t* list, object_t* object) {
+        return -1;
+}
diff --git a/libcnary/node.c b/libcnary/node.c
new file mode 100644
index 0000000..956ba2f
--- /dev/null
+++ b/libcnary/node.c
@@ -0,0 +1,207 @@
+/*
+ * node.c
+ *
+ *  Created on: Mar 7, 2011
+ *      Author: posixninja
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "node.h"
+#include "node_list.h"
+#include "node_iterator.h"
+
+void node_destroy(node_t* node) {
+        if(!node) return;
+
+        if (node->children && node->children->count > 0) {
+                node_t* ch;
+                while ((ch = node->children->begin)) {
+                        node_list_remove(node->children, ch);
+                        node_destroy(ch);
+                }
+        }
+        node_list_destroy(node->children);
+        node->children = NULL;
+
+        free(node);
+}
+
+node_t* node_create(node_t* parent, void* data) {
+        int error = 0;
+
+        node_t* node = (node_t*) malloc(sizeof(node_t));
+        if(node == NULL) {
+                return NULL;
+        }
+        memset(node, '\0', sizeof(node_t));
+
+        node->data = data;
+        node->depth = 0;
+        node->next = NULL;
+        node->prev = NULL;
+        node->count = 0;
+        node->isLeaf = TRUE;
+        node->isRoot = TRUE;
+        node->parent = NULL;
+        node->children = node_list_create(node);
+
+        // Pass NULL to create a root node
+        if(parent != NULL) {
+                // This is a child node so attach it to it's parent
+                error = node_attach(parent, node);
+                if(error < 0) {
+                        // Unable to attach nodes
+                        printf("ERROR: %d \"Unable to attach nodes\"\n", error);
+                        node_destroy(node);
+                        return NULL;
+                }
+        }
+
+        return node;
+}
+
+int node_attach(node_t* parent, node_t* child) {
+        if (!parent || !child) return -1;
+        child->isLeaf = TRUE;
+        child->isRoot = FALSE;
+        child->parent = parent;
+        child->depth = parent->depth + 1;
+        if(parent->isLeaf == TRUE) {
+                parent->isLeaf = FALSE;
+        }
+        int res = node_list_add(parent->children, child);
+        if (res == 0) {
+                parent->count++;
+        }
+        return res;
+}
+
+int node_detach(node_t* parent, node_t* child) {
+        if (!parent || !child) return 0;
+        if (node_list_remove(parent->children, child) == 0) {
+                parent->count--;
+        }
+        return 0;
+}
+
+int node_insert(node_t* parent, unsigned int index, node_t* child)
+{
+        if (!parent || !child) return;
+        child->isLeaf = TRUE;
+        child->isRoot = FALSE;
+        child->parent = parent;
+        child->depth = parent->depth + 1;
+        if(parent->isLeaf == TRUE) {
+                parent->isLeaf = FALSE;
+        }
+        int res = node_list_insert(parent->children, index, child);
+        if (res == 0) {
+                parent->count++;
+        }
+        return res;
+}
+
+void node_debug(node_t* node) {
+        int i = 0;
+        node_t* current = NULL;
+        node_iterator_t* iter = NULL;
+        for(i = 0; i < node->depth; i++) {
+                printf("\t");
+        }
+        if(node->isRoot) {
+                printf("ROOT\n");
+        }
+
+        if(node->isLeaf && !node->isRoot) {
+                printf("LEAF\n");
+
+        } else {
+                if(!node->isRoot) {
+                        printf("NODE\n");
+                }
+                iter = node_iterator_create(node->children);
+                for(current = iter->begin; current != NULL; current = iter->next(iter)) {
+                        node_debug(current);
+                }
+        }
+
+}
+
+unsigned int node_n_children(struct node_t* node)
+{
+        if (!node) return 0;
+        return node->count;
+}
+
+node_t* node_nth_child(struct node_t* node, unsigned int n)
+{
+        if (!node || !node->children || !node->children->begin) return NULL;
+        int index = 0;
+        int found = 0;
+        node_t *ch;
+        for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
+                if (index++ == n) {
+                        found = 1;
+                        break;
+                }
+        }
+        if (!found) {
+                return NULL;
+        }
+        return ch;
+}
+
+node_t* node_first_child(struct node_t* node)
+{
+        if (!node || !node->children) return NULL;
+        return node->children->begin;
+}
+
+node_t* node_prev_sibling(struct node_t* node)
+{
+        if (!node) return NULL;
+        return node->prev;
+}
+
+node_t* node_next_sibling(struct node_t* node)
+{
+        if (!node) return NULL;
+        return node->next;
+}
+
+int node_child_position(struct node_t* parent, node_t* child)
+{
+        if (!parent || !parent->children || !parent->children->begin || !child) return -1;
+        int index = 0;
+        int found = 0;
+        node_t *ch;
+        for (ch = node_first_child(parent); ch; ch = node_next_sibling(ch)) {
+                if (ch == child) {
+                        found = 1;
+                        break;
+                }
+                index++;
+        }
+        if (!found) {
+                return -1;
+        }
+        return index;
+}
+
+node_t* node_copy_deep(node_t* node, copy_func_t copy_func)
+{
+        if (!node) return NULL;
+        void *data;
+        if (copy_func) {
+                data = copy_func(node->data);
+        }
+        node_t* copy = node_create(NULL, data);
+        node_t* ch;
+        for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
+                node_t* cc = node_copy_deep(ch, copy_func);
+                node_attach(copy, cc);
+        }
+        return copy;
+}
diff --git a/libcnary/node_iterator.c b/libcnary/node_iterator.c
new file mode 100644
index 0000000..eef3a4f
--- /dev/null
+++ b/libcnary/node_iterator.c
@@ -0,0 +1,64 @@
+/*
+ * node_iterator.c
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "node.h"
+#include "node_list.h"
+#include "node_iterator.h"
+
+void node_iterator_destroy(node_iterator_t* iterator) {
+        if(iterator) {
+                free(iterator);
+        }
+}
+
+node_iterator_t* node_iterator_create(node_list_t* list) {
+        node_iterator_t* iterator = (node_iterator_t*) malloc(sizeof(node_iterator_t));
+        if(iterator == NULL) {
+                return NULL;
+        }
+        memset(iterator, '\0', sizeof(node_iterator_t));
+
+        iterator->count = 0;
+        iterator->position = 0;
+
+        iterator->end = NULL;
+        iterator->begin = NULL;
+        iterator->value = list->begin;
+
+        iterator->list = NULL;
+        iterator->next = node_iterator_next;
+        iterator->bind = node_iterator_bind;
+
+
+        if(list != NULL) {
+                iterator->bind(iterator, list);
+        }
+
+        return iterator;
+}
+
+node_t* node_iterator_next(node_iterator_t* iterator) {
+        node_t* node = iterator->value;
+        if (node) {
+                iterator->value = node->next;
+        }
+        iterator->position++;
+        return node;
+}
+
+int node_iterator_bind(node_iterator_t* iterator, node_list_t* list) {
+        iterator->position = 0;
+        iterator->end = list->end;
+        iterator->count = list->count;
+        iterator->begin = list->begin;
+        iterator->value = list->begin;
+        return 0;
+}
diff --git a/libcnary/node_list.c b/libcnary/node_list.c
new file mode 100644
index 0000000..8464af2
--- /dev/null
+++ b/libcnary/node_list.c
@@ -0,0 +1,130 @@
+/*
+ * node_list.c
+ *
+ *  Created on: Mar 8, 2011
+ *      Author: posixninja
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "list.h"
+#include "node.h"
+#include "node_list.h"
+
+void node_list_destroy(node_list_t* list) {
+        if(list != NULL) {
+                list_destroy((list_t*) list);
+        }
+}
+
+node_list_t* node_list_create(node_t* node) {
+        node_list_t* list = (node_list_t*) malloc(sizeof(node_list_t));
+        if(list == NULL) {
+                return NULL;
+        }
+        memset(list, '\0', sizeof(node_list_t));
+
+        // Initialize structure
+        list_init((list_t*) list);
+        list->count = 0;
+        return list;
+}
+
+int node_list_add(node_list_t* list, node_t* node) {
+        if (!list || !node) return -1;
+
+        // Find the last element in the list
+        node_t* last = list->end;
+
+        // Setup our new node as the new last element
+        node->next = NULL;
+        node->prev = last;
+
+        // Set the next element of our old "last" element
+        last->next = node;
+
+        // Set the lists prev to the new last element
+        list->end = node;
+
+        // Increment our node count for this list
+        list->count++;
+        return 0;
+}
+
+int node_list_insert(node_list_t* list, unsigned int index, node_t* node) {
+        if (!list || !node) return -1;
+        if (index >= list->count) {
+                return node_list_add(list, node);
+        }
+
+        // Get the first element in the list
+        node_t* cur = list->begin;
+
+        unsigned int pos = 0;
+        node_t* prev = NULL;
+
+        if (index > 0) {
+                while (pos < index) {
+                        prev = cur;
+                        cur = cur->next;
+                        pos++;
+                }
+        }
+
+        if (prev) {
+                // Set previous node
+                node->prev = prev;
+                // Set next node of our new node to next node of the previous node
+                node->next = prev->next;
+                // Set next node of previous node to our new node
+                prev->next = node;
+        } else {
+                node->prev = NULL;
+                // get old first element in list
+                node->next = list->begin;
+                // set new node as first element in list
+                list->begin = node;
+        }
+
+        if (node->next == NULL) {
+                // Set the lists prev to the new last element
+                list->end = node;
+        } else {
+                // set prev of the new next element to our node
+                node->next->prev = node;
+        }
+
+        // Increment our node count for this list
+        list->count++;
+        return 0;
+}
+
+int node_list_remove(node_list_t* list, node_t* node) {
+        if (!list || !node) return -1;
+        if (list->count == 0) return -1;
+
+        node_t* n;
+        for (n = list->begin; n; n = n->next) {
+                if (node == n) {
+                        node_t* newnode = node->next;
+                        if (node->prev) {
+                                node->prev->next = newnode;
+                                if (newnode) {
+                                        newnode->prev = node->prev;
+                                }
+                        } else {
+                                // we just removed the first element
+                                if (newnode) {
+                                        newnode->prev = NULL;
+                                }
+                                list->begin = newnode;
+                        }
+                        list->count--;
+                        return 0;
+                }
+        }       
+        return -1;
+}
+