Llib

A Compact C Utilities Library

Since we are now in the 21st century, llib uses C99, but is compatible with MSVC when compiled as C++. This leads to some 'unnecessary' casting to keep C++ happy, but working in the intersection between C99 and MSVC C++ makes this library very portable. The features it depends on are the freedom to declare variables in for-loops and variadic preprocessor macros.

It has been tested on Windows 7 64-bit (mingw and MSVC), and both Linux 32-bit and 64-bit.

There are a number of kitchen-sink extended C libraries like glibc and the Apache Portable Runtime but these are big and awkward to use on all platforms. llib aims to be small as possible and intended for static linking with your application (the BSD licensing should help with this).

llib provides a refcounting mechanism, extended string functions, dynamically-resizable arrays, doubly-linked lists and maps using binary trees. The aim of this first release is not to produce the most efficient code possible but to explore the API and validate the refcounting semantics.

Using this basic mechanism will cost your program less than 10Kb; a Linux executable using features from the whole library is less than 40Kb.

A note on style: although C has been heavily influenced by C++ over the years, it remains C. So judicious use of statement macros like FOR is fine, if they are suitably hygenic:

#define FOR(i,n) for (int i = 0, n_ = (n); i < n_; i++)

Reference Counting

llib provides refcounted arrays, which contain their own size. You do not ever use free on objects created by llib, and instead use obj_unref.

#include <stdio.h>
#include <llib/obj.h>

int main()
{
    int *ai = array_new(int,10);
    for (int i = 0, n = array_len(ai); i < n; ++i)
        ai[i] = 10.0*i;
    ...
    obj_unref(ai);
    return 0;
}

C does not have smart pointers, but dumb pointers with hidden secrets. All objects are over-allocated, with a hidden header behind the pointer. This keeps track of its size if it is an array, and there is a type descriptor indexing a type object which contains a 'destructor' for the object. Objects start out with a reference count of 1, and the macro obj_ref increments this count; if un-referenced and the count is zero, then we call the destructor and free the memory.

typedef struct ObjHeader_ {
    unsigned int type:14;
    unsigned int is_array:1;
    unsigned int is_ref_container:1;
    unsigned int _ref:16;
    unsigned int _len:32;
} ObjHeader;

This allows for objects to safely share other objects without having to fully take ownership. Reference counting cuts down on the amount of 'defensive copying' needed in typical code.

Unless you specifically define LLIB_NO_REF_ABBREV, the basic operations are aliased as ref and unref; there is also an alias dispose for obj_unref_v which un-references multiple objects.

It is straightforward to create new objects which fit with llib's object scheme:

typedef struct {
    int *ages;
} Bonzo;

static void Bonzo_dispose(Bonzo *self) {
    printf("disposing Bonzo\n");
    unref(self->ages);
}

Bonzo *Bonzo_new(int *ages) {
    Bonzo *self = obj_new(Bonzo,Bonzo_dispose);
    self->ages = ref(ages);
    return self;
}

void test_bonzo() {
    int AGES[] = {45,42,30,16,17};
    int *ages = array_new(int,5);

    FOR(i,5) ages[i] = AGES[i];  //??

    Bonzo *b = Bonzo_new(ages);

    unref(ages);

    printf("%d %d\n",b->ages[0],b->ages[1]);

    unref(b);
}

There is nothing special about such structures; when creating them with the macro obj_new you can provide a dispose function. In this case, Bonzo objects reference the array of ages, and they un-reference this array when they are finally disposed. The test function releases the array ages, and thereafter the only reference to ages is kept within the struct.

Arrays can be reference containers which hold refcounted objects:

    Bonzo *dogs = array_new_ref(Bonzo,3);
    // see? They all happily share the same ages array!
    dogs[0] = Bonzo_new(ages);
    dogs[1] = Bonzo_new(ages);
    dogs[2] = Bonzo_new(ages);
    ...
    // this un-references the Bonzo objects
    // only then the array will die
    unref(dogs);

Sequences

llib provides resizable arrays, called 'seqs'.

float **s = seq_new(float);
seq_add(s,1.2);
seq_add(s,5.2);
....
float *arr = ref(*s);
unref(s);

// array still lives!
FOR(i,array_len(arr)) printf("%f ",arr[i]);
printf("\n");

// alternative macro
// FOR_ARR(float,pf,arr) printf("%f ",*pf);

You treat seqs like a pointer to an array, and use seq_add to ensure that the array is resized when needed. *s is always a valid llib array, and in particular array_len returns the correct size.

A seq keeps a reference to this array, and to get a reference to the array you can just say ref(*s) and then it's fine to dispose of the seq itself. The function seq_array_ref combines these two operations of sharing the array and disposing the seq, plus resizing to fit.

These can also explicitly be reference containers which derereference their objects afterwards if you create them using seq_new_ref.

Linked Lists

A doubly-linked list is a very useful data structure which offers fast insertion at arbitrary posiitions. It is sufficiently simple that it is continuously reinvented, which is one of the endemic C diseases.

    List *l = list_new_str();
    list_add (l,"two");
    list_add (l,"three");
    list_insert_front(l,"one");
    printf("size %d 2nd is '%s'\n",list_size(l),list_get(l,1));
    FOR_LIST(pli, l)
        printf("'%s' ",pli->data);
    printf("\n");
    unref(l);
    printf("remaining %d\n",obj_kount());
    return 0;
//    size 3 2nd is 'two'
//    'one' 'two' 'three'
//    remaining 0

A list of strings is a ref container, but with the added thing that if we try to add a string which is not one of ours then a proper refcounted copy is made. So it is safe to add strings from any source, such as a local buffer on the heap. These are all properly disposed of with the list.

Generally, containers in C are annoying, because of the need for typecasts. (Already with -Wall GCC is giving us some warnings about those printf flags.) Integer types can fit into the pointer payload fine enough, but it isn't possible to directly insert floating-point numbers. List wrappers do a certain amount of pointer aliasing magic for us:

    float ** pw = (float**)listw_new();
    listw_add(pw, 10);
    listw_add(pw, 20);
    listw_add(pw, 30);
    listw_add(pw, 40);
    listw_insert(pw, listw_first(pw), 5);
    printf("first %f\n",listw_get(pw,0));
    FOR_LISTW(p, pw)
        printf("%f\n",**pw);

They are declared as if they were seqs (pointers to arrays) and there's a way to iterate over typed values.

Generally I've found that sequences are easier to use (and much more efficient to iterate over) unless there are many insertions in the middle.

Maps

Maps may have two kinds of keys; integer/pointer, and strings. Like string lists, the latter own their key strings and they will be safely disposed of later. They may contain integer/pointer values, or string values. The difference again is with the special semantics needed to own arbitrary strings.

Typecasting is again irritating, so there are macros map_puti etc for the common integer-valued case:

    Map *m = map_new_str_ptr();
    map_puti(m,"hello",23);
    map_puti(m,"alice",10);
    map_puti(m,"frodo",2353);

    printf("lookup %d\n",map_geti(m,"alice"));

    map_remove(m,"alice");
    FOR_MAP(mi,m)
        printf("key %s value %d\n",mi->key,mi->value);
    unref(m);

The implementation in llib is a binary tree - not in general the best, but it works reliably and has defined iteration order.

Maps can be initialized from arrays of MapkeyValue structs. Afterwards, such an array can be generated using map_to_array:

    MapKeyValue mk[] = {
        {"alpha","A"},
        {"beta","B"},
        {"gamma","C"},
        {NULL,NULL}
    };
    Map *m = map_new_str_str();
    map_put_keyvalues(m,mk);

    MapKeyValue *pkv = map_to_array(m);

    for (MapKeyValue *p = pkv; p->key; ++p)
        printf("%s='%s' ",p->key,p->value);
    printf("\n");

    unref(m);
    unref(pkv);

llib also provides 'simple maps' which are arrays of strings where the even elements are the keys and the odd elements are the values; str_lookup will look up these values by linear search, which is efficient enough for small arrays. smap_new creates a sequence so that smap_put and smap_get do linear lookup; smap_add simply adds a pair which can be more efficient for bulk operations.

Interfaces

Sometimes we are not interested in the particular implementation, only in the abstract functionality. For instance, arrays, lists and maps can all be iterated over, and maps are indexable. This idea was popularized by Java, and the llib concept is similar. List and Map support the Iterable interface:

    #include <llib/interface.h"
    ...
    List *ls = list_new_str();
    list_add(ls, "ein");
    list_add(ls, "zwei");
    list_add(ls, "drei");
    Iterator *it = interface_get_iterator(ls);
    char *s;
    while (it->next(it,&s)) {
        printf("got '%s'\n",s);
    }
    unref(it);

There is an optional function nextpair in the Iterator struct, which grabs key/value pairs:

    Map *m = map_new_str_str();
    map_put(m,"one","1");
    map_put(m,"two","2");
    map_put(m,"three","3");
    Iterator *it = interface_get_iterator(m);
    char *key, *val;
    while (it->nextpair(it,&key,&val)) {
        printf("'%s': '%s'\n",key,val);
    }

next is also defined for Map - it returns the keys - but a non-NULL nextpair means we have an associative array.

Naturally C does not provide us with any special syntactical sugar, especially to create 'objects' that implement interfaces. Here is a simple example - how