Data Structures in C

While looking for something else to do, I realized how much I missed writing C code. I really enjoy how the C language allows me, as a programmer, to communicate almost directly with the machine, specifying exactly what and how to execute tasks.

In C, structures are fairly easy to understand, and you can use the built-in primitives provided by the language. However, when dealing with larger structures, libraries, or applications, or when it's impractical to know the dimensions of your dataset at compile time, using malloc and similar functions becomes an invaluable tool. The challenge here is that with this flexibility comes the responsibility of carefully managing memory allocation yourself. Do I really need to reinvent the wheel every time I require a dynamically allocated list with attached operations, or when I need a simple queue?

Enters my new repository of C data structures!

What is included

I've compiled some of the C code I've written and created a library that includes three data structures I believe are essential for most applications:

Vector vector_t also known as a list, which can also be used as a tuple.
Matrix matrix_t a set of operations that manipulates a 1D vector, virtually transforming it into a matrix.
Linked List node_t a simple linked list structure where the list is a pointer to the head and tail nodes.

Vector operations

1vector_t *vector_t_create(const size_t);

1void vector_t_destroy(vector_t *);

1// Retrieves the size (capacity) of `vector_t`
2size_t vector_t_size(const vector_t *);

1// Grows or shrinks a `vector_t`
2void vector_t_resize(vector_t *, const size_t);

1// Compacts a sparsed vector keeping
2// intact the order of members.
3size_t vector_t_compact(vector_t *);

1// Inserts an element at given `size_t` in the `vector_t`
2// Does not replace any value, only places `item` in the 
3// position `index`, moving right all subsequent non-null 
4// items, unless position holds a `NULL` pointer.
5void vector_t_insert(vector_t *, const size_t, void *);

1// Updates or inserts an element at given `size_t` within
2// the `vector_t`
3void vector_t_set(vector_t *, const size_t, void *);

1void *vector_t_get(const vector_t *, const size_t);

1// Removes `count` elements from `start` position
2void vector_t_remove(vector_t *, size_t, const size_t);

1// Inserts member right after the last non-null
2// position of `vector_t`
3void vector_t_push(vector_t *, void *);

1// Move a member to a new index, overriding any
2// value in `destination`
3void vector_t_move(vector_t *, const size_t, const size_t);

1// Swaps poistions of any two members
2void vector_t_swap(vector_t *, const size_t, const size_t);

1// Copy the provided `vector_t` keeping members with same pointer
2vector_t *vector_t_copy(const vector_t *);

1// Reverse the provided `vector_t`
2void vector_t_reverse(vector_t *);

Matrix operations

1matrix_t *matrix_t_create(const size_t rows, const size_t cols);

1void matrix_t_destroy(matrix_t *);

1void matrix_t_set(matrix_t *matrix, const size_t row, const size_t col, void *item);

1void *matrix_t_get(matrix_t *matrix, const size_t row, const size_t col);

Examples

Vector

1#include "vector.h"
2
3int main() {
4  // create vector with size = 3
5  vector_t *v = vector_t_create(3);
6
7  int i = 42;
8  vector_t_set(v, 0, &i);
9
10  // it's the same pointer
11  (*(int *)vector_t_get(v, 0)) == i
12
13  int j = 101;
14  // insert j in 3rd position
15  vector_t_insert(v, 2, &j);
16  // remove two positions, starting in index 1, positions are set to `NULL`
17  // does not actually resize the vector
18  vector_t_remove(v, 1, 2);
19
20  // do not forget to free memory
21  vector_t_destroy(v);
22
23  return 0;
24}

Matrix

1#include "matrix.h"
2
3int main() {
4  // matrix of 2 x 3
5  matrix_t *m = matrix_t_create(2, 3);
6
7  matrix_t_cols(m) == 3;
8  matrix_t_rows(m) == 2;
9
10  int i = 42;
11  matrix_t_set(m, 0, 0, &i);
12
13  matrix_t_destroy(m);
14
15  return 0;
16}

Node (Linked List)

1#include "node.h"
2
3int main() {
4  int s[4] = {1, 37, 42, 101};
5
6  // head(42) -> NULL
7  node_t *head = node_t_create(&s[2], NULL);
8  node_t *tail = NULL;
9
10  // head(37) -> next(42) -> NULL
11  node_t_unshift(&s[1], &head);
12  
13  // head(1) -> next(37) -> next(42) -> NULL
14  node_t_unshift(&s[0], &head);
15
16  // head(1) -> next(37) -> next(42) -> next(101) -> NULL
17  tail = node_t_push(&s[3], &head);
18
19  // head(1)
20  node_t_peek(head);
21
22  // tail(101)
23  node_t_peek(tail);
24
25  // i = 1
26  // head(37) -> next(42) -> next(101) -> NULL
27  int i = *(int *)node_t_shift(&head);
28
29  // head(37)
30  node_t_peek(head);
31
32  // do not forget to free memory
33  node_t_destroy(head);
34
35  return 0;
36}

Building a Queue or Stack with a Linked List

You can leverage the node_t structure to build an efficient queue or stack by maintaining a reference to the head of the stack, or in the case of a queue, both the head and tail. The operations on node_t simplify the implementation of these structures.

Thread-Safe Queue System

Creating a simple thread-safe queue system can be beneficial for many queuing operations. This can be accomplished using the POSIX pthreads module.

queue.c

1#include <pthread.h>
2#include "node.h"
3
4typedef struct queue_t
5{
6  node_t *head;
7  node_t *tail;
8  size_t size;
9  pthread_mutex_t lock;
10} queue_t;
11
12queue_t *queue_t_create()
13{
14  queue_t *q = malloc_realloc(sizeof(*q), NULL);
15  q->size = 0;
16  pthread_mutex_init(&q->lock, NULL);
17  return q;
18}
19
20void queue_t_append(queue_t *q, void *v)
21{
22  pthread_mutex_lock(&q->lock);
23  q->tail = node_t_push(v, q->head == NULL ? &q->head : &q->tail);
24  q->size++;
25  pthread_mutex_unlock(&q->lock);
26}
27
28void queue_t_prepend(queue_t *q, void *v)
29{
30  pthread_mutex_lock(&q->lock);
31  node_t_unshift(v, &q->head);
32  q->size++;
33  pthread_mutex_unlock(&q->lock);
34}
35
36void *queue_shift(queue_t *q)
37{
38  node_t *t = NULL;
39  pthread_mutex_lock(&q->lock);
40
41  if (q->size > 0)
42  {
43    t = node_t_shift(&q->head);
44    q->size--;
45  }
46
47  pthread_mutex_unlock(&q->lock);
48  return t;
49}
50
51size_t queue_size(queue_t *q)
52{
53  return q->size;
54}
55
56void queue_destroy(queue_t *q)
57{
58  pthread_mutex_destroy(&q->lock);
59  node_t_destroy(q->head);
60  free(q);
61}

While very rudimentary, I hope this can be useful for someone too.