C collections implementation [vector, map, string-value map (svmap), dynamic type list (dynlist)]

COLLECTIONS.md

C Collections

C Collections is a light and short C implementation of usefull collections. It contains:

• fixed type vector
• string-int map
• string-fixed type map (svmap)
• dynamic type list (dynlist)

Code Example

Vector example:

vector_t v;
vector_init(&v, char);
{
    char c = '*';
    vector_add(&v, &c);
    if (vector_err(&v))
        return -1;
}
printf("%c\n", vector_get_val(&v, char, 0));
vector_free(&v);

Should output:

*

Map example:

map_t m;
map_init(&m);
map_add(&m, "hello", 42);
if (map_err(&m))
    return -1;
map_add(&m, "world", 69);
if (map_err(&m))
    return -1;
map_balance(&m);
map_foreach_i(&m) {
    printf("[%s] = %d\n", map_iter_key(i), map_iter_value(i));
}
map_del(&m, map_get(&m, "hello"));
map_balance(&m);
map_foreach_i(&m) {
    printf("[%s] = %d\n", map_iter_key(i), map_iter_value(i));
}
map_free(&m);

Should output:

[hello] = 42
[world] = 69
[world] = 69

Svmap example:

svmap_t svm;
svmap_init(&svm, char);
{
    char c = '%';
    svmap_add(&svm, "hello", &c);
    if (svmap_err(&svm))
        return -1;
    c = '$';
    svmap_add(&svm, "world", &c);
    if (svmap_err(&svm))
        return -1;
    svmap_balance(&svm);
}
svmap_foreach_i(&svm) {
    char c = svmap_iter_value_val(&svm, char, i);
    printf("[%s] = '%c'\n", svmap_iter_key(i), c);
}
svmap_free(&svm);

Should output:

[hello] = '%'
[world] = '$'

Dynlist example:

dynlist_t l;
enum { CHAR, STR, INT };
dynlist_init(&l);
dynlist_setup(&l, char);
dynlist_setup(&l, char *);
dynlist_setup(&l, int);
{
    char c = '&';
    char *s = "hello";
    int i = 42;
    dynlist_add(&l, INT, &i);
    dynlist_add(&l, CHAR, &c);
    dynlist_add(&l, STR, &s);
    s = "world";
    dynlist_add(&l, STR, &s);
}
dynlist_foreach_i(&l)
    switch (dynlist_iter_type(i)) {
    case CHAR:
        printf("Got a char: '%c'\n", dynlist_iter_get_val(&l, char, i));
        break;
    case STR:
        printf("Got a string: \"%s\"\n", dynlist_iter_get_val(&l, char *, i));
        break;
    case INT:
        printf("Got an int: %d\n", dynlist_iter_get_val(&l, int, i));
        break;
    }
dynlist_free(&l);

Should output:

Got an int: 42
Got a char: '&'
Got a string: "hello"
Got a string: "world"

Download

Just download as ZIP or check out how to clone a gist.

Usage

This project is header only, the only thing needed is to include the header you need or to copy it if it's short enough.

API Reference

Read carefully all the examples above and refer to the sources for more informations. Feel free to commit comments or corrections.

License

No license available yet.

dynlist.h

#pragma once
#ifndef __DYNLIST_H__
#define __DYNLIST_H__

#include "vector.h"

/* ----- */

typedef vector_t dynlist_t;
typedef int dynlist_sentinel_t[2];

static void _dynlist_setup_size(dynlist_t *l, int size)
{
  vector_t v;

  vector_init_size(&v, size);
  vector_add(l, &v);
}

static int _dynlist_err(dynlist_t *l)
{
    vector_foreach_i(l, vector_t)
        if (vector_err(i))
            return 1;
    return 0;
}

static void _dynlist_add(dynlist_t *l, int type, void *data)
{
  vector_t *v = vector_get(l, type + 1);
  dynlist_sentinel_t sentinel = { type, v->len };
  vector_add(vector_get(l, 0), &sentinel);
  vector_add(v, data);
}

static void _dynlist_insert(dynlist_t *l, int type, void *data, int pos)
{
  vector_t *v = vector_get(l, type + 1);
  dynlist_sentinel_t sentinel = { type, v->len };
  vector_insert(vector_get(l, 0), &sentinel, pos);
  vector_add(v, data);
}

#define dynlist(A) ((dynlist_t *)(A))
#define dynlist_sentinel(A) ((dynlist_sentinel_t *)(A))
#define dynlist_init(A) vector_init(A, vector_t); _dynlist_setup_size(A, sizeof(dynlist_sentinel_t))
#define dynlist_setup_size(A, B) _dynlist_setup_size(A, B)
#define dynlist_setup(A, B) _dynlist_setup_size(A, sizeof(B))
#define dynlist_free(A) vector_foreach_i(A, vector_t) { vector_free(i); } vector_free(A)
#define dynlist_err(A) (_dynlist_err(A) != 0)

#define dynlist_foreach_i(A) vector_foreach_i(vector_get(A, 0), dynlist_sentinel_t)
#define dynlist_foreach_var(A, B) vector_foreach_var(vector_get(A, 0), dynlist_sentinel_t, B)
#define dynlist_foreach(A, B) vector_foreach(vector_get(A, 0), B)

#define dynlist_add(A, B, C) _dynlist_add(A, B, C)
#define dynlist_inset(A, B, C, D) _dynlist_insert(A, B, C, D)

#define dynlist_get_iter(A, B) dynlist_sentinel(vector_get(vector_get(A, 0), B))
#define dynlist_iter_type(A) (**dynlist_sentinel(A))
#define dynlist_iter_get(A, B) vector_get(vector_get(A, dynlist_iter_type(B) + 1), (*dynlist_sentinel(B))[1])
#define dynlist_iter_get_ref(A, B, C) ((B *)(dynlist_iter_get(A, C)))
#define dynlist_iter_get_val(A, B, C)  (*(dynlist_iter_get_ref(A, B, C)))
#define dynlist_get(A, B) dynlist_iter_get(A, dynlist_get_iter(A, B))
#define dynlist_get_ref(A, B, C) dynlist_iter_get_ref(A, B, dynlist_get_iter(A, C))
#define dynlist_get_val(A, B, C) dynlist_iter_get_val(A, B, dynlist_get_iter(A, C))
#define dynlist_last_index(A) vector_last_index(vector_get(A, 0))
#define dynlist_get_last_iter(A) dynlist_sentinel(vector_get(vector_get(A, 0), dynlist_last_index(A)))
#define dynlist_extract(A, B) vector(vector_get(A, (B) + 1))

#define dynlist_del(A, B) vector_del(vector_get(A, **dynlist_get_iter(A, B) + 1), (*dynlist_get_iter(A, B))[1]); vector_del(vector_get(A, 0), B)

#endif /* !__DYNLIST_H__ */

map.h

#pragma once
#ifndef __MAP_H__
#define __MAP_H__

/* system headers */
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/* ----- */

typedef struct
{
    int index;
    char *key;
    int value;
} map_pair_t;

typedef struct _map_item_
{
    map_pair_t *pair;
    map_pair_t data;
    struct _map_item_ *prev;
    struct _map_item_ *next;
    struct _map_item_ *skip;
    struct _map_item_ *back;
} map_item_t;

typedef struct
{
    int min, max, len;
    map_item_t *head;
} map_t;

/* ----- */

static void _map_free(map_t *m)
{
    map_item_t *tmp;
    for (map_item_t *i = m->head; i != NULL;) {
        tmp = i->next;
        free(i);
        i = tmp;
    }
    memset(m, 0, sizeof(map_t));
    m->min = INT_MAX;
}

static int _map_hash_key(char *s, int len)
/*
 * This is random but it works for:
 *  - 1 <= len <= 15
 *  - 0 <= n <= ~12047
 */
{
  int i, up = *s - 32;
  for (int j = 0; j < len - 1; j++) {
    i = s[j + 1] - s[j];
    if (i > 0)
        up += i;
  }
  return (up << 4) + (len - 1);
}

static void _map_push_front(map_t *m, char *key, int value)
{
    map_item_t *item = calloc(1, sizeof(map_item_t));
    if (item != NULL) {
        int index = _map_hash_key(key, strlen(key));
        item->pair = &item->data;
        item->data.index = index;
        item->data.key = key;
        item->data.value = value;
        item->next = m->head;
        if (m->head)
            m->head->prev = item;
        m->head = item;
        if (index > m->max)
            m->max = index;
        if (index < m->min)
            m->min = index;
        m->len++;
        return;
    }
    m->head = NULL;
}

static map_item_t *_map_set_skip_right(map_item_t **map, int len);
static map_item_t *_map_set_skip_left(map_item_t **map, int len)
{
  len /= 2;
  map -= len;
  if (len <= 1)
    return (NULL);
  (*map)->back = _map_set_skip_left(map, len);
  (*map)->skip = _map_set_skip_right(map, len);
  return (*map);
}

map_item_t *_map_set_skip_right(map_item_t **map, int len)
{
  len /= 2;
  map += len;
  if (len <= 1)
    return (NULL);
  (*map)->back = _map_set_skip_left(map, len);
  (*map)->skip = _map_set_skip_right(map, len);
  return (*map);
}

static void _map_balance(map_t *m)
{
    map_item_t *map;
    map_item_t **tab;
    map_pair_t **count;
    map_pair_t *tmp;
    int range, i, j;

    map = m->head;
    tab = malloc((m->len + 1) * sizeof(map_item_t *));
    if (tab == NULL) {
error:
        _map_free(m);
        return;
    }
    for (i = 0; map != NULL; i++, map = map->next)
        tab[i] = map;
    tab[i] = NULL;

    range = m->max - m->min + 1;
    count = calloc(range, sizeof(map_pair_t *));
    if (count == NULL) {
        free(tab);
        goto error;
    }
    for (i = 0; i < m->len; i++)
        count[tab[i]->pair->index - m->min] = tab[i]->pair;
    for (i = m->min, j = 0; i <= m->max; i++)
        if (count[i - m->min])
        {
            tmp = tab[j]->pair;
            tab[j++]->pair = count[i - m->min];
            count[i - m->min] = tmp;
        }
    tab[j - 1]->next = NULL;
    (*tab)->skip = _map_set_skip_right(tab, j);

    free(count);
    free(tab);
}

static map_pair_t *_map_binary_search(map_t *m, char *key)
{
    map_item_t *map = m->head;
    int index = _map_hash_key(key, strlen(key));
    if (index == map->pair->index)
        return (map->pair);
    map = map->skip != NULL ? map->skip : map->next;
    while (map != NULL) {
        if (index == map->pair->index)
            return (map->pair);
        if (index < map->pair->index)
            goto backward;
        map = map->skip != NULL ? map->skip : map->next;
    }
    return NULL;
    while (map != NULL) {
        if (index == map->pair->index)
            return (map->pair);
        if (index > map->pair->index)
            return (NULL);
backward:
        map = map->back != NULL ? map->back : map->prev;
    }
    return NULL;
}

static void _map_del(map_t *m, map_pair_t *p)
/*
 * This function does not change min and max
 * and so does not improve balancing perfs
 * but balancing is still needed after this function
 */
{
    map_item_t *i;
    for (i = m->head; i != NULL; i = i->next)
        i->pair = &i->data;
    for (i = m->head; i != NULL; i = i->next) {
        if (&i->data == p) {
            if (i == m->head)
                m->head = i->next;
            else
                i->prev->next = i->next;
            goto found;
        }
    }
found:
    if (i->next != NULL)
        i->next->prev = i->prev;
    free(i);
    m->len--;
}

#define map(A) ((map_t *)(A))
#define map_init(A) memset(map(A), 0, sizeof(map_t)); map(A)->min = INT_MAX
#define map_free(A) _map_free(A)
#define map_err(A) (map(A)->len != 0 && map(A)->head == NULL)

#define map_foreach_i(A) for (map_item_t *i = map(A)->head; i != NULL; i = i->next)
#define map_foreach_var(A, B) for (map_item_t *B = map(A)->head; B != NULL; B = i->next)
#define map_foreach(A, B) for (B = map(A)->head; B != NULL; B = i->next)
#define map_iter_key(A) (A)->pair->key
#define map_iter_value(A) (A)->pair->value

#define map_add(A, B, C) _map_push_front(A, B, C)
#define map_balance(A) _map_balance(A)
#define map_get(A, B) _map_binary_search(A, B)
#define map_del(A, B) _map_del(A, B)

#endif /* !__MAP_H__ */

svmap.h

#pragma once
#ifndef __SVMAP_H__
#define __SVMAP_H__

#include "map.h"
#include "vector.h"

/* ----- */

typedef struct
{
    map_t m;
    vector_t v;
} svmap_t;

/* ----- */

static void *_svmap_get(svmap_t *svm, char *key)
{
    map_pair_t *p = map_get(&svm->m, key);
    if (p == NULL)
        return NULL;
    return vector_get(&svm->v, p->value);
}

#define svmap(A) ((svmap_t *)(A))
#define svmap_init_size(A, B) map_init(&svmap(A)->m); vector_init_size(&svmap(A)->v, B)
#define svmap_init(A, B) map_init(&svmap(A)->m); vector_init(&svmap(A)->v, B)
#define svmap_free(A) vector_free(&svmap(A)->v); map_free(&svmap(A)->m)
#define svmap_err(A) (vector_err(&svmap(A)->v) || map_err(&svmap(A)->m))

#define svmap_foreach_i(A) map_foreach_i(&svmap(A)->m)
#define svmap_foreach_var(A, B) map_foreach_var(&svmap(A)->m, B)
#define svmap_foreach(A, B) map_foreach(&svmap(A)->m, B)
#define svmap_iter_key(A) (A)->pair->key
#define svmap_iter_value(A, B) vector_get(&svmap(A)->v, (B)->pair->value)
#define svmap_iter_value_ref(A, B, C) vector_get_ref(&svmap(A)->v, B, (C)->pair->value)
#define svmap_iter_value_val(A, B, C) vector_get_val(&svmap(A)->v, B, (C)->pair->value)

#define svmap_add(A, B, C) vector_add(&svmap(A)->v, C); map_add(&svmap(A)->m, B, vector_last_index(&svmap(A)->v))
#define svmap_balance(A) map_balance(&svmap(A)->m)
#define svmap_get(A, B) _svmap_get(A, B)
#define svmap_get_ref(A, B, C) ((B *)(_svmap_get(A, C)))
#define svmap_get_val(A, B, C) (*(svmap_get_ref(A, B, C)))
#define svmap_del(A, B) _map_del(&svmap(A)->m, B)

#endif /* !__SVMAP_H__ */

vector.h

#pragma once
#ifndef __VECTOR_H__
#define __VECTOR_H__

/* system headers */
#include <stdlib.h>
#include <stddef.h>
#include <string.h>

/* ----- */

#define PTR_ADD(A, B) ((void *)(((ptrdiff_t)(A)) + ((ptrdiff_t)(B))))
#define PTR_SUB(A, B) (((ptrdiff_t)(A)) - ((ptrdiff_t)(B)))

/* ----- */

typedef struct
{
    int size;
    void *data;
    int len;
} vector_t;

static void _vector_add(vector_t *v, void *data)
{
    v->data = realloc(v->data, (v->len + 1) * v->size);
    if (v->data != NULL) {
        memcpy(PTR_ADD(v->data, v->len * v->size), data, v->size);
        v->len++;
    }
}

static void _vector_insert(vector_t *v, void *data, int pos)
{
    v->data = realloc(v->data, (v->len + 1) * v->size);
    if (v->data != NULL) {
        void *ptr = PTR_ADD(v->data, pos * v->size);
        memmove(PTR_ADD(ptr, v->size), ptr, (v->len - pos) * v->size);
        memcpy(ptr, data, v->size);
        v->len++;
    }
}

static void _vector_insert_vector(vector_t *v1, vector_t *v2, int pos)
{
    v1->data = realloc(v1->data, (v1->len + v2->len) * v1->size);
    if (v1->data != NULL) {
        void *ptr = PTR_ADD(v1->data, pos * v1->size);
        memmove(PTR_ADD(ptr, v2->len * v1->size), ptr, (v1->len - pos) * v1->size);
        memcpy(ptr, v2->data, v2->len * v1->size);
        v1->len += v2->len;
    }
}

static void _vector_merge(vector_t *v1, vector_t *v2)
{
    v1->data = realloc(v1->data, (v1->len + v2->len) * v1->size);
    if (v1->data != NULL) {
        memcpy(PTR_ADD(v1->data, v1->len * v1->size), v2->data, v2->len * v1->size);
        v1->len += v2->len;
    }
}

static void _vector_del(vector_t *v, int pos)
{
    int newlen = v->len - 1;
    if (pos < newlen)
        memmove(PTR_ADD(v->data, pos * v->size), PTR_ADD(v->data, (pos + 1) * v->size), (newlen - pos) * v->size);
    v->data = realloc(v->data, newlen * v->size);
    v->len--;
}

#define vector(A) ((vector_t *)(A))
#define vector_init_size(A, B) memset(A, 0, sizeof(vector_t)); vector(A)->size = (B)
#define vector_init(A, B) vector_init_size(A, sizeof(B))
#define vector_free(A) if (vector(A)->len > 0) { free(vector(A)->data); vector(A)->data = NULL; vector(A)->len = 0; } (void)0
#define vector_err(A) (vector(A)->len != 0 && vector(A)->data == NULL)

#define vector_foreach_i(A, B) for (B *i = vector(A)->data; PTR_SUB(i, vector(A)->data) < vector(A)->len * vector(A)->size; i = PTR_ADD(i, vector(A)->size))
#define vector_foreach_var(A, B, C) for (B *C = vector(A)->data; PTR_SUB(C, vector(A)->data) < vector(A)->len * vector(A)->size; C = PTR_ADD(C, vector(A)->size))
#define vector_foreach(A, B) for (B = vector(A)->data; PTR_SUB(B, vector(A)->data) < vector(A)->len * vector(A)->size; B = PTR_ADD(B, vector(A)->size))

#define vector_add(A, B) _vector_add(A, B)
#define vector_insert(A, B, C) _vector_insert(A, B, C)
#define vector_insert_vector(A, B, C) _vector_insert_vector(A, B, C)
#define vector_merge(A, B) _vector_merge(A, B)

#define vector_get(A, B) PTR_ADD(vector(A)->data, (B) * vector(A)->size)
#define vector_get_ref(A, B, C) ((B *)(vector_get(A, C)))
#define vector_get_val(A, B, C) (*(vector_get_ref(A, B, C)))
#define vector_last_index(A) (vector(A)->len - 1)
#define vector_get_last(A) vector_get(A, vector_last_index(A))
#define vector_get_last_ref(A, B) ((B *)(vector_get_last(A)))
#define vector_get_last_val(A, B) (*(vector_get_last_ref(A, B)))

#define vector_del(A, B) _vector_del(A, B)

/* ----- */

typedef vector_t vector_int_t;

static int vector_index_of_int(vector_int_t *v, int n)
{
    for (int i = 0; i < v->len; i++)
        if (*(int *)vector_get(v, i) == n)
            return i;
    return -1;
}

#endif /* !__VECTOR_H__ */