vendor/golang.org/x/text/unicode/norm/trie.go

   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 package norm
   6
   7 type valueRange struct {
   8         value  uint16 // header: value:stride
   9         lo, hi byte   // header: lo:n
  10 }
  11
  12 type sparseBlocks struct {
  13         values []valueRange
  14         offset []uint16
  15 }
  16
  17 var nfcSparse = sparseBlocks{
  18         values: nfcSparseValues[:],
  19         offset: nfcSparseOffset[:],
  20 }
  21
  22 var nfkcSparse = sparseBlocks{
  23         values: nfkcSparseValues[:],
  24         offset: nfkcSparseOffset[:],
  25 }
  26
  27 var (
  28         nfcData  = newNfcTrie(0)
  29         nfkcData = newNfkcTrie(0)
  30 )
  31
  32 // lookupValue determines the type of block n and looks up the value for b.
  33 // For n < t.cutoff, the block is a simple lookup table. Otherwise, the block
  34 // is a list of ranges with an accompanying value. Given a matching range r,
  35 // the value for b is by r.value + (b - r.lo) * stride.
  36 func (t *sparseBlocks) lookup(n uint32, b byte) uint16 {
  37         offset := t.offset[n]
  38         header := t.values[offset]
  39         lo := offset + 1
  40         hi := lo + uint16(header.lo)
  41         for lo < hi {
  42                 m := lo + (hi-lo)/2
  43                 r := t.values[m]
  44                 if r.lo <= b && b <= r.hi {
  45                         return r.value + uint16(b-r.lo)*header.value
  46                 }
  47                 if b < r.lo {
  48                         hi = m
  49                 } else {
  50                         lo = m + 1
  51                 }
  52         }
  53         return 0
  54 }