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 <adas@xxxxxxxxxx>
---
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
--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
