Sentinel based Deque


#1

As I continue playing with Rust I was looking for a sentinel deque/list and could not find one. So I decided to try and implement it myself. Coming from Java I thought it’s going to be an easy task :slight_smile: ha ha not so much but eventually I think I succeeded.

Again it’s based on raw pointers, but I believe that the simplicity of the code justifies the unsafety of the raw pointers.
If some one finds it useful -> I am happy :slight_smile: Here is the repo: https://github.com/atsiporu/sentinel_list

The idea is once you push element on to the list you get a handle back. With this handle you can query the element or you can unlink it from the list.
That’s really it.

Because it’s sentinel based I don’t need to do null checks, which is not that expensive but still.

List lacks iterator implementations which I am going to do next, for now its a deque.

Any comments or critique are welcome. If you think there is a better way please let me know.

Thanks.


Trouble implementing linked list mutable iterator variant (based on Gankro's tutorial)
#2

Cool work :+1: Did you ever look at crossbeam's MsQueue? It exposes a thread-safe queue, I think as a linked list with a sentinel, so could be an interesting implementation to trawl through, though it doesn’t give you a linked list API. There is a LinkedList struct in the standard library though. I’m a bit of a casual when it comes to data structures though so my input could be off the mark :slight_smile:


#3

Thanks. No I didn’t see the crossbeam’s MsQueue, but after your post I took a quick look and it looks really cool. I would need to spend more time reading through the code though. Concurrent data structures are interesting beasts. After looking at crossbeam I started to read the blob of Aaron Turon on lock free ds: https://aturon.github.io/blog/2015/08/27/epoch/
And it’s enjoyable reading. I come from a single threaded world and I rarely have to deal with threads, however I am aware of the “counter/epoch” technique, it comes up in a single threaded world two, that’s how java, for example, detects concurrent modification to the collection to invalidate an iterator.