Linked Ring is a C library that provides a data structure called Linked Ring Buffer, designed for scenarios where multiple producers can use a single allocated buffer. It offers an efficient and memory-saving alternative to traditional circular buffers by eliminating the need for separate buffers for each producer.
Read One Size Fits All: Linked Ring instead of a Ring Buffer article which delves deeper into the idea behind the Linked Ring Buffer data structure.
It's just in place replacement for ring buffer, but without taking up all that extra space for multiply buffers used by different producers-consumers.
Struct called struct linked_ring represent a linked ring buffer. This struct contains pointers to the cells that make up the buffer, as well as information about the size of the buffer, the current write positions, and the owners of the elements in the buffer.
A struct called struct lr_cell represent an element, which consists of a data field and a pointer to the next element in the buffer.
The size of each element in the buffer is determined by the type of data stored in the lr_data_t and lr_owner_t fields. If a 64-bit system is used, the element will consume 8 bytes of memory, or 4 bytes in case of 32-bit system.
The library provides a number of functions for initializing and manipulating linked ring buffers, such as:
lr_init(), initializes a new linked ring bufferlr_put(), adds an element to the end of the bufferlr_get(), removes an element from the front of the buffer for a specific ownerIt also provides utility functions such as:
lr_count(), returns the number of elements in the bufferlr_exists(), checks whether an element with a specific owner is present in the bufferlr_set_mutex(), sets the mutex for thread-safe operations.To use the Linked Ring library in your project, you will need to include the lr.h header file in your source code and link against the library when compiling.
To initialize a new linked ring buffer, you can use the lr_init() function. This function takes a pointer to a struct linked_ring and the size of the buffer (in number of elements) as arguments, and returns an lr_result_t enum indicating the result of the operation.
For example:
#include <linked_ring.h>
#define BUFFER_SIZE 10
struct lr_cell cells[BUFFER_SIZE];
struct linked_ring lr;
lr_result_t result = lr_init(&lr, BUFFER_SIZE, cells);
if (result != OK) {
// Error initializing the buffer
}To add data to the end of the buffer, you can use the lr_put() function. This function takes a pointer to a struct linked_ring, a data value, and an owner value as arguments, and returns an lr_result_t enum indicating the result of the operation. The owner value is used to associate the data with a specific consumer or user.
For example:
lr_data_t data = 50303;
lr_owner_t owner = 31337;
lr_result_t result = lr_put(&lr, data, owner);
if (result != OK) {
// Error adding data to the buffer
}To remove data from the front of the buffer, you can use the lr_get() function. This function takes a pointer to a struct linked_ring, a pointer to a lr_data_t variable, and a pointer to a lr_owner_t variable as arguments, and returns an lr_result_t enum indicating the result of the operation. The lr_get() function will store the data value of the element being removed for specific owner.
For example:
lr_owner_t owner = 31337;
lr_data_t obtain_data;
lr_result_t result = lr_get(&lr, &obtain_data, owner);
if (result != OK) {
// Error removing data from the buffer
}The Linked Ring Buffer data structure provides efficient performance characteristics, making it suitable for a wide range of applications. Here's an overview of the performance characteristics and function complexities:
lr_init: The initialization function has a time complexity of O(N), where N is the size of the buffer. It sets up the internal data structure and links the cells in a ring.lr_put: Adding an element to the buffer using the lr_put function has a time complexity of O(1), as it simply appends the element to the buffer. The function performs a constant number of operations regardless of the buffer size.lr_get: Retrieving and removing an element from the buffer using the lr_get function also has a time complexity of O(1). It retrieves the element at the read position and updates linked list chain.lr_count: Counting the number of elements in the buffer using the lr_count function has a time complexity of O(N), where N is the number of elements in the buffer. The function iterates through the linked list of elements and counts them.The Linked Ring data structure requires a fixed amount of memory to store the buffer. The size of each element in the buffer is determined by the type of data stored in the lr_data_t and lr_owner_t fields. If a 64-bit system is used, the element will consume 8 bytes of memory, or 4 bytes in case of 32-bit system.
The total amount of memory consumed by the Linked Ring buffer and structure can be calculated as follows:
Memory Consumption = ((owners_nr + cells_nr) * (sizeof(lr_data_t) + sizeof(struct lr_cell *))) + sizeof(struct linked_ring)Circular buffers and linked rings are both types of fixed-size buffers that are useful for storing and accessing data in a FIFO (first-in, first-out) manner. In a circular buffer, the data is stored in an array, while in a linked ring, the data is stored in a series of linked cells that form a circular chain.
There are a few key differences between circular buffers and linked rings that may influence when you would choose to use one or the other:
The performance of Linked Ring Buffers is due to the fact that the buffer is only initialized once and all consumers can access the same buffer. This reduces the overhead of initializing and allocating multiple buffers, which is required with Circular Buffers.
The performance of Linked Ring Buffers also depends on the size of the buffer and the number of producers. In general, the larger the buffer and the more consumers accessing it, the more memory efficient the Linked Ring Buffer will be.
Linked Ring Buffers use more memory than Circular Buffers. The amount of memory saved by using Linked Ring depends on how many producers can use the buffer.
In N multiple consumer case we allocate just one linked ring buffer and N circular buffers of CELLS_NR cells.
Linked ring buffer size in this case is equal to (OWNERS_NR + CELLS_NR) * (sizeof(lr_data_t) + sizeof(struct lr_cell *)) + sizeof(struct linked_ring)
Therefore, memory needed for allocation for Linked Ring Buffer in multiple producer case is the same while memory consumption of Circular Buffer is equal to OWNERS_NR * CELLS_NR * sizeof(lr_data_t) + sizeof(struct linked_ring)
As we can see, Linked Ring Buffer needs less memory in multiple consumer case.
The Linked Ring Buffer Library is licensed under the MIT License, as described in the LICENSE.md file. This license allows users to use, modify, and distribute the code as they see fit, with minimal restrictions. Please be sure to read and understand the terms of the license before using the code
The Linked Ring Buffer Library is an open source project, and we welcome contributions from the community! There are several areas where you can make a meaningful contribution to the library:
lr_put() function to check if the buffer is full before adding a new element, and provide a flag or configuration option to allow users to specify whether they want to enable overflow behavior or not.lr_data_t field is defined as a void * type, which allows for the storage of any type of data. However, this can be inconvenient for users who want to store specific types of data in the buffer. You can help by providing a more convenient way for users to define the data type for elements in the buffer.We hope these ideas inspire you to make a contribution to the Linked Ring Buffer Library! We look forward to reviewing your pull request.