arc.go 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235
  1. package arc
  2. import (
  3. "sync"
  4. "time"
  5. list "github.com/bahlo/generic-list-go"
  6. "github.com/samber/lo"
  7. )
  8. //modify from https://github.com/alexanderGugel/arc
  9. // Option is part of Functional Options Pattern
  10. type Option[K comparable, V any] func(*ARC[K, V])
  11. func WithSize[K comparable, V any](maxSize int) Option[K, V] {
  12. return func(a *ARC[K, V]) {
  13. a.c = maxSize
  14. }
  15. }
  16. type ARC[K comparable, V any] struct {
  17. p int
  18. c int
  19. t1 *list.List[*entry[K, V]]
  20. b1 *list.List[*entry[K, V]]
  21. t2 *list.List[*entry[K, V]]
  22. b2 *list.List[*entry[K, V]]
  23. mutex sync.Mutex
  24. len int
  25. cache map[K]*entry[K, V]
  26. }
  27. // New returns a new Adaptive Replacement Cache (ARC).
  28. func New[K comparable, V any](options ...Option[K, V]) *ARC[K, V] {
  29. arc := &ARC[K, V]{
  30. p: 0,
  31. t1: list.New[*entry[K, V]](),
  32. b1: list.New[*entry[K, V]](),
  33. t2: list.New[*entry[K, V]](),
  34. b2: list.New[*entry[K, V]](),
  35. len: 0,
  36. cache: make(map[K]*entry[K, V]),
  37. }
  38. for _, option := range options {
  39. option(arc)
  40. }
  41. return arc
  42. }
  43. // Set inserts a new key-value pair into the cache.
  44. // This optimizes future access to this entry (side effect).
  45. func (a *ARC[K, V]) Set(key K, value V) {
  46. a.mutex.Lock()
  47. defer a.mutex.Unlock()
  48. a.set(key, value)
  49. }
  50. func (a *ARC[K, V]) set(key K, value V) {
  51. a.setWithExpire(key, value, time.Unix(0, 0))
  52. }
  53. // SetWithExpire stores any representation of a response for a given key and given expires.
  54. // The expires time will round to second.
  55. func (a *ARC[K, V]) SetWithExpire(key K, value V, expires time.Time) {
  56. a.mutex.Lock()
  57. defer a.mutex.Unlock()
  58. a.setWithExpire(key, value, expires)
  59. }
  60. func (a *ARC[K, V]) setWithExpire(key K, value V, expires time.Time) {
  61. ent, ok := a.cache[key]
  62. if !ok {
  63. a.len++
  64. ent := &entry[K, V]{key: key, value: value, ghost: false, expires: expires.Unix()}
  65. a.req(ent)
  66. a.cache[key] = ent
  67. return
  68. }
  69. if ent.ghost {
  70. a.len++
  71. }
  72. ent.value = value
  73. ent.ghost = false
  74. ent.expires = expires.Unix()
  75. a.req(ent)
  76. }
  77. // Get retrieves a previously via Set inserted entry.
  78. // This optimizes future access to this entry (side effect).
  79. func (a *ARC[K, V]) Get(key K) (value V, ok bool) {
  80. a.mutex.Lock()
  81. defer a.mutex.Unlock()
  82. ent, ok := a.get(key)
  83. if !ok {
  84. return lo.Empty[V](), false
  85. }
  86. return ent.value, true
  87. }
  88. func (a *ARC[K, V]) get(key K) (e *entry[K, V], ok bool) {
  89. ent, ok := a.cache[key]
  90. if !ok {
  91. return ent, false
  92. }
  93. a.req(ent)
  94. return ent, !ent.ghost
  95. }
  96. // GetWithExpire returns any representation of a cached response,
  97. // a time.Time Give expected expires,
  98. // and a bool set to true if the key was found.
  99. // This method will NOT update the expires.
  100. func (a *ARC[K, V]) GetWithExpire(key K) (V, time.Time, bool) {
  101. a.mutex.Lock()
  102. defer a.mutex.Unlock()
  103. ent, ok := a.get(key)
  104. if !ok {
  105. return lo.Empty[V](), time.Time{}, false
  106. }
  107. return ent.value, time.Unix(ent.expires, 0), true
  108. }
  109. // Len determines the number of currently cached entries.
  110. // This method is side-effect free in the sense that it does not attempt to optimize random cache access.
  111. func (a *ARC[K, V]) Len() int {
  112. a.mutex.Lock()
  113. defer a.mutex.Unlock()
  114. return a.len
  115. }
  116. func (a *ARC[K, V]) req(ent *entry[K, V]) {
  117. switch {
  118. case ent.ll == a.t1 || ent.ll == a.t2:
  119. // Case I
  120. ent.setMRU(a.t2)
  121. case ent.ll == a.b1:
  122. // Case II
  123. // Cache Miss in t1 and t2
  124. // Adaptation
  125. var d int
  126. if a.b1.Len() >= a.b2.Len() {
  127. d = 1
  128. } else {
  129. d = a.b2.Len() / a.b1.Len()
  130. }
  131. a.p = min(a.p+d, a.c)
  132. a.replace(ent)
  133. ent.setMRU(a.t2)
  134. case ent.ll == a.b2:
  135. // Case III
  136. // Cache Miss in t1 and t2
  137. // Adaptation
  138. var d int
  139. if a.b2.Len() >= a.b1.Len() {
  140. d = 1
  141. } else {
  142. d = a.b1.Len() / a.b2.Len()
  143. }
  144. a.p = max(a.p-d, 0)
  145. a.replace(ent)
  146. ent.setMRU(a.t2)
  147. case ent.ll == nil && a.t1.Len()+a.b1.Len() == a.c:
  148. // Case IV A
  149. if a.t1.Len() < a.c {
  150. a.delLRU(a.b1)
  151. a.replace(ent)
  152. } else {
  153. a.delLRU(a.t1)
  154. }
  155. ent.setMRU(a.t1)
  156. case ent.ll == nil && a.t1.Len()+a.b1.Len() < a.c:
  157. // Case IV B
  158. if a.t1.Len()+a.t2.Len()+a.b1.Len()+a.b2.Len() >= a.c {
  159. if a.t1.Len()+a.t2.Len()+a.b1.Len()+a.b2.Len() == 2*a.c {
  160. a.delLRU(a.b2)
  161. }
  162. a.replace(ent)
  163. }
  164. ent.setMRU(a.t1)
  165. case ent.ll == nil:
  166. // Case IV, not A nor B
  167. ent.setMRU(a.t1)
  168. }
  169. }
  170. func (a *ARC[K, V]) delLRU(list *list.List[*entry[K, V]]) {
  171. lru := list.Back()
  172. list.Remove(lru)
  173. a.len--
  174. delete(a.cache, lru.Value.key)
  175. }
  176. func (a *ARC[K, V]) replace(ent *entry[K, V]) {
  177. if a.t1.Len() > 0 && ((a.t1.Len() > a.p) || (ent.ll == a.b2 && a.t1.Len() == a.p)) {
  178. lru := a.t1.Back().Value
  179. lru.value = lo.Empty[V]()
  180. lru.ghost = true
  181. a.len--
  182. lru.setMRU(a.b1)
  183. } else {
  184. lru := a.t2.Back().Value
  185. lru.value = lo.Empty[V]()
  186. lru.ghost = true
  187. a.len--
  188. lru.setMRU(a.b2)
  189. }
  190. }
  191. func min(a, b int) int {
  192. if a < b {
  193. return a
  194. }
  195. return b
  196. }
  197. func max(a int, b int) int {
  198. if a < b {
  199. return b
  200. }
  201. return a
  202. }