{"action":"created","issue":{"url":"https://api.github.com/repos/chrsmithdemos/leveldb/issues/103","labels_url":"https://api.github.com/repos/chrsmithdemos/leveldb/issues/103/labels{/name}","comments_url":"https://api.github.com/repos/chrsmithdemos/leveldb/issues/103/comments","events_url":"https://api.github.com/repos/chrsmithdemos/leveldb/issues/103/events","html_url":"https://github.com/chrsmithdemos/leveldb/issues/103","id":58997581,"number":103,"title":"The defective binary search code in Block::Iter::Seek()  in block.cc","user":{"login":"GoogleCodeExporter","id":9614759,"avatar_url":"https://avatars.githubusercontent.com/u/9614759?v=3","gravatar_id":"","url":"https://api.github.com/users/GoogleCodeExporter","html_url":"https://github.com/GoogleCodeExporter","followers_url":"https://api.github.com/users/GoogleCodeExporter/followers","following_url":"https://api.github.com/users/GoogleCodeExporter/following{/other_user}","gists_url":"https://api.github.com/users/GoogleCodeExporter/gists{/gist_id}","starred_url":"https://api.github.com/users/GoogleCodeExporter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/GoogleCodeExporter/subscriptions","organizations_url":"https://api.github.com/users/GoogleCodeExporter/orgs","repos_url":"https://api.github.com/users/GoogleCodeExporter/repos","events_url":"https://api.github.com/users/GoogleCodeExporter/events{/privacy}","received_events_url":"https://api.github.com/users/GoogleCodeExporter/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/chrsmithdemos/leveldb/labels/auto-migrated","name":"auto-migrated","color":"ededed"},{"url":"https://api.github.com/repos/chrsmithdemos/leveldb/labels/Priority-Medium","name":"Priority-Medium","color":"ededed"},{"url":"https://api.github.com/repos/chrsmithdemos/leveldb/labels/Type-Defect","name":"Type-Defect","color":"ededed"}],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-02-26T00:42:34Z","updated_at":"2015-02-26T00:42:34Z","closed_at":"2015-02-26T00:42:34Z","body":"```\nThe following code is from Seek() function in block.cc. As the comments says, \nit performs a stl::lower_bound operation in the restart array. However, I \nbelieve the implementation is flawed. \n\n    // Binary search in restart array to find the first restart point\n    // with a key >= target\n    uint32_t left = 0;\n    uint32_t right = num_restarts_ - 1;\n    while (left < right) {\n      uint32_t mid = (left + right + 1) / 2;\n\n      ......\n\n      Slice mid_key(key_ptr, non_shared);\n      if (Compare(mid_key, target) < 0) {\n        // Key at \"mid\" is smaller than \"target\".  Therefore all\n        // blocks before \"mid\" are uninteresting.\n        left = mid;\n      } else {\n        // Key at \"mid\" is >= \"target\".  Therefore all blocks at or\n        // after \"mid\" are uninteresting.\n        right = mid - 1;\n      }\n    }\n\nIn some cases, it may find a previous restart point instead of the correct one. \nAlthough the final result is correct, it involves unnecessary iteration and \nconfusing. I think the following code is better.\n\n    // Binary search in restart array to find the first restart point\n    // with a key >= target\n    uint32_t left = 0;\n    uint32_t right = num_restarts_;\n    while (left < right) {\n      uint32_t mid = (left + right) / 2;\n\n      ......\n\n      Slice mid_key(key_ptr, non_shared);\n      if (Compare(mid_key, target) < 0) {\n        // Key at \"mid\" is smaller than \"target\".  Therefore all\n        // blocks before \"mid\" are uninteresting.\n        left = mid + 1;\n      } else {\n        // Key at \"mid\" is >= \"target\".  Therefore all blocks at or\n        // after \"mid\" are uninteresting.\n        right = mid;\n      }\n    }\n```\n\n-----\nOriginal issue reported on code.google.com by `yangzhuo...@gmail.com` on 15 Jul 2012 at 1:36"},"comment":{"url":"https://api.github.com/repos/chrsmithdemos/leveldb/issues/comments/76099533","html_url":"https://github.com/chrsmithdemos/leveldb/issues/103#issuecomment-76099533","issue_url":"https://api.github.com/repos/chrsmithdemos/leveldb/issues/103","id":76099533,"user":{"login":"GoogleCodeExporter","id":9614759,"avatar_url":"https://avatars.githubusercontent.com/u/9614759?v=3","gravatar_id":"","url":"https://api.github.com/users/GoogleCodeExporter","html_url":"https://github.com/GoogleCodeExporter","followers_url":"https://api.github.com/users/GoogleCodeExporter/followers","following_url":"https://api.github.com/users/GoogleCodeExporter/following{/other_user}","gists_url":"https://api.github.com/users/GoogleCodeExporter/gists{/gist_id}","starred_url":"https://api.github.com/users/GoogleCodeExporter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/GoogleCodeExporter/subscriptions","organizations_url":"https://api.github.com/users/GoogleCodeExporter/orgs","repos_url":"https://api.github.com/users/GoogleCodeExporter/repos","events_url":"https://api.github.com/users/GoogleCodeExporter/events{/privacy}","received_events_url":"https://api.github.com/users/GoogleCodeExporter/received_events","type":"User","site_admin":false},"created_at":"2015-02-26T00:42:34Z","updated_at":"2015-02-26T00:42:34Z","body":"```\nThis code needs to implement something other than\nstd::lower_bound.  I suspect there are misleading\ncomments in the code that are leading you astray.\n\nIn particular, the block stores multiple keys\nbetween each restart point.  And what the binary\nsearch needs to do is find the largest restart\npoint with a key < target so we can start\ndecoding from there and find any occurrence of\ntarget that might occur between restart points.\n\nConsider the following example with target==250.\n\n  restart point 0:  key == 100\n                    ... some keys in range [100..199] here ...\n  restart point 1:  key == 200\n                    ... some keys in range [200..299] here ...\n  restart point 2:  key == 300\n                    ... some keys in range [300..inf] here ...\n\nIn this example, we would want the binary search\nto find restart point 1 (key == 200) and then\nsequentially decode from there.\n\nNow consider your proposed code.\nFirst iteration:\n  left = 0\n  right = 3 \n  mid = (left + right) / 2 == 1\n  Compare(mid_key, target) == Compare(200, 250)\n  The comparison returns < 0, so we do:\n     left = mid + 1 = 2\nWe have skipped past the correct result of binary\nsearch (restart point 1).  So we will end up starting\nthe decoding process too late in the block.\n\nSorry about the misleading comment.  I will change\nthe following comment:\n    // Binary search in restart array to find the first restart point\n    // with a key >= target\nto:\n    // Binary search in restart array to find the last restart point\n    // with a key < target\n\n```\n\n-----\nOriginal comment by `san...@google.com` on 16 Jul 2012 at 5:04\n* Changed state: **Invalid**"}}