1 /*
2 * Balanced tree type functions
3 *
4 * Copyright (C) 2006-2021, 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.h"
28 #include "libcdata_btree_node.h"
29 #include "libcdata_btree_values_list.h"
30 #include "libcdata_definitions.h"
31 #include "libcdata_libcerror.h"
32 #include "libcdata_libcthreads.h"
33 #include "libcdata_list.h"
34 #include "libcdata_list_element.h"
35 #include "libcdata_tree_node.h"
36 #include "libcdata_types.h"
37
38 /* Creates a tree
39 * Make sure the value tree is referencing, is set to NULL
40 * Returns 1 if successful or -1 on error
41 */
libcdata_btree_initialize(libcdata_btree_t ** tree,int maximum_number_of_values,libcerror_error_t ** error)42 int libcdata_btree_initialize(
43 libcdata_btree_t **tree,
44 int maximum_number_of_values,
45 libcerror_error_t **error )
46 {
47 libcdata_internal_btree_t *internal_tree = NULL;
48 static char *function = "libcdata_btree_initialize";
49
50 if( tree == NULL )
51 {
52 libcerror_error_set(
53 error,
54 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
55 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
56 "%s: invalid tree.",
57 function );
58
59 return( -1 );
60 }
61 if( *tree != NULL )
62 {
63 libcerror_error_set(
64 error,
65 LIBCERROR_ERROR_DOMAIN_RUNTIME,
66 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
67 "%s: invalid tree value already set.",
68 function );
69
70 return( -1 );
71 }
72 if( maximum_number_of_values <= 0 )
73 {
74 libcerror_error_set(
75 error,
76 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
77 LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
78 "%s: invalid maximum number of values value out of bounds.",
79 function );
80
81 return( -1 );
82 }
83 internal_tree = memory_allocate_structure(
84 libcdata_internal_btree_t );
85
86 if( internal_tree == NULL )
87 {
88 libcerror_error_set(
89 error,
90 LIBCERROR_ERROR_DOMAIN_MEMORY,
91 LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
92 "%s: unable to create tree.",
93 function );
94
95 goto on_error;
96 }
97 if( memory_set(
98 internal_tree,
99 0,
100 sizeof( libcdata_internal_btree_t ) ) == NULL )
101 {
102 libcerror_error_set(
103 error,
104 LIBCERROR_ERROR_DOMAIN_MEMORY,
105 LIBCERROR_MEMORY_ERROR_SET_FAILED,
106 "%s: unable to clear tree.",
107 function );
108
109 memory_free(
110 internal_tree );
111
112 return( -1 );
113 }
114 if( libcdata_array_initialize(
115 &( internal_tree->values_array ),
116 0,
117 error ) != 1 )
118 {
119 libcerror_error_set(
120 error,
121 LIBCERROR_ERROR_DOMAIN_RUNTIME,
122 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
123 "%s: unable to create values array.",
124 function );
125
126 goto on_error;
127 }
128 if( libcdata_tree_node_initialize(
129 &( internal_tree->root_node ),
130 error ) != 1 )
131 {
132 libcerror_error_set(
133 error,
134 LIBCERROR_ERROR_DOMAIN_RUNTIME,
135 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
136 "%s: unable to create root node.",
137 function );
138
139 goto on_error;
140 }
141 internal_tree->maximum_number_of_values = maximum_number_of_values;
142
143 #if defined( HAVE_MULTI_THREAD_SUPPORT ) && !defined( HAVE_LOCAL_LIBCDATA )
144 if( libcthreads_read_write_lock_initialize(
145 &( internal_tree->read_write_lock ),
146 error ) != 1 )
147 {
148 libcerror_error_set(
149 error,
150 LIBCERROR_ERROR_DOMAIN_RUNTIME,
151 LIBCERROR_RUNTIME_ERROR_INITIALIZE_FAILED,
152 "%s: unable to initialize read/write lock.",
153 function );
154
155 goto on_error;
156 }
157 #endif
158 *tree = (libcdata_btree_t *) internal_tree;
159
160 return( 1 );
161
162 on_error:
163 if( internal_tree != NULL )
164 {
165 if( internal_tree->values_array != NULL )
166 {
167 libcdata_array_free(
168 &( internal_tree->values_array ),
169 NULL,
170 NULL );
171 }
172 memory_free(
173 internal_tree );
174 }
175 return( -1 );
176 }
177
178 /* Frees a tree, its sub nodes
179 * Uses the value_free_function to free the value
180 * Returns 1 if successful or -1 on error
181 */
libcdata_btree_free(libcdata_btree_t ** tree,int (* value_free_function)(intptr_t ** value,libcerror_error_t ** error),libcerror_error_t ** error)182 int libcdata_btree_free(
183 libcdata_btree_t **tree,
184 int (*value_free_function)(
185 intptr_t **value,
186 libcerror_error_t **error ),
187 libcerror_error_t **error )
188 {
189 libcdata_internal_btree_t *internal_tree = NULL;
190 static char *function = "libcdata_btree_free";
191 int result = 1;
192
193 if( tree == NULL )
194 {
195 libcerror_error_set(
196 error,
197 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
198 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
199 "%s: invalid tree.",
200 function );
201
202 return( -1 );
203 }
204 if( *tree != NULL )
205 {
206 internal_tree = (libcdata_internal_btree_t *) *tree;
207 *tree = NULL;
208
209 #if defined( HAVE_MULTI_THREAD_SUPPORT ) && !defined( HAVE_LOCAL_LIBCDATA )
210 if( libcthreads_read_write_lock_free(
211 &( internal_tree->read_write_lock ),
212 error ) != 1 )
213 {
214 libcerror_error_set(
215 error,
216 LIBCERROR_ERROR_DOMAIN_RUNTIME,
217 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
218 "%s: unable to free read/write lock.",
219 function );
220
221 result = -1;
222 }
223 #endif
224 if( libcdata_tree_node_free(
225 &( internal_tree->root_node ),
226 (int (*)(intptr_t **, libcerror_error_t **)) &libcdata_btree_values_list_free,
227 error ) != 1 )
228 {
229 libcerror_error_set(
230 error,
231 LIBCERROR_ERROR_DOMAIN_RUNTIME,
232 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
233 "%s: unable to free root node.",
234 function );
235
236 result = -1;
237 }
238 if( libcdata_array_free(
239 &( internal_tree->values_array ),
240 value_free_function,
241 error ) != 1 )
242 {
243 libcerror_error_set(
244 error,
245 LIBCERROR_ERROR_DOMAIN_RUNTIME,
246 LIBCERROR_RUNTIME_ERROR_FINALIZE_FAILED,
247 "%s: unable to free values array.",
248 function );
249
250 result = -1;
251 }
252 memory_free(
253 internal_tree );
254 }
255 return( result );
256 }
257
258 /* TODO add clone function ? */
259
260 /* Retrieves the number of values in the tree
261 * Returns 1 if successful or -1 on error
262 */
libcdata_btree_get_number_of_values(libcdata_btree_t * tree,int * number_of_values,libcerror_error_t ** error)263 int libcdata_btree_get_number_of_values(
264 libcdata_btree_t *tree,
265 int *number_of_values,
266 libcerror_error_t **error )
267 {
268 libcdata_internal_btree_t *internal_tree = NULL;
269 static char *function = "libcdata_btree_get_number_of_values";
270
271 if( tree == NULL )
272 {
273 libcerror_error_set(
274 error,
275 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
276 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
277 "%s: invalid tree.",
278 function );
279
280 return( -1 );
281 }
282 internal_tree = (libcdata_internal_btree_t *) tree;
283
284 if( libcdata_array_get_number_of_entries(
285 internal_tree->values_array,
286 number_of_values,
287 error ) != 1 )
288 {
289 libcerror_error_set(
290 error,
291 LIBCERROR_ERROR_DOMAIN_RUNTIME,
292 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
293 "%s: unable to retrieve number of values array entries.",
294 function );
295
296 return( -1 );
297 }
298 return( 1 );
299 }
300
301 /* Retrieves a specific value
302 * Returns 1 if successful or -1 on error
303 */
libcdata_btree_get_value_by_index(libcdata_btree_t * tree,int value_index,intptr_t ** value,libcerror_error_t ** error)304 int libcdata_btree_get_value_by_index(
305 libcdata_btree_t *tree,
306 int value_index,
307 intptr_t **value,
308 libcerror_error_t **error )
309 {
310 libcdata_internal_btree_t *internal_tree = NULL;
311 static char *function = "libcdata_btree_get_value_by_index";
312
313 if( tree == NULL )
314 {
315 libcerror_error_set(
316 error,
317 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
318 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
319 "%s: invalid tree.",
320 function );
321
322 return( -1 );
323 }
324 internal_tree = (libcdata_internal_btree_t *) tree;
325
326 if( libcdata_array_get_entry_by_index(
327 internal_tree->values_array,
328 value_index,
329 value,
330 error ) != 1 )
331 {
332 libcerror_error_set(
333 error,
334 LIBCERROR_ERROR_DOMAIN_RUNTIME,
335 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
336 "%s: unable to retrieve value: %d from array.",
337 function,
338 value_index );
339
340 return( -1 );
341 }
342 return( 1 );
343 }
344
345 /* Retrieves a value from the tree
346 *
347 * Uses the value_compare_function to determine the similarity of the entries
348 * The value_compare_function should return LIBCDATA_COMPARE_LESS,
349 * LIBCDATA_COMPARE_EQUAL, LIBCDATA_COMPARE_GREATER if successful or -1 on error
350 *
351 * Returns 1 if successful, 0 if no such value or -1 on error
352 */
libcdata_btree_get_value_by_value(libcdata_btree_t * tree,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,intptr_t ** existing_value,libcerror_error_t ** error)353 int libcdata_btree_get_value_by_value(
354 libcdata_btree_t *tree,
355 intptr_t *value,
356 int (*value_compare_function)(
357 intptr_t *first_value,
358 intptr_t *second_value,
359 libcerror_error_t **error ),
360 libcdata_tree_node_t **upper_node,
361 intptr_t **existing_value,
362 libcerror_error_t **error )
363 {
364 libcdata_internal_btree_t *internal_tree = NULL;
365 libcdata_list_element_t *existing_list_element = NULL;
366 static char *function = "libcdata_btree_get_value_by_value";
367 int result = 0;
368
369 if( tree == NULL )
370 {
371 libcerror_error_set(
372 error,
373 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
374 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
375 "%s: invalid tree.",
376 function );
377
378 return( -1 );
379 }
380 internal_tree = (libcdata_internal_btree_t *) tree;
381
382 result = libcdata_btree_node_get_upper_node_by_value(
383 internal_tree->root_node,
384 value,
385 value_compare_function,
386 upper_node,
387 &existing_list_element,
388 error );
389
390 if( result == -1 )
391 {
392 libcerror_error_set(
393 error,
394 LIBCERROR_ERROR_DOMAIN_RUNTIME,
395 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
396 "%s: unable to retrieve upper node by value.",
397 function );
398
399 return( -1 );
400 }
401 else if( result != 0 )
402 {
403 if( libcdata_list_element_get_value(
404 existing_list_element,
405 existing_value,
406 error ) != 1 )
407 {
408 libcerror_error_set(
409 error,
410 LIBCERROR_ERROR_DOMAIN_RUNTIME,
411 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
412 "%s: unable to retrieve value from values list element.",
413 function );
414
415 return( -1 );
416 }
417 }
418 else
419 {
420 if( existing_value == NULL )
421 {
422 libcerror_error_set(
423 error,
424 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
425 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
426 "%s: invalid existing value.",
427 function );
428
429 return( -1 );
430 }
431 *existing_value = NULL;
432 }
433 return( result );
434 }
435
436 /* Inserts a value into a tree
437 *
438 * Uses the value_compare_function to determine the order of the entries
439 * The value_compare_function should return LIBCDATA_COMPARE_LESS,
440 * LIBCDATA_COMPARE_EQUAL, LIBCDATA_COMPARE_GREATER if successful or -1 on error
441 *
442 * Returns 1 if successful, 0 if the value already exists or -1 on error
443 */
libcdata_btree_insert_value(libcdata_btree_t * tree,int * value_index,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,intptr_t ** existing_value,libcerror_error_t ** error)444 int libcdata_btree_insert_value(
445 libcdata_btree_t *tree,
446 int *value_index,
447 intptr_t *value,
448 int (*value_compare_function)(
449 intptr_t *first_value,
450 intptr_t *second_value,
451 libcerror_error_t **error ),
452 libcdata_tree_node_t **upper_node,
453 intptr_t **existing_value,
454 libcerror_error_t **error )
455 {
456 libcdata_internal_btree_t *internal_tree = NULL;
457 libcdata_list_t *values_list = NULL;
458 libcdata_list_element_t *existing_list_element = NULL;
459 static char *function = "libcdata_btree_insert_value";
460 int number_of_values_list_elements = 0;
461 int result = 0;
462
463 if( tree == NULL )
464 {
465 libcerror_error_set(
466 error,
467 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
468 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
469 "%s: invalid tree.",
470 function );
471
472 return( -1 );
473 }
474 internal_tree = (libcdata_internal_btree_t *) tree;
475
476 if( upper_node == NULL )
477 {
478 libcerror_error_set(
479 error,
480 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
481 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
482 "%s: invalid upper node.",
483 function );
484
485 return( -1 );
486 }
487 if( value_index == NULL )
488 {
489 libcerror_error_set(
490 error,
491 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
492 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
493 "%s: invalid value index.",
494 function );
495
496 return( -1 );
497 }
498 if( existing_value == NULL )
499 {
500 libcerror_error_set(
501 error,
502 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
503 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
504 "%s: invalid existing value.",
505 function );
506
507 return( -1 );
508 }
509 result = libcdata_btree_node_get_upper_node_by_value(
510 internal_tree->root_node,
511 value,
512 value_compare_function,
513 upper_node,
514 &existing_list_element,
515 error );
516
517 if( result == -1 )
518 {
519 libcerror_error_set(
520 error,
521 LIBCERROR_ERROR_DOMAIN_RUNTIME,
522 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
523 "%s: unable to retrieve upper node in root node.",
524 function );
525
526 return( -1 );
527 }
528 else if( result != 0 )
529 {
530 if( libcdata_list_element_get_value(
531 existing_list_element,
532 existing_value,
533 error ) != 1 )
534 {
535 libcerror_error_set(
536 error,
537 LIBCERROR_ERROR_DOMAIN_RUNTIME,
538 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
539 "%s: unable to retrieve value from values list element.",
540 function );
541
542 return( -1 );
543 }
544 return( 0 );
545 }
546 *existing_value = NULL;
547
548 if( libcdata_btree_node_insert_value(
549 *upper_node,
550 value,
551 value_compare_function,
552 error ) != 1 )
553 {
554 libcerror_error_set(
555 error,
556 LIBCERROR_ERROR_DOMAIN_RUNTIME,
557 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
558 "%s: unable to insert value in upper node.",
559 function );
560
561 return( -1 );
562 }
563 if( libcdata_tree_node_get_value(
564 *upper_node,
565 (intptr_t **) &values_list,
566 error ) != 1 )
567 {
568 libcerror_error_set(
569 error,
570 LIBCERROR_ERROR_DOMAIN_RUNTIME,
571 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
572 "%s: unable to retrieve values list.",
573 function );
574
575 return( -1 );
576 }
577 if( libcdata_list_get_number_of_elements(
578 values_list,
579 &number_of_values_list_elements,
580 error ) != 1 )
581 {
582 libcerror_error_set(
583 error,
584 LIBCERROR_ERROR_DOMAIN_RUNTIME,
585 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
586 "%s: unable to retrieve number of values list elements.",
587 function );
588
589 return( -1 );
590 }
591 if( number_of_values_list_elements >= internal_tree->maximum_number_of_values )
592 {
593 if( libcdata_btree_node_split(
594 *upper_node,
595 error ) != 1 )
596 {
597 libcerror_error_set(
598 error,
599 LIBCERROR_ERROR_DOMAIN_RUNTIME,
600 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
601 "%s: unable to split upper node.",
602 function );
603
604 return( -1 );
605 }
606 /* TODO do merge of upper node with its parent node */
607 /* TODO loop until number_of_values_list_elements < internal_tree->maximum_number_of_values */
608
609 /* Make sure existing list element updated after the split
610 */
611 result = libcdata_btree_node_get_sub_node_by_value(
612 *upper_node,
613 value,
614 value_compare_function,
615 upper_node,
616 &existing_list_element,
617 error );
618
619 if( result == -1 )
620 {
621 libcerror_error_set(
622 error,
623 LIBCERROR_ERROR_DOMAIN_RUNTIME,
624 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
625 "%s: unable to retrieve split sub node by value.",
626 function );
627
628 return( -1 );
629 }
630 result = libcdata_btree_node_get_sub_node_by_value(
631 *upper_node,
632 value,
633 value_compare_function,
634 upper_node,
635 &existing_list_element,
636 error );
637
638 if( result != 1 )
639 {
640 libcerror_error_set(
641 error,
642 LIBCERROR_ERROR_DOMAIN_RUNTIME,
643 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
644 "%s: unable to retrieve split sub node by value.",
645 function );
646
647 return( -1 );
648 }
649 }
650 if( libcdata_array_append_entry(
651 internal_tree->values_array,
652 value_index,
653 value,
654 error ) != 1 )
655 {
656 libcerror_error_set(
657 error,
658 LIBCERROR_ERROR_DOMAIN_RUNTIME,
659 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
660 "%s: unable to append value to values array.",
661 function );
662
663 return( -1 );
664 }
665 return( 1 );
666 }
667
668 /* Replaces a value in the tree
669 * Returns 1 if successful or -1 on error
670 */
libcdata_btree_replace_value(libcdata_btree_t * tree,libcdata_tree_node_t * upper_node,int * value_index,intptr_t * value,int * replacement_value_index,intptr_t * replacement_value,libcerror_error_t ** error)671 int libcdata_btree_replace_value(
672 libcdata_btree_t *tree,
673 libcdata_tree_node_t *upper_node,
674 int *value_index,
675 intptr_t *value,
676 int *replacement_value_index,
677 intptr_t *replacement_value,
678 libcerror_error_t **error )
679 {
680 libcdata_internal_btree_t *internal_tree = NULL;
681 intptr_t *check_value = NULL;
682 static char *function = "libcdata_btree_replace_value";
683 int number_of_sub_nodes = 0;
684
685 if( tree == NULL )
686 {
687 libcerror_error_set(
688 error,
689 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
690 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
691 "%s: invalid tree.",
692 function );
693
694 return( -1 );
695 }
696 internal_tree = (libcdata_internal_btree_t *) tree;
697
698 if( upper_node == NULL )
699 {
700 libcerror_error_set(
701 error,
702 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
703 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
704 "%s: invalid upper node.",
705 function );
706
707 return( -1 );
708 }
709 if( value_index == NULL )
710 {
711 libcerror_error_set(
712 error,
713 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
714 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
715 "%s: invalid value index.",
716 function );
717
718 return( -1 );
719 }
720 if( replacement_value_index == NULL )
721 {
722 libcerror_error_set(
723 error,
724 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
725 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
726 "%s: invalid value index.",
727 function );
728
729 return( -1 );
730 }
731 if( libcdata_tree_node_get_number_of_sub_nodes(
732 upper_node,
733 &number_of_sub_nodes,
734 error ) != 1 )
735 {
736 libcerror_error_set(
737 error,
738 LIBCERROR_ERROR_DOMAIN_RUNTIME,
739 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
740 "%s: unable to retrieve number of sub nodes.",
741 function );
742
743 return( -1 );
744 }
745 if( number_of_sub_nodes != 0 )
746 {
747 libcerror_error_set(
748 error,
749 LIBCERROR_ERROR_DOMAIN_RUNTIME,
750 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
751 "%s: cannot replace upper node with sub nodes.",
752 function );
753
754 return( -1 );
755 }
756 if( libcdata_array_get_entry_by_index(
757 internal_tree->values_array,
758 *value_index,
759 &check_value,
760 error ) != 1 )
761 {
762 libcerror_error_set(
763 error,
764 LIBCERROR_ERROR_DOMAIN_RUNTIME,
765 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
766 "%s: unable to retrieve value: %d from array.",
767 function,
768 *value_index );
769
770 return( -1 );
771 }
772 if( value != check_value )
773 {
774 libcerror_error_set(
775 error,
776 LIBCERROR_ERROR_DOMAIN_RUNTIME,
777 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
778 "%s: invalid value: %d value out of bounds.",
779 function,
780 *value_index );
781
782 return( -1 );
783 }
784 if( libcdata_btree_node_replace_value(
785 upper_node,
786 value,
787 replacement_value,
788 error ) != 1 )
789 {
790 libcerror_error_set(
791 error,
792 LIBCERROR_ERROR_DOMAIN_RUNTIME,
793 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
794 "%s: unable to replace value: %d.",
795 function,
796 *value_index );
797
798 return( -1 );
799 }
800 if( libcdata_array_set_entry_by_index(
801 internal_tree->values_array,
802 *value_index,
803 replacement_value,
804 error ) != 1 )
805 {
806 libcerror_error_set(
807 error,
808 LIBCERROR_ERROR_DOMAIN_RUNTIME,
809 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
810 "%s: unable to set value: %d in values array.",
811 function,
812 *value_index );
813
814 return( -1 );
815 }
816 *replacement_value_index = *value_index;
817 *value_index = -1;
818
819 return( 1 );
820 }
821
822 /* Removes a value from the tree
823 * Returns 1 if successful or -1 on error
824 */
libcdata_btree_remove_value(libcdata_btree_t * tree,libcdata_tree_node_t * upper_node,int * value_index,intptr_t * value,libcerror_error_t ** error)825 int libcdata_btree_remove_value(
826 libcdata_btree_t *tree,
827 libcdata_tree_node_t *upper_node,
828 int *value_index,
829 intptr_t *value,
830 libcerror_error_t **error )
831 {
832 libcdata_internal_btree_t *internal_tree = NULL;
833 intptr_t *check_value = NULL;
834 static char *function = "libcdata_btree_remove_value";
835 int number_of_sub_nodes = 0;
836
837 if( tree == NULL )
838 {
839 libcerror_error_set(
840 error,
841 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
842 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
843 "%s: invalid tree.",
844 function );
845
846 return( -1 );
847 }
848 internal_tree = (libcdata_internal_btree_t *) tree;
849
850 if( upper_node == NULL )
851 {
852 libcerror_error_set(
853 error,
854 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
855 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
856 "%s: invalid upper node.",
857 function );
858
859 return( -1 );
860 }
861 if( value_index == NULL )
862 {
863 libcerror_error_set(
864 error,
865 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
866 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
867 "%s: invalid value index.",
868 function );
869
870 return( -1 );
871 }
872 if( libcdata_tree_node_get_number_of_sub_nodes(
873 upper_node,
874 &number_of_sub_nodes,
875 error ) != 1 )
876 {
877 libcerror_error_set(
878 error,
879 LIBCERROR_ERROR_DOMAIN_RUNTIME,
880 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
881 "%s: unable to retrieve number of sub nodes.",
882 function );
883
884 return( -1 );
885 }
886 if( number_of_sub_nodes != 0 )
887 {
888 libcerror_error_set(
889 error,
890 LIBCERROR_ERROR_DOMAIN_RUNTIME,
891 LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
892 "%s: cannot replace upper node with sub nodes.",
893 function );
894
895 return( -1 );
896 }
897 if( libcdata_array_get_entry_by_index(
898 internal_tree->values_array,
899 *value_index,
900 &check_value,
901 error ) != 1 )
902 {
903 libcerror_error_set(
904 error,
905 LIBCERROR_ERROR_DOMAIN_RUNTIME,
906 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
907 "%s: unable to retrieve value: %d from array.",
908 function,
909 *value_index );
910
911 return( -1 );
912 }
913 if( value != check_value )
914 {
915 libcerror_error_set(
916 error,
917 LIBCERROR_ERROR_DOMAIN_RUNTIME,
918 LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
919 "%s: invalid value: %d value out of bounds.",
920 function,
921 *value_index );
922
923 return( -1 );
924 }
925 if( libcdata_btree_node_remove_value(
926 upper_node,
927 value,
928 NULL,
929 error ) != 1 )
930 {
931 libcerror_error_set(
932 error,
933 LIBCERROR_ERROR_DOMAIN_RUNTIME,
934 LIBCERROR_RUNTIME_ERROR_REMOVE_FAILED,
935 "%s: unable to remove value: %d from upper node.",
936 function,
937 *value_index );
938
939 return( -1 );
940 }
941 /* TODO reshuffle values array ?
942 * Better to mark and ignore deleted items, otherwise index values need to be updated as well
943 */
944 if( libcdata_array_set_entry_by_index(
945 internal_tree->values_array,
946 *value_index,
947 NULL,
948 error ) != 1 )
949 {
950 libcerror_error_set(
951 error,
952 LIBCERROR_ERROR_DOMAIN_RUNTIME,
953 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
954 "%s: unable to set value: %d in values array.",
955 function,
956 *value_index );
957
958 return( -1 );
959 }
960 *value_index = -1;
961
962 return( 1 );
963 }
964
965