diff options
| author | Vivien Kraus <vivien@planete-kraus.eu> | 2023-04-10 00:31:30 +0200 |
|---|---|---|
| committer | Vivien Kraus <vivien@planete-kraus.eu> | 2023-04-29 11:58:03 +0200 |
| commit | a7eabc052607333e19379a769ac2002089aac6e0 (patch) | |
| tree | 19033d19a75d674c2f84e35c1a37842b340774a2 | |
| parent | 73a5639a652406e04f4157103de674355207ecc8 (diff) | |
trie node: if a branch has only 0s, it is considered empty
| -rw-r--r-- | src/libdisfluid/disfluid-tests.h | 7 | ||||
| -rw-r--r-- | src/libdisfluid/disfluid-trie-node.h | 19 |
2 files changed, 18 insertions, 8 deletions
diff --git a/src/libdisfluid/disfluid-tests.h b/src/libdisfluid/disfluid-tests.h index c949940..730739e 100644 --- a/src/libdisfluid/disfluid-tests.h +++ b/src/libdisfluid/disfluid-tests.h @@ -467,11 +467,8 @@ START_TEST (test_db_trie_inner) ck_assert_int_eq (memcmp (actual_common_part._data, common_part._data, common_part._nbytes), 0); - ck_assert_int_eq (actual_branches[0]._nbytes, 32); - for (size_t i = 0; i < 32; i++) - { - ck_assert_int_eq (actual_branches[0]._data[i], 0); - } + ck_assert_int_eq (actual_branches[0]._nbytes, 0); + ck_assert_ptr_null (actual_branches[0]._data); ck_assert_int_eq (actual_branches[1]._nbytes, 32); ck_assert_int_eq (memcmp (actual_branches[1]._data, series, 32), 0); FREE (actual_common_part._data); diff --git a/src/libdisfluid/disfluid-trie-node.h b/src/libdisfluid/disfluid-trie-node.h index 855a236..39f27e0 100644 --- a/src/libdisfluid/disfluid-trie-node.h +++ b/src/libdisfluid/disfluid-trie-node.h @@ -83,7 +83,9 @@ cleanup: /* - the common part length, on 1 byte, minimum 1, maximum 251; */ /* - the common part bytes, padded with 0s for 251 bytes; */ /* - if this is a leaf node: 32 bytes for the ID of the content; */ -/* - if this is a non-leaf node: 256 * 32 bytes for the ID of the branches. */ +/* - if this is a non-leaf node: 256 * 32 bytes for the ID of the + branches. If an entry has 32 zeros, then it is considered + free. */ static int db_read_trie_node (const char *db_root, @@ -110,7 +112,7 @@ db_read_trie_node (const char *db_root, goto cleanup; } common_part->_nbytes = (uint8_t) (char) raw_data._data[4]; - if (common_part->_nbytes < 1 || common_part->_nbytes > 251) + if (common_part->_nbytes > 251) { error = -1; goto cleanup; @@ -145,6 +147,17 @@ db_read_trie_node (const char *db_root, goto cleanup; } memcpy (branches[i]._data, raw_data._data + 256 + (i * 32), 32); + size_t n_zero = 0; + while (n_zero < branches[i]._nbytes + && branches[i]._data[n_zero] == 0) + { + n_zero++; + } + if (n_zero == branches[i]._nbytes) + { + FREE (branches[i]._data); + branches[i]._nbytes = 0; + } } } else @@ -176,7 +189,7 @@ db_write_trie_node_aux (const char *db_root, { assert (id->_data == NULL); int error = 0; - if (common_part._nbytes == 0 || common_part._nbytes > 251) + if (common_part._nbytes > 251) { error = -1; goto cleanup; |