diff options
Diffstat (limited to 'base/data-struct/radix-tree-adaptive.c')
-rw-r--r-- | base/data-struct/radix-tree-adaptive.c | 48 |
1 files changed, 37 insertions, 11 deletions
diff --git a/base/data-struct/radix-tree-adaptive.c b/base/data-struct/radix-tree-adaptive.c index 1eef1f896..cd53dd600 100644 --- a/base/data-struct/radix-tree-adaptive.c +++ b/base/data-struct/radix-tree-adaptive.c @@ -581,12 +581,11 @@ static void _degrade_to_n16(struct node48 *n48, struct value *result) for (i = 0; i < 256; i++) { if (n48->keys[i] < 48) { n16->keys[count] = i; + n16->values[count] = n48->values[n48->keys[i]]; count++; } } - memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values)); - free(n48); result->type = NODE16; @@ -598,16 +597,16 @@ static void _degrade_to_n48(struct node256 *n256, struct value *result) unsigned i, count = 0; struct node48 *n48 = zalloc(sizeof(*n48)); - memset(n48->keys, 48, sizeof(n48->keys)); - n48->nr_entries = n256->nr_entries; for (i = 0; i < 256; i++) { if (n256->values[i].type == UNSET) - continue; + n48->keys[i] = 48; - n48->keys[i] = count; - n48->values[count] = n256->values[i]; - count++; + else { + n48->keys[i] = count; + n48->values[count] = n256->values[i]; + count++; + } } free(n256); @@ -1036,6 +1035,7 @@ void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, static bool _check_nodes(struct value *v, unsigned *count) { + uint64_t bits; unsigned i, ncount; struct value_chain *vc; struct prefix_chain *pc; @@ -1090,22 +1090,47 @@ static bool _check_nodes(struct value *v, unsigned *count) return true; case NODE48: + bits = 0; n48 = v->value.ptr; ncount = 0; for (i = 0; i < 256; i++) { if (n48->keys[i] < 48) { + if (n48->keys[i] >= n48->nr_entries) { + fprintf(stderr, "referencing value past nr_entries (n48)\n"); + return false; + } + + if (bits & (1ull << n48->keys[i])) { + fprintf(stderr, "duplicate entry (n48) %u\n", (unsigned) n48->keys[i]); + return false; + } + bits = bits | (1ull << n48->keys[i]); ncount++; + if (!_check_nodes(n48->values + n48->keys[i], count)) return false; } } + for (i = 0; i < n48->nr_entries; i++) { + if (!(bits & (1ull << i))) { + fprintf(stderr, "not all values are referenced (n48)\n"); + return false; + } + } + if (ncount != n48->nr_entries) { fprintf(stderr, "incorrect number of entries in n48, n48->nr_entries = %u, actual = %u\n", n48->nr_entries, ncount); return false; } + for (i = 0; i < n48->nr_entries; i++) + if (n48->values[i].type == UNSET) { + fprintf(stderr, "value in UNSET (n48)\n"); + return false; + } + for (i = n48->nr_entries; i < 48; i++) if (n48->values[i].type != UNSET) { fprintf(stderr, "unused value is not UNSET (n48)\n"); @@ -1234,9 +1259,10 @@ static void _dump(FILE *out, struct value v, unsigned indent) fprintf(out, "%x ", i); fprintf(out, ">\n"); - for (i = 0; i < 256; i++) - if (n48->keys[i] < 48) - _dump(out, n48->values[i], indent + 1); + for (i = 0; i < n48->nr_entries; i++) { + assert(n48->values[i].type != UNSET); + _dump(out, n48->values[i], indent + 1); + } break; case NODE256: |