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  // 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  }
    55
View as plain text