deq

#include <deq.h>

The CTL deq, analogous to the STL std::<deque>, is a container specializing in paged allocations. A deq can be used in place of a vec when push_front and pop_front is desired, or when the collection of elements is large enough to warrant a copy-free reallocation less prone to receiving the C equivalent of a bad_alloc. The performance of a deq is similar to that of a vec with O(1) access time to elements within the deq, but does not guarantee a contiguous array of elements like that of a vec. Pointers to elements within a deq are valid as the deq grows with push_back and push_front, but invalidated when an element is inserted or erased from the middle of the deq.

Example 1: Storing, Sorting, and Summing Integers

A deq can inserted elements at the back of the container, like vec, but also supports fast element insertion at the front of the container:

#include <stdlib.h>
#include <stdio.h>

#define P
#define T int
#include <deq.h>

int compare(int* a, int* b) { return *b < *a; }

int main(void)
{
    deq_int a = deq_int_init();
    for(int i = 0; i < 16; i++)
    {
        deq_int_push_back(&a, rand() % 1024);
        deq_int_push_front(&a, rand() % 1024);
    }
    deq_int_sort(&a, compare);
    int sum = 0;
    foreach(deq_int, &a, it)
    {
        printf("%d\n", *it.ref);
        sum += *it.ref;
    }
    printf("sum: %d\n", sum);
    deq_int_free(&a);
}

As per usual, #define P states no per-element cleanup is necessary once the deq is freed. A deq offers O(1) access time to any element within a deq, given access is performed with _at. The foreach statement above can be replaced with a conventional for loop:

    int sum = 0;
    for(size_t i = 0; i < a.size; i++)
    {
        int* ref = deq_int_at(&a, i);
        printf("%d\n", *ref);
        sum += *ref;
    }

Example 2: Queuing and Inspecting Strings

The deq container serves as an ideal double ended queue. By enqueuing random IP addresses to the back of a deq, the front of the deq can be popped, inspected, and re-inserted, all within O(1) time.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#include <str.h>

#define T str
#include <deq.h>

int main(void)
{
    deq_str a = deq_str_init();
    for(size_t i = 0; i < 32; i++)
    {
        str ip = str_init("");
        size_t max = 4;
        for(size_t j = 0; j < max; j++)
        {
            char sub[16];
            sprintf(sub, "%03d", rand() % UINT8_MAX);
            str_append(&ip, sub);
            if(j != max - 1)
                str_append(&ip, ".");
        }
        deq_str_push_back(&a, ip);
    }
    str s = str_copy(deq_str_front(&a));
    deq_str_pop_front(&a);
    puts(str_c_str(&s));
    deq_str_push_front(&a, s);
    deq_str_free(&a);
}

The deq_str container omits the #define P directive, and inherits _copy and _free from the str type provided by the #include <str.h> line. At time of freeing, each str element of the deq is correctly freed.