aboutsummaryrefslogtreecommitdiffstats
path: root/trie/iterator.go
Commit message (Collapse)AuthorAgeFilesLines
* trie: more node iterator improvements (#14615)Felix Lange2017-06-211-107/+136
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * ethdb: remove Set Set deadlocks immediately and isn't part of the Database interface. * trie: add Err to Iterator This is useful for testing because the underlying NodeIterator doesn't need to be kept in a separate variable just to get the error. * trie: add LeafKey to iterator, panic when not at leaf LeafKey is useful for callers that can't interpret Path. * trie: retry failed seek/peek in iterator Next Instead of failing iteration irrecoverably, make it so Next retries the pending seek or peek every time. Smaller changes in this commit make this easier to test: * The iterator previously returned from Next on encountering a hash node. This caused it to visit the same path twice. * Path returned nibbles with terminator symbol for valueNode attached to fullNode, but removed it for valueNode attached to shortNode. Now the terminator is always present. This makes Path unique to each node and simplifies Leaf. * trie: add Path to MissingNodeError The light client trie iterator needs to know the path of the node that's missing so it can retrieve a proof for it. NodeIterator.Path is not sufficient because it is updated when the node is resolved and actually visited by the iterator. Also remove unused fields. They were added a long time ago before we knew which fields would be needed for the light client.
* trie: add start key to NodeIterator constructorsFelix Lange2017-04-251-51/+76
| | | | | | | | | The 'step' method is split into two parts, 'peek' and 'push'. peek returns the next state but doesn't make it current. The end of iteration was previously tracked by setting 'trie' to nil. End of iteration is now tracked using the 'iteratorEnd' error, which is slightly cleaner and requires less code.
* trie: clean up iterator constructorsFelix Lange2017-04-251-11/+4
| | | | | | | Make it so each iterator has exactly one public constructor: - NodeIterators can be created through a method. - Iterators can be created through NewIterator on any NodeIterator.
* trie: rework and document key encodingFelix Lange2017-04-251-1/+2
| | | | | 'encode' and 'decode' are meaningless because the code deals with three encodings. Document the encodings and give a name to each one.
* trie: implement unionIterator (#14312)Nick Johnson2017-04-131-12/+126
|
* core, consensus: pluggable consensus engines (#3817)Péter Szilágyi2017-04-051-0/+1
| | | | | This commit adds pluggable consensus engines to go-ethereum. In short, it introduces a generic consensus interface, and refactors the entire codebase to use this interface.
* trie: add difference iterator (#3637)Nick Johnson2017-02-231-107/+248
| | | | | This PR implements a differenceIterator, which allows iterating over trie nodes that exist in one trie but not in another. This is a prerequisite for most GC strategies, in order to find obsolete nodes.
* trie, core/state: improve memory usage and performance (#3135)Felix Lange2016-10-151-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * trie: store nodes as pointers This avoids memory copies when unwrapping node interface values. name old time/op new time/op delta Get 388ns ± 8% 215ns ± 2% -44.56% (p=0.000 n=15+15) GetDB 363ns ± 3% 202ns ± 2% -44.21% (p=0.000 n=15+15) UpdateBE 1.57µs ± 2% 1.29µs ± 3% -17.80% (p=0.000 n=13+15) UpdateLE 1.92µs ± 2% 1.61µs ± 2% -16.25% (p=0.000 n=14+14) HashBE 2.16µs ± 6% 2.18µs ± 6% ~ (p=0.436 n=15+15) HashLE 7.43µs ± 3% 7.21µs ± 3% -2.96% (p=0.000 n=15+13) * trie: close temporary databases in GetDB benchmark * trie: don't keep []byte from DB load around Nodes decoded from a DB load kept hashes and values as sub-slices of the DB value. This can be a problem because loading from leveldb often returns []byte with a cap that's larger than necessary, increasing memory usage. * trie: unload old cached nodes * trie, core/state: use cache unloading for account trie * trie: use explicit private flags (fixes Go 1.5 reflection issue). * trie: fixup cachegen overflow at request of nick * core/state: rename journal size constant
* core, trie: replace state caches with trie journalFelix Lange2016-09-281-122/+60
|
* core, core/state, trie: enterprise hand-tuned multi-level cachingPéter Szilágyi2016-05-261-11/+13
|
* core/state, trie: switch iterator panics to error fieldsPéter Szilágyi2016-02-161-7/+19
|
* core/state, trie: node iterator reports parent hashes tooPéter Szilágyi2016-02-161-8/+14
|
* core/state, trie: surface iterator entry hashesPéter Szilágyi2016-02-161-10/+15
|
* core/state, trie: add node iterator, test state/trie sync consistencyPéter Szilágyi2016-02-161-3/+117
|
* trie: added error handlingzsfelfoldi2015-12-011-3/+16
| | | | Created alternate versions of Trie and SecureTrie functions that can return a MissingNodeError (used by ODR services)
* core, trie: new trieFelix Lange2015-09-231-35/+29
|
* faster hex-prefix codec and string -> []byteEthan Buchman2015-08-061-1/+1
|
* all: fix license headers one more timeFelix Lange2015-07-241-1/+1
| | | | I forgot to update one instance of "go-ethereum" in commit 3f047be5a.
* all: update license headers to distiguish GPL/LGPLFelix Lange2015-07-231-4/+4
| | | | | All code outside of cmd/ is licensed as LGPL. The headers now reflect this by calling the whole work "the go-ethereum library".
* all: update license informationFelix Lange2015-07-071-0/+16
|
* Fixed iterator bug which skips the 0x000...000 key=2015-03-051-7/+21
|
* Fixed iteratorobscuren2015-02-081-2/+1
|
* Moved ptrie => trie. Removed old trieobscuren2015-01-081-93/+59
|
* Refactored ethutil.Config.Db outobscuren2015-01-071-0/+2
|
* ethtrie => trieobscuren2014-10-311-0/+143