This project aims to provide helper macros to ease the implementation of certain
linear data structures like, singly and doubly linked lists, stacks, queues,
and dynamic arrays.
To include the whole collection of data structures include the file 'mlists.h'
into your project. Each data structure can be included independently if desired:
- array.h: dynamic arrays
- singly.h: singly linked lists
- doubly.h: doubly linked lists
- stack.h: stacks
- queue.h: queues
These data structures were designed to work in a cyclic manner, with the porpuse
of easing certain edge cases, and to avoid segfaults in the case of arrays.
Also, every data structure excepting dynamic arrays has 2 sets of macros;
-
To treat the list as an 'explicit container': that is a list that keeps track of its own length in-memory.
-
To treat the list in its primitive form: that is a list that doesn't store any extra information about its length.
Here's a brief description of what each header file was created for:
- container.h: Macros to implement lists that save their length in-memory.
- node_definitions.h: Macros to generate singly and doubly linked lists' nodes as structural types.
- array.h: Macros to deal with dynamic array containers
- singly.h: singly linked lists.
- doubly.h: doubly linked lists.
- stack.h: stacks.
- queue.h: queues.
- mlists.h: Wrap the whole library for simple inclusion.
The intended use consists of mainly 2 steps
-
Create a linear list structural type with the provided macros
-
Generate functions for such type wrapping macros into function definitions.
For example, to create a dynamic array type and an initializer:
#include "some_directory/array.h"
// Create an array container type that holds void* pointers:
typedef struct Array
{
double other;
ARRAY_CONTAINER(void*)
}Array;
// Wrap a macro into function: ptr is previously allocated in-stack or in-heap
Array init_array(Array* ptr, size_t initial_size, double something)
{
return a_compound(Array, ptr, initial_size, .other = something);
}
Arrays are the easiest to get started on.
The rest of data structures as for now, are implemented as linked lists:
- singly.h, stack.h, queue.h: implemented as cyclic singly linked lists.
- doubly.h: implemented as cyclic doubly linked list.
That is, stacks, queues and singly linked lsits have some level of afinity
with respect to their operations.
So, these are the steps to create any kind of linked list:
-
Create a linear list structural type with the provided macros
1.1 Create a node type that contains the desired data.
1.2 Create a container type that contains the list's head and additional data
depending on which type of structure is, for example queues need a pointer to
keep track of their tail.
Let's check this stack example:
#include "some_directory/stack.h"
// typedefd node structural type with the alias ptrnode
def_singly_node(ptrnode, void *data; size_t x;);
// typedefd stack container struct type as ptrstack
def_stack_container(ptrstack, ptrnode);
// typedefd simple stack struct type as ptrstack_simple
def_stack(ptrstack_simple, ptrnode);
// let's create an initializer for each type:
static inline void new_ptrnode(ptrstack* ref)
{
sc_init(ref)
}
static inline void ptrnode_simple new_ptrnode_simp(ptrstack_simple* ref)
{
// yes this macro is different than the used in above's function
s_init(ref)
}
// let's create an insertion operation for each type:
static inline void ptrnode_insert(ptrstack* ref, ptrnode* inserting)
{
sc_add(ref, inserting)
}
static inline void ptrnode_simp_insert(ptrstack_simple* ref, ptrnode* inserting)
{
// yes this macro is different than the used in above's function
s_add(ref, inserting)
}
It is possible to keep track of a list's length, to do this, you have to use
a macro suffixed with "_container" or "_CONTAINER" when definig the list's type.
This adds an arithmetic type member into the struct, which can only be modified
by certain macros that describe insert/delete operations.
The following illustration shows how the memory layout of a simple and container
singly linked list and the node structural type might look like:
As explained, there's a dummy node in the container, and its expected to be a
node's complete type, this dummy node serves to mark the beginning and end of
a list, that is: the last node's right pointer points to this dummy node and the
right pointer of the dummy points to the first element, as illustrated:
Now let's check the operations described as macros for each linear list type.
First of all, there's some sort of macro-naming convention depending on which
type of list the macro is operating on, and wether the list variable it's an
explicit container, that is one that keeps it's length in-memory, or a
simple container, that is one that doesn't keep it's length in-memory.
let's review this naming convention:
the first letters of a macro represent the data structure on which is intended
to be used for example:
- sl: singly list
- dl: doubly list
- s: stack
- q: queue
- a: array
Followed this preffix, there's a symbol that indicates wether the macro
modifies the in-memory length of a container or not. This symbol is a 'c' for
"container", followed by the preffix formed by the initials of the data structure
and the 'c' symbol, there's an underscore followed by the name of the operation,
some common operations for the data structures:
- add: add an element
- pop: pop an element
- init: initialize given a pointer.
This way is easy to tell which datatype is being used, for example the following
macros would mean:
- slc_add: singly list container add
- s_add: stack add
- qc_pop: stack container pop
and so on.
Notice that although there are common operations among all these data structures,
some of them don't require the same type of argument to work.
So now that the important concepts were explained, let's summarize all the
operations for linked lists in a table, (arrays aren't in this table because
those are somewhat their own thing, unlike stacks and queues which are something
of a disguised singly linked list).
Note: simple variant refers to the macro that is intended to be used with
lists that don't keep track of their length
| code/type | stack | queue | singly | doubly |
|---|---|---|---|---|
| compound | (type, stack*, ...) |
(type, queue*, ...) |
(type, singly*, ...) |
(type, doubly*, ...) |
| init | (stack*) |
(queue*) |
(singly) |
(doubly*) |
| add | (stack*, node*) |
(queue*, node*) |
(singly*, node**, node*) |
x |
| pop | (stack*) |
(queue*) |
(singly*, node**)simple variant: (node**) |
(doubly*, node*) |
| get_pop | (stack*, node*) |
(queue*, node*) |
(singly*, node**, node*)simple variant: (node**, node*) |
x |
| adda | x | x | x | (doubly*, node*)simple variant: (node*) |
| addb | x | x | x | (doubly*, node*)simple variant: (node*) |
It's pretty straight forward to get on iterating lists, all data structures
have a macro to get their first node, and some others have a macro to get
their last node, and you can easily use the node type as an iterator.
Here are some important macros that facilitate iteration over lists:
- get_head: get list's first node (works with singly and doubly linked lists).
- get_tail: get lists's last node (only works with doubly linked lists).
- lempty: check wether a list is empty.
- get_len: get the container's lenght.
- mv_next/prev: set a pointer to the next or previous pointer.
- iauto: evaluates if an iterator points to the dummy node.
- cyclic_next/prev: get next/prev node skipping the dummy node.
There's a bit more info in the headers: container.h and node_definitions.h
This macros were designed to represent the a set of basic operations for each
data structure, that means that there might be some algorithms that cannot be
described only with the provided macros.
A big downside for linked lists is the use of a dummy node, that means that if
a node is a big type, every instance of a list then needs at least sizeof(node)
of memory space, however, the tradeoff for this is that there's no need to
check for NULL pointers or other conditionals on edge cases like inserting at
the end or the beginning of a linked list.
So far the names in the macros are pretty weak? in the sense that some of them
are way to generic and may cause troubles, like get_len for instance.
On the other hand, the intended use is to include these headers into .c
files, like some sort of template?, so there's less chance of having macro
name collisions across multiple files.
The last limitation I see with this kind of implementation is that VLA's with
base size of 0 are not allowed as the last member of a node, since that's not
standard defined to my knowledge, however it seems that these VLA's are allowed
if they have at least 1 element.