trie.go 1.2 KB

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