Set after Delete seems to delete key

[minsung-moloco]

The following test fails with h.Get(1) returning that the key:value entry does not exist:

func TestHaxmap(t *testing.T) {
    h := haxmap.New[int, string]()
    for i := 1; i <= 10; i++ {
        h.Set(i, strconv.Itoa(i))
    }
    for i := 1; i <= 10; i++ {
        h.Del(i)
    }
    for i := 1; i <= 10; i++ {
        h.Set(i, strconv.Itoa(i))
    }
    for i := 1; i <= 10; i++ {
        id, ok := h.Get(i)
        assert.Equal(t, strconv.Itoa(i), id)
        assert.True(t, ok)
    }
}

I'm assuming it has to do with the lazy delete, where the h.Del(i) only flags it and h.Set(i) deletes the entry rather than setting it, but I haven't looked too deeply into it. My local environment is an M1 Macbook with Go version 1.19.

[semihbkgr]

After some debugging, I have an idea why it gets failed.

When an element is deleted, it should be removed from the map indexes if it is. This remove operation is applied in this function.

func (m *Map[K, V]) removeItemFromIndex(item *element[K, V]) {
    for {
        data := m.metadata.Load()
        index := item.keyHash >> data.keyshifts
        ptr := (*unsafe.Pointer)(unsafe.Pointer(uintptr(data.data) + index*intSizeBytes))

        next := item.next()
        if next != nil && item.keyHash>>data.keyshifts != index {
            next = nil // do not set index to next item if it's not the same slice index
        }
        atomic.CompareAndSwapPointer(ptr, unsafe.Pointer(item), unsafe.Pointer(next))

        if data == m.metadata.Load() { // check that no resize happened
            m.numItems.Add(^uintptr(0)) // decrement counter
            return
        }
    }
}

It tries to remove only the first possible index occurrence. However it is possible that the removed element can be referenced by more than one index.

Example scenario:

index 0 -> element1 element1.next-> element2 index 1 -> element2

after deleting element1

index 0 -> element2 index 1 -> element2

after deleting element2

index 0 -> element2 (marked as deleted) index 1 -> nil

So we have to check if the index is marked as deleted when new element is set (when getting the index of the element in func (md metadata[K, V]) indexElement(hashedKey uintptr) element[K, V])