diff options
Diffstat (limited to 'libcnary')
-rw-r--r-- | libcnary/CMakeLists.txt | 16 | ||||
-rw-r--r-- | libcnary/Makefile | 21 | ||||
-rw-r--r-- | libcnary/README | 5 | ||||
-rw-r--r-- | libcnary/cnary.c | 30 | ||||
-rw-r--r-- | libcnary/include/iterator.h | 33 | ||||
-rw-r--r-- | libcnary/include/list.h | 24 | ||||
-rw-r--r-- | libcnary/include/node.h | 59 | ||||
-rw-r--r-- | libcnary/include/node_iterator.h | 39 | ||||
-rw-r--r-- | libcnary/include/node_list.h | 31 | ||||
-rw-r--r-- | libcnary/include/object.h | 25 | ||||
-rw-r--r-- | libcnary/iterator.c | 45 | ||||
-rw-r--r-- | libcnary/list.c | 31 | ||||
-rw-r--r-- | libcnary/node.c | 207 | ||||
-rw-r--r-- | libcnary/node_iterator.c | 64 | ||||
-rw-r--r-- | libcnary/node_list.c | 130 |
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; +} + |