From: Abhi Das <adas@redhat.com> To: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, cluster-devel@redhat.com Cc: Abhi Das <adas@redhat.com> Subject: [RFC PATCH 4/5] gfs2: Add sort functionality with extra parameter Date: Fri, 25 Jul 2014 12:38:07 -0500 [thread overview] Message-ID: <1406309888-10749-5-git-send-email-adas@redhat.com> (raw) In-Reply-To: <1406309888-10749-1-git-send-email-adas@redhat.com> 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@redhat.com> --- 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
WARNING: multiple messages have this Message-ID (diff)
From: Abhi Das <adas@redhat.com> To: cluster-devel.redhat.com Subject: [Cluster-devel] [RFC PATCH 4/5] gfs2: Add sort functionality with extra parameter Date: Fri, 25 Jul 2014 12:38:07 -0500 [thread overview] Message-ID: <1406309888-10749-5-git-send-email-adas@redhat.com> (raw) In-Reply-To: <1406309888-10749-1-git-send-email-adas@redhat.com> 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@redhat.com> --- 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
next prev parent reply other threads:[~2014-07-25 17:38 UTC|newest] Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top 2014-07-25 17:38 [RFC PATCH 0/5] xgetdents system call Abhi Das 2014-07-25 17:38 ` [Cluster-devel] " Abhi Das 2014-07-25 17:38 ` [RFC PATCH 1/5] fs: xstat system call VFS bits Abhi Das 2014-07-25 17:38 ` [Cluster-devel] " Abhi Das 2014-07-25 17:38 ` Abhi Das 2014-07-25 18:17 ` [Cluster-devel] " Bob Peterson 2014-07-25 18:17 ` Bob Peterson 2014-07-25 17:38 ` [RFC PATCH 2/5] fs: Add xgetdents system call and xreaddir file operation Abhi Das 2014-07-25 17:38 ` [Cluster-devel] " Abhi Das 2014-07-25 17:38 ` Abhi Das 2014-07-29 8:20 ` Michael Kerrisk 2014-07-29 8:20 ` [Cluster-devel] " Michael Kerrisk 2014-07-29 8:20 ` Michael Kerrisk 2014-07-25 17:38 ` [RFC PATCH 3/5] gfs2: Add a dynamic buffer backed by a vector of pages Abhi Das 2014-07-25 17:38 ` [Cluster-devel] " Abhi Das 2014-07-25 17:38 ` Abhi Das 2014-07-25 18:42 ` [Cluster-devel] " Bob Peterson 2014-07-25 18:42 ` Bob Peterson 2014-07-25 17:38 ` Abhi Das [this message] 2014-07-25 17:38 ` [Cluster-devel] [RFC PATCH 4/5] gfs2: Add sort functionality with extra parameter Abhi Das 2014-07-25 17:38 ` [RFC PATCH 5/5] gfs2: Add xreaddir file operation and supporting functions Abhi Das 2014-07-25 17:38 ` [Cluster-devel] " Abhi Das 2014-07-29 18:58 ` Jonathan Corbet 2014-07-29 18:58 ` [Cluster-devel] " Jonathan Corbet 2014-07-29 22:25 ` Abhijith Das 2014-07-29 22:25 ` [Cluster-devel] " Abhijith Das 2014-07-30 9:06 ` Steven Whitehouse 2014-07-30 13:57 ` Jonathan Corbet 2014-07-30 13:57 ` [Cluster-devel] " Jonathan Corbet 2014-07-29 8:18 ` [RFC PATCH 0/5] xgetdents system call Michael Kerrisk 2014-07-29 8:18 ` [Cluster-devel] " Michael Kerrisk 2014-07-29 8:18 ` Michael Kerrisk
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1406309888-10749-5-git-send-email-adas@redhat.com \ --to=adas@redhat.com \ --cc=cluster-devel@redhat.com \ --cc=linux-fsdevel@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.