From 4d11ca17d0f73f5bd783f45900118295fdfed46b Mon Sep 17 00:00:00 2001 From: Tomofumi Hayashi Date: Sat, 27 Apr 2019 20:38:39 +0900 Subject: barometer: update DMA's vendoring packages Change-Id: I0578b094f1ecdaed20c906be2ba29d51b8089d7c Signed-off-by: Tomofumi Hayashi --- .../golang.org/x/text/unicode/rangetable/merge.go | 260 +++++++++++++++++++++ 1 file changed, 260 insertions(+) create mode 100644 src/dma/vendor/golang.org/x/text/unicode/rangetable/merge.go (limited to 'src/dma/vendor/golang.org/x/text/unicode/rangetable/merge.go') diff --git a/src/dma/vendor/golang.org/x/text/unicode/rangetable/merge.go b/src/dma/vendor/golang.org/x/text/unicode/rangetable/merge.go new file mode 100644 index 00000000..ea2a0803 --- /dev/null +++ b/src/dma/vendor/golang.org/x/text/unicode/rangetable/merge.go @@ -0,0 +1,260 @@ +// Copyright 2015 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. + +package rangetable + +import ( + "unicode" +) + +// atEnd is used to mark a completed iteration. +const atEnd = unicode.MaxRune + 1 + +// Merge returns a new RangeTable that is the union of the given tables. +// It can also be used to compact user-created RangeTables. The entries in +// R16 and R32 for any given RangeTable should be sorted and non-overlapping. +// +// A lookup in the resulting table can be several times faster than using In +// directly on the ranges. Merge is an expensive operation, however, and only +// makes sense if one intends to use the result for more than a couple of +// hundred lookups. +func Merge(ranges ...*unicode.RangeTable) *unicode.RangeTable { + rt := &unicode.RangeTable{} + if len(ranges) == 0 { + return rt + } + + iter := tablesIter(make([]tableIndex, len(ranges))) + + for i, t := range ranges { + iter[i] = tableIndex{t, 0, atEnd} + if len(t.R16) > 0 { + iter[i].next = rune(t.R16[0].Lo) + } + } + + if r0 := iter.next16(); r0.Stride != 0 { + for { + r1 := iter.next16() + if r1.Stride == 0 { + rt.R16 = append(rt.R16, r0) + break + } + stride := r1.Lo - r0.Hi + if (r1.Lo == r1.Hi || stride == r1.Stride) && (r0.Lo == r0.Hi || stride == r0.Stride) { + // Fully merge the next range into the previous one. + r0.Hi, r0.Stride = r1.Hi, stride + continue + } else if stride == r0.Stride { + // Move the first element of r1 to r0. This may eliminate an + // entry. + r0.Hi = r1.Lo + r0.Stride = stride + r1.Lo = r1.Lo + r1.Stride + if r1.Lo > r1.Hi { + continue + } + } + rt.R16 = append(rt.R16, r0) + r0 = r1 + } + } + + for i, t := range ranges { + iter[i] = tableIndex{t, 0, atEnd} + if len(t.R32) > 0 { + iter[i].next = rune(t.R32[0].Lo) + } + } + + if r0 := iter.next32(); r0.Stride != 0 { + for { + r1 := iter.next32() + if r1.Stride == 0 { + rt.R32 = append(rt.R32, r0) + break + } + stride := r1.Lo - r0.Hi + if (r1.Lo == r1.Hi || stride == r1.Stride) && (r0.Lo == r0.Hi || stride == r0.Stride) { + // Fully merge the next range into the previous one. + r0.Hi, r0.Stride = r1.Hi, stride + continue + } else if stride == r0.Stride { + // Move the first element of r1 to r0. This may eliminate an + // entry. + r0.Hi = r1.Lo + r1.Lo = r1.Lo + r1.Stride + if r1.Lo > r1.Hi { + continue + } + } + rt.R32 = append(rt.R32, r0) + r0 = r1 + } + } + + for i := 0; i < len(rt.R16) && rt.R16[i].Hi <= unicode.MaxLatin1; i++ { + rt.LatinOffset = i + 1 + } + + return rt +} + +type tableIndex struct { + t *unicode.RangeTable + p uint32 + next rune +} + +type tablesIter []tableIndex + +// sortIter does an insertion sort using the next field of tableIndex. Insertion +// sort is a good sorting algorithm for this case. +func sortIter(t []tableIndex) { + for i := range t { + for j := i; j > 0 && t[j-1].next > t[j].next; j-- { + t[j], t[j-1] = t[j-1], t[j] + } + } +} + +// next16 finds the ranged to be added to the table. If ranges overlap between +// multiple tables it clips the result to a non-overlapping range if the +// elements are not fully subsumed. It returns a zero range if there are no more +// ranges. +func (ti tablesIter) next16() unicode.Range16 { + sortIter(ti) + + t0 := ti[0] + if t0.next == atEnd { + return unicode.Range16{} + } + r0 := t0.t.R16[t0.p] + r0.Lo = uint16(t0.next) + + // We restrict the Hi of the current range if it overlaps with another range. + for i := range ti { + tn := ti[i] + // Since our tableIndices are sorted by next, we can break if the there + // is no overlap. The first value of a next range can always be merged + // into the current one, so we can break in case of equality as well. + if rune(r0.Hi) <= tn.next { + break + } + rn := tn.t.R16[tn.p] + rn.Lo = uint16(tn.next) + + // Limit r0.Hi based on next ranges in list, but allow it to overlap + // with ranges as long as it subsumes it. + m := (rn.Lo - r0.Lo) % r0.Stride + if m == 0 && (rn.Stride == r0.Stride || rn.Lo == rn.Hi) { + // Overlap, take the min of the two Hi values: for simplicity's sake + // we only process one range at a time. + if r0.Hi > rn.Hi { + r0.Hi = rn.Hi + } + } else { + // Not a compatible stride. Set to the last possible value before + // rn.Lo, but ensure there is at least one value. + if x := rn.Lo - m; r0.Lo <= x { + r0.Hi = x + } + break + } + } + + // Update the next values for each table. + for i := range ti { + tn := &ti[i] + if rune(r0.Hi) < tn.next { + break + } + rn := tn.t.R16[tn.p] + stride := rune(rn.Stride) + tn.next += stride * (1 + ((rune(r0.Hi) - tn.next) / stride)) + if rune(rn.Hi) < tn.next { + if tn.p++; int(tn.p) == len(tn.t.R16) { + tn.next = atEnd + } else { + tn.next = rune(tn.t.R16[tn.p].Lo) + } + } + } + + if r0.Lo == r0.Hi { + r0.Stride = 1 + } + + return r0 +} + +// next32 finds the ranged to be added to the table. If ranges overlap between +// multiple tables it clips the result to a non-overlapping range if the +// elements are not fully subsumed. It returns a zero range if there are no more +// ranges. +func (ti tablesIter) next32() unicode.Range32 { + sortIter(ti) + + t0 := ti[0] + if t0.next == atEnd { + return unicode.Range32{} + } + r0 := t0.t.R32[t0.p] + r0.Lo = uint32(t0.next) + + // We restrict the Hi of the current range if it overlaps with another range. + for i := range ti { + tn := ti[i] + // Since our tableIndices are sorted by next, we can break if the there + // is no overlap. The first value of a next range can always be merged + // into the current one, so we can break in case of equality as well. + if rune(r0.Hi) <= tn.next { + break + } + rn := tn.t.R32[tn.p] + rn.Lo = uint32(tn.next) + + // Limit r0.Hi based on next ranges in list, but allow it to overlap + // with ranges as long as it subsumes it. + m := (rn.Lo - r0.Lo) % r0.Stride + if m == 0 && (rn.Stride == r0.Stride || rn.Lo == rn.Hi) { + // Overlap, take the min of the two Hi values: for simplicity's sake + // we only process one range at a time. + if r0.Hi > rn.Hi { + r0.Hi = rn.Hi + } + } else { + // Not a compatible stride. Set to the last possible value before + // rn.Lo, but ensure there is at least one value. + if x := rn.Lo - m; r0.Lo <= x { + r0.Hi = x + } + break + } + } + + // Update the next values for each table. + for i := range ti { + tn := &ti[i] + if rune(r0.Hi) < tn.next { + break + } + rn := tn.t.R32[tn.p] + stride := rune(rn.Stride) + tn.next += stride * (1 + ((rune(r0.Hi) - tn.next) / stride)) + if rune(rn.Hi) < tn.next { + if tn.p++; int(tn.p) == len(tn.t.R32) { + tn.next = atEnd + } else { + tn.next = rune(tn.t.R32[tn.p].Lo) + } + } + } + + if r0.Lo == r0.Hi { + r0.Stride = 1 + } + + return r0 +} -- cgit 1.2.3-korg