diff options
author | Felix Lange <fjl@users.noreply.github.com> | 2017-04-12 22:27:23 +0800 |
---|---|---|
committer | Péter Szilágyi <peterke@gmail.com> | 2017-04-12 22:27:23 +0800 |
commit | 30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2 (patch) | |
tree | 3ec076154049f1fa71b19fd9b7762085059ff15b /vendor/github.com/naoina/go-stringutil/da.go | |
parent | b57680b0b21036460c689aab1e82d89297738d50 (diff) | |
download | dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.tar dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.tar.gz dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.tar.bz2 dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.tar.lz dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.tar.xz dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.tar.zst dexon-30d706c35e16305e2e3ec0eb6a6bdd6aba50d9d2.zip |
cmd/geth: add --config file flag (#13875)
* p2p/discover, p2p/discv5: add marshaling methods to Node
* p2p/netutil: make Netlist decodable from TOML
* common/math: encode nil HexOrDecimal256 as 0x0
* cmd/geth: add --config file flag
* cmd/geth: add missing license header
* eth: prettify Config again, fix tests
* eth: use gasprice.Config instead of duplicating its fields
* eth/gasprice: hide nil default from dumpconfig output
* cmd/geth: hide genesis block in dumpconfig output
* node: make tests compile
* console: fix tests
* cmd/geth: make TOML keys look exactly like Go struct fields
* p2p: use discovery by default
This makes the zero Config slightly more useful. It also fixes package
node tests because Node detects reuse of the datadir through the
NodeDatabase.
* cmd/geth: make ethstats URL settable through config file
* cmd/faucet: fix configuration
* cmd/geth: dedup attach tests
* eth: add comment for DefaultConfig
* eth: pass downloader.SyncMode in Config
This removes the FastSync, LightSync flags in favour of a more
general SyncMode flag.
* cmd/utils: remove jitvm flags
* cmd/utils: make mutually exclusive flag error prettier
It now reads:
Fatal: flags --dev, --testnet can't be used at the same time
* p2p: fix typo
* node: add DefaultConfig, use it for geth
* mobile: add missing NoDiscovery option
* cmd/utils: drop MakeNode
This exposed a couple of places that needed to be updated to use
node.DefaultConfig.
* node: fix typo
* eth: make fast sync the default mode
* cmd/utils: remove IPCApiFlag (unused)
* node: remove default IPC path
Set it in the frontends instead.
* cmd/geth: add --syncmode
* cmd/utils: make --ipcdisable and --ipcpath mutually exclusive
* cmd/utils: don't enable WS, HTTP when setting addr
* cmd/utils: fix --identity
Diffstat (limited to 'vendor/github.com/naoina/go-stringutil/da.go')
-rw-r--r-- | vendor/github.com/naoina/go-stringutil/da.go | 253 |
1 files changed, 253 insertions, 0 deletions
diff --git a/vendor/github.com/naoina/go-stringutil/da.go b/vendor/github.com/naoina/go-stringutil/da.go new file mode 100644 index 000000000..8fe651659 --- /dev/null +++ b/vendor/github.com/naoina/go-stringutil/da.go @@ -0,0 +1,253 @@ +package stringutil + +import ( + "fmt" + "sort" + "unicode/utf8" +) + +const ( + terminationCharacter = '#' +) + +func mustDoubleArray(da *doubleArray, err error) *doubleArray { + if err != nil { + panic(err) + } + return da +} + +func (da *doubleArray) Build(keys []string) error { + records := makeRecords(keys) + if err := da.build(records, 1, 0, make(map[int]struct{})); err != nil { + return err + } + return nil +} + +type doubleArray struct { + bc []baseCheck + node []int +} + +func newDoubleArray(keys []string) (*doubleArray, error) { + da := &doubleArray{ + bc: []baseCheck{0}, + node: []int{-1}, // A start index is adjusting to 1 because 0 will be used as a mark of non-existent node. + } + if err := da.Build(keys); err != nil { + return nil, err + } + return da, nil +} + +// baseCheck contains BASE, CHECK and Extra flags. +// From the top, 22bits of BASE, 2bits of Extra flags and 8bits of CHECK. +// +// BASE (22bit) | Extra flags (2bit) | CHECK (8bit) +// |----------------------|--|--------| +// 32 10 8 0 +type baseCheck uint32 + +func (bc baseCheck) Base() int { + return int(bc >> 10) +} + +func (bc *baseCheck) SetBase(base int) { + *bc |= baseCheck(base) << 10 +} + +func (bc baseCheck) Check() byte { + return byte(bc) +} + +func (bc *baseCheck) SetCheck(check byte) { + *bc |= baseCheck(check) +} + +func (bc baseCheck) IsEmpty() bool { + return bc&0xfffffcff == 0 +} + +func (da *doubleArray) Lookup(path string) (length int) { + idx := 1 + tmpIdx := idx + for i := 0; i < len(path); i++ { + c := path[i] + tmpIdx = da.nextIndex(da.bc[tmpIdx].Base(), c) + if tmpIdx >= len(da.bc) || da.bc[tmpIdx].Check() != c { + break + } + idx = tmpIdx + } + if next := da.nextIndex(da.bc[idx].Base(), terminationCharacter); next < len(da.bc) && da.bc[next].Check() == terminationCharacter { + return da.node[da.bc[next].Base()] + } + return -1 +} + +func (da *doubleArray) LookupByBytes(path []byte) (length int) { + idx := 1 + tmpIdx := idx + for i := 0; i < len(path); i++ { + c := path[i] + tmpIdx = da.nextIndex(da.bc[tmpIdx].Base(), c) + if tmpIdx >= len(da.bc) || da.bc[tmpIdx].Check() != c { + break + } + idx = tmpIdx + } + if next := da.nextIndex(da.bc[idx].Base(), terminationCharacter); next < len(da.bc) && da.bc[next].Check() == terminationCharacter { + return da.node[da.bc[next].Base()] + } + return -1 +} + +func (da *doubleArray) build(srcs []record, idx, depth int, usedBase map[int]struct{}) error { + sort.Stable(recordSlice(srcs)) + base, siblings, leaf, err := da.arrange(srcs, idx, depth, usedBase) + if err != nil { + return err + } + if leaf != nil { + da.bc[idx].SetBase(len(da.node)) + da.node = append(da.node, leaf.value) + } + for _, sib := range siblings { + da.setCheck(da.nextIndex(base, sib.c), sib.c) + } + for _, sib := range siblings { + if err := da.build(srcs[sib.start:sib.end], da.nextIndex(base, sib.c), depth+1, usedBase); err != nil { + return err + } + } + return nil +} + +func (da *doubleArray) setBase(i, base int) { + da.bc[i].SetBase(base) +} + +func (da *doubleArray) setCheck(i int, check byte) { + da.bc[i].SetCheck(check) +} + +func (da *doubleArray) findEmptyIndex(start int) int { + i := start + for ; i < len(da.bc); i++ { + if da.bc[i].IsEmpty() { + break + } + } + return i +} + +// findBase returns good BASE. +func (da *doubleArray) findBase(siblings []sibling, start int, usedBase map[int]struct{}) (base int) { + for idx, firstChar := start+1, siblings[0].c; ; idx = da.findEmptyIndex(idx + 1) { + base = da.nextIndex(idx, firstChar) + if _, used := usedBase[base]; used { + continue + } + i := 0 + for ; i < len(siblings); i++ { + next := da.nextIndex(base, siblings[i].c) + if len(da.bc) <= next { + da.bc = append(da.bc, make([]baseCheck, next-len(da.bc)+1)...) + } + if !da.bc[next].IsEmpty() { + break + } + } + if i == len(siblings) { + break + } + } + usedBase[base] = struct{}{} + return base +} + +func (da *doubleArray) arrange(records []record, idx, depth int, usedBase map[int]struct{}) (base int, siblings []sibling, leaf *record, err error) { + siblings, leaf, err = makeSiblings(records, depth) + if err != nil { + return -1, nil, nil, err + } + if len(siblings) < 1 { + return -1, nil, leaf, nil + } + base = da.findBase(siblings, idx, usedBase) + da.setBase(idx, base) + return base, siblings, leaf, err +} + +type sibling struct { + start int + end int + c byte +} + +func (da *doubleArray) nextIndex(base int, c byte) int { + return base ^ int(c) +} + +func makeSiblings(records []record, depth int) (sib []sibling, leaf *record, err error) { + var ( + pc byte + n int + ) + for i, r := range records { + if len(r.key) <= depth { + leaf = &r + continue + } + c := r.key[depth] + switch { + case pc < c: + sib = append(sib, sibling{start: i, c: c}) + case pc == c: + continue + default: + return nil, nil, fmt.Errorf("stringutil: BUG: records hasn't been sorted") + } + if n > 0 { + sib[n-1].end = i + } + pc = c + n++ + } + if n == 0 { + return nil, leaf, nil + } + sib[n-1].end = len(records) + return sib, leaf, nil +} + +type record struct { + key string + value int +} + +func makeRecords(srcs []string) (records []record) { + termChar := string(terminationCharacter) + for _, s := range srcs { + records = append(records, record{ + key: string(s + termChar), + value: utf8.RuneCountInString(s), + }) + } + return records +} + +type recordSlice []record + +func (rs recordSlice) Len() int { + return len(rs) +} + +func (rs recordSlice) Less(i, j int) bool { + return rs[i].key < rs[j].key +} + +func (rs recordSlice) Swap(i, j int) { + rs[i], rs[j] = rs[j], rs[i] +} |