In this video, we'll introduce our first data structure, the LIFO buffer.
Many times in embedded programming,
we need to use a data structure to organize our data,
and a good example of this is the buffer.
Oftentimes, we have a source of data,
or a producer, and we also have a destination for data, a consumer.
These two devices usually need to pass data in between one another.
It is possible that these two devices often do not work at the same speed.
Sometimes, one is much faster at producing or consuming the data.
This means that we cannot just call the consumer from
the producer to handle that data directly with a function call.
We need an intermediate location to store data to act as a buffer for this interface.
This buffer is usually implemented as
a data structure in shared memory between these two processing interfaces.
There are multiple types of buffer data structures we will introduce in this module.
First we will discuss the LIFO buffer or last-in-first-out buffer.
The LIFO buffer adds data and removes data from the same end.
The LIFO data structure can be referred to as a stack,
but not be confused with the processor stack.
The LIFO differs from the processor stack because it
adds and removes data of the same type,
whereas the stack on the processor adds or removes
different types of data depending on the type of calling convention or function.
In terms of memory,
this buffer usually is implemented in an array-like format but it is not an array.
LIFO buffers are a contiguous piece of memory that require
special methods to add and remove data.
Here's an example of a LIFO buffer use case.
Say you need to record temperatures throughout the day from
a sensor and you need to find the average temperature of that set.
Suppose you do not care about the order of
the temperature data nor the time the temperature was taken.
Our program might start by storing a temperature item into the buffer.
You would perform an add item to our structure,
also known as a push.
Let's say you follow that up with two more temperature measurements.
You would need to perform two more adds or two more pushes.
Now let's say you are ready to start processing that temperature data.
You would first remove,
or also known as pop, a data item.
You can now process this data element.
You can do another pop to remove the second data item.
Now we'll say we'll follow that up again with another add.
So at this point, we would now have grown our data structure back to two elements.
In the structure, you can see that the first element
added still sits in the structure in the first position.
This is because the buffer removes the most recently added item first.
Given this behavior, let us define what a LIFO buffer data structure might be defined as.
There are a few things you need to track.
You need to track, at a minimum,
the total length of the buffer,
the starting location of the buffer in memory and also the current number of elements.
Alternatively, you may instead track
the current location of the most recently added item.
This would be referred to as the head or the tip.
The difference between the head and the base would be the number
of items that were added.
You also need to define an underlying data type for these members.
In our example, we were adding or removing temperature data points.
But how large was this data?
This is the powerful part of an abstract data structure.
So we can create a LIFO buffer for any type of the fundamental buffer.
Here we have made a LIFO buffer for a byte buffer.
We set the base of the buffer and the head of
the buffer to be of type uint8, both pointers.
The length we'll defined is an unsigned 32-bit int.
This could also be defined as a size_t to help with portability.
This structure could also be implemented with
an array formatting index if the designer so chooses,
but we're going to stay with pointers.
Now you need a way to create and initialize a LIPO data structure.
There are two aspects to this.
First we need to create an instance of the LIFO structure to track a LIFO buffer.
We can do this by allocating a structure that has type LIFO Buf.
Second, we need to allocate the memory of the actual buffer.
These two concepts are different.
We need both a place to store the data in
the buffer region as well as a structure to track how we're using that buffer region.
We can allocate the buffer region on the heap or as an array.
Here, we have used malloc to allocate a region of shared memory for the buffer.
Again, we are allocating in the heap,
so be sure to track the return point or to make sure your allocation was successful.
To initialize your buffer region,
you need to set the buffer base pointer to the allocated region from the heap.
Additionally, when you called malloc,
you need to specify the size to allocate in bytes.
That is where the buffer length comes into play.
Once allocated, you also need to store
that length of the buffer into the buffer structure.
Finally, you need to set our tip pointer to the base
since there is zero data added to your buffer at start.
The tip will point to the next available open spot in the buffer.
When empty, the buffer base pointer should equal the head pointer or the tip pointer.
You technically do not need to track the absolute end of
the buffer because that's imbedded into the structure itself.
We have the base location as well as the length of the buffer,
and with this, we can calculate the end.
Now we will write a function that checks if the buffer is full.
We'll define this function as buffer full and take in
a parameter to a LIFO buffer structure, a pointer.
This structure will return an enumerated type called buffer status or LB status.
This will allow us to define specific states of this buffer in an enumeration.
This could include buffer full,
buffer empty and buffer null.
The first action we need to do is check to see if our buffer pointer is not null.
If it is, perhaps we can return our buffer null error.
Next we will check to see if
the buffer head has moved to the end of the allocated region.
We can do this by calculating the length of the buffer
multiplied by the size of each item and then add that to the base pointer.
If this calculated value is equal to the head pointer,
we know we have already filled our region and we can
return the buffer full enumeration Otherwise,
we'll return a buffer not full.
The next function we will introduce is the buffer add function.
Similar to buffer full,
we need to pass in the buffer structure pointer and also return the LB status type.
Additionally, we're going to also have to provide the parameter that we're going to add.
We start by validating that we have a non-null buffer pointer.
Next, we check to see if our buffer is full.
Here, we can use our buffer full function that we just previously defined.
It is very important that we check for the boundary of
the buffer if it being full so that we do not overfill.
This could cause a condition called the buffer overflow.
This could have many undesirable results and programs often causing some serious errors.
If full, we should skip adding the new item and
perhaps throw an error that the buffer was full or cannot add.
If the buffer is not full,
we should copy the current parameter to add into
the current head position and then move the head to the next available spot.
We can finish this function by returning an LB no error enumeration.
In this quick example,
we learned about a basic LIFO buffer data structure,
a real tongue twister.
This structure is often referred to as a stack data structure as it operates very
similarly to the microcontroller stack in the way that it adds and removes.
The only difference is that your LIFO buffer data structure can be
created for any data type that you wish to buffer.
Next we will look into more complicated data structures.