summaryrefslogtreecommitdiffstats
path: root/libcnary
diff options
context:
space:
mode:
Diffstat (limited to 'libcnary')
-rw-r--r--libcnary/Makefile.am17
-rw-r--r--libcnary/include/node.h52
-rw-r--r--libcnary/include/node_list.h23
-rw-r--r--libcnary/node.c181
-rw-r--r--libcnary/node_list.c128
5 files changed, 259 insertions, 142 deletions
diff --git a/libcnary/Makefile.am b/libcnary/Makefile.am
index e2187ec..f5c7bc9 100644
--- a/libcnary/Makefile.am
+++ b/libcnary/Makefile.am
@@ -1,12 +1,15 @@
-AM_CFLAGS = $(GLOBAL_CFLAGS) -I$(top_srcdir)/libcnary/include
+AM_CFLAGS = \
+ $(GLOBAL_CFLAGS) \
+ -I$(top_srcdir)/libcnary/include
+
AM_LDFLAGS =
noinst_LTLIBRARIES = libcnary.la
-libcnary_la_LIBADD =
+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
+ node.c \
+ node_list.c \
+ include/node.h \
+ include/node_list.h \
+ include/object.h
diff --git a/libcnary/include/node.h b/libcnary/include/node.h
index 7e9da50..5b3ae37 100644
--- a/libcnary/include/node.h
+++ b/libcnary/include/node.h
@@ -24,42 +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 Members
void *data;
- struct node_t* parent;
- struct node_list_t* children;
-} 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_list.h b/libcnary/include/node_list.h
index 380916e..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();
+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/node.c b/libcnary/node.c
index c24ca7a..63b449c 100644
--- a/libcnary/node.c
+++ b/libcnary/node.c
@@ -27,11 +27,12 @@
#include "node.h"
#include "node_list.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);
@@ -43,14 +44,14 @@ 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->next = NULL;
@@ -60,12 +61,11 @@ node_t* node_create(node_t* parent, void* data) {
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;
}
@@ -74,45 +74,141 @@ 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->parent = parent;
- if(!parent->children) {
+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 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) {
- parent->count--;
+ if (parent->count > 0) parent->count--;
+ child->parent = NULL;
+ child->prev = NULL;
+ child->next = NULL;
}
return node_index;
}
-int node_insert(node_t* parent, unsigned int node_index, node_t* child)
+int node_insert(node_t parent, unsigned int node_index, node_t child)
{
- if (!parent || !child) return -1;
- child->parent = parent;
- if(!parent->children) {
+ 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_insert(parent->children, node_index, child);
if (res == 0) {
+ child->parent = parent;
parent->count++;
}
return res;
}
-static void _node_debug(node_t* node, unsigned int depth) {
+static void _node_debug(node_t node, unsigned int depth)
+{
unsigned int i = 0;
- node_t* current = NULL;
+ node_t current = NULL;
for(i = 0; i < depth; i++) {
printf("\t");
}
@@ -133,23 +229,23 @@ static void _node_debug(node_t* node, unsigned int depth) {
}
-void node_debug(node_t* node)
+void node_debug(node_t node)
{
_node_debug(node, 0);
}
-unsigned int node_n_children(struct node_t* node)
+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;
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 (node_index++ == n) {
found = 1;
@@ -162,30 +258,30 @@ 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;
+ 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;
@@ -194,23 +290,32 @@ int node_child_position(struct node_t* parent, node_t* child)
node_index++;
}
if (!found) {
- return -1;
+ return NODE_ERR_NOT_FOUND;
}
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_list.c b/libcnary/node_list.c
index b0dca0a..218c81d 100644
--- a/libcnary/node_list.c
+++ b/libcnary/node_list.c
@@ -28,16 +28,17 @@
#include "node.h"
#include "node_list.h"
-void node_list_destroy(node_list_t* list) {
+void node_list_destroy(node_list_t list)
+{
free(list);
}
-node_list_t* node_list_create() {
- 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->begin = NULL;
@@ -46,11 +47,12 @@ node_list_t* node_list_create() {
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;
@@ -70,88 +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 node_index, node_t* node) {
- if (!list || !node) return -1;
- if (node_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;
+ node_t cur = list->begin;
+ node_t prev = NULL;
- unsigned int pos = 0;
- node_t* prev = NULL;
-
- if (node_index > 0) {
- while (pos < node_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;
+// 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;
- 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;
- } else {
- list->end = NULL;
- }
- list->begin = newnode;
- }
- list->count--;
- return node_index;
+ 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;
}
- node_index++;
- }
- return -1;
-}
+ if (newnode) {
+ newnode->prev = node->prev;
+ } else {
+ // we removed the last element, set new end
+ list->end = node->prev;
+ }
+
+ // fully detach node from list
+ node->prev = NULL;
+ node->next = NULL;
+
+ list->count--;
+ return node_index;
+ }
+ return NODE_ERR_NOT_FOUND;
+}
© 2009-2020 sukimashita.com - Generated by cgit - Icons from Tango - Uses Google Analytics