From 7b320119ba532fd409ec7dade7ad02011c309599 Mon Sep 17 00:00:00 2001 From: Niall Sheridan Date: Wed, 18 Oct 2017 13:15:14 +0100 Subject: Update dependencies --- vendor/golang.org/x/text/collate/build/trie.go | 290 +++++++++++++++++++++++++ 1 file changed, 290 insertions(+) create mode 100644 vendor/golang.org/x/text/collate/build/trie.go (limited to 'vendor/golang.org/x/text/collate/build/trie.go') diff --git a/vendor/golang.org/x/text/collate/build/trie.go b/vendor/golang.org/x/text/collate/build/trie.go new file mode 100644 index 0000000..9404a34 --- /dev/null +++ b/vendor/golang.org/x/text/collate/build/trie.go @@ -0,0 +1,290 @@ +// Copyright 2012 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// The trie in this file is used to associate the first full character +// in a UTF-8 string to a collation element. +// All but the last byte in a UTF-8 byte sequence are +// used to look up offsets in the index table to be used for the next byte. +// The last byte is used to index into a table of collation elements. +// This file contains the code for the generation of the trie. + +package build + +import ( + "fmt" + "hash/fnv" + "io" + "reflect" +) + +const ( + blockSize = 64 + blockOffset = 2 // Subtract 2 blocks to compensate for the 0x80 added to continuation bytes. +) + +type trieHandle struct { + lookupStart uint16 // offset in table for first byte + valueStart uint16 // offset in table for first byte +} + +type trie struct { + index []uint16 + values []uint32 +} + +// trieNode is the intermediate trie structure used for generating a trie. +type trieNode struct { + index []*trieNode + value []uint32 + b byte + refValue uint16 + refIndex uint16 +} + +func newNode() *trieNode { + return &trieNode{ + index: make([]*trieNode, 64), + value: make([]uint32, 128), // root node size is 128 instead of 64 + } +} + +func (n *trieNode) isInternal() bool { + return n.value != nil +} + +func (n *trieNode) insert(r rune, value uint32) { + const maskx = 0x3F // mask out two most-significant bits + str := string(r) + if len(str) == 1 { + n.value[str[0]] = value + return + } + for i := 0; i < len(str)-1; i++ { + b := str[i] & maskx + if n.index == nil { + n.index = make([]*trieNode, blockSize) + } + nn := n.index[b] + if nn == nil { + nn = &trieNode{} + nn.b = b + n.index[b] = nn + } + n = nn + } + if n.value == nil { + n.value = make([]uint32, blockSize) + } + b := str[len(str)-1] & maskx + n.value[b] = value +} + +type trieBuilder struct { + t *trie + + roots []*trieHandle + + lookupBlocks []*trieNode + valueBlocks []*trieNode + + lookupBlockIdx map[uint32]*trieNode + valueBlockIdx map[uint32]*trieNode +} + +func newTrieBuilder() *trieBuilder { + index := &trieBuilder{} + index.lookupBlocks = make([]*trieNode, 0) + index.valueBlocks = make([]*trieNode, 0) + index.lookupBlockIdx = make(map[uint32]*trieNode) + index.valueBlockIdx = make(map[uint32]*trieNode) + // The third nil is the default null block. The other two blocks + // are used to guarantee an offset of at least 3 for each block. + index.lookupBlocks = append(index.lookupBlocks, nil, nil, nil) + index.t = &trie{} + return index +} + +func (b *trieBuilder) computeOffsets(n *trieNode) *trieNode { + hasher := fnv.New32() + if n.index != nil { + for i, nn := range n.index { + var vi, vv uint16 + if nn != nil { + nn = b.computeOffsets(nn) + n.index[i] = nn + vi = nn.refIndex + vv = nn.refValue + } + hasher.Write([]byte{byte(vi >> 8), byte(vi)}) + hasher.Write([]byte{byte(vv >> 8), byte(vv)}) + } + h := hasher.Sum32() + nn, ok := b.lookupBlockIdx[h] + if !ok { + n.refIndex = uint16(len(b.lookupBlocks)) - blockOffset + b.lookupBlocks = append(b.lookupBlocks, n) + b.lookupBlockIdx[h] = n + } else { + n = nn + } + } else { + for _, v := range n.value { + hasher.Write([]byte{byte(v >> 24), byte(v >> 16), byte(v >> 8), byte(v)}) + } + h := hasher.Sum32() + nn, ok := b.valueBlockIdx[h] + if !ok { + n.refValue = uint16(len(b.valueBlocks)) - blockOffset + n.refIndex = n.refValue + b.valueBlocks = append(b.valueBlocks, n) + b.valueBlockIdx[h] = n + } else { + n = nn + } + } + return n +} + +func (b *trieBuilder) addStartValueBlock(n *trieNode) uint16 { + hasher := fnv.New32() + for _, v := range n.value[:2*blockSize] { + hasher.Write([]byte{byte(v >> 24), byte(v >> 16), byte(v >> 8), byte(v)}) + } + h := hasher.Sum32() + nn, ok := b.valueBlockIdx[h] + if !ok { + n.refValue = uint16(len(b.valueBlocks)) + n.refIndex = n.refValue + b.valueBlocks = append(b.valueBlocks, n) + // Add a dummy block to accommodate the double block size. + b.valueBlocks = append(b.valueBlocks, nil) + b.valueBlockIdx[h] = n + } else { + n = nn + } + return n.refValue +} + +func genValueBlock(t *trie, n *trieNode) { + if n != nil { + for _, v := range n.value { + t.values = append(t.values, v) + } + } +} + +func genLookupBlock(t *trie, n *trieNode) { + for _, nn := range n.index { + v := uint16(0) + if nn != nil { + if n.index != nil { + v = nn.refIndex + } else { + v = nn.refValue + } + } + t.index = append(t.index, v) + } +} + +func (b *trieBuilder) addTrie(n *trieNode) *trieHandle { + h := &trieHandle{} + b.roots = append(b.roots, h) + h.valueStart = b.addStartValueBlock(n) + if len(b.roots) == 1 { + // We insert a null block after the first start value block. + // This ensures that continuation bytes UTF-8 sequences of length + // greater than 2 will automatically hit a null block if there + // was an undefined entry. + b.valueBlocks = append(b.valueBlocks, nil) + } + n = b.computeOffsets(n) + // Offset by one extra block as the first byte starts at 0xC0 instead of 0x80. + h.lookupStart = n.refIndex - 1 + return h +} + +// generate generates and returns the trie for n. +func (b *trieBuilder) generate() (t *trie, err error) { + t = b.t + if len(b.valueBlocks) >= 1<<16 { + return nil, fmt.Errorf("maximum number of value blocks exceeded (%d > %d)", len(b.valueBlocks), 1<<16) + } + if len(b.lookupBlocks) >= 1<<16 { + return nil, fmt.Errorf("maximum number of lookup blocks exceeded (%d > %d)", len(b.lookupBlocks), 1<<16) + } + genValueBlock(t, b.valueBlocks[0]) + genValueBlock(t, &trieNode{value: make([]uint32, 64)}) + for i := 2; i < len(b.valueBlocks); i++ { + genValueBlock(t, b.valueBlocks[i]) + } + n := &trieNode{index: make([]*trieNode, 64)} + genLookupBlock(t, n) + genLookupBlock(t, n) + genLookupBlock(t, n) + for i := 3; i < len(b.lookupBlocks); i++ { + genLookupBlock(t, b.lookupBlocks[i]) + } + return b.t, nil +} + +func (t *trie) printArrays(w io.Writer, name string) (n, size int, err error) { + p := func(f string, a ...interface{}) { + nn, e := fmt.Fprintf(w, f, a...) + n += nn + if err == nil { + err = e + } + } + nv := len(t.values) + p("// %sValues: %d entries, %d bytes\n", name, nv, nv*4) + p("// Block 2 is the null block.\n") + p("var %sValues = [%d]uint32 {", name, nv) + var printnewline bool + for i, v := range t.values { + if i%blockSize == 0 { + p("\n\t// Block %#x, offset %#x", i/blockSize, i) + } + if i%4 == 0 { + printnewline = true + } + if v != 0 { + if printnewline { + p("\n\t") + printnewline = false + } + p("%#04x:%#08x, ", i, v) + } + } + p("\n}\n\n") + ni := len(t.index) + p("// %sLookup: %d entries, %d bytes\n", name, ni, ni*2) + p("// Block 0 is the null block.\n") + p("var %sLookup = [%d]uint16 {", name, ni) + printnewline = false + for i, v := range t.index { + if i%blockSize == 0 { + p("\n\t// Block %#x, offset %#x", i/blockSize, i) + } + if i%8 == 0 { + printnewline = true + } + if v != 0 { + if printnewline { + p("\n\t") + printnewline = false + } + p("%#03x:%#02x, ", i, v) + } + } + p("\n}\n\n") + return n, nv*4 + ni*2, err +} + +func (t *trie) printStruct(w io.Writer, handle *trieHandle, name string) (n, sz int, err error) { + const msg = "trie{ %sLookup[%d:], %sValues[%d:], %sLookup[:], %sValues[:]}" + n, err = fmt.Fprintf(w, msg, name, handle.lookupStart*blockSize, name, handle.valueStart*blockSize, name, name) + sz += int(reflect.TypeOf(trie{}).Size()) + return +} -- cgit v1.2.3