diff options
Diffstat (limited to 'libcnary')
| -rw-r--r-- | libcnary/CMakeLists.txt | 16 | ||||
| -rw-r--r-- | libcnary/Makefile | 21 | ||||
| -rw-r--r-- | libcnary/Makefile.am | 15 | ||||
| -rw-r--r-- | libcnary/include/iterator.h | 49 | ||||
| -rw-r--r-- | libcnary/include/list.h | 40 | ||||
| -rw-r--r-- | libcnary/include/node.h | 62 | ||||
| -rw-r--r-- | libcnary/include/node_iterator.h | 55 | ||||
| -rw-r--r-- | libcnary/include/node_list.h | 23 | ||||
| -rw-r--r-- | libcnary/iterator.c | 61 | ||||
| -rw-r--r-- | libcnary/list.c | 47 | ||||
| -rw-r--r-- | libcnary/node.c | 235 | ||||
| -rw-r--r-- | libcnary/node_iterator.c | 80 | ||||
| -rw-r--r-- | libcnary/node_list.c | 141 |
13 files changed, 295 insertions, 550 deletions
diff --git a/libcnary/CMakeLists.txt b/libcnary/CMakeLists.txt deleted file mode 100644 index bbbe8ce..0000000 --- a/libcnary/CMakeLists.txt +++ /dev/null @@ -1,16 +0,0 @@ -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 deleted file mode 100644 index bdd165d..0000000 --- a/libcnary/Makefile +++ /dev/null @@ -1,21 +0,0 @@ -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/Makefile.am b/libcnary/Makefile.am new file mode 100644 index 0000000..f5c7bc9 --- /dev/null +++ b/libcnary/Makefile.am @@ -0,0 +1,15 @@ +AM_CFLAGS = \ + $(GLOBAL_CFLAGS) \ + -I$(top_srcdir)/libcnary/include + +AM_LDFLAGS = + +noinst_LTLIBRARIES = libcnary.la +libcnary_la_LIBADD = +libcnary_la_LDFLAGS = $(AM_LDFLAGS) -no-undefined +libcnary_la_SOURCES = \ + node.c \ + node_list.c \ + include/node.h \ + include/node_list.h \ + include/object.h diff --git a/libcnary/include/iterator.h b/libcnary/include/iterator.h deleted file mode 100644 index a33c4ff..0000000 --- a/libcnary/include/iterator.h +++ /dev/null @@ -1,49 +0,0 @@ -/* - * iterator.h - * - * Created on: Mar 8, 2011 - * Author: posixninja - * - * Copyright (c) 2011 Joshua Hill. All Rights Reserved. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#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 deleted file mode 100644 index 6b18e6f..0000000 --- a/libcnary/include/list.h +++ /dev/null @@ -1,40 +0,0 @@ -/* - * list.h - * - * Created on: Mar 8, 2011 - * Author: posixninja - * - * Copyright (c) 2011 Joshua Hill. All Rights Reserved. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#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 index f9afdd6..5b3ae37 100644 --- a/libcnary/include/node.h +++ b/libcnary/include/node.h @@ -24,52 +24,54 @@ #ifndef NODE_H_ #define NODE_H_ +#include "node_list.h" #include "object.h" #define NODE_TYPE 1; -struct node_list_t; +#ifndef NODE_MAX_DEPTH +#define NODE_MAX_DEPTH 512 +#endif + +#define NODE_ERR_SUCCESS 0 +#define NODE_ERR_INVALID_ARG -1 +#define NODE_ERR_NO_MEM -2 +#define NODE_ERR_PARENT -3 +#define NODE_ERR_CIRCULAR_REF -4 +#define NODE_ERR_MAX_DEPTH -5 +#define NODE_ERR_NOT_FOUND -6 // This class implements the abstract iterator class -typedef struct node_t { +typedef struct node* node_t; +struct node { // Super class - struct node_t* next; - struct node_t* prev; + node_t next; + 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; + node_t parent; + node_list_t children; +}; -void node_destroy(struct node_t* node); -struct node_t* node_create(struct node_t* parent, void* data); +void node_destroy(node_t node); +node_t node_create(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); +int node_attach(node_t parent, node_t child); +int node_detach(node_t parent, node_t child); +int node_insert(node_t parent, unsigned int index, 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); +unsigned int node_n_children(node_t node); +node_t node_nth_child(node_t node, unsigned int n); +node_t node_first_child(node_t node); +node_t node_prev_sibling(node_t node); +node_t node_next_sibling(node_t node); +int node_child_position(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); +node_t node_copy_deep(node_t node, copy_func_t copy_func); -void node_debug(struct node_t* node); +void node_debug(node_t node); #endif /* NODE_H_ */ diff --git a/libcnary/include/node_iterator.h b/libcnary/include/node_iterator.h deleted file mode 100644 index d3bce3a..0000000 --- a/libcnary/include/node_iterator.h +++ /dev/null @@ -1,55 +0,0 @@ -/* - * node_iterator.h - * - * Created on: Mar 8, 2011 - * Author: posixninja - * - * Copyright (c) 2011 Joshua Hill. All Rights Reserved. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#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 index 7b9e311..d566b00 100644 --- a/libcnary/include/node_list.h +++ b/libcnary/include/node_list.h @@ -24,24 +24,27 @@ #ifndef NODE_LIST_H_ #define NODE_LIST_H_ -struct node_t; +#include "node.h" + +typedef struct node* node_t; // This class implements the list_t abstract class -typedef struct node_list_t { +struct node_list { // list_t members - struct node_t* begin; - struct node_t* end; + node_t begin; + node_t end; // node_list_t members unsigned int count; -} node_list_t; +}; +typedef struct node_list* node_list_t; -void node_list_destroy(struct node_list_t* list); -struct node_list_t* node_list_create(struct node_t* node); +void node_list_destroy(node_list_t list); +node_list_t node_list_create(); -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); +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/iterator.c b/libcnary/iterator.c deleted file mode 100644 index 492a8ae..0000000 --- a/libcnary/iterator.c +++ /dev/null @@ -1,61 +0,0 @@ -/* - * iterator.c - * - * Created on: Mar 8, 2011 - * Author: posixninja - * - * Copyright (c) 2011 Joshua Hill. All Rights Reserved. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#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 deleted file mode 100644 index 2f05347..0000000 --- a/libcnary/list.c +++ /dev/null @@ -1,47 +0,0 @@ -/* - * list.c - * - * Created on: Mar 8, 2011 - * Author: posixninja - * - * Copyright (c) 2011 Joshua Hill. All Rights Reserved. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#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 index 0a8f414..63b449c 100644 --- a/libcnary/node.c +++ b/libcnary/node.c @@ -26,13 +26,13 @@ #include "node.h" #include "node_list.h" -#include "node_iterator.h" -void node_destroy(node_t* node) { +void node_destroy(node_t node) +{ if(!node) return; if (node->children && node->children->count > 0) { - node_t* ch; + node_t ch; while ((ch = node->children->begin)) { node_list_remove(node->children, ch); node_destroy(ch); @@ -44,32 +44,28 @@ void node_destroy(node_t* node) { free(node); } -node_t* node_create(node_t* parent, void* data) { +node_t node_create(node_t parent, void* data) +{ int error = 0; - node_t* node = (node_t*) malloc(sizeof(node_t)); - if(node == NULL) { + node_t node = (node_t)calloc(1, sizeof(struct node)); + 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); + node->children = NULL; // Pass NULL to create a root node - if(parent != NULL) { + if (parent != NULL) { // This is a child node so attach it to it's parent error = node_attach(parent, node); - if(error < 0) { + if (error < 0) { // Unable to attach nodes - printf("ERROR: %d \"Unable to attach nodes\"\n", error); node_destroy(node); return NULL; } @@ -78,88 +74,180 @@ node_t* node_create(node_t* parent, void* data) { 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; +static int node_depth_from_root(node_t n) +{ + int d = 0; + while (n && n->parent) { + d++; + n = n->parent; + if (d > NODE_MAX_DEPTH) return d; // early out + } + return d; +} + +static int node_subtree_max_depth(node_t root) +{ + if (!root) return 0; + + typedef struct { node_t n; int depth; } frame_t; + size_t cap = 64, sp = 0; + frame_t *st = (frame_t*)malloc(cap * sizeof(*st)); + if (!st) return NODE_MAX_DEPTH + 1; + + st[sp++] = (frame_t){ root, 0 }; + int maxd = 0; + + while (sp) { + frame_t f = st[--sp]; + if (f.depth > maxd) maxd = f.depth; + if (maxd > NODE_MAX_DEPTH) break; + + if (!f.n->children) continue; + + for (node_t ch = node_first_child(f.n); ch; ch = node_next_sibling(ch)) { + if (sp == cap) { + cap *= 2; + frame_t *tmp = (frame_t*)realloc(st, cap * sizeof(*st)); + if (!tmp) { maxd = NODE_MAX_DEPTH + 1; goto out; } + st = tmp; + } + st[sp++] = (frame_t){ ch, f.depth + 1 }; + } + } + +out: + free(st); + return maxd; +} + +static int would_create_cycle(node_t parent, node_t child) +{ + // if parent is anywhere in child's ancestor chain => cycle + for (node_t p = parent; p; p = p->parent) { + if (p == child) return 1; + } + return 0; +} + +int node_attach(node_t parent, node_t child) +{ + if (!parent || !child) return NODE_ERR_INVALID_ARG; + + // already parented? + if (child->parent) return NODE_ERR_PARENT; + + // self/cycle guard + if (parent == child) return NODE_ERR_CIRCULAR_REF; + if (would_create_cycle(parent, child)) return NODE_ERR_CIRCULAR_REF; + + // depth guard: depth(parent)+1+max_depth(child_subtree) <= NODE_MAX_DEPTH + int pd = node_depth_from_root(parent); + int cd = node_subtree_max_depth(child); + if (pd + 1 + cd > NODE_MAX_DEPTH) { + return NODE_ERR_MAX_DEPTH; + } + + if (!parent->children) { + parent->children = node_list_create(); + if (!parent->children) return NODE_ERR_NO_MEM; } int res = node_list_add(parent->children, child); if (res == 0) { + child->parent = parent; parent->count++; } return res; } -int node_detach(node_t* parent, node_t* child) { - if (!parent || !child) return -1; - int index = node_list_remove(parent->children, child); - if (index >= 0) { - parent->count--; +int node_detach(node_t parent, node_t child) +{ + if (!parent || !child) return NODE_ERR_INVALID_ARG; + if (!parent->children) return NODE_ERR_NOT_FOUND; + if (child->parent && child->parent != parent) return NODE_ERR_PARENT; + + int node_index = node_list_remove(parent->children, child); + if (node_index >= 0) { + if (parent->count > 0) parent->count--; + child->parent = NULL; + child->prev = NULL; + child->next = NULL; } - return index; + return node_index; } -int node_insert(node_t* parent, unsigned int index, node_t* child) +int node_insert(node_t parent, unsigned int node_index, 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; + if (!parent || !child) return NODE_ERR_INVALID_ARG; + + // already parented? + if (child->parent) return NODE_ERR_PARENT; + + // self/cycle guard + if (parent == child) return NODE_ERR_CIRCULAR_REF; + if (would_create_cycle(parent, child)) return NODE_ERR_CIRCULAR_REF; + + // depth guard: depth(parent)+1+max_depth(child_subtree) <= NODE_MAX_DEPTH + int pd = node_depth_from_root(parent); + int cd = node_subtree_max_depth(child); + if (pd + 1 + cd > NODE_MAX_DEPTH) { + return NODE_ERR_MAX_DEPTH; } - int res = node_list_insert(parent->children, index, child); + + if (!parent->children) { + parent->children = node_list_create(); + if (!parent->children) return NODE_ERR_NO_MEM; + } + int res = node_list_insert(parent->children, node_index, child); if (res == 0) { + child->parent = parent; 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++) { +static void _node_debug(node_t node, unsigned int depth) +{ + unsigned int i = 0; + node_t current = NULL; + for(i = 0; i < depth; i++) { printf("\t"); } - if(node->isRoot) { + if(!node->parent) { printf("ROOT\n"); } - if(node->isLeaf && !node->isRoot) { + if(!node->children && node->parent) { printf("LEAF\n"); - } else { - if(!node->isRoot) { + if(node->parent) { printf("NODE\n"); } - iter = node_iterator_create(node->children); - for(current = iter->begin; current != NULL; current = iter->next(iter)) { - node_debug(current); + for (current = node_first_child(node); current; current = node_next_sibling(current)) { + _node_debug(current, depth+1); } } } -unsigned int node_n_children(struct node_t* node) +void node_debug(node_t node) +{ + _node_debug(node, 0); +} + +unsigned int node_n_children(node_t node) { if (!node) return 0; return node->count; } -node_t* node_nth_child(struct node_t* node, unsigned int n) +node_t node_nth_child(node_t node, unsigned int n) { if (!node || !node->children || !node->children->begin) return NULL; - int index = 0; + unsigned int node_index = 0; int found = 0; - node_t *ch; + node_t ch; for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { - if (index++ == n) { + if (node_index++ == n) { found = 1; break; } @@ -170,55 +258,64 @@ node_t* node_nth_child(struct node_t* node, unsigned int n) return ch; } -node_t* node_first_child(struct node_t* node) +node_t node_first_child(node_t node) { if (!node || !node->children) return NULL; return node->children->begin; } -node_t* node_prev_sibling(struct node_t* node) +node_t node_prev_sibling(node_t node) { if (!node) return NULL; return node->prev; } -node_t* node_next_sibling(struct node_t* node) +node_t node_next_sibling(node_t node) { if (!node) return NULL; return node->next; } -int node_child_position(struct node_t* parent, node_t* child) +int node_child_position(node_t parent, node_t child) { - if (!parent || !parent->children || !parent->children->begin || !child) return -1; - int index = 0; + if (!parent || !parent->children || !parent->children->begin || !child) return NODE_ERR_INVALID_ARG; + int node_index = 0; int found = 0; - node_t *ch; + node_t ch; for (ch = node_first_child(parent); ch; ch = node_next_sibling(ch)) { if (ch == child) { found = 1; break; } - index++; + node_index++; } if (!found) { - return -1; + return NODE_ERR_NOT_FOUND; } - return index; + return node_index; } -node_t* node_copy_deep(node_t* node, copy_func_t copy_func) +node_t node_copy_deep(node_t node, copy_func_t copy_func) { if (!node) return NULL; void *data = NULL; if (copy_func) { data = copy_func(node->data); } - node_t* copy = node_create(NULL, data); - node_t* ch; + node_t copy = node_create(NULL, data); + if (!copy) return NULL; + 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); + node_t cc = node_copy_deep(ch, copy_func); + if (!cc) { + node_destroy(copy); + return NULL; + } + if (node_attach(copy, cc) < 0) { + node_destroy(cc); + node_destroy(copy); + return NULL; + } } return copy; } diff --git a/libcnary/node_iterator.c b/libcnary/node_iterator.c deleted file mode 100644 index dedf3b4..0000000 --- a/libcnary/node_iterator.c +++ /dev/null @@ -1,80 +0,0 @@ -/* - * node_iterator.c - * - * Created on: Mar 8, 2011 - * Author: posixninja - * - * Copyright (c) 2011 Joshua Hill. All Rights Reserved. - * - * This library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public - * License as published by the Free Software Foundation; either - * version 2.1 of the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public - * License along with this library; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA - */ - -#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 index 5b291e7..218c81d 100644 --- a/libcnary/node_list.c +++ b/libcnary/node_list.c @@ -25,34 +25,34 @@ #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); - } +void node_list_destroy(node_list_t list) +{ + free(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) { +node_list_t node_list_create() +{ + node_list_t list = (node_list_t)calloc(1, sizeof(struct node_list)); + if (list == NULL) { return NULL; } - memset(list, '\0', sizeof(node_list_t)); // Initialize structure - list_init((list_t*) list); + list->begin = NULL; + list->end = NULL; list->count = 0; return list; } -int node_list_add(node_list_t* list, node_t* node) { - if (!list || !node) return -1; +int node_list_add(node_list_t list, node_t node) +{ + if (!list || !node) return NODE_ERR_INVALID_ARG; // Find the last element in the list - node_t* last = list->end; + node_t last = list->end; // Setup our new node as the new last element node->next = NULL; @@ -62,6 +62,9 @@ int node_list_add(node_list_t* list, node_t* node) { if (last) { // but only if the node list is not empty last->next = node; + } else { + // otherwise this is the start of the list + list->begin = node; } // Set the lists prev to the new last element @@ -69,86 +72,80 @@ int node_list_add(node_list_t* list, node_t* node) { // Increment our node count for this list list->count++; - return 0; + return NODE_ERR_SUCCESS; } -int node_list_insert(node_list_t* list, unsigned int index, node_t* node) { - if (!list || !node) return -1; - if (index >= list->count) { +int node_list_insert(node_list_t list, unsigned int node_index, node_t node) +{ + if (!list || !node) return NODE_ERR_INVALID_ARG; + if (node_index > list->count) return NODE_ERR_INVALID_ARG; + if (node_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; + node_t cur = list->begin; + node_t prev = NULL; - if (index > 0) { - while (pos < index) { - prev = cur; - cur = cur->next; - pos++; - } + for (unsigned int pos = 0; pos < node_index; pos++) { + if (!cur) return NODE_ERR_INVALID_ARG; + prev = cur; + cur = cur->next; } + // insert node before cur + node->prev = prev; + node->next = cur; + 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; + if (cur) { + cur->prev = node; } else { - // set prev of the new next element to our node - node->next->prev = node; + // should not happen with bounds above, but keeps things consistent + list->end = node; } // Increment our node count for this list list->count++; - return 0; + return NODE_ERR_SUCCESS; } -int node_list_remove(node_list_t* list, node_t* node) { - if (!list || !node) return -1; - if (list->count == 0) return -1; - - int index = 0; - 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 { - // last element in the list - list->end = node->prev; - } - } else { - // we just removed the first element - if (newnode) { - newnode->prev = NULL; - } - list->begin = newnode; - } - list->count--; - return index; +// Returns removed index (>=0) on success, or NODE_ERR_* (<0) on failure. +int node_list_remove(node_list_t list, node_t node) +{ + if (!list || !node) return NODE_ERR_INVALID_ARG; + if (list->count == 0) return NODE_ERR_NOT_FOUND; + + int node_index = 0; + for (node_t n = list->begin; n; n = n->next, node_index++) { + if (node != n) continue; + + node_t newnode = node->next; + if (node->prev) { + node->prev->next = newnode; + } else { + // we just removed the first element + list->begin = newnode; + } + + if (newnode) { + newnode->prev = node->prev; + } else { + // we removed the last element, set new end + list->end = node->prev; } - index++; - } - return -1; -} + // fully detach node from list + node->prev = NULL; + node->next = NULL; + + list->count--; + return node_index; + } + return NODE_ERR_NOT_FOUND; +} |