Skip to content
Archive of posts filed under the Theory category.

Shortest Path First Routing: Djikstras Algorithm in C

Background I took over a project consisting of PIC chips interfacing with basic 802.15.4 radio modules.  These modules had no routing or mesh networking abilities.  The only feature was the ability to send and receive to other modules that were within range.  When I first received the project the routing method was that every packet was […]

The XOR Linked List In C++

Background It is possible to store the pointers in a linked list in such a way that they ‘overlap’ by using the logical XOR operator.  This allows a user to cut the memory footprint of a basic linked list by 50% at the expense of a couple extra CPU operations.  In today’s world this technique […]

Endianness: Big Endian vs. Little Endian; Shifting and Casting Examples

Background I ran into a bug recently where I was trying to extract the lower 32 bits from a 64 bit pointer referencing two contiguous 32 bit variables in memory.   They were taken out opposite what was expected due to my confusion with the way data is stored.  There is a fairly good writeup […]

The Difference Between Blocking, Lock-Free, and Wait-Free Queues

Background I recently grew an interest in lock free queues and during my research noticed some confusion concerning blocking, lock-free, and wait-free queues.  There are quite a few claimed implementations that do not meet the requirements.  This is my attempt to alleviate some confusion.  I define an interrupt safe queue as one that will succeed […]