Implement Compare-and-Swap (CAS) in Go

Compare-and-Swap (CAS) is a fundamental atomic operation used in concurrent programming to safely update a shared variable. It allows you to read a value, compare it with an expected value, and if they match, atomically update it to a new value. This challenge asks you to implement a thread-safe CAS operation in Go.

Problem Description

Your task is to create a function, CompareAndSwap, that takes a pointer to an integer, an expected integer value, and a new integer value. The function should atomically check if the value pointed to by the pointer is equal to the expected value. If it is, the function should update the value to newVal and return true. If the value is not equal to expected, the function should not modify the value and return false.

This operation must be thread-safe, meaning that even if multiple goroutines call CompareAndSwap on the same memory location concurrently, the operation will behave correctly without data races.

Key Requirements:

• The function signature should be: func CompareAndSwap(ptr *int, expected, newVal int) bool
• The operation must be atomic.
• The function should return true if the swap occurred, false otherwise.

Expected Behavior:

• If *ptr == expected, then *ptr becomes newVal, and the function returns true.
• If *ptr != expected, then *ptr remains unchanged, and the function returns false.

Edge Cases to Consider:

• Multiple goroutines attempting to swap concurrently.
• Scenarios where the expected value is updated by another goroutine between the read and the potential write.

Examples

Example 1:

Input:
ptr points to 10
expected = 10
newVal = 20

Output:
true
ptr now points to 20

Explanation: The value pointed to by ptr (10) matches expected (10). The value is updated to newVal (20), and the function returns true.

Example 2:

Input:
ptr points to 10
expected = 15
newVal = 20

Output:
false
ptr still points to 10

Explanation: The value pointed to by ptr (10) does not match expected (15). The value is not updated, and the function returns false.

Example 3: (Concurrent Scenario) Imagine two goroutines operating on the same ptr:

Goroutine A: ptr points to 5 expected = 5 newVal = 10

Goroutine B: ptr points to 5 expected = 5 newVal = 15

If Goroutine A successfully reads *ptr as 5, and then before it can write, Goroutine B also reads *ptr as 5 and writes 15, then Goroutine A's subsequent write of 10 would overwrite 15. A proper CAS implementation would ensure only one goroutine succeeds in this scenario.

If Goroutine A performs CAS and succeeds (updates to 10), then when Goroutine B performs its CAS, *ptr will be 10, which does not match its expected of 5, so Goroutine B will return false. The final value will be 10. If Goroutine B performs CAS and succeeds first (updates to 15), then when Goroutine A performs its CAS, *ptr will be 15, which does not match its expected of 5, so Goroutine A will return false. The final value will be 15.

Constraints

• The input ptr will always be a valid non-nil pointer to an int.
• The expected and newVal will be valid int values.
• The implementation should be efficient and suitable for high-concurrency scenarios.

Notes

Go's sync/atomic package provides atomic operations. You will likely need to use functions from this package to ensure atomicity. Consider the atomic.Value type or specific integer atomic functions if appropriate. Think about how to guarantee that the read-compare-write sequence happens as a single, indivisible operation.