List

I’ve just been documenting the list.

I’m finding I’m having to explain a lot about ordered vs unordered usage – I think I’m going to split the list into two, an ordered version and an unordered version.

Update

Man.

Docs take foooooooooooooooooooooooooorever.

I know this of course.

I’m just sayin’ 🙂

The code is basically complete – I need to update build files for all the platforms, and then run test on them all.

It’s all doc work now.

Update

Turned out to be a test bug.

Been writing docs. Getting the filled-in template pages up for each prototype. Done about half.

Inadvertantly detected race condition in ringbuffer read test

Release 7.0.0 features exponential backoff for atomic operations.

There was a bug in this code which meant the backoff loop instead of running up to 0/1/2/4/8/16/32/etc times, was running a very large number of times (billions).

This caused the ringbuffer read test to fault 🙂

I’ve added now a random delay in all the tests, which is present only in debug builds (i.e. slow builds) and I’m running it through now.

Raspberry Pi rocks

Raspberry Pi is up and running and currently executing the test programme.

It’s been flawless. Wrote an image of the Pi port of Debian on an SD card, this has gcc, make, nano, etc, on board. Booted perfectly, logged in, transferred the liblfds source code, compiled it all, first time I’ve build on Linux for a bit so fixed one of two bugs (and as ever always surprised that the MS compiler I’m using doesn’t complain when I used undefined enum types – yes, you read that right!)

Fabulous. Got my own tiny form factor 32-bit quad-core ARM platform, for 70 bucks all told. Couldn’t ask for more.

Raspberry Pi

The Raspberry Pi arrived yesterday.

I ordered the wrong type of SD card – d’oh. I should have ordered a micro SD card.

The local water main broke this morning – it’s just been fixed – so I can now ablute and then head out to buy a card.

The Grand Renaming

Is done.

Directories and filenames are long form, prototypes are short form.

I’ve omitted “multipleconsumer_mutipleproducer” – it’s the default. I might include it in the future, if the addition of other data structure variants would make its use beneficial. Right now it’s not needed, that level of naming complexity does not exist, so it is omitted.

Now I can finally get on with the docs, in their final, proper form.

short form chosen

Like so;

lfds700_btree_au
lfds700_freelist_mm
lfds700_hash_a
lfds700_list_as
lfds700_queue_mm
lfds700_queue_bss
lfds700_ringbuffer_mm
lfds700_stack_mm

It’s alphabetic, with least varying parts first.

With lock-free, you basically get three forms of data structures; fully singlethreaded (which isn’t really lock-free, there are no locks), two threaded where one thread writes and the other only reads (say, single producer/consumer queue), and fully multi-threaded (any number of concurrent whatevers).

I’m toying with the idea of adding in single-threaded variants of these data structures.

The outstanding question for me now though is the long form name.

“lfds700_queue_bounded_singleconsumer_singleproducer” needs to be what it is, but do I really want to add “multipleconsumer_multipleproducer” on the end of every fully multi-threaded data structure name?

ahhhhhhhh

The Raspberry Pi 2 Model B has a MICRO SD slot, not as SD slot…

Anyone want a very nice 16GB SD card?

Naming conventions

So there are data structures and variants upon them, so you can’t just say “queue”. You have to indicate variant.

The current long form versions of the names are;

lfds700_btree_addonly_unbalanced
lfds700_freelist
lfds700_hash_addonly
lfds700_list_addonly_singlylinked
lfds700_queue_mutiple_producer_mutiple_consumer
lfds700_queue_single_producer_single_consumer_bounded
lfds700_ringbuffer_mutiple_producer_mutiple_consumer
lfds700_stack

These forms prefix on all prototypes, i.e.

lfds700_queue_single_producer_single_consumer_bounded_init()
lfds700_queue_single_producer_single_consumer_bounded_cleanup()
lfds700_queue_single_producer_single_consumer_bounded_enqueue()
lfds700_queue_single_producer_single_consumer_bounded_dequeue()
lfds700_queue_single_producer_single_consumer_bounded_query()

Obviously, so long a name is awkward.

The public headers and the per-data structure directory will retain the long form name, to aid comprehension. Possibly the filenames will retain the long form too. However, the prototype must be shortened.

Question is, to what?

These following seem to be the three options;

lfds700_ahash
lfds700_aslist
lfds700_aubtree
lfds700_mmqueue
lfds700_ssbqueue
lfds700_mmringbuffer

===

lfds700_a_hash
lfds700_as_list
lfds700_au_btree
lfds700_mm_queue
lfds700_ssb_queue
lfds700_mm_ringbuffer

===

lfds700_hash_a
lfds700_list_as
lfds700_btree_au
lfds700_queue_mm
lfds700_queue_ssb
lfds700_ringbuffer_mm