Scroll to navigation

MTREE_DIFF_SUBTREE(3) Librecast Programmer's Manual MTREE_DIFF_SUBTREE(3)


mtree_diff_subtree - compare two subtrees and return bitmap


Librecast library (liblibrecast, -llibrecast)


#include <librecast/mtree.h>
unsigned char *mtree_diff_subtree(mtree_t *t1, mtree_t *t2, size_t root, unsigned bits);
unsigned char *mtree_diff_map(mtree_t *t1, mtree_t *t2);

Compile and link with -llibrecast.


The mtree_diff_subtree function performs a bredth-first comparison of the merkle trees t1 and t2 and returns a pointer to a bitmap, setting bits bits for any chunks that differ. bits should be set to the number of packets required to to transport each chunk. When bits > 1, chunks will be fragmented into multiple packets, and the bitmap will represent the packets required.

Checking the popcount (Hamming Weight) of the returned bitmap gives the number of packets required to patch the differences.

The returned bitmap must be freed by the caller when no longer needed by passing to free(3).

mtree_diff_map() is a convenience wrapper that is the same as calling mtree_diff_subtree() with root set to zero (whole tree) and bits set to one. Thus, it returns a bitmap of the entire tree with a single bit per chunk.


mtree_verify() returns zero if the tree is valid, or NULL on error, with errno set to indicate the error.


Not enough space/cannot allocate memory (POSIX.1-2001).


mtree_init(3), mtree_free(3), mtree_build(3), free(3)

2023-06-20 LIBRECAST