ulist.c

Go to the documentation of this file.

/*
 * Copyright (C) 2011 STRATO AG
 * written by Arne Jansen <[email protected]>
 * Distributed under the GNU GPL license version 2.
 */

#include <linux/slab.h>
#include <linux/module.h>
#include "ulist.h"

/*
 * ulist is a generic data structure to hold a collection of unique u64
 * values. The only operations it supports is adding to the list and
 * enumerating it.
 * It is possible to store an auxiliary value along with the key.
 *
 * The implementation is preliminary and can probably be sped up
 * significantly. A first step would be to store the values in an rbtree
 * as soon as ULIST_SIZE is exceeded.
 *
 * A sample usage for ulists is the enumeration of directed graphs without
 * visiting a node twice. The pseudo-code could look like this:
 *
 * ulist = ulist_alloc();
 * ulist_add(ulist, root);
 * ULIST_ITER_INIT(&uiter);
 *
 * while ((elem = ulist_next(ulist, &uiter)) {
 *  for (all child nodes n in elem)
 *      ulist_add(ulist, n);
 *  do something useful with the node;
 * }
 * ulist_free(ulist);
 *
 * This assumes the graph nodes are adressable by u64. This stems from the
 * usage for tree enumeration in btrfs, where the logical addresses are
 * 64 bit.
 *
 * It is also useful for tree enumeration which could be done elegantly
 * recursively, but is not possible due to kernel stack limitations. The
 * loop would be similar to the above.
 */

void ulist_init(struct ulist *ulist)
{
    ulist->nnodes = 0;
    ulist->nodes = ulist->int_nodes;
    ulist->nodes_alloced = ULIST_SIZE;
}
EXPORT_SYMBOL(ulist_init);

void ulist_fini(struct ulist *ulist)
{
    /*
     * The first ULIST_SIZE elements are stored inline in struct ulist.
     * Only if more elements are alocated they need to be freed.
     */
    if (ulist->nodes_alloced > ULIST_SIZE)
        kfree(ulist->nodes);
    ulist->nodes_alloced = 0;   /* in case ulist_fini is called twice */
}
EXPORT_SYMBOL(ulist_fini);

void ulist_reinit(struct ulist *ulist)
{
    ulist_fini(ulist);
    ulist_init(ulist);
}
EXPORT_SYMBOL(ulist_reinit);

struct ulist *ulist_alloc(gfp_t gfp_mask)
{
    struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);

    if (!ulist)
        return NULL;

    ulist_init(ulist);

    return ulist;
}
EXPORT_SYMBOL(ulist_alloc);

void ulist_free(struct ulist *ulist)
{
    if (!ulist)
        return;
    ulist_fini(ulist);
    kfree(ulist);
}
EXPORT_SYMBOL(ulist_free);

int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
{
    return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
}

int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
            u64 *old_aux, gfp_t gfp_mask)
{
    int i;

    for (i = 0; i < ulist->nnodes; ++i) {
        if (ulist->nodes[i].val == val) {
            if (old_aux)
                *old_aux = ulist->nodes[i].aux;
            return 0;
        }
    }

    if (ulist->nnodes >= ulist->nodes_alloced) {
        u64 new_alloced = ulist->nodes_alloced + 128;
        struct ulist_node *new_nodes;
        void *old = NULL;

        /*
         * if nodes_alloced == ULIST_SIZE no memory has been allocated
         * yet, so pass NULL to krealloc
         */
        if (ulist->nodes_alloced > ULIST_SIZE)
            old = ulist->nodes;

        new_nodes = krealloc(old, sizeof(*new_nodes) * new_alloced,
                     gfp_mask);
        if (!new_nodes)
            return -ENOMEM;

        if (!old)
            memcpy(new_nodes, ulist->int_nodes,
                   sizeof(ulist->int_nodes));

        ulist->nodes = new_nodes;
        ulist->nodes_alloced = new_alloced;
    }
    ulist->nodes[ulist->nnodes].val = val;
    ulist->nodes[ulist->nnodes].aux = aux;
    ++ulist->nnodes;

    return 1;
}
EXPORT_SYMBOL(ulist_add);

struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
{
    if (ulist->nnodes == 0)
        return NULL;
    if (uiter->i < 0 || uiter->i >= ulist->nnodes)
        return NULL;

    return &ulist->nodes[uiter->i++];
}
EXPORT_SYMBOL(ulist_next);