/src/libplist/libcnary/node.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * node.c |
3 | | * |
4 | | * Created on: Mar 7, 2011 |
5 | | * Author: posixninja |
6 | | * |
7 | | * Copyright (c) 2011 Joshua Hill. All Rights Reserved. |
8 | | * |
9 | | * This library is free software; you can redistribute it and/or |
10 | | * modify it under the terms of the GNU Lesser General Public |
11 | | * License as published by the Free Software Foundation; either |
12 | | * version 2.1 of the License, or (at your option) any later version. |
13 | | * |
14 | | * This library is distributed in the hope that it will be useful, |
15 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
17 | | * Lesser General Public License for more details. |
18 | | * |
19 | | * You should have received a copy of the GNU Lesser General Public |
20 | | * License along with this library; if not, write to the Free Software |
21 | | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA |
22 | | */ |
23 | | #include <stdio.h> |
24 | | #include <stdlib.h> |
25 | | #include <string.h> |
26 | | |
27 | | #include "node.h" |
28 | | #include "node_list.h" |
29 | | |
30 | | void node_destroy(node_t node) |
31 | 36.7k | { |
32 | 36.7k | if(!node) return; |
33 | | |
34 | 36.7k | if (node->children && node->children->count > 0) { |
35 | 0 | node_t ch; |
36 | 0 | while ((ch = node->children->begin)) { |
37 | 0 | node_list_remove(node->children, ch); |
38 | 0 | node_destroy(ch); |
39 | 0 | } |
40 | 0 | } |
41 | 36.7k | node_list_destroy(node->children); |
42 | 36.7k | node->children = NULL; |
43 | | |
44 | 36.7k | free(node); |
45 | 36.7k | } |
46 | | |
47 | | node_t node_create(node_t parent, void* data) |
48 | 36.7k | { |
49 | 36.7k | int error = 0; |
50 | | |
51 | 36.7k | node_t node = (node_t)calloc(1, sizeof(struct node)); |
52 | 36.7k | if (node == NULL) { |
53 | 0 | return NULL; |
54 | 0 | } |
55 | | |
56 | 36.7k | node->data = data; |
57 | 36.7k | node->next = NULL; |
58 | 36.7k | node->prev = NULL; |
59 | 36.7k | node->count = 0; |
60 | 36.7k | node->parent = NULL; |
61 | 36.7k | node->children = NULL; |
62 | | |
63 | | // Pass NULL to create a root node |
64 | 36.7k | if(parent != NULL) { |
65 | | // This is a child node so attach it to it's parent |
66 | 0 | error = node_attach(parent, node); |
67 | 0 | if(error < 0) { |
68 | | // Unable to attach nodes |
69 | 0 | printf("ERROR: %d \"Unable to attach nodes\"\n", error); |
70 | 0 | node_destroy(node); |
71 | 0 | return NULL; |
72 | 0 | } |
73 | 0 | } |
74 | | |
75 | 36.7k | return node; |
76 | 36.7k | } |
77 | | |
78 | | int node_attach(node_t parent, node_t child) |
79 | 28.1k | { |
80 | 28.1k | if (!parent || !child) return -1; |
81 | 28.1k | child->parent = parent; |
82 | 28.1k | if(!parent->children) { |
83 | 8.03k | parent->children = node_list_create(); |
84 | 8.03k | } |
85 | 28.1k | int res = node_list_add(parent->children, child); |
86 | 28.1k | if (res == 0) { |
87 | 28.1k | parent->count++; |
88 | 28.1k | } |
89 | 28.1k | return res; |
90 | 28.1k | } |
91 | | |
92 | | int node_detach(node_t parent, node_t child) |
93 | 36.7k | { |
94 | 36.7k | if (!parent || !child) return -1; |
95 | 29.6k | int node_index = node_list_remove(parent->children, child); |
96 | 29.6k | if (node_index >= 0) { |
97 | 29.6k | parent->count--; |
98 | 29.6k | } |
99 | 29.6k | return node_index; |
100 | 36.7k | } |
101 | | |
102 | | int node_insert(node_t parent, unsigned int node_index, node_t child) |
103 | 1.50k | { |
104 | 1.50k | if (!parent || !child) return -1; |
105 | 1.50k | child->parent = parent; |
106 | 1.50k | if(!parent->children) { |
107 | 0 | parent->children = node_list_create(); |
108 | 0 | } |
109 | 1.50k | int res = node_list_insert(parent->children, node_index, child); |
110 | 1.50k | if (res == 0) { |
111 | 1.50k | parent->count++; |
112 | 1.50k | } |
113 | 1.50k | return res; |
114 | 1.50k | } |
115 | | |
116 | | static void _node_debug(node_t node, unsigned int depth) |
117 | 0 | { |
118 | 0 | unsigned int i = 0; |
119 | 0 | node_t current = NULL; |
120 | 0 | for(i = 0; i < depth; i++) { |
121 | 0 | printf("\t"); |
122 | 0 | } |
123 | 0 | if(!node->parent) { |
124 | 0 | printf("ROOT\n"); |
125 | 0 | } |
126 | |
|
127 | 0 | if(!node->children && node->parent) { |
128 | 0 | printf("LEAF\n"); |
129 | 0 | } else { |
130 | 0 | if(node->parent) { |
131 | 0 | printf("NODE\n"); |
132 | 0 | } |
133 | 0 | for (current = node_first_child(node); current; current = node_next_sibling(current)) { |
134 | 0 | _node_debug(current, depth+1); |
135 | 0 | } |
136 | 0 | } |
137 | |
|
138 | 0 | } |
139 | | |
140 | | void node_debug(node_t node) |
141 | 0 | { |
142 | 0 | _node_debug(node, 0); |
143 | 0 | } |
144 | | |
145 | | unsigned int node_n_children(node_t node) |
146 | 75 | { |
147 | 75 | if (!node) return 0; |
148 | 75 | return node->count; |
149 | 75 | } |
150 | | |
151 | | node_t node_nth_child(node_t node, unsigned int n) |
152 | 0 | { |
153 | 0 | if (!node || !node->children || !node->children->begin) return NULL; |
154 | 0 | unsigned int node_index = 0; |
155 | 0 | int found = 0; |
156 | 0 | node_t ch; |
157 | 0 | for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { |
158 | 0 | if (node_index++ == n) { |
159 | 0 | found = 1; |
160 | 0 | break; |
161 | 0 | } |
162 | 0 | } |
163 | 0 | if (!found) { |
164 | 0 | return NULL; |
165 | 0 | } |
166 | 0 | return ch; |
167 | 0 | } |
168 | | |
169 | | node_t node_first_child(node_t node) |
170 | 40.5k | { |
171 | 40.5k | if (!node || !node->children) return NULL; |
172 | 11.1k | return node->children->begin; |
173 | 40.5k | } |
174 | | |
175 | | node_t node_prev_sibling(node_t node) |
176 | 1.50k | { |
177 | 1.50k | if (!node) return NULL; |
178 | 1.50k | return node->prev; |
179 | 1.50k | } |
180 | | |
181 | | node_t node_next_sibling(node_t node) |
182 | 136k | { |
183 | 136k | if (!node) return NULL; |
184 | 136k | return node->next; |
185 | 136k | } |
186 | | |
187 | | int node_child_position(node_t parent, node_t child) |
188 | 0 | { |
189 | 0 | if (!parent || !parent->children || !parent->children->begin || !child) return -1; |
190 | 0 | int node_index = 0; |
191 | 0 | int found = 0; |
192 | 0 | node_t ch; |
193 | 0 | for (ch = node_first_child(parent); ch; ch = node_next_sibling(ch)) { |
194 | 0 | if (ch == child) { |
195 | 0 | found = 1; |
196 | 0 | break; |
197 | 0 | } |
198 | 0 | node_index++; |
199 | 0 | } |
200 | 0 | if (!found) { |
201 | 0 | return -1; |
202 | 0 | } |
203 | 0 | return node_index; |
204 | 0 | } |
205 | | |
206 | | node_t node_copy_deep(node_t node, copy_func_t copy_func) |
207 | 0 | { |
208 | 0 | if (!node) return NULL; |
209 | 0 | void *data = NULL; |
210 | 0 | if (copy_func) { |
211 | 0 | data = copy_func(node->data); |
212 | 0 | } |
213 | 0 | node_t copy = node_create(NULL, data); |
214 | 0 | node_t ch; |
215 | 0 | for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) { |
216 | 0 | node_t cc = node_copy_deep(ch, copy_func); |
217 | 0 | node_attach(copy, cc); |
218 | 0 | } |
219 | 0 | return copy; |
220 | 0 | } |