You can use the CAS primitive between processes. It is guaranteed to be atomic, which is why semaphores are usually built on top of CAS.
He essentially packs 4 byte strings into integers (assuming 32 bit integers) in an atomic manner. In the strictest sense there are no locks here, but at the end of the day he treats each memory location as its own lock. He also does some busy waiting, which is just a good old spin lock:
while(!InsertAt(data,insertedAt));
Interesting concept but nothing too new. I would also caution against using this code without understanding it first. I don't see much error checking in there.
I think "lock-free" is a misnomer. If you are using a test-and-set instruction, you have incurred all the performance cost of a lock. While much work has been done recently to improve the performance of instructions like CMPXCHG, you still need to treat them like a UDP broadcast message (avoid if possible).
One case I don't think he handles is if a user does a Lookup() for some value in a slot, then tries to delete that slot. In this case, the wrong value might be deleted if an InsertAt() happens in the meanwhile.
I believe FreeBSD also uses this style of buffer for dmesg, which sadly also results in a lot of interlacing if two kernel threads are trying to write to the buffer at once.
He essentially packs 4 byte strings into integers (assuming 32 bit integers) in an atomic manner. In the strictest sense there are no locks here, but at the end of the day he treats each memory location as its own lock. He also does some busy waiting, which is just a good old spin lock:
Interesting concept but nothing too new. I would also caution against using this code without understanding it first. I don't see much error checking in there.