stablemap/map_test.go at main · homier/stablemap · GitHub

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

import (
	"testing"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestStableMap_Basic(t *testing.T) {
	sm := New[string, int](16)

	// Set and Get
	err := sm.Set("foo", 42)
	require.NoError(t, err)

	v, ok := sm.Get("foo")
	require.True(t, ok)
	assert.Equal(t, 42, v)

	// Update existing key
	err = sm.Set("foo", 100)
	require.NoError(t, err)

	v, ok = sm.Get("foo")
	require.True(t, ok)
	assert.Equal(t, 100, v)

	// Get non-existent key
	_, ok = sm.Get("bar")
	assert.False(t, ok)

	// Delete
	deleted := sm.Delete("foo")
	assert.True(t, deleted)

	_, ok = sm.Get("foo")
	assert.False(t, ok)

	// Delete non-existent key
	deleted = sm.Delete("foo")
	assert.False(t, deleted)
}

func TestStableMap_Stats(t *testing.T) {
	sm := New[int, int](16)

	stats := sm.Stats()
	assert.Equal(t, 0, stats.Size)
	assert.Equal(t, 14, stats.EffectiveCapacity) // 16 * 7/8 = 14

	for i := range 5 {
		_ = sm.Set(i, i)
	}

	stats = sm.Stats()
	assert.Equal(t, 5, stats.Size)
}

func TestStableMap_AutoCompaction(t *testing.T) {
	sm := New[int, int](32)
	effectiveCapacity := sm.Stats().EffectiveCapacity
	threshold := effectiveCapacity / 3

	// Fill the table
	for i := range effectiveCapacity {
		_ = sm.Set(i, i*10)
	}

	// Delete up to the compaction threshold — compaction triggers automatically
	for i := range threshold {
		sm.Delete(i)
	}

	stats := sm.Stats()
	assert.Equal(t, 0, stats.Tombstones, "tombstones should be cleared after auto-compaction")
	assert.Equal(t, effectiveCapacity-threshold, stats.Size)

	// Verify remaining values are intact
	for i := threshold; i < effectiveCapacity; i++ {
		v, ok := sm.Get(i)
		require.True(t, ok)
		assert.Equal(t, i*10, v)
	}
}

func TestStableMap_Reset(t *testing.T) {
	sm := New[int, int](16)

	for i := range 5 {
		_ = sm.Set(i, i)
	}

	assert.Equal(t, 5, sm.Stats().Size)

	sm.Reset()

	assert.Equal(t, 0, sm.Stats().Size)

	_, ok := sm.Get(0)
	assert.False(t, ok)
}

func TestStableMap_ErrTableFull(t *testing.T) {
	sm := New[int, int](8)
	capacity := sm.Stats().EffectiveCapacity

	for i := range capacity {
		err := sm.Set(i, i)
		require.NoError(t, err)
	}

	err := sm.Set(capacity+1, 999)
	assert.ErrorIs(t, err, ErrTableFull)
}

func TestStableMap_WithHashFunc(t *testing.T) {
	customHash := func(k int) uint64 {
		return uint64(k * 31)
	}

	sm := New(16, WithHashFunc[int, int](customHash))

	_ = sm.Set(1, 100)
	v, ok := sm.Get(1)
	require.True(t, ok)
	assert.Equal(t, 100, v)
}