talloc

Talloc is a hierarchical memory allocator. That means that it is similar to malloc, but it can also track the natural tree-like structure of memory dependencies. Freeing a talloc-ed chunk of memory will free all of its dependencies.

Example

As an example we develop the allocation operations for a bi-dimensional matrix of integers. For simplicity, the example does not handle out-of-memory errors.

struct matrix {
    size_t rows;
    size_t cols;
    int **data;
};

struct matrix *new_matrix(size_t rows, size_t cols) {

    struct matrix *m = tzalloc(sizeof(*m), NULL);

    m->rows = rows;
    m->cols = cols;
    m->data = tzalloc(rows * sizeof(*m->data), m);

    for (size_t i = 0; i < rows; i++)
        m->data[i] = talloc(cols * sizeof(**m->data), m->data);

    return m;
}

void free_matrix(struct matrix *m) {

    tfree(m);
}

API

The API is really simple and each function does what you expect. For a detailed explanation of each function, see the inline documentation.

The only detail is that you cannot mix the malloc and talloc families of functions for a given chunk of memory. Once a chunk is allocated with talloc (malloc), it can only be freed with tfree (free).

Basic

void *talloc(size_t size, void *parent);

void *tzalloc(size_t size, void *parent);

void *trealloc(void *mem, size_t size);

void *tfree(void *mem);

Advanced

/**
 * Get the parent of a talloc'ed memory chunk (the chunk on which it depends).
 */
void *talloc_get_parent(void *mem);

/**
 * Change the parent of a talloc'ed memory chunk. This will affect the
 * dependencies of the entire subtree rooted at the given chunk.
 */
void talloc_set_parent(void *mem, void *parent);

/**
 * Remove a talloc'ed memory chunk from the dependency tree, taking care of its
 * children (they now depend on parent).
 */
void talloc_steal(void *mem, void *parent);

Overhead

For each talloc'ed chunk of memory, 3 extra pointers are used to maintain the internal structure. The time overhead for using talloc is quite small, since (as you can see) the code is extremely simple.

Credits

This library was created in an attempt to simplify the awesome but unnecessarily bloated Samba talloc.

Relevant

Source: xkcd