Mercurial > lbo > hg > leveldb-rs

changeset 150:01e070c97ee7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix bug in default comparator: Return correct separator for difficult cases This is important if TableBuilder wants a separator between K and succ(K), where succ(K) is usually just a string of K's first characters plus 1. In this case we now return K with its last byte incremented by one, which isn't really "short" anymore, but a valid separator. Otherwise, logic relying on the key in index blocks being actually *past* the referenced block fails in some cases, for example on the last block of a table.
author Lewin Bormann <lbo@spheniscida.de>
date Sun, 29 Jan 2017 16:13:36 +0100
parents 11f887625190
children 6e14c9e7e53d
files src/cmp.rs
diffstat 1 files changed, 11 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/src/cmp.rs	Sun Jan 29 15:26:56 2017 +0100
+++ b/src/cmp.rs	Sun Jan 29 16:13:36 2017 +0100
@@ -57,7 +57,12 @@
 
             diff_at += 1;
         }
-        return a.to_vec();
+        // Backup case: either `a` is full of 0xff, or all different places are less than 2
+        // characters apart.
+        // The result is not necessarily short, but a good separator.
+        let mut sep = a.to_vec();
+        sep[a.len() - 1] += 1;
+        return sep;
     }
 
     fn find_short_succ(&self, a: &[u8]) -> Vec<u8> {
@@ -194,15 +199,17 @@
         assert_eq!(DefaultCmp.find_shortest_sep("abcd".as_bytes(), "abcf".as_bytes()),
                    "abce".as_bytes());
         assert_eq!(DefaultCmp.find_shortest_sep("abc".as_bytes(), "acd".as_bytes()),
-                   "abc".as_bytes());
+                   "abd".as_bytes());
         assert_eq!(DefaultCmp.find_shortest_sep("abcdefghi".as_bytes(), "abcffghi".as_bytes()),
                    "abce".as_bytes());
         assert_eq!(DefaultCmp.find_shortest_sep("a".as_bytes(), "a".as_bytes()),
                    "a".as_bytes());
         assert_eq!(DefaultCmp.find_shortest_sep("a".as_bytes(), "b".as_bytes()),
-                   "a".as_bytes());
+                   "b".as_bytes());
         assert_eq!(DefaultCmp.find_shortest_sep("abc".as_bytes(), "zzz".as_bytes()),
                    "b".as_bytes());
+        assert_eq!(DefaultCmp.find_shortest_sep("yyy".as_bytes(), "z".as_bytes()),
+                   "yyz".as_bytes());
         assert_eq!(DefaultCmp.find_shortest_sep("".as_bytes(), "".as_bytes()),
                    "".as_bytes());
     }
@@ -229,7 +236,7 @@
                    LookupKey::new("b".as_bytes(), types::MAX_SEQUENCE_NUMBER).internal_key());
         assert_eq!(cmp.find_shortest_sep(LookupKey::new("abc".as_bytes(), 1).internal_key(),
                                          LookupKey::new("acd".as_bytes(), 2).internal_key()),
-                   LookupKey::new("abc".as_bytes(), 1).internal_key());
+                   LookupKey::new("abd".as_bytes(), 1).internal_key());
         assert_eq!(cmp.find_shortest_sep(LookupKey::new("abc".as_bytes(), 1).internal_key(),
                                          LookupKey::new("abe".as_bytes(), 2).internal_key()),
                    LookupKey::new("abd".as_bytes(), 1).internal_key());