impl/memory: Implement Queries

impl/memory/binary_tools.go

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+package memory
+
+import (
+        "fmt"
+)
+
+func bjoin(itms ...[]byte) []byte {
+        total := 0
+        for _, i := range itms {
+                total += len(i)
+        }
+        ret := make([]byte, 0, total)
+        for _, i := range itms {
+                ret = append(ret, i...)
+        }
+        return ret
+}
+
+// invert simply inverts all the bytes in bs.
+func invert(bs []byte) []byte {
+        if bs == nil {

[dnj, 2015/08/28 16:37:54]

if len(bs) == 0

[iannucci, 2015/08/28 19:48:55]

Done.

+                return nil
+        }
+        ret := make([]byte, len(bs))
+        for i, b := range bs {
+                ret[i] = 0xFF ^ b
+        }
+        return ret
+}
+
+func increment(bstr []byte) []byte {
+        if bstr == nil {

[dnj, 2015/08/28 16:37:54]

len(bstr) == 0

But one cannot increment zero-length, correct? I'd panic here.

[iannucci, 2015/08/28 19:48:55]

Done.

+                return nil
+        }
+
+        // Copy bstr
+        ret := bjoin(bstr)
+        for i := len(ret) - 1; i >= 0; i-- {
+                if ret[i] == 0xFF {
+                        ret[i] = 0
+                } else {
+                        ret[i]++
+                        return ret
+                }
+        }
+
+        // This byte string was ALL FF's. The only safe incrementation to do here

[dnj, 2015/08/28 16:37:54]

0xFF (you use 0x prefix elsewhere)

[iannucci, 2015/08/28 19:48:54]

done

+        // would be to add a new byte to the beginning of bstr with the value 0x01,
+        // and a byte to the beginning OF ALL OTHER []byte's which bstr may be
+        // compared with. This is obviously impossible to do here, so panic. If we
+        // hit this, then we would need to add a spare 0 byte before every index
+        // column.
+        //
+        // Another way to think about this is that we just accumulated a 'carry' bit,
+        // and the new value has overflowed this representation.
+        //
+        // Fortunately, the first byte of a serialized index column entry is a
+        // PropertyType byte, and the only valid values that we'll be incrementing
+        // are never equal to 0xFF, since they have the higbit set (so either they're

[dnj, 2015/08/28 16:37:54]

high bit**

[iannucci, 2015/08/28 19:48:55]

Done

+        // 0x8*, or 0x7*, depending on if it's inverted).
+        impossible(fmt.Errorf("incrementing %v would require more sigfigs", bstr))
+        return nil
+}