1 /*
2 * Index tree functions
3 *
4 * Copyright (C) 2008-2018, Joachim Metz <joachim.metz@gmail.com>
5 *
6 * Refer to AUTHORS for acknowledgements.
7 *
8 * This software 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 software 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 software. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22 #include <common.h>
23 #include <types.h>
24
25 #include "libpff_definitions.h"
26 #include "libpff_index_tree.h"
27 #include "libpff_index_value.h"
28 #include "libpff_libbfio.h"
29 #include "libpff_libcerror.h"
30 #include "libpff_libcnotify.h"
31 #include "libpff_libfcache.h"
32 #include "libpff_libfdata.h"
33
34 /* Retrieves the number of leaf nodes for the specific identifier
35 * Returns 1 if successful or -1 on error
36 */
libpff_index_tree_get_number_of_leaf_nodes_by_identifier(libfdata_tree_t * index_tree,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,int * number_of_leaf_nodes,libcerror_error_t ** error)37 int libpff_index_tree_get_number_of_leaf_nodes_by_identifier(
38 libfdata_tree_t *index_tree,
39 libbfio_handle_t *file_io_handle,
40 libfcache_cache_t *cache,
41 uint64_t identifier,
42 int *number_of_leaf_nodes,
43 libcerror_error_t **error )
44 {
45 libfdata_tree_node_t *index_tree_root_node = NULL;
46 static char *function = "libpff_index_tree_get_number_of_leaf_nodes_by_identifier";
47
48 if( index_tree == NULL )
49 {
50 libcerror_error_set(
51 error,
52 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
53 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
54 "%s: invalid index tree.",
55 function );
56
57 return( -1 );
58 }
59 if( number_of_leaf_nodes == NULL )
60 {
61 libcerror_error_set(
62 error,
63 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
64 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
65 "%s: invalid number of leaf nodes.",
66 function );
67
68 return( -1 );
69 }
70 #if defined( HAVE_DEBUG_OUTPUT )
71 if( libcnotify_verbose != 0 )
72 {
73 libcnotify_printf(
74 "%s: requested identifier\t: 0x%08" PRIx64 " (%" PRIu64 ").\n",
75 function,
76 identifier,
77 identifier );
78 }
79 #endif
80 if( libfdata_tree_get_root_node(
81 index_tree,
82 &index_tree_root_node,
83 error ) != 1 )
84 {
85 libcerror_error_set(
86 error,
87 LIBCERROR_ERROR_DOMAIN_RUNTIME,
88 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
89 "%s: unable to retrieve root node from index tree.",
90 function );
91
92 return( -1 );
93 }
94 *number_of_leaf_nodes = 0;
95
96 if( libpff_index_tree_node_get_number_of_leaf_nodes_by_identifier(
97 index_tree_root_node,
98 file_io_handle,
99 cache,
100 identifier,
101 number_of_leaf_nodes,
102 error ) != 1 )
103 {
104 libcerror_error_set(
105 error,
106 LIBCERROR_ERROR_DOMAIN_RUNTIME,
107 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
108 "%s: unable to retrieve number of leaf nodes by identifier in root node.",
109 function );
110
111 return( -1 );
112 }
113 return( 1 );
114 }
115
116 /* Retrieves the number of leaf nodes for the specific identifier
117 * Returns 1 if successful or -1 on error
118 */
libpff_index_tree_node_get_number_of_leaf_nodes_by_identifier(libfdata_tree_node_t * index_tree_node,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,int * number_of_leaf_nodes,libcerror_error_t ** error)119 int libpff_index_tree_node_get_number_of_leaf_nodes_by_identifier(
120 libfdata_tree_node_t *index_tree_node,
121 libbfio_handle_t *file_io_handle,
122 libfcache_cache_t *cache,
123 uint64_t identifier,
124 int *number_of_leaf_nodes,
125 libcerror_error_t **error )
126 {
127 libfdata_tree_node_t *index_tree_sub_node = NULL;
128 libpff_index_value_t *index_tree_sub_node_value = NULL;
129 static char *function = "libpff_index_tree_node_get_number_of_leaf_nodes_by_identifier";
130 int16_t compare = 0;
131 int number_of_sub_nodes = 0;
132 int result = 0;
133 int sub_node_index = 0;
134
135 if( index_tree_node == NULL )
136 {
137 libcerror_error_set(
138 error,
139 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
140 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
141 "%s: invalid index tree node.",
142 function );
143
144 return( -1 );
145 }
146 if( libfdata_tree_node_get_number_of_sub_nodes(
147 index_tree_node,
148 (intptr_t *) file_io_handle,
149 cache,
150 &number_of_sub_nodes,
151 0,
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 from index tree node.",
159 function );
160
161 return( -1 );
162 }
163 for( sub_node_index = 0;
164 sub_node_index < number_of_sub_nodes;
165 sub_node_index++ )
166 {
167 if( libfdata_tree_node_get_sub_node_by_index(
168 index_tree_node,
169 (intptr_t *) file_io_handle,
170 cache,
171 sub_node_index,
172 &index_tree_sub_node,
173 0,
174 error ) != 1 )
175 {
176 libcerror_error_set(
177 error,
178 LIBCERROR_ERROR_DOMAIN_RUNTIME,
179 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
180 "%s: unable to retrieve sub node: %d from index tree node.",
181 function,
182 sub_node_index );
183
184 return( -1 );
185 }
186 if( libfdata_tree_node_get_node_value(
187 index_tree_sub_node,
188 (intptr_t *) file_io_handle,
189 cache,
190 (intptr_t **) &index_tree_sub_node_value,
191 0,
192 error ) != 1 )
193 {
194 libcerror_error_set(
195 error,
196 LIBCERROR_ERROR_DOMAIN_RUNTIME,
197 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
198 "%s: unable to retrieve index tree sub node value: %d.",
199 function,
200 sub_node_index );
201
202 return( -1 );
203 }
204 if( index_tree_sub_node_value == NULL )
205 {
206 libcerror_error_set(
207 error,
208 LIBCERROR_ERROR_DOMAIN_RUNTIME,
209 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
210 "%s: missing index tree sub node value: %d.",
211 function,
212 sub_node_index );
213
214 return( -1 );
215 }
216 #if defined( HAVE_DEBUG_OUTPUT )
217 if( libcnotify_verbose != 0 )
218 {
219 libcnotify_printf(
220 "%s: index tree sub node value: %d identifier\t: 0x%08" PRIx64 " (%" PRIu64 ").\n",
221 function,
222 sub_node_index,
223 index_tree_sub_node_value->identifier,
224 index_tree_sub_node_value->identifier );
225 }
226 #endif
227 if( identifier > index_tree_sub_node_value->identifier )
228 {
229 compare = 1;
230 }
231 else if( identifier < index_tree_sub_node_value->identifier )
232 {
233 compare = -1;
234 }
235 else
236 {
237 compare = 0;
238 }
239 result = libfdata_tree_node_is_leaf(
240 index_tree_sub_node,
241 (intptr_t *) file_io_handle,
242 cache,
243 0,
244 error );
245
246 if( result == -1 )
247 {
248 libcerror_error_set(
249 error,
250 LIBCERROR_ERROR_DOMAIN_RUNTIME,
251 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
252 "%s: unable to determine if index tree sub node: %d is a leaf node.",
253 function,
254 sub_node_index );
255
256 return( -1 );
257 }
258 else if( result != 0 )
259 {
260 result = libfdata_tree_node_is_deleted(
261 index_tree_sub_node,
262 error );
263
264 if( result == -1 )
265 {
266 libcerror_error_set(
267 error,
268 LIBCERROR_ERROR_DOMAIN_RUNTIME,
269 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
270 "%s: unable to determine if index tree sub node: %d is a deleted node.",
271 function,
272 sub_node_index );
273
274 return( -1 );
275 }
276 else if( result == 0 )
277 {
278 if( compare == 0 )
279 {
280 if( number_of_leaf_nodes == NULL )
281 {
282 libcerror_error_set(
283 error,
284 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
285 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
286 "%s: invalid number of leaf nodes.",
287 function );
288
289 return( -1 );
290 }
291 *number_of_leaf_nodes += 1;
292 }
293 }
294 }
295 else
296 {
297 /* A branch node contains the identifier of its first sub node
298 */
299 if( ( compare == 0 )
300 || ( ( compare > 0 )
301 && ( sub_node_index == ( number_of_sub_nodes - 1 ) ) ) )
302 {
303 result = libpff_index_tree_node_get_number_of_leaf_nodes_by_identifier(
304 index_tree_sub_node,
305 file_io_handle,
306 cache,
307 identifier,
308 number_of_leaf_nodes,
309 error );
310
311 if( result == -1 )
312 {
313 libcerror_error_set(
314 error,
315 LIBCERROR_ERROR_DOMAIN_RUNTIME,
316 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
317 "%s: unable to retrieve leaf index tree node by identifier in sub node: %d.",
318 function,
319 sub_node_index );
320
321 return( -1 );
322 }
323 break;
324 }
325 else if( ( compare < 0 )
326 && ( sub_node_index >= 1 ) )
327 {
328 if( libfdata_tree_node_get_sub_node_by_index(
329 index_tree_node,
330 (intptr_t *) file_io_handle,
331 cache,
332 sub_node_index - 1,
333 &index_tree_sub_node,
334 0,
335 error ) != 1 )
336 {
337 libcerror_error_set(
338 error,
339 LIBCERROR_ERROR_DOMAIN_RUNTIME,
340 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
341 "%s: unable to retrieve sub node: %d from index tree node.",
342 function,
343 sub_node_index - 1 );
344
345 return( -1 );
346 }
347 result = libpff_index_tree_node_get_number_of_leaf_nodes_by_identifier(
348 index_tree_sub_node,
349 file_io_handle,
350 cache,
351 identifier,
352 number_of_leaf_nodes,
353 error );
354
355 if( result == -1 )
356 {
357 libcerror_error_set(
358 error,
359 LIBCERROR_ERROR_DOMAIN_RUNTIME,
360 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
361 "%s: unable to retrieve leaf index tree node by identifier in sub node: %d.",
362 function,
363 sub_node_index - 1 );
364
365 return( -1 );
366 }
367 break;
368 }
369 }
370 }
371 return( 1 );
372 }
373
374 /* Retrieves the leaf node for the specific identifier
375 * Returns 1 if successful, 0 if no value was found or -1 on error
376 */
libpff_index_tree_get_leaf_node_by_identifier(libfdata_tree_t * index_tree,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,int * leaf_node_index,libfdata_tree_node_t ** leaf_index_tree_node,libcerror_error_t ** error)377 int libpff_index_tree_get_leaf_node_by_identifier(
378 libfdata_tree_t *index_tree,
379 libbfio_handle_t *file_io_handle,
380 libfcache_cache_t *cache,
381 uint64_t identifier,
382 int *leaf_node_index,
383 libfdata_tree_node_t **leaf_index_tree_node,
384 libcerror_error_t **error )
385 {
386 libfdata_tree_node_t *index_tree_root_node = NULL;
387 static char *function = "libpff_index_tree_get_leaf_node_by_identifier";
388 int result = 0;
389
390 if( index_tree == NULL )
391 {
392 libcerror_error_set(
393 error,
394 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
395 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
396 "%s: invalid index tree.",
397 function );
398
399 return( -1 );
400 }
401 if( leaf_index_tree_node == NULL )
402 {
403 libcerror_error_set(
404 error,
405 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
406 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
407 "%s: invalid leaf index tree node.",
408 function );
409
410 return( -1 );
411 }
412 #if defined( HAVE_DEBUG_OUTPUT )
413 if( libcnotify_verbose != 0 )
414 {
415 libcnotify_printf(
416 "%s: requested identifier\t: 0x%08" PRIx64 " (%" PRIu64 ").\n",
417 function,
418 identifier,
419 identifier );
420 }
421 #endif
422 if( libfdata_tree_get_root_node(
423 index_tree,
424 &index_tree_root_node,
425 error ) != 1 )
426 {
427 libcerror_error_set(
428 error,
429 LIBCERROR_ERROR_DOMAIN_RUNTIME,
430 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
431 "%s: unable to retrieve root node from index tree.",
432 function );
433
434 return( -1 );
435 }
436 result = libpff_index_tree_node_get_leaf_node_by_identifier(
437 index_tree_root_node,
438 file_io_handle,
439 cache,
440 identifier,
441 leaf_node_index,
442 leaf_index_tree_node,
443 error );
444
445 if( result == -1 )
446 {
447 libcerror_error_set(
448 error,
449 LIBCERROR_ERROR_DOMAIN_RUNTIME,
450 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
451 "%s: unable to retrieve leaf node by identifier in root node.",
452 function );
453
454 return( -1 );
455 }
456 return( result );
457 }
458
459 /* Retrieves the leaf node for the specific identifier
460 * Returns 1 if successful, 0 if no leaf node was found or -1 on error
461 */
libpff_index_tree_node_get_leaf_node_by_identifier(libfdata_tree_node_t * index_tree_node,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,int * leaf_node_index,libfdata_tree_node_t ** leaf_index_tree_node,libcerror_error_t ** error)462 int libpff_index_tree_node_get_leaf_node_by_identifier(
463 libfdata_tree_node_t *index_tree_node,
464 libbfio_handle_t *file_io_handle,
465 libfcache_cache_t *cache,
466 uint64_t identifier,
467 int *leaf_node_index,
468 libfdata_tree_node_t **leaf_index_tree_node,
469 libcerror_error_t **error )
470 {
471 libfdata_tree_node_t *index_tree_sub_node = NULL;
472 libpff_index_value_t *index_tree_sub_node_value = NULL;
473 static char *function = "libpff_index_tree_node_get_leaf_node_by_identifier";
474 int16_t compare = 0;
475 int number_of_sub_nodes = 0;
476 int result = 0;
477 int sub_node_index = 0;
478
479 if( index_tree_node == NULL )
480 {
481 libcerror_error_set(
482 error,
483 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
484 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
485 "%s: invalid index tree node.",
486 function );
487
488 return( -1 );
489 }
490 if( libfdata_tree_node_get_number_of_sub_nodes(
491 index_tree_node,
492 (intptr_t *) file_io_handle,
493 cache,
494 &number_of_sub_nodes,
495 0,
496 error ) != 1 )
497 {
498 libcerror_error_set(
499 error,
500 LIBCERROR_ERROR_DOMAIN_RUNTIME,
501 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
502 "%s: unable to retrieve number of sub nodes from index tree node.",
503 function );
504
505 return( -1 );
506 }
507 for( sub_node_index = 0;
508 sub_node_index < number_of_sub_nodes;
509 sub_node_index++ )
510 {
511 if( libfdata_tree_node_get_sub_node_by_index(
512 index_tree_node,
513 (intptr_t *) file_io_handle,
514 cache,
515 sub_node_index,
516 &index_tree_sub_node,
517 0,
518 error ) != 1 )
519 {
520 libcerror_error_set(
521 error,
522 LIBCERROR_ERROR_DOMAIN_RUNTIME,
523 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
524 "%s: unable to retrieve sub node: %d from index tree node.",
525 function,
526 sub_node_index );
527
528 return( -1 );
529 }
530 if( libfdata_tree_node_get_node_value(
531 index_tree_sub_node,
532 (intptr_t *) file_io_handle,
533 cache,
534 (intptr_t **) &index_tree_sub_node_value,
535 0,
536 error ) != 1 )
537 {
538 libcerror_error_set(
539 error,
540 LIBCERROR_ERROR_DOMAIN_RUNTIME,
541 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
542 "%s: unable to retrieve index tree sub node value: %d.",
543 function,
544 sub_node_index );
545
546 return( -1 );
547 }
548 if( index_tree_sub_node_value == NULL )
549 {
550 libcerror_error_set(
551 error,
552 LIBCERROR_ERROR_DOMAIN_RUNTIME,
553 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
554 "%s: missing index tree sub node value: %d.",
555 function,
556 sub_node_index );
557
558 return( -1 );
559 }
560 #if defined( HAVE_DEBUG_OUTPUT )
561 if( libcnotify_verbose != 0 )
562 {
563 libcnotify_printf(
564 "%s: index tree sub node value: %d identifier\t: 0x%08" PRIx64 " (%" PRIu64 ").\n",
565 function,
566 sub_node_index,
567 index_tree_sub_node_value->identifier,
568 index_tree_sub_node_value->identifier );
569 }
570 #endif
571 if( identifier > index_tree_sub_node_value->identifier )
572 {
573 compare = 1;
574 }
575 else if( identifier < index_tree_sub_node_value->identifier )
576 {
577 compare = -1;
578 }
579 else
580 {
581 compare = 0;
582 }
583 result = libfdata_tree_node_is_leaf(
584 index_tree_sub_node,
585 (intptr_t *) file_io_handle,
586 cache,
587 0,
588 error );
589
590 if( result == -1 )
591 {
592 libcerror_error_set(
593 error,
594 LIBCERROR_ERROR_DOMAIN_RUNTIME,
595 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
596 "%s: unable to determine if index tree sub node: %d is a leaf node.",
597 function,
598 sub_node_index );
599
600 return( -1 );
601 }
602 else if( result != 0 )
603 {
604 result = libfdata_tree_node_is_deleted(
605 index_tree_sub_node,
606 error );
607
608 if( result == -1 )
609 {
610 libcerror_error_set(
611 error,
612 LIBCERROR_ERROR_DOMAIN_RUNTIME,
613 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
614 "%s: unable to determine if index tree sub node: %d is a deleted node.",
615 function,
616 sub_node_index );
617
618 return( -1 );
619 }
620 else if( result == 0 )
621 {
622 if( compare == 0 )
623 {
624 if( leaf_node_index == NULL )
625 {
626 libcerror_error_set(
627 error,
628 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
629 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
630 "%s: invalid leaf node index.",
631 function );
632
633 return( -1 );
634 }
635 if( *leaf_node_index == 0 )
636 {
637 if( leaf_index_tree_node == NULL )
638 {
639 libcerror_error_set(
640 error,
641 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
642 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
643 "%s: invalid leaf index tree node.",
644 function );
645
646 return( -1 );
647 }
648 if( *leaf_index_tree_node != NULL )
649 {
650 libcerror_error_set(
651 error,
652 LIBCERROR_ERROR_DOMAIN_RUNTIME,
653 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
654 "%s: leaf index tree node value already set.",
655 function );
656
657 return( -1 );
658 }
659 *leaf_index_tree_node = index_tree_sub_node;
660
661 result = 1;
662
663 break;
664 }
665 else
666 {
667 *leaf_node_index -= 1;
668 }
669 }
670 }
671 result = 0;
672 }
673 else
674 {
675 /* A branch node contains the identifier of its first sub node
676 */
677 if( ( compare == 0 )
678 || ( ( compare > 0 )
679 && ( sub_node_index == ( number_of_sub_nodes - 1 ) ) ) )
680 {
681 result = libpff_index_tree_node_get_leaf_node_by_identifier(
682 index_tree_sub_node,
683 file_io_handle,
684 cache,
685 identifier,
686 leaf_node_index,
687 leaf_index_tree_node,
688 error );
689
690 if( result == -1 )
691 {
692 libcerror_error_set(
693 error,
694 LIBCERROR_ERROR_DOMAIN_RUNTIME,
695 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
696 "%s: unable to retrieve leaf index tree node by identifier in sub node: %d.",
697 function,
698 sub_node_index );
699
700 return( -1 );
701 }
702 break;
703 }
704 else if( ( compare < 0 )
705 && ( sub_node_index >= 1 ) )
706 {
707 if( libfdata_tree_node_get_sub_node_by_index(
708 index_tree_node,
709 (intptr_t *) file_io_handle,
710 cache,
711 sub_node_index - 1,
712 &index_tree_sub_node,
713 0,
714 error ) != 1 )
715 {
716 libcerror_error_set(
717 error,
718 LIBCERROR_ERROR_DOMAIN_RUNTIME,
719 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
720 "%s: unable to retrieve sub node: %d from index tree node.",
721 function,
722 sub_node_index - 1 );
723
724 return( -1 );
725 }
726 result = libpff_index_tree_node_get_leaf_node_by_identifier(
727 index_tree_sub_node,
728 file_io_handle,
729 cache,
730 identifier,
731 leaf_node_index,
732 leaf_index_tree_node,
733 error );
734
735 if( result == -1 )
736 {
737 libcerror_error_set(
738 error,
739 LIBCERROR_ERROR_DOMAIN_RUNTIME,
740 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
741 "%s: unable to retrieve leaf index tree node by identifier in sub node: %d.",
742 function,
743 sub_node_index - 1 );
744
745 return( -1 );
746 }
747 break;
748 }
749 }
750 }
751 return( result );
752 }
753
754 /* Retrieves the index value for the specific identifier
755 * Returns 1 if successful, 0 if no value was found or -1 on error
756 */
libpff_index_tree_get_value_by_identifier(libfdata_tree_t * index_tree,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,int value_index,libpff_index_value_t ** index_value,libcerror_error_t ** error)757 int libpff_index_tree_get_value_by_identifier(
758 libfdata_tree_t *index_tree,
759 libbfio_handle_t *file_io_handle,
760 libfcache_cache_t *cache,
761 uint64_t identifier,
762 int value_index,
763 libpff_index_value_t **index_value,
764 libcerror_error_t **error )
765 {
766 libfdata_tree_node_t *leaf_index_tree_node = NULL;
767 static char *function = "libpff_index_tree_get_value_by_identifier";
768 int result = 0;
769
770 result = libpff_index_tree_get_leaf_node_by_identifier(
771 index_tree,
772 file_io_handle,
773 cache,
774 identifier,
775 &value_index,
776 &leaf_index_tree_node,
777 error );
778
779 if( result == -1 )
780 {
781 libcerror_error_set(
782 error,
783 LIBCERROR_ERROR_DOMAIN_RUNTIME,
784 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
785 "%s: unable to retrieve leaf node by identifier in root node.",
786 function );
787
788 return( -1 );
789 }
790 else if( result != 0 )
791 {
792 if( leaf_index_tree_node == NULL )
793 {
794 libcerror_error_set(
795 error,
796 LIBCERROR_ERROR_DOMAIN_RUNTIME,
797 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
798 "%s: missing leaf index tree node.",
799 function );
800
801 return( -1 );
802 }
803 if( libfdata_tree_node_get_node_value(
804 leaf_index_tree_node,
805 (intptr_t *) file_io_handle,
806 cache,
807 (intptr_t **) index_value,
808 0,
809 error ) != 1 )
810 {
811 libcerror_error_set(
812 error,
813 LIBCERROR_ERROR_DOMAIN_RUNTIME,
814 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
815 "%s: unable to retrieve leaf index tree node value.",
816 function );
817
818 return( -1 );
819 }
820 }
821 return( result );
822 }
823
824 /* Retrieves the upper branch node for the specific identifier
825 * Returns 1 if successful, 0 if no value was found or -1 on error
826 */
libpff_index_tree_node_get_upper_branch_node_by_identifier(libfdata_tree_node_t * index_tree_node,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,libfdata_tree_node_t ** upper_branch_index_tree_node,libcerror_error_t ** error)827 int libpff_index_tree_node_get_upper_branch_node_by_identifier(
828 libfdata_tree_node_t *index_tree_node,
829 libbfio_handle_t *file_io_handle,
830 libfcache_cache_t *cache,
831 uint64_t identifier,
832 libfdata_tree_node_t **upper_branch_index_tree_node,
833 libcerror_error_t **error )
834 {
835 libfdata_tree_node_t *index_tree_sub_node = NULL;
836 libpff_index_value_t *index_tree_sub_node_value = NULL;
837 static char *function = "libpff_index_tree_node_get_upper_branch_node_by_identifier";
838 int16_t compare = 0;
839 int number_of_sub_nodes = 0;
840 int result = 0;
841 int sub_node_index = 0;
842
843 if( index_tree_node == NULL )
844 {
845 libcerror_error_set(
846 error,
847 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
848 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
849 "%s: invalid index tree node.",
850 function );
851
852 return( -1 );
853 }
854 if( upper_branch_index_tree_node == NULL )
855 {
856 libcerror_error_set(
857 error,
858 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
859 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
860 "%s: invalid upper branch index tree node.",
861 function );
862
863 return( -1 );
864 }
865 if( libfdata_tree_node_get_number_of_sub_nodes(
866 index_tree_node,
867 (intptr_t *) file_io_handle,
868 cache,
869 &number_of_sub_nodes,
870 0,
871 error ) != 1 )
872 {
873 libcerror_error_set(
874 error,
875 LIBCERROR_ERROR_DOMAIN_RUNTIME,
876 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
877 "%s: unable to retrieve number of sub nodes from index tree node.",
878 function );
879
880 return( -1 );
881 }
882 if( number_of_sub_nodes == 0 )
883 {
884 result = libfdata_tree_node_is_leaf(
885 index_tree_node,
886 (intptr_t *) file_io_handle,
887 cache,
888 0,
889 error );
890
891 if( result == -1 )
892 {
893 libcerror_error_set(
894 error,
895 LIBCERROR_ERROR_DOMAIN_RUNTIME,
896 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
897 "%s: unable to determine if index tree node is a leaf node.",
898 function,
899 sub_node_index );
900
901 return( -1 );
902 }
903 else if( result != 0 )
904 {
905 return( 0 );
906 }
907 result = libfdata_tree_node_is_deleted(
908 index_tree_node,
909 error );
910
911 if( result == -1 )
912 {
913 libcerror_error_set(
914 error,
915 LIBCERROR_ERROR_DOMAIN_RUNTIME,
916 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
917 "%s: unable to determine if index tree node is deleted.",
918 function,
919 sub_node_index );
920
921 return( -1 );
922 }
923 else if( result != 0 )
924 {
925 return( 0 );
926 }
927 if( *upper_branch_index_tree_node != NULL )
928 {
929 libcerror_error_set(
930 error,
931 LIBCERROR_ERROR_DOMAIN_RUNTIME,
932 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
933 "%s: upper branch index tree node value already set.",
934 function );
935
936 return( -1 );
937 }
938 *upper_branch_index_tree_node = index_tree_node;
939
940 return( 1 );
941 }
942 for( sub_node_index = 0;
943 sub_node_index < number_of_sub_nodes;
944 sub_node_index++ )
945 {
946 if( libfdata_tree_node_get_sub_node_by_index(
947 index_tree_node,
948 (intptr_t *) file_io_handle,
949 cache,
950 sub_node_index,
951 &index_tree_sub_node,
952 0,
953 error ) != 1 )
954 {
955 libcerror_error_set(
956 error,
957 LIBCERROR_ERROR_DOMAIN_RUNTIME,
958 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
959 "%s: unable to retrieve sub node: %d from index tree node.",
960 function,
961 sub_node_index );
962
963 return( -1 );
964 }
965 if( libfdata_tree_node_get_node_value(
966 index_tree_sub_node,
967 (intptr_t *) file_io_handle,
968 cache,
969 (intptr_t **) &index_tree_sub_node_value,
970 0,
971 error ) != 1 )
972 {
973 libcerror_error_set(
974 error,
975 LIBCERROR_ERROR_DOMAIN_RUNTIME,
976 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
977 "%s: unable to retrieve index tree sub node value: %d.",
978 function,
979 sub_node_index );
980
981 return( -1 );
982 }
983 if( index_tree_sub_node_value == NULL )
984 {
985 libcerror_error_set(
986 error,
987 LIBCERROR_ERROR_DOMAIN_RUNTIME,
988 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
989 "%s: missing index tree sub node value: %d.",
990 function,
991 sub_node_index );
992
993 return( -1 );
994 }
995 #if defined( HAVE_DEBUG_OUTPUT )
996 if( libcnotify_verbose != 0 )
997 {
998 libcnotify_printf(
999 "%s: index tree sub node value: %d identifier\t: 0x%08" PRIx64 " (%" PRIu64 ").\n",
1000 function,
1001 sub_node_index,
1002 index_tree_sub_node_value->identifier,
1003 index_tree_sub_node_value->identifier );
1004 }
1005 #endif
1006 if( identifier > index_tree_sub_node_value->identifier )
1007 {
1008 compare = 1;
1009 }
1010 else if( identifier < index_tree_sub_node_value->identifier )
1011 {
1012 compare = -1;
1013 }
1014 else
1015 {
1016 compare = 0;
1017 }
1018 result = libfdata_tree_node_is_leaf(
1019 index_tree_sub_node,
1020 (intptr_t *) file_io_handle,
1021 cache,
1022 0,
1023 error );
1024
1025 if( result == -1 )
1026 {
1027 libcerror_error_set(
1028 error,
1029 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1030 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1031 "%s: unable to determine if index tree sub node: %d is a leaf node.",
1032 function,
1033 sub_node_index );
1034
1035 return( -1 );
1036 }
1037 else if( result != 0 )
1038 {
1039 result = libfdata_tree_node_is_deleted(
1040 index_tree_sub_node,
1041 error );
1042
1043 if( result == -1 )
1044 {
1045 libcerror_error_set(
1046 error,
1047 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1048 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1049 "%s: unable to determine if index tree sub node: %d is a deleted node.",
1050 function,
1051 sub_node_index );
1052
1053 return( -1 );
1054 }
1055 else if( result == 0 )
1056 {
1057 if( compare == 0 )
1058 {
1059 if( *upper_branch_index_tree_node != NULL )
1060 {
1061 libcerror_error_set(
1062 error,
1063 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1064 LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
1065 "%s: upper branch index tree node value already set.",
1066 function );
1067
1068 return( -1 );
1069 }
1070 *upper_branch_index_tree_node = index_tree_node;
1071
1072 result = 1;
1073
1074 break;
1075 }
1076 }
1077 result = 0;
1078 }
1079 else
1080 {
1081 /* A branch node contains the identifier of its first sub node
1082 */
1083 if( ( compare == 0 )
1084 || ( ( compare > 0 )
1085 && ( sub_node_index == ( number_of_sub_nodes - 1 ) ) ) )
1086 {
1087 result = libpff_index_tree_node_get_upper_branch_node_by_identifier(
1088 index_tree_sub_node,
1089 file_io_handle,
1090 cache,
1091 identifier,
1092 upper_branch_index_tree_node,
1093 error );
1094
1095 if( result == -1 )
1096 {
1097 libcerror_error_set(
1098 error,
1099 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1100 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1101 "%s: unable to retrieve upper branch index tree node by identifier in sub node: %d.",
1102 function,
1103 sub_node_index );
1104
1105 return( -1 );
1106 }
1107 else if( result == 0 )
1108 {
1109 if( *upper_branch_index_tree_node == NULL )
1110 {
1111 *upper_branch_index_tree_node = index_tree_sub_node;
1112
1113 result = 1;
1114 }
1115 }
1116 break;
1117 }
1118 else if( ( compare < 0 )
1119 && ( sub_node_index >= 1 ) )
1120 {
1121 if( libfdata_tree_node_get_sub_node_by_index(
1122 index_tree_node,
1123 (intptr_t *) file_io_handle,
1124 cache,
1125 sub_node_index - 1,
1126 &index_tree_sub_node,
1127 0,
1128 error ) != 1 )
1129 {
1130 libcerror_error_set(
1131 error,
1132 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1133 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1134 "%s: unable to retrieve sub node: %d from index tree node.",
1135 function,
1136 sub_node_index - 1 );
1137
1138 return( -1 );
1139 }
1140 result = libpff_index_tree_node_get_upper_branch_node_by_identifier(
1141 index_tree_sub_node,
1142 file_io_handle,
1143 cache,
1144 identifier,
1145 upper_branch_index_tree_node,
1146 error );
1147
1148 if( result == -1 )
1149 {
1150 libcerror_error_set(
1151 error,
1152 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1153 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1154 "%s: unable to retrieve upper branch index tree node by identifier in sub node: %d.",
1155 function,
1156 sub_node_index - 1 );
1157
1158 return( -1 );
1159 }
1160 else if( result == 0 )
1161 {
1162 if( *upper_branch_index_tree_node == NULL )
1163 {
1164 *upper_branch_index_tree_node = index_tree_sub_node;
1165
1166 result = 1;
1167 }
1168 }
1169 break;
1170 }
1171 }
1172 }
1173 if( result == 0 )
1174 {
1175 if( *upper_branch_index_tree_node == NULL )
1176 {
1177 *upper_branch_index_tree_node = index_tree_node;
1178
1179 result = 1;
1180 }
1181 }
1182 return( result );
1183 }
1184
1185 /* Inserts an index value to the index tree
1186 * Returns 1 if successful or -1 on error
1187 */
libpff_index_tree_insert_value(libfdata_tree_t * index_tree,libbfio_handle_t * file_io_handle,libfcache_cache_t * cache,uint64_t identifier,off64_t node_data_offset,size64_t node_data_size,libcerror_error_t ** error)1188 int libpff_index_tree_insert_value(
1189 libfdata_tree_t *index_tree,
1190 libbfio_handle_t *file_io_handle,
1191 libfcache_cache_t *cache,
1192 uint64_t identifier,
1193 off64_t node_data_offset,
1194 size64_t node_data_size,
1195 libcerror_error_t **error )
1196 {
1197 libfdata_tree_node_t *index_tree_branch_node = NULL;
1198 libfdata_tree_node_t *index_tree_root_node = NULL;
1199 libpff_index_value_t *index_tree_branch_node_value = NULL;
1200 static char *function = "libpff_index_tree_insert_value";
1201 int number_of_sub_nodes = 0;
1202 int sub_node_index = 0;
1203
1204 if( index_tree == NULL )
1205 {
1206 libcerror_error_set(
1207 error,
1208 LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
1209 LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
1210 "%s: invalid index tree.",
1211 function );
1212
1213 return( -1 );
1214 }
1215 if( libfdata_tree_get_root_node(
1216 index_tree,
1217 &index_tree_root_node,
1218 error ) != 1 )
1219 {
1220 libcerror_error_set(
1221 error,
1222 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1223 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1224 "%s: unable to retrieve root node from index tree.",
1225 function );
1226
1227 return( -1 );
1228 }
1229 if( libpff_index_tree_node_get_upper_branch_node_by_identifier(
1230 index_tree_root_node,
1231 file_io_handle,
1232 cache,
1233 identifier,
1234 &index_tree_branch_node,
1235 error ) != 1 )
1236 {
1237 libcerror_error_set(
1238 error,
1239 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1240 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1241 "%s: unable to retrieve upper branch index tree node by identifier: %" PRIu64 ".",
1242 function,
1243 identifier );
1244
1245 return( -1 );
1246 }
1247 if( libfdata_tree_node_get_number_of_sub_nodes(
1248 index_tree_branch_node,
1249 (intptr_t *) file_io_handle,
1250 cache,
1251 &number_of_sub_nodes,
1252 0,
1253 error ) != 1 )
1254 {
1255 libcerror_error_set(
1256 error,
1257 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1258 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1259 "%s: unable to retrieve number of sub nodes of branch node.",
1260 function );
1261
1262 return( -1 );
1263 }
1264 if( number_of_sub_nodes >= 512 )
1265 {
1266 if( libfdata_tree_node_get_node_value(
1267 index_tree_branch_node,
1268 (intptr_t *) file_io_handle,
1269 cache,
1270 (intptr_t **) &index_tree_branch_node_value,
1271 0,
1272 error ) != 1 )
1273 {
1274 libcerror_error_set(
1275 error,
1276 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1277 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1278 "%s: unable to retrieve index tree branch node value.",
1279 function );
1280
1281 return( -1 );
1282 }
1283 if( index_tree_branch_node_value == NULL )
1284 {
1285 libcerror_error_set(
1286 error,
1287 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1288 LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
1289 "%s: missing index tree branch node value.",
1290 function,
1291 sub_node_index );
1292
1293 return( -1 );
1294 }
1295 #if defined( HAVE_DEBUG_OUTPUT )
1296 if( libcnotify_verbose != 0 )
1297 {
1298 libcnotify_printf(
1299 "%s: index tree branch node value identifier\t: 0x%08" PRIx64 " (%" PRIu64 ").\n",
1300 function,
1301 index_tree_branch_node_value->identifier,
1302 index_tree_branch_node_value->identifier );
1303 }
1304 #endif
1305 if( libfdata_tree_node_split_sub_nodes(
1306 index_tree_branch_node,
1307 32,
1308 error ) != 1 )
1309 {
1310 libcerror_error_set(
1311 error,
1312 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1313 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
1314 "%s: unable to split index tree branch node value.",
1315 function );
1316
1317 return( -1 );
1318 }
1319 index_tree_root_node = index_tree_branch_node;
1320 index_tree_branch_node = NULL;
1321
1322 if( libpff_index_tree_node_get_upper_branch_node_by_identifier(
1323 index_tree_root_node,
1324 file_io_handle,
1325 cache,
1326 identifier,
1327 &index_tree_branch_node,
1328 error ) != 1 )
1329 {
1330 libcerror_error_set(
1331 error,
1332 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1333 LIBCERROR_RUNTIME_ERROR_GET_FAILED,
1334 "%s: unable to retrieve upper branch index tree node by identifier: %" PRIu64 ".",
1335 function,
1336 identifier );
1337
1338 return( -1 );
1339 }
1340 }
1341 if( libfdata_tree_node_insert_sub_node(
1342 index_tree_branch_node,
1343 (intptr_t *) file_io_handle,
1344 cache,
1345 &sub_node_index,
1346 0,
1347 node_data_offset,
1348 node_data_size,
1349 0,
1350 (int (*)(intptr_t *, intptr_t *, libcerror_error_t **)) &libpff_index_value_compare,
1351 LIBFDATA_TREE_NODE_INSERT_FLAG_NON_UNIQUE_SUB_NODE_VALUES,
1352 0,
1353 error ) != 1 )
1354 {
1355 libcerror_error_set(
1356 error,
1357 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1358 LIBCERROR_RUNTIME_ERROR_APPEND_FAILED,
1359 "%s: unable to insert index value: %" PRIu64 " in branch index tree node.",
1360 function,
1361 identifier );
1362
1363 return( -1 );
1364 }
1365 if( libfdata_tree_node_set_leaf_sub_node(
1366 index_tree_branch_node,
1367 sub_node_index,
1368 error ) != 1 )
1369 {
1370 libcerror_error_set(
1371 error,
1372 LIBCERROR_ERROR_DOMAIN_RUNTIME,
1373 LIBCERROR_RUNTIME_ERROR_SET_FAILED,
1374 "%s: unable to set leaf in index tree sub node: %d.",
1375 function,
1376 sub_node_index );
1377
1378 return( -1 );
1379 }
1380 return( 1 );
1381 }
1382
1383