Permalink
Commits on Feb 17, 2017
  1. protocol/patricia: remove error case in Delete

    Delete used to return ErrPrefix in one case: when the
    requested key exactly matches an interior node. There
    were three problems with this:
    
    First, it didn't cover all cases where the requested key
    is a prefix of an existing item. Consider the following
    tree of three items (001, 010, and 011):
    
        0             (interior node)
        +-- 001       (leaf node)
        +-- 01        (interior node)
            +--  010  (leaf node)
            +--  011  (leaf node)
    
    Attempting to delete 01 produced ErrPrefix, but
    attempting to delete 00 was a no-op, returning a nil
    error. Both of those keys are prefixes of other keys in
    the set.
    
    Second, there was a bug in the recursive call. It
    returned a nil node on error. This returned all the way
    up the stack and caused the root node to be replaced
    with nil. Thus, attempting to delete a nonexistent key
    corresponding to an interior node would actually delete
    the entire tree.
    
    Third, and most broadly, attempting to delete a prefix
    of an existing key (whether or not it matches an
    interior node) shouldn't be an error. It should be a
    no-op, just like trying to delete any other key that's
    not in the set.
    
    This patch addresses these issues by removing the error
    condition and treating that case as a no-op.
    
    There's no significant difference in performance in the
    existing benchmarks.
    
    benchmark                      old ns/op     new ns/op     delta
    BenchmarkInserts-4             27923330      27744174      -0.64%
    BenchmarkInsertsRootHash-4     37095589      37046587      -0.13%
    
    benchmark                      old allocs     new allocs     delta
    BenchmarkInserts-4             161756         161755         -0.00%
    BenchmarkInsertsRootHash-4     171776         171776         +0.00%
    
    benchmark                      old bytes     new bytes     delta
    BenchmarkInserts-4             11642978      11642854      -0.00%
    BenchmarkInsertsRootHash-4     11970751      11970739      -0.00%
    
    Closes #546
    kr committed with chainbot Feb 17, 2017
  2. protocol/patricia: remove unused parameter

    There's no need for insert, delete, and lookup to be
    methods on Tree. The *Tree is completely unused in the
    body of those three functions (other than in the
    recursive calls).
    
    Closes #545
    kr committed with chainbot Feb 17, 2017
Commits on Feb 16, 2017
Commits on Feb 13, 2017
  1. Readme: better support for multi-entry GOPATH

    Using 'go list' here does the right thing when GOPATH
    has more than one directory in it. (There are still one
    or two other places in this document that won't work
    correctly in that scenario, but they are harder to fix.)
    
    Closes #515
    kr committed with chainbot Feb 13, 2017
Commits on Feb 9, 2017
  1. errors: clarify documentation

    Using these parameter names for Sub seems to make its
    behavior clearer.
    
    Closes #500
    kr committed with chainbot Feb 9, 2017
  2. errors: add new function Sub

    Sub takes an existing error, which might have an associated stack trace or
    other metadata, and substitutes a new root error, which is sometimes
    necessary to return a certain error code to the client.
    
    This change also updates all call sites I could find to use the new
    function.
    
    Closes #496
    kr committed with chainbot Feb 9, 2017