среда, 19 сентября 2012 г.

Simplest (and fastest) allocator in C

I need to allocate strings (in UI) with the same length in my MCU program, so I can use: 1) static local buffer in functions or use 2) common buffer. 1) cons: implicit memory "eating" 2) cons: funcs are not reenterable. I use next simple (simplest!) and fast allocator - it allocate strings with the same length. It has only to necessary functions in it's API: allocate and free. Here is the code:
#include <stdint.h>
#include "bset.h"
/** string count */
#define GUI_TMPSTR_N 3
/** max string length */
#define GUI_TMPSTR_MAXLEN 64
/// block of temporary strings with the same length
typedef struct gui_tmpstr_buf_t {
        bset_t pool;
        char buf[GUI_TMPSTR_N][GUI_TMPSTR_MAXLEN];
} gui_tmpstr_buf_t;

#define GUI_TMPSTR_BUF_INITIALIZER() { \
        .pool = BSET_INITIALIZER(), \
        .buf = {0} \
}

// global blocks for allocation
gui_tmpstr_buf_t _tmpstrbuf = GUI_TMPSTR_BUF_INITIALIZER();

/// allocate temporary string
char*
gui_tmpstr_alloc(void) {
        int i;
        BSET_FORCLR(i, &_tmpstrbuf.pool) {
                if (i >= GUI_TMPSTR_N)
                        break;
                BSET_SET(i, &_tmpstrbuf.pool);
                return (_tmpstrbuf.buf[i]);
        }
        return (NULL);
}

/// free allocated tmp. string
void
gui_tmpstr_free(char* ptr) {
        intptr_t i = ((intptr_t)ptr - (intptr_t)_tmpstrbuf.buf);
        if (i <= 0) {
                // ptr is BEFORE base addr (buf)
                return;
        }
        if (i % GUI_TMPSTR_MAXLEN) {
                // ptr is not align on GUI_TMPSTR_MAXLEN
                return;
        }
        i /= GUI_TMPSTR_MAXLEN;
        if (BSET_ISSET(i, &_tmpstrbuf.pool)) {
                // free in pool
                BSET_CLR(i, &_tmpstrbuf.pool);
        }
}
GUI_TMPSTR_MAXLEN defines length of each string, GUI_TMPSTR_N defines available strings number. I used such string in UI (cutting strings, modifing, so on...).

Used bset.h is modified BSD select.h with API (macroses): BSET_SET(), BSET_CLR(), BSET_TGL(), BSET_ISSET(), BSET_FOREACH(), BSET_FORSET(), BSET_FORCLR(), BSET_FOREACHBYTE(), BSET_FOREACHMASK(), BSET_BYTE(), BSET_MASK(), BSET_COPY(), BSET_ZERO().

Most interesting are BSET_CLR() - clear item from bit's set, BSET_SET() - set item in bit's set, BSET_FORCLR() - iterate over cleared items in bit's set - looking for free strings in pool.

Little example:
char* ptr = gui_tmpstr_alloc();
if (ptr) {
  // USAGE of ptr
  ...
  // free:
  gui_tmpstr_free(ptr);
}

Комментариев нет:

Отправить комментарий

Thanks for your posting!