impl/memory: Implement Queries

impl/memory/binary_tools.go

Index: impl/memory/binary_tools.go
diff --git a/impl/memory/binary_tools.go b/impl/memory/binary_tools.go
new file mode 100644
index 0000000000000000000000000000000000000000..66e93a4a0cec138ae985130b17b1164db37f91d5
--- /dev/null
+++ b/impl/memory/binary_tools.go
@@ -0,0 +1,67 @@
+// 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
+}