This is essentially a copy of the sort function and its helpers from lib/sort.c with the exception of an additional 'void *opaque' parameter added here. custom cmp_func and swap_func functions can make use of the opaque field for relevant context
Signed-off-by: Abhi Das <[email protected]> --- fs/gfs2/util.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/gfs2/util.h | 4 ++++ 2 files changed, 59 insertions(+) diff --git a/fs/gfs2/util.c b/fs/gfs2/util.c index 7345489..2c1aee3 100644 --- a/fs/gfs2/util.c +++ b/fs/gfs2/util.c @@ -562,3 +562,58 @@ void vp_reset(struct vbuf *vb) if (vpx) vpx->vp_top = vpx->vp_baseptr; } + +/* heap sort that takes an opaque context - directly copied from lib/sort.c */ +static void u32_swap(void *opaque, void *a, void *b, int size) +{ + u32 t = *(u32 *)a; + *(u32 *)a = *(u32 *)b; + *(u32 *)b = t; +} + +static void generic_swap(void *opaque, void *a, void *b, int size) +{ + char t; + do { + t = *(char *)a; + *(char *)a++ = *(char *)b; + *(char *)b++ = t; + } while (--size > 0); +} + +void ctx_sort(void *opaque, void *base, size_t num, size_t size, + int (*cmp_func)(void *, const void *, const void *), + void (*swap_func)(void *, void *, void *, int size)) +{ + int i = (num/2 - 1) * size, n = num * size, c, r; + + if (!swap_func) + swap_func = (size == 4 ? u32_swap : 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(opaque, base + c, base + c + size) < 0) + c += size; + if (cmp_func(opaque, base + r, base + c) >= 0) + break; + swap_func(opaque, base + r, base + c, size); + } + } + + /* sort */ + for (i = n - size; i > 0; i -= size) { + swap_func(opaque, base, base + i, size); + for (r = 0; r * 2 + size < i; r = c) { + c = r * 2 + size; + if (c < i - size && + cmp_func(opaque, base + c, base + c + size) < 0) + c += size; + if (cmp_func(opaque, base + r, base + c) >= 0) + break; + swap_func(opaque, base + r, base + c, size); + } + } +} diff --git a/fs/gfs2/util.h b/fs/gfs2/util.h index 40fb692..3e10d72 100644 --- a/fs/gfs2/util.h +++ b/fs/gfs2/util.h @@ -210,5 +210,9 @@ int vp_read(struct vbuf *vb, void *to, const void *from, size_t count); int vp_write(struct vbuf *vb, void *to, const void *from, size_t count); int vp_append(struct vbuf *vb, const void *from, size_t count); int vp_memset(struct vbuf *vb, void *to, int c, size_t count); + +void ctx_sort(void *opaque, void *base, size_t num, size_t size, + int (*cmp_func)(void *, const void *, const void *), + void (*swap_func)(void *, void *, void *, int size)); #endif /* __UTIL_DOT_H__ */ -- 1.8.1.4
