Home

Awesome

Markiyan's library of "commonly used" functions. The primary platform is FreeBSD. Default compiler: clang (please see configure.ac).

TODO

mncommon/array.h

Resizable realloc(3)-based arrays of the specified element size. Elements are always allocated contiguously in memory.

Automatic initializers (on element allocation) and finalizers (on element deallocation).

Array re-sizing: increment (tail grow by one), decrement (tail shrink by one), arbitrary re-size. Arbitrary re-size can either preserve the items, or clean them up and produce a freshly initialized array of the given size.

Array iterators: first, last, next, previous.

Array traversing given a callback.

In-place sorting, a thin wrapper over standard qsort(3).

Limitations: element addresses are not guaranteed to be preserved after any array re-sizing. Never refer to element addresses from elsewhere unless you use allocate-once arrays.

mncommon/list.h

A limited alternative to sys/queue.h's LIST, although with the completely different interface.

Provides the same functionality as mncommon/array.h plus: element addresses are guaranteed to be preserved after list re-sizing. Elements are never allocated in continuous memory. As in array, provides O(1) access to a list element by index at the cost of maintaining internal index structure. Internal index is implemented as a contiguous array.

Limitations: no insert/delete in the middle of the list, no in-place sort.

mncommon/profile.h

Selective profiling of program code using x86 rdtsc instruction.

Named profiling blocks. Profiling block is a linear fragment of code enclosed between a symmetric pair of PROFILE_START()/PROFILE_STOP() macros. Each block can be assigned a distinctive name.

Pretty printing of profile statistics: total of calls, min/max/avg execution time by profile block.

Compile time turning on/off.

Limitations: recursive blocks are not supported.

mncommon/rbt.h

My own implementation of red-black tree. Not as fast as sys/tree.h's RB_* macros because of probably recursive algorithm as opposed to iterative one in sys/tree.h.

mncommon/trie.h

My own implementation of trie. Reasonably fast, my quick tests over rbt show it's a bit faster.

mncommon/traversedir.h

A thin wrapper over directory(3) 4.2BSD API. Just call traverse_dir(path, cb, udata) to traverse a directory using your own callback.

mncommon/bytestream.h

Combine standard POSIX read(2)/write(2)) and related system calls (send(2), recv(2), etc) with memory management features: automatically extend via realloc(3) when placing data into internal buffer. Conveniently access memory within the buffer, track current position and end of data that have been read up to now. When needed, reuse the buffer before the next read/write. One important thing that has to be remembered: memory locations inside the internal buffer are never guaranteed to be preserved across read()'s and write()'s due to automatic memory management inside the bytestream. Typical patterns of use are suitable for streaming processors or parsers:

static bytestream_t in, out;

void
init(void)
{
    if (bytestream_init(&in, 4096) != 0) {
        FAIL("bytestream_init");
    }
    if (bytestream_init(&out, 4096) != 0) {
        FAIL("bytestream_init");
    }
    in.read_more = bytestream_recv_more;
    in.write = bytestream_send;
}

void
fini(void)
{
    bytestream_fini(&in);
    bytestream_fini(&out);
}

void write_test_request(int fd)
{
    bytestream_cat(&out, "GET / HTTP/1.0\r\n", strlen("GET / HTTP/1.0\r\n"));
    bytestream_cat(&out, "Host: example.com\r\n", strlen("Host: example.com\r\n"));
    bytestream_cat(&out, "\r\n", strlen("\r\n"));
    bytestream_produce_data(&out, fd);
    bytestream_rewind(&out);
}

void read_test_response(int fd)
{
    int done = 0;

    while (!done) {
        if (SNEEDMORE(&in)) {
            bytestream_consume_data(&in, fd);
        }
        /*
         *  -   use SPDATA(&in) to access current data of your interest,
         *      starting from zero offset.
         *  -   use SEDATA(&in) to get the pointer right after the
         *      last byte of the available data.
         *  -   use SAVAIL(&in) to get the size of data you can
         *      process in this cycle.
         *  -   use SADVANCEPOS(&in, ...) to advance current data
         *      pointer as you want. Don't try to advance current data
         *      pointer more than by currently SAVAIL(&in) bytes.
         *      Always do SADVANCEPOS() within the loop to
         *      indicate to bytestream_consume_data() how much data
         *      you have processed.
         *  -   read mncommon/bytestream.h for more macros.
         */
        if (... /* done? */ ) {
            done = 1;
        } else {
            /* state machine to parse a piece of response */
        }
    }
    bytestream_recycle(&in, SPOS(&in));
}

mncommon/json.h

A fast callback-style JSON parser. Unlike traditional JSON parsers, doesn't build objects in memory. Individual callbacks can be registered for the following events: object start, object end, object key, object value, array start, array end, array item. Supported simple data types: string, signed integer, float, boolean, as well as special value null.

mncommon/stqueue.h

Singly-linked tail queue with O(1) insertions at queue's tail (enqueue), O(1) "insertions after" the given element in the middle, and O(1) deletions from head (dequeue). "Insertions before" and removals of any given element to/from the middle are O(n). This is a simpler and more limited implementation of singly-linked tail queue comparing to STAILQ from <sys/queue.h>. It can be best used when you only need enqueue/dequeue operations.

mncommon/dtqueue.h

Doubly-linked tail queue with O(1) additions at queue's tail, enqueue, O(1) removals from head, dequeue, as well as O(1) additions before/after and removals of any given element to/from the middle. This is a simpler and more limited implementation of doubly-linked tail queue comparing to TAILQ from <sys/queue.h>. It can be best used when you only need enqueue operations combined with either dequeue or removals from the middle.

mncommon/memdebug.h

A thin macro-based layer over memory(3) and str{n}dup(3) that allows to track currently allocated memory. Limitation: doesn't track memory allocated by those compilation units that didn't include "mncommon/memdebug.h".

mncommon/dumpm.h

Miscellaneous debugging utilities:

mncommon/util.h

Miscellaneous macros.