1 /*
2  * Balanced tree node functions
3  *
4  * Copyright (C) 2006-2020, Joachim Metz <joachim.metz@gmail.com>
5  *
6  * Refer to AUTHORS for acknowledgements.
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public License
19  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
20  */
21 
22 #include <common.h>
23 #include <memory.h>
24 #include <types.h>
25 
26 #include "libcdata_array.h"
27 #include "libcdata_btree_node.h"
28 #include "libcdata_btree_values_list.h"
29 #include "libcdata_definitions.h"
30 #include "libcdata_libcerror.h"
31 #include "libcdata_list.h"
32 #include "libcdata_list_element.h"
33 #include "libcdata_tree_node.h"
34 #include "libcdata_types.h"
35 
36 /* Retrieves the sub node for the specific value
37  *
38  * Uses the value_compare_function to determine the similarity of the entries
39  * The value_compare_function should return LIBCDATA_COMPARE_LESS,
40  * LIBCDATA_COMPARE_EQUAL, LIBCDATA_COMPARE_GREATER if successful or -1 on error
41  *
42  * If value_compare_function is NULL the pointer of the value is used to check for a match
43  *
44  * Returns 1 if successful, 0 if the value does not exist or -1 on error
45  * If there was no possible sub match values_list_element is set to NULL
46  * it there is a possible sub match values_list_element is set but 0 is returned
47  * If the node is a leaf node sub_node is not set to NULL
48  */
libcdata_btree_node_get_sub_node_by_value(libcdata_tree_node_t * node,intptr_t * value,int (* value_compare_function)(intptr_t * first_value,intptr_t * second_value,libcerror_error_t ** error),libcdata_tree_node_t ** sub_node,libcdata_list_element_t ** values_list_element,libcerror_error_t ** error)49 int libcdata_btree_node_get_sub_node_by_value(
50      libcdata_tree_node_t *node,
51      intptr_t *value,
52      int (*value_compare_function)(
53             intptr_t *first_value,
54             intptr_t *second_value,
55             libcerror_error_t **error ),
56      libcdata_tree_node_t **sub_node,
57      libcdata_list_element_t **values_list_element,
58      libcerror_error_t **error )
59 {
60 	libcdata_list_t *values_list                      = NULL;
61 	libcdata_list_element_t *safe_values_list_element = NULL;
62 	libcdata_tree_node_t *safe_sub_node               = NULL;
63 	intptr_t *values_list_value                       = NULL;
64 	static char *function                             = "libcdata_btree_node_get_sub_node_by_value";
65 	int number_of_sub_nodes                           = 0;
66 	int number_of_values_list_elements                = 0;
67 	int result                                        = 0;
68 	int sub_node_index                                = 0;
69 	int values_list_element_index                     = 0;
70 
71 	if( node == NULL )
72 	{
73 		libcerror_error_set(
74 		 error,
75 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
76 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
77 		 "%s: invalid node.",
78 		 function );
79 
80 		return( -1 );
81 	}
82 	if( value == NULL )
83 	{
84 		libcerror_error_set(
85 		 error,
86 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
87 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
88 		 "%s: invalid value.",
89 		 function );
90 
91 		return( -1 );
92 	}
93 	if( sub_node == NULL )
94 	{
95 		libcerror_error_set(
96 		 error,
97 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
98 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
99 		 "%s: invalid sub node.",
100 		 function );
101 
102 		return( -1 );
103 	}
104 	if( values_list_element == NULL )
105 	{
106 		libcerror_error_set(
107 		 error,
108 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
109 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
110 		 "%s: invalid values list element.",
111 		 function );
112 
113 		return( -1 );
114 	}
115 	*sub_node            = NULL;
116 	*values_list_element = NULL;
117 
118 	if( libcdata_tree_node_get_value(
119 	     node,
120 	     (intptr_t **) &values_list,
121 	     error ) != 1 )
122 	{
123 		libcerror_error_set(
124 		 error,
125 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
126 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
127 		 "%s: unable to retrieve values list.",
128 		 function );
129 
130 		return( -1 );
131 	}
132 	if( values_list != NULL )
133 	{
134 		if( libcdata_list_get_number_of_elements(
135 		     values_list,
136 		     &number_of_values_list_elements,
137 		     error ) != 1 )
138 		{
139 			libcerror_error_set(
140 			 error,
141 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
142 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
143 			 "%s: unable to retrieve number of values list elements.",
144 			 function );
145 
146 			return( -1 );
147 		}
148 	}
149 	if( libcdata_tree_node_get_number_of_sub_nodes(
150 	     node,
151 	     &number_of_sub_nodes,
152 	     error ) != 1 )
153 	{
154 		libcerror_error_set(
155 		 error,
156 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
157 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
158 		 "%s: unable to retrieve number of sub nodes.",
159 		 function );
160 
161 		return( -1 );
162 	}
163 	if( ( number_of_sub_nodes != 0 )
164 	 && ( ( number_of_values_list_elements + 1 ) != number_of_sub_nodes ) )
165 	{
166 		libcerror_error_set(
167 		 error,
168 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
169 		 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
170 		 "%s: invalid number of values list elements value out of bounds.",
171 		 function );
172 
173 		return( -1 );
174 	}
175 	if( number_of_values_list_elements == 0 )
176 	{
177 		return( 0 );
178 	}
179 	if( libcdata_list_get_first_element(
180 	     values_list,
181 	     &safe_values_list_element,
182 	     error ) != 1 )
183 	{
184 		libcerror_error_set(
185 		 error,
186 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
187 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
188 		 "%s: unable to retrieve first values list element.",
189 		 function );
190 
191 		return( -1 );
192 	}
193 	if( number_of_sub_nodes != 0 )
194 	{
195 		if( libcdata_tree_node_get_sub_node_by_index(
196 		     node,
197 		     0,
198 		     &safe_sub_node,
199 		     error ) != 1 )
200 		{
201 			libcerror_error_set(
202 			 error,
203 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
204 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
205 			 "%s: unable to retrieve sub node: 0.",
206 			 function );
207 
208 			return( -1 );
209 		}
210 	}
211 	for( values_list_element_index = 0;
212 	     values_list_element_index < number_of_values_list_elements;
213 	     values_list_element_index++ )
214 	{
215 		if( libcdata_list_element_get_value(
216 		     safe_values_list_element,
217 		     &values_list_value,
218 		     error ) != 1 )
219 		{
220 			libcerror_error_set(
221 			 error,
222 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
223 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
224 			 "%s: unable to retrieve value from values list element: %d.",
225 			 function,
226 			 values_list_element_index );
227 
228 			return( -1 );
229 		}
230 		if( values_list_value == NULL )
231 		{
232 			libcerror_error_set(
233 			 error,
234 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
235 			 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
236 			 "%s: invalid values list element: %d - missing value.",
237 			 function,
238 			 values_list_element_index );
239 
240 			return( -1 );
241 		}
242 		if( value_compare_function != NULL )
243 		{
244 			result = value_compare_function(
245 			          value,
246 			          values_list_value,
247 			          error );
248 		}
249 		else if( value == values_list_value )
250 		{
251 			result = LIBCDATA_COMPARE_EQUAL;
252 		}
253 		else
254 		{
255 			result = LIBCDATA_COMPARE_GREATER;
256 		}
257 		if( result == -1 )
258 		{
259 			libcerror_error_set(
260 			 error,
261 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
262 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
263 			 "%s: unable to compare value with values list value: %d.",
264 			 function,
265 			 values_list_element_index );
266 
267 			return( -1 );
268 		}
269 		else if( result == LIBCDATA_COMPARE_EQUAL )
270 		{
271 			*sub_node            = safe_sub_node;
272 			*values_list_element = safe_values_list_element;
273 
274 			return( 1 );
275 		}
276 		else if( result == LIBCDATA_COMPARE_LESS )
277 		{
278 			break;
279 		}
280 		else if( result != LIBCDATA_COMPARE_GREATER )
281 		{
282 			libcerror_error_set(
283 			 error,
284 			 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
285 			 LIBCERROR_ARGUMENT_ERROR_UNSUPPORTED_VALUE,
286 			 "%s: unsupported value compare function return value: %d.",
287 			 function,
288 			 result );
289 
290 			return( -1 );
291 		}
292 		if( libcdata_list_element_get_next_element(
293 		     safe_values_list_element,
294 		     &safe_values_list_element,
295 		     error ) != 1 )
296 		{
297 			libcerror_error_set(
298 			 error,
299 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
300 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
301 			 "%s: unable to retrieve next element from values list element: %d.",
302 			 function,
303 			 values_list_element_index );
304 
305 			return( -1 );
306 		}
307 		if( number_of_sub_nodes != 0 )
308 		{
309 			if( libcdata_tree_node_get_next_node(
310 			     safe_sub_node,
311 			     &safe_sub_node,
312 			     error ) != 1 )
313 			{
314 				libcerror_error_set(
315 				 error,
316 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
317 				 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
318 				 "%s: unable to retrieve next node from sub node: %d.",
319 				 function,
320 				 sub_node_index );
321 
322 				return( -1 );
323 			}
324 			sub_node_index++;
325 		}
326 	}
327 	*sub_node            = safe_sub_node;
328 	*values_list_element = safe_values_list_element;
329 
330 	return( 0 );
331 }
332 
333 /* Retrieves the upper node for the specific value
334  *
335  * Uses the value_compare_function to determine the similarity of the entries
336  * The value_compare_function should return LIBCDATA_COMPARE_LESS,
337  * LIBCDATA_COMPARE_EQUAL, LIBCDATA_COMPARE_GREATER if successful or -1 on error
338  *
339  * Returns 1 if successful, 0 if the value does not exist or -1 on error
340  */
libcdata_btree_node_get_upper_node_by_value(libcdata_tree_node_t * node,intptr_t * value,int (* value_compare_function)(intptr_t * first_value,intptr_t * second_value,libcerror_error_t ** error),libcdata_tree_node_t ** upper_node,libcdata_list_element_t ** values_list_element,libcerror_error_t ** error)341 int libcdata_btree_node_get_upper_node_by_value(
342      libcdata_tree_node_t *node,
343      intptr_t *value,
344      int (*value_compare_function)(
345             intptr_t *first_value,
346             intptr_t *second_value,
347             libcerror_error_t **error ),
348      libcdata_tree_node_t **upper_node,
349      libcdata_list_element_t **values_list_element,
350      libcerror_error_t **error )
351 {
352 	libcdata_list_element_t *sub_values_list_element = NULL;
353 	libcdata_tree_node_t *sub_node                   = NULL;
354 	static char *function                            = "libcdata_btree_node_get_upper_node_by_value";
355 	int result                                       = 0;
356 
357 	if( node == NULL )
358 	{
359 		libcerror_error_set(
360 		 error,
361 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
362 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
363 		 "%s: invalid node.",
364 		 function );
365 
366 		return( -1 );
367 	}
368 	if( value == NULL )
369 	{
370 		libcerror_error_set(
371 		 error,
372 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
373 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
374 		 "%s: invalid value.",
375 		 function );
376 
377 		return( -1 );
378 	}
379 	if( value_compare_function == NULL )
380 	{
381 		libcerror_error_set(
382 		 error,
383 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
384 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
385 		 "%s: invalid value compare function.",
386 		 function );
387 
388 		return( -1 );
389 	}
390 	if( upper_node == NULL )
391 	{
392 		libcerror_error_set(
393 		 error,
394 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
395 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
396 		 "%s: invalid upper node.",
397 		 function );
398 
399 		return( -1 );
400 	}
401 	if( values_list_element == NULL )
402 	{
403 		libcerror_error_set(
404 		 error,
405 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
406 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
407 		 "%s: invalid values list element.",
408 		 function );
409 
410 		return( -1 );
411 	}
412 	*upper_node          = NULL;
413 	*values_list_element = NULL;
414 
415 	result = libcdata_btree_node_get_sub_node_by_value(
416 	          node,
417 	          value,
418 	          value_compare_function,
419 	          &sub_node,
420 	          &sub_values_list_element,
421 	          error );
422 
423 	if( result == -1 )
424 	{
425 		libcerror_error_set(
426 		 error,
427 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
428 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
429 		 "%s: unable to retrieve sub node by value.",
430 		 function );
431 
432 		return( -1 );
433 	}
434 	else if( sub_node != NULL )
435 	{
436 		result = libcdata_btree_node_get_upper_node_by_value(
437 		          sub_node,
438 		          value,
439 		          value_compare_function,
440 		          upper_node,
441 		          values_list_element,
442 		          error );
443 
444 		if( result == -1 )
445 		{
446 			libcerror_error_set(
447 			 error,
448 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
449 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
450 			 "%s: unable to retrieve upper node in sub node.",
451 			 function );
452 
453 			return( -1 );
454 		}
455 	}
456 	else if( result != 0 )
457 	{
458 		*values_list_element = sub_values_list_element;
459 	}
460 	if( *upper_node == NULL )
461 	{
462 		*upper_node = node;
463 	}
464 	return( result );
465 }
466 
467 /* Appends a value into a tree node
468  * Returns 1 if successful or -1 on error
469  */
libcdata_btree_node_append_value(libcdata_tree_node_t * node,intptr_t * value,libcerror_error_t ** error)470 int libcdata_btree_node_append_value(
471      libcdata_tree_node_t *node,
472      intptr_t *value,
473      libcerror_error_t **error )
474 {
475 	libcdata_list_t *values_list = NULL;
476 	static char *function        = "libcdata_btree_node_append_value";
477 
478 	if( libcdata_tree_node_get_value(
479 	     node,
480 	     (intptr_t **) &values_list,
481 	     error ) != 1 )
482 	{
483 		libcerror_error_set(
484 		 error,
485 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
486 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
487 		 "%s: unable to retrieve values list.",
488 		 function );
489 
490 		return( -1 );
491 	}
492 	if( values_list == NULL )
493 	{
494 		if( libcdata_list_initialize(
495 		     &values_list,
496 		     error ) != 1 )
497 		{
498 			libcerror_error_set(
499 			 error,
500 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
501 			 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
502 			 "%s: unable to create values list.",
503 			 function );
504 
505 			return( -1 );
506 		}
507 		if( libcdata_tree_node_set_value(
508 		     node,
509 		     (intptr_t *) values_list,
510 		     error ) != 1 )
511 		{
512 			libcerror_error_set(
513 			 error,
514 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
515 			 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
516 			 "%s: unable to set values list.",
517 			 function );
518 
519 			libcdata_list_free(
520 			 &values_list,
521 			 NULL,
522 			 NULL );
523 
524 			return( -1 );
525 		}
526 	}
527 	if( libcdata_list_append_value(
528 	     values_list,
529 	     value,
530 	     error ) != 1 )
531 	{
532 		libcerror_error_set(
533 		 error,
534 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
535 		 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
536 		 "%s: unable to append value to values list.",
537 		 function );
538 
539 		return( -1 );
540 	}
541 	return( 1 );
542 }
543 
544 /* Inserts a value into a tree node
545  * The tree node must be the most upper node (leaf)
546  *
547  * Uses the value_compare_function to determine the order of the entries
548  * The value_compare_function should return LIBCDATA_COMPARE_LESS,
549  * LIBCDATA_COMPARE_EQUAL, LIBCDATA_COMPARE_GREATER if successful or -1 on error
550  *
551  * Returns 1 if successful, 0 if the value already exists or -1 on error
552  */
libcdata_btree_node_insert_value(libcdata_tree_node_t * node,intptr_t * value,int (* value_compare_function)(intptr_t * first_value,intptr_t * second_value,libcerror_error_t ** error),libcerror_error_t ** error)553 int libcdata_btree_node_insert_value(
554      libcdata_tree_node_t *node,
555      intptr_t *value,
556      int (*value_compare_function)(
557             intptr_t *first_value,
558             intptr_t *second_value,
559             libcerror_error_t **error ),
560      libcerror_error_t **error )
561 {
562 	libcdata_list_t *values_list = NULL;
563 	static char *function        = "libcdata_btree_node_insert_value";
564 	int number_of_sub_nodes      = 0;
565 	int result                   = 0;
566 
567 	if( libcdata_tree_node_get_number_of_sub_nodes(
568 	     node,
569 	     &number_of_sub_nodes,
570 	     error ) != 1 )
571 	{
572 		libcerror_error_set(
573 		 error,
574 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
575 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
576 		 "%s: unable to retrieve number of sub nodes.",
577 		 function );
578 
579 		return( -1 );
580 	}
581 	if( number_of_sub_nodes != 0 )
582 	{
583 		libcerror_error_set(
584 		 error,
585 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
586 		 LIBCERROR_ARGUMENT_ERROR_UNSUPPORTED_VALUE,
587 		 "%s: cannot insert value in node with sub nodes.",
588 		 function );
589 
590 		return( -1 );
591 	}
592 	if( libcdata_tree_node_get_value(
593 	     node,
594 	     (intptr_t **) &values_list,
595 	     error ) != 1 )
596 	{
597 		libcerror_error_set(
598 		 error,
599 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
600 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
601 		 "%s: unable to retrieve values list.",
602 		 function );
603 
604 		return( -1 );
605 	}
606 	if( values_list == NULL )
607 	{
608 		if( libcdata_list_initialize(
609 		     &values_list,
610 		     error ) != 1 )
611 		{
612 			libcerror_error_set(
613 			 error,
614 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
615 			 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
616 			 "%s: unable to create values list.",
617 			 function );
618 
619 			return( -1 );
620 		}
621 		if( libcdata_tree_node_set_value(
622 		     node,
623 		     (intptr_t *) values_list,
624 		     error ) != 1 )
625 		{
626 			libcerror_error_set(
627 			 error,
628 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
629 			 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
630 			 "%s: unable to set values list.",
631 			 function );
632 
633 			libcdata_list_free(
634 			 &values_list,
635 			 NULL,
636 			 NULL );
637 
638 			return( -1 );
639 		}
640 	}
641 	result = libcdata_list_insert_value(
642 	          values_list,
643 	          value,
644 	          value_compare_function,
645 	          LIBCDATA_INSERT_FLAG_UNIQUE_ENTRIES,
646 	          error );
647 
648 	if( result == -1 )
649 	{
650 		libcerror_error_set(
651 		 error,
652 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
653 		 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
654 		 "%s: unable to insert value in values list.",
655 		 function );
656 
657 		return( -1 );
658 	}
659 	return( result );
660 }
661 
662 /* Replaces a value in the tree node
663  * The tree node must be the most upper node (leaf) in the first call
664  * Returns 1 if successful or -1 on error
665  */
libcdata_btree_node_replace_value(libcdata_tree_node_t * node,intptr_t * value,intptr_t * replacement_value,libcerror_error_t ** error)666 int libcdata_btree_node_replace_value(
667      libcdata_tree_node_t *node,
668      intptr_t *value,
669      intptr_t *replacement_value,
670      libcerror_error_t **error )
671 {
672 	libcdata_list_element_t *values_list_element = NULL;
673 	libcdata_tree_node_t *parent_node            = NULL;
674 	libcdata_tree_node_t *sub_node               = NULL;
675 	static char *function                        = "libcdata_btree_node_replace_value";
676 	int result                                   = 0;
677 
678 	if( value == NULL )
679 	{
680 		libcerror_error_set(
681 		 error,
682 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
683 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
684 		 "%s: invalid value.",
685 		 function );
686 
687 		return( -1 );
688 	}
689 	if( replacement_value == NULL )
690 	{
691 		libcerror_error_set(
692 		 error,
693 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
694 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
695 		 "%s: invalid replacement value.",
696 		 function );
697 
698 		return( -1 );
699 	}
700 	result = libcdata_btree_node_get_sub_node_by_value(
701 	          node,
702 	          value,
703 	          NULL,
704 	          &sub_node,
705 	          &values_list_element,
706 	          error );
707 
708 	if( result == -1 )
709 	{
710 		libcerror_error_set(
711 		 error,
712 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
713 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
714 		 "%s: unable to retrieve sub node by value.",
715 		 function );
716 
717 		return( -1 );
718 	}
719 	else if( result != 0 )
720 	{
721 		if( libcdata_list_element_set_value(
722 		     values_list_element,
723 		     replacement_value,
724 		     error ) != 1 )
725 		{
726 			libcerror_error_set(
727 			 error,
728 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
729 			 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
730 			 "%s: unable to set value in values list element.",
731 			 function );
732 
733 			return( -1 );
734 		}
735 	}
736 	if( libcdata_tree_node_get_parent_node(
737 	     node,
738 	     &parent_node,
739 	     error ) != 1 )
740 	{
741 		libcerror_error_set(
742 		 error,
743 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
744 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
745 		 "%s: unable to retrieve parent node.",
746 		 function );
747 
748 		return( -1 );
749 	}
750 	if( parent_node != NULL )
751 	{
752 		if( libcdata_btree_node_replace_value(
753 		     parent_node,
754 		     value,
755 		     replacement_value,
756 		     error ) != 1 )
757 		{
758 			libcerror_error_set(
759 			 error,
760 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
761 			 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
762 			 "%s: unable to replace value in parent node.",
763 			 function );
764 
765 			return( -1 );
766 		}
767 	}
768 	return( 1 );
769 }
770 
771 /* Flattens a tree node and its sub node
772  * Returns 1 if successful or -1 on error
773  */
libcdata_btree_node_flatten_node(libcdata_tree_node_t ** node,libcerror_error_t ** error)774 int libcdata_btree_node_flatten_node(
775      libcdata_tree_node_t **node,
776      libcerror_error_t **error )
777 {
778 	libcdata_tree_node_t *sub_node = NULL;
779 	static char *function          = "libcdata_btree_node_flatten_node";
780 
781 	if( node == NULL )
782 	{
783 		libcerror_error_set(
784 		 error,
785 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
786 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
787 		 "%s: invalid node.",
788 		 function );
789 
790 		return( -1 );
791 	}
792 	if( libcdata_tree_node_get_first_sub_node(
793 	     *node,
794 	     &sub_node,
795 	     error ) != 1 )
796 	{
797 		libcerror_error_set(
798 		 error,
799 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
800 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
801 		 "%s: unable to retrieve first sub node.",
802 		 function );
803 
804 		return( -1 );
805 	}
806 	if( libcdata_tree_node_remove_node(
807 	     *node,
808 	     sub_node,
809 	     error ) != 1 )
810 	{
811 		libcerror_error_set(
812 		 error,
813 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
814 		 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
815 		 "%s: unable to remove sub node from node.",
816 		 function );
817 
818 		return( -1 );
819 	}
820 	if( libcdata_tree_node_replace_node(
821 	     *node,
822 	     sub_node,
823 	     error ) != 1 )
824 	{
825 		libcerror_error_set(
826 		 error,
827 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
828 		 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
829 		 "%s: unable to replace node with sub node.",
830 		 function );
831 
832 		libcdata_tree_node_append_node(
833 		 *node,
834 		 sub_node,
835 		 NULL );
836 
837 		return( -1 );
838 	}
839 	if( libcdata_tree_node_free(
840 	     node,
841 	     (int (*)(intptr_t **, libcerror_error_t **)) &libcdata_btree_values_list_free,
842 	     error ) != 1 )
843 	{
844 		libcerror_error_set(
845 		 error,
846 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
847 		 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
848 		 "%s: unable to free node.",
849 		 function );
850 
851 		return( -1 );
852 	}
853 	*node = sub_node;
854 
855 	return( 1 );
856 }
857 
858 /* Removes a sub node from the B-tree node
859  * Returns 1 if successful or -1 on error
860  */
libcdata_btree_node_remove_sub_node(libcdata_tree_node_t * node,libcdata_tree_node_t ** sub_node,libcerror_error_t ** error)861 int libcdata_btree_node_remove_sub_node(
862      libcdata_tree_node_t *node,
863      libcdata_tree_node_t **sub_node,
864      libcerror_error_t **error )
865 {
866 	static char *function = "libcdata_btree_node_remove_sub_node";
867 
868 	if( node == NULL )
869 	{
870 		libcerror_error_set(
871 		 error,
872 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
873 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
874 		 "%s: invalid node.",
875 		 function );
876 
877 		return( -1 );
878 	}
879 	if( sub_node == NULL )
880 	{
881 		libcerror_error_set(
882 		 error,
883 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
884 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
885 		 "%s: invalid sub node.",
886 		 function );
887 
888 		return( -1 );
889 	}
890 	if( libcdata_tree_node_remove_node(
891 	     node,
892 	     *sub_node,
893 	     error ) != 1 )
894 	{
895 		libcerror_error_set(
896 		 error,
897 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
898 		 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
899 		 "%s: unable to remove sub node from node.",
900 		 function );
901 
902 		return( -1 );
903 	}
904 	if( libcdata_tree_node_free(
905 	     sub_node,
906 	     (int (*)(intptr_t **, libcerror_error_t **)) &libcdata_btree_values_list_free,
907 	     error ) != 1 )
908 	{
909 		libcerror_error_set(
910 		 error,
911 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
912 		 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
913 		 "%s: unable to free sub node.",
914 		 function );
915 
916 		return( -1 );
917 	}
918 	return( 1 );
919 }
920 
921 /* Removes a value from the tree node
922  * The tree node must be the most upper node (leaf) in the first call
923  * Returns 1 if successful, 0 if no such value or -1 on error
924  */
libcdata_btree_node_remove_value(libcdata_tree_node_t * node,intptr_t * value,intptr_t * replacement_value,libcerror_error_t ** error)925 int libcdata_btree_node_remove_value(
926      libcdata_tree_node_t *node,
927      intptr_t *value,
928      intptr_t *replacement_value,
929      libcerror_error_t **error )
930 {
931 	libcdata_list_t *sub_node_values_list        = NULL;
932 	libcdata_list_t *values_list                 = NULL;
933 	libcdata_list_element_t *values_list_element = NULL;
934 	libcdata_tree_node_t *parent_node            = NULL;
935 	libcdata_tree_node_t *sub_node               = NULL;
936 	static char *function                        = "libcdata_btree_node_remove_value";
937 	int number_of_sub_nodes                      = 0;
938 	int number_of_values_list_elements           = 0;
939 	int result                                   = 0;
940 	int sub_node_number_of_sub_nodes             = 0;
941 	int sub_node_number_of_values_list_elements  = 0;
942 
943 	if( value == NULL )
944 	{
945 		libcerror_error_set(
946 		 error,
947 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
948 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
949 		 "%s: invalid value.",
950 		 function );
951 
952 		return( -1 );
953 	}
954 	result = libcdata_btree_node_get_sub_node_by_value(
955 	          node,
956 	          value,
957 	          NULL,
958 	          &sub_node,
959 	          &values_list_element,
960 	          error );
961 
962 	if( result == -1 )
963 	{
964 		libcerror_error_set(
965 		 error,
966 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
967 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
968 		 "%s: unable to retrieve sub node by value.",
969 		 function );
970 
971 		return( -1 );
972 	}
973 	if( libcdata_tree_node_get_value(
974 	     node,
975 	     (intptr_t **) &values_list,
976 	     error ) != 1 )
977 	{
978 		libcerror_error_set(
979 		 error,
980 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
981 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
982 		 "%s: unable to retrieve values list.",
983 		 function );
984 
985 		return( -1 );
986 	}
987 	if( libcdata_list_get_number_of_elements(
988 	     values_list,
989 	     &number_of_values_list_elements,
990 	     error ) != 1 )
991 	{
992 		libcerror_error_set(
993 		 error,
994 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
995 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
996 		 "%s: unable to retrieve number of values list elements.",
997 		 function );
998 
999 		return( -1 );
1000 	}
1001 	if( libcdata_tree_node_get_number_of_sub_nodes(
1002 	     node,
1003 	     &number_of_sub_nodes,
1004 	     error ) != 1 )
1005 	{
1006 		libcerror_error_set(
1007 		 error,
1008 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1009 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1010 		 "%s: unable to retrieve number of sub nodes.",
1011 		 function );
1012 
1013 		return( -1 );
1014 	}
1015 	if( sub_node != NULL )
1016 	{
1017 		if( libcdata_tree_node_get_value(
1018 		     sub_node,
1019 		     (intptr_t **) &sub_node_values_list,
1020 		     error ) != 1 )
1021 		{
1022 			libcerror_error_set(
1023 			 error,
1024 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1025 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1026 			 "%s: unable to retrieve sub node values list.",
1027 			 function );
1028 
1029 			return( -1 );
1030 		}
1031 		if( libcdata_list_get_number_of_elements(
1032 		     sub_node_values_list,
1033 		     &sub_node_number_of_values_list_elements,
1034 		     error ) != 1 )
1035 		{
1036 			libcerror_error_set(
1037 			 error,
1038 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1039 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1040 			 "%s: unable to retrieve sub node number of values list elements.",
1041 			 function );
1042 
1043 			return( -1 );
1044 		}
1045 		if( libcdata_tree_node_get_number_of_sub_nodes(
1046 		     sub_node,
1047 		     &sub_node_number_of_sub_nodes,
1048 		     error ) != 1 )
1049 		{
1050 			libcerror_error_set(
1051 			 error,
1052 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1053 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1054 			 "%s: unable to retrieve number of sub nodes.",
1055 			 function );
1056 
1057 			return( -1 );
1058 		}
1059 		/* If the sub node is empty remove it
1060 		 */
1061 		if( ( sub_node_number_of_sub_nodes == 0 )
1062 		 && ( sub_node_number_of_values_list_elements == 0 ) )
1063 		{
1064 			if( libcdata_btree_node_remove_sub_node(
1065 			     node,
1066 			     &sub_node,
1067 			     error ) != 1 )
1068 			{
1069 				libcerror_error_set(
1070 				 error,
1071 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1072 				 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
1073 				 "%s: unable to remove remaining sub node from node.",
1074 				 function );
1075 
1076 				return( -1 );
1077 			}
1078 			if( libcdata_tree_node_get_number_of_sub_nodes(
1079 			     node,
1080 			     &number_of_sub_nodes,
1081 			     error ) != 1 )
1082 			{
1083 				libcerror_error_set(
1084 				 error,
1085 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1086 				 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1087 				 "%s: unable to retrieve number of sub nodes.",
1088 				 function );
1089 
1090 				return( -1 );
1091 			}
1092 			if( values_list_element == NULL )
1093 			{
1094 				if( libcdata_list_get_last_element(
1095 				     values_list,
1096 				     &values_list_element,
1097 				     error ) != 1 )
1098 				{
1099 					libcerror_error_set(
1100 					 error,
1101 					 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1102 					 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1103 					 "%s: unable to retrieve last values list element.",
1104 					 function );
1105 
1106 					return( -1 );
1107 				}
1108 				if( libcdata_list_element_get_value(
1109 				     values_list_element,
1110 				     &replacement_value,
1111 				     error ) != 1 )
1112 				{
1113 					libcerror_error_set(
1114 					 error,
1115 					 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1116 					 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1117 					 "%s: unable to retrieve value from last values list element.",
1118 					 function );
1119 
1120 					return( -1 );
1121 				}
1122 			}
1123 			if( values_list_element != NULL )
1124 			{
1125 				if( libcdata_btree_values_list_remove_element(
1126 				     values_list,
1127 				     &values_list_element,
1128 				     error ) != 1 )
1129 				{
1130 					libcerror_error_set(
1131 					 error,
1132 					 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1133 					 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
1134 					 "%s: unable to remove element from values list.",
1135 					 function );
1136 
1137 					return( -1 );
1138 				}
1139 				if( libcdata_list_get_number_of_elements(
1140 				     values_list,
1141 				     &number_of_values_list_elements,
1142 				     error ) != 1 )
1143 				{
1144 					libcerror_error_set(
1145 					 error,
1146 					 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1147 					 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1148 					 "%s: unable to retrieve number of values list elements.",
1149 					 function );
1150 
1151 					return( -1 );
1152 				}
1153 			}
1154 		}
1155 	}
1156 	if( number_of_sub_nodes != 0 )
1157 	{
1158 		if( ( number_of_values_list_elements + 1 ) != number_of_sub_nodes )
1159 		{
1160 			libcerror_error_set(
1161 			 error,
1162 			 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1163 			 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
1164 			 "%s: invalid number of values list elements value out of bounds.",
1165 			 function );
1166 
1167 			return( -1 );
1168 		}
1169 		/* If one sub node remains flatten the node
1170 		 */
1171 		if( number_of_sub_nodes == 1 )
1172 		{
1173 			if( libcdata_btree_node_flatten_node(
1174 			     &node,
1175 			     error ) != 1 )
1176 			{
1177 				libcerror_error_set(
1178 				 error,
1179 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1180 				 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1181 				 "%s: unable to flatten node.",
1182 				 function );
1183 
1184 				return( -1 );
1185 			}
1186 			if( libcdata_tree_node_get_value(
1187 			     node,
1188 			     (intptr_t **) &values_list,
1189 			     error ) != 1 )
1190 			{
1191 				libcerror_error_set(
1192 				 error,
1193 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1194 				 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1195 				 "%s: unable to retrieve values list.",
1196 				 function );
1197 
1198 				return( -1 );
1199 			}
1200 		}
1201 		/* If the sub node contains more than one values list elements
1202 		 * use the replacement value determined in the sub node
1203 		 */
1204 		else if( values_list_element != NULL )
1205 		{
1206 			if( replacement_value == NULL )
1207 			{
1208 				libcerror_error_set(
1209 				 error,
1210 				 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1211 				 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1212 				 "%s: invalid replacement value.",
1213 				 function );
1214 
1215 				return( -1 );
1216 			}
1217 			if( libcdata_list_element_set_value(
1218 			     values_list_element,
1219 			     replacement_value,
1220 			     error ) != 1 )
1221 			{
1222 				libcerror_error_set(
1223 				 error,
1224 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1225 				 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
1226 				 "%s: unable to set value in values list element.",
1227 				 function );
1228 
1229 				return( -1 );
1230 			}
1231 		}
1232 	}
1233 	/* In a leaf node remove the values list element from the list
1234 	 */
1235 	else if( values_list_element != NULL )
1236 	{
1237 		if( libcdata_btree_values_list_replace_element_with_previous(
1238 		     values_list,
1239 		     &values_list_element,
1240 		     &replacement_value,
1241 		     error ) != 1 )
1242 		{
1243 			libcerror_error_set(
1244 			 error,
1245 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1246 			 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
1247 			 "%s: unable to replace values list element with previous.",
1248 			 function );
1249 
1250 			return( -1 );
1251 		}
1252 	}
1253 	if( libcdata_tree_node_get_parent_node(
1254 	     node,
1255 	     &parent_node,
1256 	     error ) != 1 )
1257 	{
1258 		libcerror_error_set(
1259 		 error,
1260 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1261 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1262 		 "%s: unable to retrieve parent node.",
1263 		 function );
1264 
1265 		return( -1 );
1266 	}
1267 	if( parent_node != NULL )
1268 	{
1269 		if( libcdata_btree_node_remove_value(
1270 		     parent_node,
1271 		     value,
1272 		     replacement_value,
1273 		     error ) == -1 )
1274 		{
1275 			libcerror_error_set(
1276 			 error,
1277 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1278 			 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
1279 			 "%s: unable to remove value from parent node.",
1280 			 function );
1281 
1282 			return( -1 );
1283 		}
1284 	}
1285 	return( result );
1286 }
1287 
1288 /* Splits the node
1289  * Returns 1 if successful or -1 on error
1290  */
libcdata_btree_node_split(libcdata_tree_node_t * node,libcerror_error_t ** error)1291 int libcdata_btree_node_split(
1292      libcdata_tree_node_t *node,
1293      libcerror_error_t **error )
1294 {
1295 	libcdata_list_t *split_values_list           = NULL;
1296 	libcdata_list_t *values_list                 = NULL;
1297 	libcdata_list_element_t *values_list_element = NULL;
1298 	libcdata_tree_node_t *sub_node               = NULL;
1299 	intptr_t *values_list_value                  = NULL;
1300 	static char *function                        = "libcdata_btree_node_split";
1301 	int number_of_split_values_list_elements     = 0;
1302 	int number_of_sub_nodes                      = 0;
1303 	int number_of_values_list_elements           = 0;
1304 	int split_values_list_element_index          = 0;
1305 	int sub_node_index                           = 0;
1306 	int values_list_element_index                = 0;
1307 
1308 	if( node == NULL )
1309 	{
1310 		libcerror_error_set(
1311 		 error,
1312 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1313 		 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1314 		 "%s: invalid node.",
1315 		 function );
1316 
1317 		return( -1 );
1318 	}
1319 	if( libcdata_tree_node_get_number_of_sub_nodes(
1320 	     node,
1321 	     &number_of_sub_nodes,
1322 	     error ) != 1 )
1323 	{
1324 		libcerror_error_set(
1325 		 error,
1326 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1327 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1328 		 "%s: unable to retrieve number of sub nodes.",
1329 		 function );
1330 
1331 		goto on_error;
1332 	}
1333 	if( number_of_sub_nodes != 0 )
1334 	{
1335 		libcerror_error_set(
1336 		 error,
1337 		 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1338 		 LIBCERROR_ARGUMENT_ERROR_UNSUPPORTED_VALUE,
1339 		 "%s: cannot split node with sub nodes.",
1340 		 function );
1341 
1342 		goto on_error;
1343 	}
1344 	if( libcdata_tree_node_get_value(
1345 	     node,
1346 	     (intptr_t **) &values_list,
1347 	     error ) != 1 )
1348 	{
1349 		libcerror_error_set(
1350 		 error,
1351 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1352 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1353 		 "%s: unable to retrieve values list.",
1354 		 function );
1355 
1356 		goto on_error;
1357 	}
1358 	/* Split to have about 25 values per sub node
1359 	 */
1360 	number_of_split_values_list_elements = 25;
1361 
1362 	if( libcdata_list_initialize(
1363 	     &split_values_list,
1364 	     error ) != 1 )
1365 	{
1366 		libcerror_error_set(
1367 		 error,
1368 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1369 		 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
1370 		 "%s: unable to create split values list.",
1371 		 function );
1372 
1373 		goto on_error;
1374 	}
1375 	if( libcdata_tree_node_set_value(
1376 	     node,
1377 	     (intptr_t *) split_values_list,
1378 	     error ) != 1 )
1379 	{
1380 		libcerror_error_set(
1381 		 error,
1382 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1383 		 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
1384 		 "%s: unable to set split values list.",
1385 		 function );
1386 
1387 		goto on_error;
1388 	}
1389 	if( libcdata_list_get_number_of_elements(
1390 	     values_list,
1391 	     &number_of_values_list_elements,
1392 	     error ) != 1 )
1393 	{
1394 		libcerror_error_set(
1395 		 error,
1396 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1397 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1398 		 "%s: unable to retrieve number of values list elements.",
1399 		 function );
1400 
1401 		goto on_error;
1402 	}
1403 	if( libcdata_list_get_first_element(
1404 	     values_list,
1405 	     &values_list_element,
1406 	     error ) != 1 )
1407 	{
1408 		libcerror_error_set(
1409 		 error,
1410 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1411 		 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1412 		 "%s: unable to retrieve first values list element.",
1413 		 function );
1414 
1415 		goto on_error;
1416 	}
1417 	for( values_list_element_index = 0;
1418 	     values_list_element_index < number_of_values_list_elements;
1419 	     values_list_element_index++ )
1420 	{
1421 		if( libcdata_list_element_get_value(
1422 		     values_list_element,
1423 		     &values_list_value,
1424 		     error ) != 1 )
1425 		{
1426 			libcerror_error_set(
1427 			 error,
1428 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1429 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1430 			 "%s: unable to retrieve value from values list element: %d.",
1431 			 function,
1432 			 values_list_element_index );
1433 
1434 			goto on_error;
1435 		}
1436 		if( values_list_value == NULL )
1437 		{
1438 			libcerror_error_set(
1439 			 error,
1440 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1441 			 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1442 			 "%s: invalid values list element: %d - missing value.",
1443 			 function,
1444 			 values_list_element_index );
1445 
1446 			goto on_error;
1447 		}
1448 		if( sub_node == NULL )
1449 		{
1450 			if( libcdata_tree_node_initialize(
1451 			     &sub_node,
1452 			     error ) != 1 )
1453 			{
1454 				libcerror_error_set(
1455 				 error,
1456 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1457 				 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
1458 				 "%s: unable to create sub node: %d.",
1459 				 function,
1460 				 sub_node_index );
1461 
1462 				goto on_error;
1463 			}
1464 		}
1465 		if( libcdata_btree_node_append_value(
1466 		     sub_node,
1467 		     values_list_value,
1468 		     error ) != 1 )
1469 		{
1470 			libcerror_error_set(
1471 			 error,
1472 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1473 			 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
1474 			 "%s: unable to append value: %d to sub node: %d.",
1475 			 function,
1476 			 values_list_element_index,
1477 			 sub_node_index );
1478 
1479 			goto on_error;
1480 		}
1481 		if( values_list_element_index >= split_values_list_element_index )
1482 		{
1483 			if( ( values_list_element_index + 1 ) < number_of_values_list_elements )
1484 			{
1485 				if( libcdata_list_append_value(
1486 				     split_values_list,
1487 				     values_list_value,
1488 				     error ) != 1 )
1489 				{
1490 					libcerror_error_set(
1491 					 error,
1492 					 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1493 					 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
1494 					 "%s: unable to append value: %d to sub nodes values list.",
1495 					 function,
1496 					 values_list_element_index );
1497 
1498 					goto on_error;
1499 				}
1500 			}
1501 			split_values_list_element_index += number_of_split_values_list_elements;
1502 
1503 			if( libcdata_tree_node_append_node(
1504 			     node,
1505 			     sub_node,
1506 			     error ) != 1 )
1507 			{
1508 				libcerror_error_set(
1509 				 error,
1510 				 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1511 				 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
1512 				 "%s: unable to append sub node: %d to node.",
1513 				 function,
1514 				 sub_node_index );
1515 
1516 				goto on_error;
1517 			}
1518 			sub_node = NULL;
1519 
1520 			sub_node_index++;
1521 		}
1522 		if( libcdata_list_element_get_next_element(
1523 		     values_list_element,
1524 		     &values_list_element,
1525 		     error ) != 1 )
1526 		{
1527 			libcerror_error_set(
1528 			 error,
1529 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1530 			 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1531 			 "%s: unable to retrieve next element from values list element: %d.",
1532 			 function,
1533 			 values_list_element_index );
1534 
1535 			goto on_error;
1536 		}
1537 	}
1538 	if( sub_node != NULL )
1539 	{
1540 		if( libcdata_tree_node_append_node(
1541 		     node,
1542 		     sub_node,
1543 		     error ) != 1 )
1544 		{
1545 			libcerror_error_set(
1546 			 error,
1547 			 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1548 			 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
1549 			 "%s: unable to append sub node: %d to node.",
1550 			 function,
1551 			 sub_node_index );
1552 
1553 			goto on_error;
1554 		}
1555 		sub_node = NULL;
1556 
1557 		sub_node_index++;
1558 	}
1559 	split_values_list = NULL;
1560 
1561 	if( libcdata_list_free(
1562 	     &values_list,
1563 	     NULL,
1564 	     error ) != 1 )
1565 	{
1566 		libcerror_error_set(
1567 		 error,
1568 		 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1569 		 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
1570 		 "%s: unable to free values list.",
1571 		 function );
1572 
1573 		goto on_error;
1574 	}
1575 	return( 1 );
1576 
1577 on_error:
1578 	if( sub_node != NULL )
1579 	{
1580 		libcdata_tree_node_remove_node(
1581 		 node,
1582 		 sub_node,
1583 		 NULL );
1584 		libcdata_tree_node_free(
1585 		 &sub_node,
1586 		 NULL,
1587 		 NULL );
1588 	}
1589 	if( split_values_list != NULL )
1590 	{
1591 		libcdata_tree_node_empty(
1592 		 node,
1593 		 NULL,
1594 		 NULL );
1595 		libcdata_tree_node_set_value(
1596 		 node,
1597 		 (intptr_t *) values_list,
1598 		 NULL );
1599 		libcdata_list_free(
1600 		 &split_values_list,
1601 		 NULL,
1602 		 NULL );
1603 	}
1604 	return( -1 );
1605 }
1606 
1607 
1608