trie.go (1233B)
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 // lookup 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 }