Repository: maypok86/otter (go)

Issue:
advised to add some methods
# Clarification and motivation

<!--
Clarify what you want to be done and why.
-->

i wanna add some method to otter to use more conveniently

# Acceptance criteria

<!--
Clarify how we can verify that the task is done.
-->


add three methods i'm thinking now 

1. getKeys() get all keys as a slice of otter
2. getVals() get all vals as a slice of otter
3. setIfAbsent(key,val) with a bool as return result,this can set a new value when the key  is not in otter,but not update valu when the key is not in otter



Pull request description:
[#27] Add SetIfAbsent function
## Description

1. Added `SetIfAbsent(key, value)` function for cache without or constant TTL
2. Added `SetIfAbsent(key, value, ttl)` function for cache with variable TTL

## Related issue(s)

- Resolves #27 

## :white_check_mark: Checklist for your Pull Request

<!--
Ideally a PR has all of the checkmarks set.

If something in this list is irrelevant to your PR, you should still set this
checkmark indicating that you are sure it is dealt with (be that by irrelevance).

If you don't set a checkmark (e. g. don't add a test for new functionality),
you must be able to justify that.
-->

#### Related changes (conditional)

- Tests
    - [x] If I added new functionality, I added tests covering it.
    - [x] If I fixed a bug, I added a regression test to prevent the bug from
      silently reappearing again.

- Documentation
    - [x] I checked whether I should update the docs and did so if necessary:
        - [README](../README.md)

- Public contracts
    - [x] My changes doesn't break project license.

#### Stylistic guide (mandatory)

- [x] My code complies with the [styles guide](https://github.com/uber-go/guide/blob/master/style.md).
- [x] My commit history is clean (only contains changes relating to my
  issue/pull request and no reverted-my-earlier-commit changes) and commit
  messages start with identifiers of related issues in square brackets.

  **Example:** `[#42] Short commit description`

  If necessary both of these can be achieved even after the commits have been
  made/pushed using [rebase and squash](https://git-scm.com/docs/git-rebase).

#### Before merging (mandatory)
- [x] Check __target__  branch of PR is set correctly


Patch:
diff --git a/cache.go b/cache.go
index 0d87306..812a4d3 100644
--- a/cache.go
+++ b/cache.go
@@ -125,6 +125,15 @@ func (c Cache[K, V]) Set(key K, value V) bool {
 	return c.cache.Set(key, value)
 }
 
+// SetIfAbsent if the specified key is not already associated with a value associates it with the given value.
+//
+// If the specified key is not already associated with a value, then it returns false.
+//
+// Also, it returns false if the key-value item had too much cost and the SetIfAbsent was dropped.
+func (c Cache[K, V]) SetIfAbsent(key K, value V) bool {
+	return c.cache.SetIfAbsent(key, value)
+}
+
 // CacheWithVariableTTL is a structure performs a best-effort bounding of a hash table using eviction algorithm
 // to determine which entries to evict when the capacity is exceeded.
 type CacheWithVariableTTL[K comparable, V any] struct {
@@ -143,3 +152,13 @@ func newCacheWithVariableTTL[K comparable, V any](c core.Config[K, V]) CacheWith
 func (c CacheWithVariableTTL[K, V]) Set(key K, value V, ttl time.Duration) bool {
 	return c.cache.SetWithTTL(key, value, ttl)
 }
+
+// SetIfAbsent if the specified key is not already associated with a value associates it with the given value
+// and sets the custom ttl for this key-value item.
+//
+// If the specified key is not already associated with a value, then it returns false.
+//
+// Also, it returns false if the key-value item had too much cost and the SetIfAbsent was dropped.
+func (c CacheWithVariableTTL[K, V]) SetIfAbsent(key K, value V, ttl time.Duration) bool {
+	return c.cache.SetIfAbsentWithTTL(key, value, ttl)
+}
diff --git a/internal/core/cache.go b/internal/core/cache.go
index 1e6384f..2ec9474 100644
--- a/internal/core/cache.go
+++ b/internal/core/cache.go
@@ -35,6 +35,11 @@ func zeroValue[V any]() V {
 	return zero
 }
 
+func getExpiration(ttl time.Duration) uint32 {
+	ttlSecond := (ttl + time.Second - 1) / time.Second
+	return unixtime.Now() + uint32(ttlSecond)
+}
+
 // Config is a set of cache settings.
 type Config[K comparable, V any] struct {
 	Capacity        int
@@ -147,7 +152,7 @@ func (c *Cache[K, V]) afterGet(got *node.Node[K, V]) {
 //
 // If it returns false, then the key-value item had too much cost and the Set was dropped.
 func (c *Cache[K, V]) Set(key K, value V) bool {
-	return c.set(key, value, c.defaultExpiration())
+	return c.set(key, value, c.defaultExpiration(), false)
 }
 
 func (c *Cache[K, V]) defaultExpiration() uint32 {
@@ -162,18 +167,45 @@ func (c *Cache[K, V]) defaultExpiration() uint32 {
 //
 // If it returns false, then the key-value item had too much cost and the SetWithTTL was dropped.
 func (c *Cache[K, V]) SetWithTTL(key K, value V, ttl time.Duration) bool {
-	ttl = (ttl + time.Second - 1) / time.Second
-	expiration := unixtime.Now() + uint32(ttl)
-	return c.set(key, value, expiration)
+	return c.set(key, value, getExpiration(ttl), false)
+}
+
+// SetIfAbsent if the specified key is not already associated with a value associates it with the given value.
+//
+// If the specified key is not already associated with a value, then it returns false.
+//
+// Also, it returns false if the key-value item had too much cost and the SetIfAbsent was dropped.
+func (c *Cache[K, V]) SetIfAbsent(key K, value V) bool {
+	return c.set(key, value, c.defaultExpiration(), true)
 }
 
-func (c *Cache[K, V]) set(key K, value V, expiration uint32) bool {
+// SetIfAbsentWithTTL if the specified key is not already associated with a value associates it with the given value
+// and sets the custom ttl for this key-value item.
+//
+// If the specified key is not already associated with a value, then it returns false.
+//
+// Also, it returns false if the key-value item had too much cost and the SetIfAbsent was dropped.
+func (c *Cache[K, V]) SetIfAbsentWithTTL(key K, value V, ttl time.Duration) bool {
+	return c.set(key, value, getExpiration(ttl), true)
+}
+
+func (c *Cache[K, V]) set(key K, value V, expiration uint32, onlyIfAbsent bool) bool {
 	cost := c.costFunc(key, value)
 	if cost > c.policy.MaxAvailableCost() {
 		return false
 	}
 
 	n := node.New(key, value, expiration, cost)
+	if onlyIfAbsent {
+		res := c.hashmap.SetIfAbsent(n)
+		if res == nil {
+			// insert
+			c.writeBuffer.Insert(node.NewAddTask(n))
+			return true
+		}
+		return false
+	}
+
 	evicted := c.hashmap.Set(n)
 	if evicted != nil {
 		// update
diff --git a/internal/hashtable/map.go b/internal/hashtable/map.go
index 3caa9b8..2c5c901 100644
--- a/internal/hashtable/map.go
+++ b/internal/hashtable/map.go
@@ -187,7 +187,17 @@ func (m *Map[K, V]) Get(key K) (got *node.Node[K, V], ok bool) {
 // Set sets the *node.Node for the key.
 //
 // Returns the evicted node or nil if the node was inserted.
-func (m *Map[K, V]) Set(n *node.Node[K, V]) (evicted *node.Node[K, V]) {
+func (m *Map[K, V]) Set(n *node.Node[K, V]) *node.Node[K, V] {
+	return m.set(n, false)
+}
+
+// SetIfAbsent sets the *node.Node if the specified key is not already associated with a value (or is mapped to null)
+// associates it with the given value and returns null, else returns the current node.
+func (m *Map[K, V]) SetIfAbsent(n *node.Node[K, V]) *node.Node[K, V] {
+	return m.set(n, true)
+}
+
+func (m *Map[K, V]) set(n *node.Node[K, V], onlyIfAbsent bool) *node.Node[K, V] {
 	for {
 	RETRY:
 		var (
@@ -231,6 +241,11 @@ func (m *Map[K, V]) Set(n *node.Node[K, V]) (evicted *node.Node[K, V]) {
 				if n.Key() != prev.Key() {
 					continue
 				}
+				if onlyIfAbsent {
+					// found node, drop set
+					rootBucket.mutex.Unlock()
+					return n
+				}
 				// in-place update.
 				// We get a copy of the value via an interface{} on each call,
 				// thus the live value pointers are unique. Otherwise atomic
diff --git a/internal/s3fifo/policy.go b/internal/s3fifo/policy.go
index 2bb3490..3359d69 100644
--- a/internal/s3fifo/policy.go
+++ b/internal/s3fifo/policy.go
@@ -78,7 +78,7 @@ func (p *Policy[K, V]) evict(deleted []*node.Node[K, V]) []*node.Node[K, V] {
 }
 
 func (p *Policy[K, V]) isFull() bool {
-	return p.small.cost+p.main.cost >= p.maxCost
+	return p.small.cost+p.main.cost > p.maxCost
 }
 
 // Write updates the eviction policy based on node updates.


Test patch:
diff --git a/cache_test.go b/cache_test.go
index e81c47e..ba8961d 100644
--- a/cache_test.go
+++ b/cache_test.go
@@ -26,12 +26,18 @@ import (
 )
 
 func TestCache_Set(t *testing.T) {
-	c, err := MustBuilder[int, int](100).WithTTL(time.Minute).CollectStats().Build()
+	const size = 100
+	c, err := MustBuilder[int, int](size).WithTTL(time.Minute).CollectStats().Build()
 	if err != nil {
 		t.Fatalf("can not create cache: %v", err)
 	}
 
-	for i := 0; i < 100; i++ {
+	for i := 0; i < size; i++ {
+		c.Set(i, i)
+	}
+
+	// update
+	for i := 0; i < size; i++ {
 		c.Set(i, i)
 	}
 
@@ -68,6 +74,63 @@ func TestCache_Set(t *testing.T) {
 	}
 }
 
+func TestCache_SetIfAbsent(t *testing.T) {
+	const size = 100
+	c, err := MustBuilder[int, int](size).WithTTL(time.Minute).CollectStats().Build()
+	if err != nil {
+		t.Fatalf("can not create cache: %v", err)
+	}
+
+	for i := 0; i < size; i++ {
+		if !c.SetIfAbsent(i, i) {
+			t.Fatalf("set was dropped. key: %d", i)
+		}
+	}
+
+	for i := 0; i < size; i++ {
+		if !c.Has(i) {
+			t.Fatalf("key should exists: %d", i)
+		}
+	}
+
+	for i := 0; i < size; i++ {
+		if c.SetIfAbsent(i, i) {
+			t.Fatalf("set wasn't dropped. key: %d", i)
+		}
+	}
+
+	c.Clear()
+
+	cc, err := MustBuilder[int, int](size).WithVariableTTL().CollectStats().Build()
+	if err != nil {
+		t.Fatalf("can not create cache: %v", err)
+	}
+
+	for i := 0; i < size; i++ {
+		if !cc.SetIfAbsent(i, i, time.Hour) {
+			t.Fatalf("set was dropped. key: %d", i)
+		}
+	}
+
+	for i := 0; i < size; i++ {
+		if !cc.Has(i) {
+			t.Fatalf("key should exists: %d", i)
+		}
+	}
+
+	for i := 0; i < size; i++ {
+		if cc.SetIfAbsent(i, i, time.Second) {
+			t.Fatalf("set wasn't dropped. key: %d", i)
+		}
+	}
+
+	if hits := cc.Stats().Hits(); hits != size {
+		t.Fatalf("hit ratio should be 100%%. Hits: %d", hits)
+	}
+
+	cc.Close()
+}
+
 func TestCache_SetWithTTL(t *testing.T) {
 	size := 256
 	c, err := MustBuilder[int, int](size).WithTTL(time.Second).Build()
diff --git a/internal/hashtable/map_test.go b/internal/hashtable/map_test.go
index d848625..87acafe 100644
--- a/internal/hashtable/map_test.go
+++ b/internal/hashtable/map_test.go
@@ -86,6 +86,34 @@ func TestMap_Set(t *testing.T) {
 	}
 }
 
+func TestMap_SetIfAbsent(t *testing.T) {
+	const numberOfNodes = 128
+	m := New[string, int]()
+	for i := 0; i < numberOfNodes; i++ {
+		res := m.SetIfAbsent(newNode[string, int](strconv.Itoa(i), i))
+		if res != nil {
+			t.Fatalf("set was dropped. got: %+v", res)
+		}
+	}
+	for i := 0; i < numberOfNodes; i++ {
+		n := newNode[string, int](strconv.Itoa(i), i)
+		res := m.SetIfAbsent(n)
+		if res == nil {
+			t.Fatalf("set was not dropped. node that was set: %+v", res)
+		}
+	}
+
+	for i := 0; i < numberOfNodes; i++ {
+		n, ok := m.Get(strconv.Itoa(i))
+		if !ok {
+			t.Fatalf("value not found for %d", i)
+		}
+		if n.Value() != i {
+			t.Fatalf("values do not match for %d: %v", i, n.Value())
+		}
+	}
+}
+
 // this code may break if the maphash.Hasher[k] structure changes.
 type hasher struct {
 	hash func(pointer unsafe.Pointer, seed uintptr) uintptr
@@ -372,7 +400,7 @@ func parallelTypedRangeDeleter(t *testing.T, m *Map[int, int], numNodes int, sto
 	cdone <- true
 }
 
-func TestMapOfParallelRange(t *testing.T) {
+func TestMap_ParallelRange(t *testing.T) {
 	const numNodes = 10_000
 	m := New[int, int]()
 	for i := 0; i < numNodes; i++ {
diff --git a/internal/s3fifo/policy_test.go b/internal/s3fifo/policy_test.go
index e6b6391..804463f 100644
--- a/internal/s3fifo/policy_test.go
+++ b/internal/s3fifo/policy_test.go
@@ -111,7 +111,7 @@ func TestPolicy_Update(t *testing.T) {
 
 	p.Read([]*node.Node[int, int]{n1, n1})
 
-	n2 := node.New[int, int](2, 1, 0, 91)
+	n2 := node.New[int, int](2, 1, 0, 92)
 	deleted := p.Write(nil, []node.WriteTask[int, int]{
 		node.NewAddTask(n2),
 	})