diff options
Diffstat (limited to 'evict.go')
| -rw-r--r-- | evict.go | 64 |
1 files changed, 37 insertions, 27 deletions
@@ -7,8 +7,8 @@ import ( // EvictionPolicyType defines the type of eviction policy. type EvictionPolicyType int -const ( - // PolicyNone indicates no eviction policy. +const ( + // PolicyNone indicates no eviction policy. PolicyNone EvictionPolicyType = iota PolicyFIFO PolicyLRU @@ -17,7 +17,6 @@ const ( ) // evictionStrategies interface defines the methods for eviction strategies. - // evictionStrategies interface defines the methods for eviction strategies. type evictionStrategies interface { OnInsert(n *node) OnUpdate(n *node) @@ -26,14 +25,13 @@ type evictionStrategies interface { } // evictionPolicy struct holds the eviction strategy and its type. - // evictionPolicy struct holds the eviction strategy and its type. type evictionPolicy struct { evictionStrategies Type EvictionPolicyType evict *node } - // pushEvict adds a node to the eviction list. +// pushEvict adds a node to the eviction list. func pushEvict(node *node, sentinnel *node) { node.EvictPrev = sentinnel node.EvictNext = node.EvictPrev.EvictNext @@ -42,7 +40,6 @@ func pushEvict(node *node, sentinnel *node) { } // SetPolicy sets the eviction policy based on the given type. - // SetPolicy sets the eviction policy based on the given type. func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error { store := map[EvictionPolicyType]func() evictionStrategies{ PolicyNone: func() evictionStrategies { @@ -61,39 +58,41 @@ func (e *evictionPolicy) SetPolicy(y EvictionPolicyType) error { return ltrPolicy{evict: e.evict} }, } + factory, ok := store[y] if !ok { return errors.New("invalid policy") } + e.evictionStrategies = factory() + return nil } -// fifoPolicy struct represents the First-In-First-Out eviction policy. - // fifoPolicy struct represents the First-In-First-Out eviction policy. +type evictOrderedPolicy interface { + evictionStrategies + getEvict() *node +} + type fifoPolicy struct { evict *node shouldEvict bool } // OnInsert adds a node to the eviction list. - // OnInsert adds a node to the eviction list. func (s fifoPolicy) OnInsert(node *node) { pushEvict(node, s.evict) } // OnAccess is a no-op for fifoPolicy. - // OnAccess is a no-op for fifoPolicy. func (fifoPolicy) OnAccess(n *node) { } // OnUpdate is a no-op for fifoPolicy. - // OnUpdate is a no-op for fifoPolicy. func (fifoPolicy) OnUpdate(n *node) { } // Evict returns the oldest node for fifoPolicy. - // Evict returns the oldest node for fifoPolicy. func (s fifoPolicy) Evict() *node { if s.shouldEvict && s.evict.EvictPrev != s.evict { return s.evict.EvictPrev @@ -102,25 +101,26 @@ func (s fifoPolicy) Evict() *node { } } +func (s fifoPolicy) getEvict() *node { + return s.evict +} + // lruPolicy struct represents the Least Recently Used eviction policy. - // lruPolicy struct represents the Least Recently Used eviction policy. type lruPolicy struct { evict *node } // OnInsert adds a node to the eviction list. - // OnInsert adds a node to the eviction list. func (s lruPolicy) OnInsert(node *node) { pushEvict(node, s.evict) } - // OnUpdate moves the accessed node to the front of the eviction list. +// OnUpdate moves the accessed node to the front of the eviction list. func (s lruPolicy) OnUpdate(node *node) { s.OnAccess(node) } // OnAccess moves the accessed node to the front of the eviction list. - // OnAccess moves the accessed node to the front of the eviction list. func (s lruPolicy) OnAccess(node *node) { node.EvictNext.EvictPrev = node.EvictPrev node.EvictPrev.EvictNext = node.EvictNext @@ -128,7 +128,6 @@ func (s lruPolicy) OnAccess(node *node) { } // Evict returns the least recently used node for lruPolicy. - // Evict returns the least recently used node for lruPolicy. func (s lruPolicy) Evict() *node { if s.evict.EvictPrev != s.evict { return s.evict.EvictPrev @@ -137,26 +136,26 @@ func (s lruPolicy) Evict() *node { } } +func (s lruPolicy) getEvict() *node { + return s.evict +} + // lfuPolicy struct represents the Least Frequently Used eviction policy. - // lfuPolicy struct represents the Least Frequently Used eviction policy. type lfuPolicy struct { evict *node } // OnInsert adds a node to the eviction list and initializes its access count. - // OnInsert adds a node to the eviction list and initializes its access count. func (s lfuPolicy) OnInsert(node *node) { pushEvict(node, s.evict) } // OnUpdate increments the access count of the node and reorders the list. - // OnUpdate increments the access count of the node and reorders the list. func (s lfuPolicy) OnUpdate(node *node) { s.OnAccess(node) } // OnAccess increments the access count of the node and reorders the list. - // OnAccess increments the access count of the node and reorders the list. func (s lfuPolicy) OnAccess(node *node) { node.Access++ @@ -169,9 +168,11 @@ func (s lfuPolicy) OnAccess(node *node) { node.EvictNext = node.EvictPrev.EvictNext node.EvictNext.EvictPrev = node node.EvictPrev.EvictNext = node + return } } + node.EvictNext.EvictPrev = node.EvictPrev node.EvictPrev.EvictNext = node.EvictNext @@ -182,7 +183,6 @@ func (s lfuPolicy) OnAccess(node *node) { } // Evict returns the least frequently used node for LFU. - // Evict returns the least frequently used node for LFU. func (s lfuPolicy) Evict() *node { if s.evict.EvictPrev != s.evict { return s.evict.EvictPrev @@ -191,8 +191,11 @@ func (s lfuPolicy) Evict() *node { } } +func (s ltrPolicy) getEvict() *node { + return s.evict +} + // ltrPolicy struct represents the Least Remaining Time eviction policy. - // ltrPolicy struct represents the Least Remaining Time eviction policy. type ltrPolicy struct { evict *node evictZero bool @@ -200,7 +203,6 @@ type ltrPolicy struct { // OnInsert adds a node to the eviction list based on its TTL (Time To Live). // It places the node in the correct position in the list based on TTL. - // OnInsert adds a node to the eviction list based on its TTL (Time To Live). func (s ltrPolicy) OnInsert(node *node) { pushEvict(node, s.evict) @@ -209,21 +211,21 @@ func (s ltrPolicy) OnInsert(node *node) { // OnAccess is a no-op for ltrPolicy. // It does not perform any action when a node is accessed. - // OnAccess is a no-op for ltrPolicy. func (s ltrPolicy) OnAccess(node *node) { } // OnUpdate updates the position of the node in the eviction list based on its TTL. // It reorders the list to maintain the correct order based on TTL. - // OnUpdate updates the position of the node in the eviction list based on its TTL. func (s ltrPolicy) OnUpdate(node *node) { if node.TTL() == 0 { return } + for v := node.EvictPrev; v.EvictPrev != s.evict; v = v.EvictPrev { if v.TTL() == 0 { continue } + if v.TTL() < node.TTL() { node.EvictNext.EvictPrev = node.EvictPrev node.EvictPrev.EvictNext = node.EvictNext @@ -232,13 +234,16 @@ func (s ltrPolicy) OnUpdate(node *node) { node.EvictNext = node.EvictPrev.EvictNext node.EvictNext.EvictPrev = node node.EvictPrev.EvictNext = node + return } } + for v := node.EvictNext; v.EvictNext != s.evict; v = v.EvictNext { if v.TTL() == 0 { continue } + if v.TTL() > node.TTL() { node.EvictNext.EvictPrev = node.EvictPrev node.EvictPrev.EvictNext = node.EvictNext @@ -247,6 +252,7 @@ func (s ltrPolicy) OnUpdate(node *node) { node.EvictNext = node.EvictPrev.EvictNext node.EvictNext.EvictPrev = node node.EvictPrev.EvictNext = node + return } } @@ -254,10 +260,14 @@ func (s ltrPolicy) OnUpdate(node *node) { // Evict returns the node with the least remaining time to live for ltrPolicy. // It returns the node at the end of the eviction list. - // Evict returns the node with the least remaining time to live for ltrPolicy. func (s ltrPolicy) Evict() *node { if s.evict.EvictPrev != s.evict && (s.evict.EvictPrev.TTL() != 0 || s.evictZero) { return s.evict.EvictPrev } + return nil } + +func (s lfuPolicy) getEvict() *node { + return s.evict +} |