diff options
author | Kent Overstreet <kent.overstreet@gmail.com> | 2017-05-08 02:28:15 -0800 |
---|---|---|
committer | Kent Overstreet <kent.overstreet@gmail.com> | 2017-05-08 06:57:17 -0800 |
commit | 63065c01285601afbe2457e92729efc11581e37d (patch) | |
tree | 8e37af7dcd60f0a260536064f4c6ec0c5dc24a06 /libbcachefs/util.c | |
parent | e57a624feb82e6d1bb8bd77c0f185939b1367b19 (diff) |
Update bcachefs sources to 9ceb982d77 bcachefs: Store bucket gens in a btree
Diffstat (limited to 'libbcachefs/util.c')
-rw-r--r-- | libbcachefs/util.c | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/libbcachefs/util.c b/libbcachefs/util.c index 5400dec5..906e7a6b 100644 --- a/libbcachefs/util.c +++ b/libbcachefs/util.c @@ -533,3 +533,47 @@ void eytzinger0_sort(void *base, size_t n, size_t size, } } } + +void sort_cmp_size(void *base, size_t num, size_t size, + int (*cmp_func)(const void *, const void *, size_t), + void (*swap_func)(void *, void *, size_t size)) +{ + /* pre-scale counters for performance */ + int i = (num/2 - 1) * size, n = num * size, c, r; + + if (!swap_func) { + if (size == 4 && alignment_ok(base, 4)) + swap_func = u32_swap; + else if (size == 8 && alignment_ok(base, 8)) + swap_func = u64_swap; + else + swap_func = generic_swap; + } + + /* heapify */ + for ( ; i >= 0; i -= size) { + for (r = i; r * 2 + size < n; r = c) { + c = r * 2 + size; + if (c < n - size && + cmp_func(base + c, base + c + size, size) < 0) + c += size; + if (cmp_func(base + r, base + c, size) >= 0) + break; + swap_func(base + r, base + c, size); + } + } + + /* sort */ + for (i = n - size; i > 0; i -= size) { + swap_func(base, base + i, size); + for (r = 0; r * 2 + size < i; r = c) { + c = r * 2 + size; + if (c < i - size && + cmp_func(base + c, base + c + size, size) < 0) + c += size; + if (cmp_func(base + r, base + c, size) >= 0) + break; + swap_func(base + r, base + c, size); + } + } +} |