diff options
Diffstat (limited to 'vendor/golang.org/x/text/unicode/norm/triegen.go')
-rw-r--r-- | vendor/golang.org/x/text/unicode/norm/triegen.go | 117 |
1 files changed, 117 insertions, 0 deletions
diff --git a/vendor/golang.org/x/text/unicode/norm/triegen.go b/vendor/golang.org/x/text/unicode/norm/triegen.go new file mode 100644 index 0000000..45d7119 --- /dev/null +++ b/vendor/golang.org/x/text/unicode/norm/triegen.go | |||
@@ -0,0 +1,117 @@ | |||
1 | // Copyright 2011 The Go Authors. All rights reserved. | ||
2 | // Use of this source code is governed by a BSD-style | ||
3 | // license that can be found in the LICENSE file. | ||
4 | |||
5 | // +build ignore | ||
6 | |||
7 | // Trie table generator. | ||
8 | // Used by make*tables tools to generate a go file with trie data structures | ||
9 | // for mapping UTF-8 to a 16-bit value. All but the last byte in a UTF-8 byte | ||
10 | // sequence are used to lookup offsets in the index table to be used for the | ||
11 | // next byte. The last byte is used to index into a table with 16-bit values. | ||
12 | |||
13 | package main | ||
14 | |||
15 | import ( | ||
16 | "fmt" | ||
17 | "io" | ||
18 | ) | ||
19 | |||
20 | const maxSparseEntries = 16 | ||
21 | |||
22 | type normCompacter struct { | ||
23 | sparseBlocks [][]uint64 | ||
24 | sparseOffset []uint16 | ||
25 | sparseCount int | ||
26 | name string | ||
27 | } | ||
28 | |||
29 | func mostFrequentStride(a []uint64) int { | ||
30 | counts := make(map[int]int) | ||
31 | var v int | ||
32 | for _, x := range a { | ||
33 | if stride := int(x) - v; v != 0 && stride >= 0 { | ||
34 | counts[stride]++ | ||
35 | } | ||
36 | v = int(x) | ||
37 | } | ||
38 | var maxs, maxc int | ||
39 | for stride, cnt := range counts { | ||
40 | if cnt > maxc || (cnt == maxc && stride < maxs) { | ||
41 | maxs, maxc = stride, cnt | ||
42 | } | ||
43 | } | ||
44 | return maxs | ||
45 | } | ||
46 | |||
47 | func countSparseEntries(a []uint64) int { | ||
48 | stride := mostFrequentStride(a) | ||
49 | var v, count int | ||
50 | for _, tv := range a { | ||
51 | if int(tv)-v != stride { | ||
52 | if tv != 0 { | ||
53 | count++ | ||
54 | } | ||
55 | } | ||
56 | v = int(tv) | ||
57 | } | ||
58 | return count | ||
59 | } | ||
60 | |||
61 | func (c *normCompacter) Size(v []uint64) (sz int, ok bool) { | ||
62 | if n := countSparseEntries(v); n <= maxSparseEntries { | ||
63 | return (n+1)*4 + 2, true | ||
64 | } | ||
65 | return 0, false | ||
66 | } | ||
67 | |||
68 | func (c *normCompacter) Store(v []uint64) uint32 { | ||
69 | h := uint32(len(c.sparseOffset)) | ||
70 | c.sparseBlocks = append(c.sparseBlocks, v) | ||
71 | c.sparseOffset = append(c.sparseOffset, uint16(c.sparseCount)) | ||
72 | c.sparseCount += countSparseEntries(v) + 1 | ||
73 | return h | ||
74 | } | ||
75 | |||
76 | func (c *normCompacter) Handler() string { | ||
77 | return c.name + "Sparse.lookup" | ||
78 | } | ||
79 | |||
80 | func (c *normCompacter) Print(w io.Writer) (retErr error) { | ||
81 | p := func(f string, x ...interface{}) { | ||
82 | if _, err := fmt.Fprintf(w, f, x...); retErr == nil && err != nil { | ||
83 | retErr = err | ||
84 | } | ||
85 | } | ||
86 | |||
87 | ls := len(c.sparseBlocks) | ||
88 | p("// %sSparseOffset: %d entries, %d bytes\n", c.name, ls, ls*2) | ||
89 | p("var %sSparseOffset = %#v\n\n", c.name, c.sparseOffset) | ||
90 | |||
91 | ns := c.sparseCount | ||
92 | p("// %sSparseValues: %d entries, %d bytes\n", c.name, ns, ns*4) | ||
93 | p("var %sSparseValues = [%d]valueRange {", c.name, ns) | ||
94 | for i, b := range c.sparseBlocks { | ||
95 | p("\n// Block %#x, offset %#x", i, c.sparseOffset[i]) | ||
96 | var v int | ||
97 | stride := mostFrequentStride(b) | ||
98 | n := countSparseEntries(b) | ||
99 | p("\n{value:%#04x,lo:%#02x},", stride, uint8(n)) | ||
100 | for i, nv := range b { | ||
101 | if int(nv)-v != stride { | ||
102 | if v != 0 { | ||
103 | p(",hi:%#02x},", 0x80+i-1) | ||
104 | } | ||
105 | if nv != 0 { | ||
106 | p("\n{value:%#04x,lo:%#02x", nv, 0x80+i) | ||
107 | } | ||
108 | } | ||
109 | v = int(nv) | ||
110 | } | ||
111 | if v != 0 { | ||
112 | p(",hi:%#02x},", 0x80+len(b)-1) | ||
113 | } | ||
114 | } | ||
115 | p("\n}\n\n") | ||
116 | return | ||
117 | } | ||