HFS+: add custom dentry hash and comparison operations

Add custom dentry hash and comparison operations for HFS+ filesystems that are
case-insensitive and/or do automatic unicode decomposition.  The new
operations reuse the existing HFS+ ASCII to unicode conversion, unicode
decomposition and case folding functionality.

Signed-off-by: Duane Griffin <duaneg@dghda.com>
Signed-off-by: Roman Zippel <zippel@linux-m68k.org>

Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 123 insertions, 0 deletions

diff --git a/fs/hfsplus/unicode.c b/fs/hfsplus/unicode.c
index 5df0052b277..9e10f9444b6 100644
--- a/fs/hfsplus/unicode.c
+++ b/fs/hfsplus/unicode.c
@@ -314,3 +314,126 @@ int hfsplus_asc2uni(struct super_block *sb, struct hfsplus_unistr *ustr,
                 return -ENAMETOOLONG;
         return 0;
 }
+
+/*
+ * Hash a string to an integer as appropriate for the HFS+ filesystem.
+ * Composed unicode characters are decomposed and case-folding is performed
+ * if the appropriate bits are (un)set on the superblock.
+ */
+int hfsplus_hash_dentry(struct dentry *dentry, struct qstr *str)
+{
+        struct super_block *sb = dentry->d_sb;
+        const char *astr;
+        const u16 *dstr;
+        int casefold, decompose, size, dsize, len;
+        unsigned long hash;
+        wchar_t c;
+        u16 c2;
+
+        casefold = (HFSPLUS_SB(sb).flags & HFSPLUS_SB_CASEFOLD);
+        decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
+        hash = init_name_hash();
+        astr = str->name;
+        len = str->len;
+        while (len > 0) {
+                size = asc2unichar(sb, astr, len, &c);
+                astr += size;
+                len -= size;
+
+                if (decompose && (dstr = decompose_unichar(c, &dsize))) {
+                        do {
+                                c2 = *dstr++;
+                                if (!casefold || (c2 = case_fold(c2)))
+                                        hash = partial_name_hash(c2, hash);
+                        } while (--dsize > 0);
+                } else {
+                        c2 = c;
+                        if (!casefold || (c2 = case_fold(c2)))
+                                hash = partial_name_hash(c2, hash);
+                }
+        }
+        str->hash = end_name_hash(hash);
+
+        return 0;
+}
+
+/*
+ * Compare strings with HFS+ filename ordering.
+ * Composed unicode characters are decomposed and case-folding is performed
+ * if the appropriate bits are (un)set on the superblock.
+ */
+int hfsplus_compare_dentry(struct dentry *dentry, struct qstr *s1, struct qstr *s2)
+{
+        struct super_block *sb = dentry->d_sb;
+        int casefold, decompose, size;
+        int dsize1, dsize2, len1, len2;
+        const u16 *dstr1, *dstr2;
+        const char *astr1, *astr2;
+        u16 c1, c2;
+        wchar_t c;
+
+        casefold = (HFSPLUS_SB(sb).flags & HFSPLUS_SB_CASEFOLD);
+        decompose = !(HFSPLUS_SB(sb).flags & HFSPLUS_SB_NODECOMPOSE);
+        astr1 = s1->name;
+        len1 = s1->len;
+        astr2 = s2->name;
+        len2 = s2->len;
+        dsize1 = dsize2 = 0;
+        dstr1 = dstr2 = NULL;
+
+        while (len1 > 0 && len2 > 0) {
+                if (!dsize1) {
+                        size = asc2unichar(sb, astr1, len1, &c);
+                        astr1 += size;
+                        len1 -= size;
+
+                        if (!decompose || !(dstr1 = decompose_unichar(c, &dsize1))) {
+                                c1 = c;
+                                dstr1 = &c1;
+                                dsize1 = 1;
+                        }
+                }
+
+                if (!dsize2) {
+                        size = asc2unichar(sb, astr2, len2, &c);
+                        astr2 += size;
+                        len2 -= size;
+
+                        if (!decompose || !(dstr2 = decompose_unichar(c, &dsize2))) {
+                                c2 = c;
+                                dstr2 = &c2;
+                                dsize2 = 1;
+                        }
+                }
+
+                c1 = *dstr1;
+                c2 = *dstr2;
+                if (casefold) {
+                        if  (!(c1 = case_fold(c1))) {
+                                dstr1++;
+                                dsize1--;
+                                continue;
+                        }
+                        if (!(c2 = case_fold(c2))) {
+                                dstr2++;
+                                dsize2--;
+                                continue;
+                        }
+                }
+                if (c1 < c2)
+                        return -1;
+                else if (c1 > c2)
+                        return 1;
+
+                dstr1++;
+                dsize1--;
+                dstr2++;
+                dsize2--;
+        }
+
+        if (len1 < len2)
+                return -1;
+        if (len1 > len2)
+                return 1;
+        return 0;
+}