diff options
| author | Nick Terrell <terrelln@fb.com> | 2022-12-13 16:21:55 -0800 |
|---|---|---|
| committer | Nick Terrell <terrelln@fb.com> | 2022-12-13 16:21:55 -0800 |
| commit | 4f2c0a4acffbec01079c28f839422e64ddeff004 (patch) | |
| tree | 06ada4a8a6d94a94c93944806041b8c994cebfc5 /lib/assoc_array.c | |
| parent | 88a309465b3f05a100c3b81966982c0f9f5d23a6 (diff) | |
| parent | 830b3c68c1fb1e9176028d02ef86f3cf76aa2476 (diff) | |
Merge branch 'main' into zstd-linus
Diffstat (limited to 'lib/assoc_array.c')
| -rw-r--r-- | lib/assoc_array.c | 8 |
1 files changed, 8 insertions, 0 deletions
diff --git a/lib/assoc_array.c b/lib/assoc_array.c index 079c72e26493..ca0b4f360c1a 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -1461,6 +1461,7 @@ int assoc_array_gc(struct assoc_array *array, struct assoc_array_ptr *cursor, *ptr; struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp; unsigned long nr_leaves_on_tree; + bool retained; int keylen, slot, nr_free, next_slot, i; pr_devel("-->%s()\n", __func__); @@ -1536,6 +1537,7 @@ continue_node: goto descend; } +retry_compress: pr_devel("-- compress node %p --\n", new_n); /* Count up the number of empty slots in this node and work out the @@ -1553,6 +1555,7 @@ continue_node: pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch); /* See what we can fold in */ + retained = false; next_slot = 0; for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) { struct assoc_array_shortcut *s; @@ -1602,9 +1605,14 @@ continue_node: pr_devel("[%d] retain node %lu/%d [nx %d]\n", slot, child->nr_leaves_on_branch, nr_free + 1, next_slot); + retained = true; } } + if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) { + pr_devel("internal nodes remain despite enough space, retrying\n"); + goto retry_compress; + } pr_devel("after: %lu\n", new_n->nr_leaves_on_branch); nr_leaves_on_tree = new_n->nr_leaves_on_branch; |