1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89
90. 90
91. 91
92. 92
93. 93
94. 94
95. 95
96. 96
97. 97
98. 98
99. 99
100. 100
101. 101
102. 102
103. 103
104. 104
105. 105
106. 106
107. 107
108. 108
109. 109
110. 110
111. 111
112. 112
113. 113
114. 114

//  Copyright (c) 2017 Couchbase, Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// 		http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package vellum

type registryCell struct {
	addr int
	node *builderNode
}

type registry struct {
	builderNodePool *builderNodePool
	table           []registryCell
	tableSize       uint
	mruSize         uint
}

func newRegistry(p *builderNodePool, tableSize, mruSize int) *registry {
	nsize := tableSize * mruSize
	rv := &registry{
		builderNodePool: p,
		table:           make([]registryCell, nsize),
		tableSize:       uint(tableSize),
		mruSize:         uint(mruSize),
	}
	return rv
}

func (r *registry) Reset() {
	var empty registryCell
	for i := range r.table {
		r.builderNodePool.Put(r.table[i].node)
		r.table[i] = empty
	}
}

func (r *registry) entry(node *builderNode) (bool, int, *registryCell) {
	if len(r.table) == 0 {
		return false, 0, nil
	}
	bucket := r.hash(node)
	start := r.mruSize * uint(bucket)
	end := start + r.mruSize
	rc := registryCache(r.table[start:end])
	return rc.entry(node, r.builderNodePool)
}

const fnvPrime = 1099511628211

func (r *registry) hash(b *builderNode) int {
	var final uint64
	if b.final {
		final = 1
	}

	var h uint64 = 14695981039346656037
	h = (h ^ final) * fnvPrime
	h = (h ^ b.finalOutput) * fnvPrime
	for _, t := range b.trans {
		h = (h ^ uint64(t.in)) * fnvPrime
		h = (h ^ t.out) * fnvPrime
		h = (h ^ uint64(t.addr)) * fnvPrime
	}
	return int(h % uint64(r.tableSize))
}

type registryCache []registryCell

func (r registryCache) entry(node *builderNode, pool *builderNodePool) (bool, int, *registryCell) {
	if len(r) == 1 {
		if r[0].node != nil && r[0].node.equiv(node) {
			return true, r[0].addr, nil
		}
		pool.Put(r[0].node)
		r[0].node = node
		return false, 0, &r[0]
	}
	for i := range r {
		if r[i].node != nil && r[i].node.equiv(node) {
			addr := r[i].addr
			r.promote(i)
			return true, addr, nil
		}
	}
	// no match
	last := len(r) - 1
	pool.Put(r[last].node)
	r[last].node = node // discard LRU
	r.promote(last)
	return false, 0, &r[0]

}

func (r registryCache) promote(i int) {
	for i > 0 {
		r.swap(i-1, i)
		i--
	}
}

func (r registryCache) swap(i, j int) {
	r[i], r[j] = r[j], r[i]
}