1// Copyright (c) 2017 Couchbase, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package vellum 16 17type registryCell struct { 18 addr int 19 node *builderNode 20} 21 22type registry struct { 23 builderNodePool *builderNodePool 24 table []registryCell 25 tableSize uint 26 mruSize uint 27} 28 29func newRegistry(p *builderNodePool, tableSize, mruSize int) *registry { 30 nsize := tableSize * mruSize 31 rv := ®istry{ 32 builderNodePool: p, 33 table: make([]registryCell, nsize), 34 tableSize: uint(tableSize), 35 mruSize: uint(mruSize), 36 } 37 return rv 38} 39 40func (r *registry) Reset() { 41 var empty registryCell 42 for i := range r.table { 43 r.builderNodePool.Put(r.table[i].node) 44 r.table[i] = empty 45 } 46} 47 48func (r *registry) entry(node *builderNode) (bool, int, *registryCell) { 49 if len(r.table) == 0 { 50 return false, 0, nil 51 } 52 bucket := r.hash(node) 53 start := r.mruSize * uint(bucket) 54 end := start + r.mruSize 55 rc := registryCache(r.table[start:end]) 56 return rc.entry(node, r.builderNodePool) 57} 58 59const fnvPrime = 1099511628211 60 61func (r *registry) hash(b *builderNode) int { 62 var final uint64 63 if b.final { 64 final = 1 65 } 66 67 var h uint64 = 14695981039346656037 68 h = (h ^ final) * fnvPrime 69 h = (h ^ b.finalOutput) * fnvPrime 70 for _, t := range b.trans { 71 h = (h ^ uint64(t.in)) * fnvPrime 72 h = (h ^ t.out) * fnvPrime 73 h = (h ^ uint64(t.addr)) * fnvPrime 74 } 75 return int(h % uint64(r.tableSize)) 76} 77 78type registryCache []registryCell 79 80func (r registryCache) entry(node *builderNode, pool *builderNodePool) (bool, int, *registryCell) { 81 if len(r) == 1 { 82 if r[0].node != nil && r[0].node.equiv(node) { 83 return true, r[0].addr, nil 84 } 85 pool.Put(r[0].node) 86 r[0].node = node 87 return false, 0, &r[0] 88 } 89 for i := range r { 90 if r[i].node != nil && r[i].node.equiv(node) { 91 addr := r[i].addr 92 r.promote(i) 93 return true, addr, nil 94 } 95 } 96 // no match 97 last := len(r) - 1 98 pool.Put(r[last].node) 99 r[last].node = node // discard LRU 100 r.promote(last) 101 return false, 0, &r[0] 102 103} 104 105func (r registryCache) promote(i int) { 106 for i > 0 { 107 r.swap(i-1, i) 108 i-- 109 } 110} 111 112func (r registryCache) swap(i, j int) { 113 r[i], r[j] = r[j], r[i] 114} 115