Skip to content

Instantly share code, notes, and snippets.

@zloedi
Last active Aug 27, 2020
Embed
What would you like to do?
Single header C library to turn your buffer into a generic doubly linked list, by sacrificing the first few elements. Provides some typesafety through the ML_Add() macro.
// Copyright (c) 2020 Stoiko Todorov
// This work is licensed under the terms of the MIT license.
// For a copy, see https://opensource.org/licenses/MIT.
// This lib turns an array into a linked list by sacrificing the first
// few elements of the array
#ifndef ML_TYPE
// by default max numItems is 65535, redefine ML_TYPE if needed
#define ML_TYPE unsigned short
#endif
typedef ML_TYPE mltype_t;
typedef struct {
mltype_t numItems;
mltype_t numWasted;
mltype_t fresh;
mltype_t chain[1];
} mlhead_t;
static inline void ML_Init( void *l, int numItems, int itemSize ) {
mlhead_t *head = ( mlhead_t* )l;
int waste = sizeof( *head ) + sizeof( *head->chain ) * 2 * numItems;
int numWasted = waste / itemSize + 1;
if ( numWasted < numItems ) {
mltype_t *next = head->chain;
mltype_t *prev = head->chain + numItems + 1;
prev[0] = numItems;
next[0] = numWasted;
next[numItems] = numItems;
for ( int i = numWasted; i < numItems; i++ ) {
int i0 = ( i + 0 ) % numItems;
int i1 = ( i + 1 ) % numItems;
next[i0] = prev[i0] = i1;
}
head->numWasted = numWasted;
head->numItems = numItems;
}
}
static inline int ML_Full( void *l, int numItems, int itemSize ) {
mlhead_t* head = ( mlhead_t* )l;
if ( ! head->numItems ) {
ML_Init( l, numItems, itemSize );
}
return ! *head->chain;
}
static inline int ML_Fresh( void *l ) {
return ( ( mlhead_t* )l )->fresh;
}
static inline int ML_Alloc( void *l ) {
mlhead_t *head = ( mlhead_t* )l;
mltype_t *next = head->chain;
mltype_t *prev = head->chain + head->numItems + 1;
// remove from free chain
int i = next[0];
next[0] = next[i];
// add to used chain
next[i] = next[head->numItems];
prev[i] = head->numItems;
next[prev[i]] = i;
prev[next[i]] = i;
head->fresh = i;
return head->fresh;
}
static inline int ML_Free( void *l, int i ) {
int result;
mlhead_t* head = ( mlhead_t* )l;
if ( i >= head->numWasted && i < head->numItems ) {
mltype_t *next = head->chain;
mltype_t *prev = head->chain + head->numItems + 1;
if ( prev[i] != next[i] ) {
// remove from used chain
next[prev[i]] = next[i];
prev[next[i]] = prev[i];
// add to free chain
next[i] = prev[i] = next[0];
next[0] = i;
// ok
result = 0;
} else {
// double remove
result = 2;
}
} else {
// bad index
result = 1;
}
return result;
}
// public(er) API
// assumes at least the first sizeof( ML_TYPE ) bytes of *l are zeroed out
// should call ML_Init( l, ... ) explicitly otherwise
static inline int ML_NextFree( void *l, int i ) {
return ( ( mlhead_t* )l )->chain[i];
}
static inline int ML_FirstFree( void *l ) {
return ML_NextFree( l, 0 );
}
static inline int ML_Next( void *l, int i ) {
mlhead_t* head = ( mlhead_t* )l;
int next = head->chain[i];
return next < head->numItems ? next : 0;
}
static inline int ML_First( void *l ) {
return ML_Next( l, ( ( mlhead_t* )l )->numItems );
}
#define ML_AddBuf(b,n,v) \
ML_Full((b),(n),sizeof(*(b))) \
? -1 \
: ((b)[ML_Alloc((b))] = (v), ML_Fresh((b)))
#define ML_Add(a,v) ML_AddBuf((a),sizeof((a))/sizeof(*(a)),v)
#define ML_Remove(a,i) ML_Free((a),(i))
// example usage
#if 0
static void PrintFree( void *list ) {
printf( "free: " );
for ( int i = ML_FirstFree( list ); i; i = ML_NextFree( list, i ) ) {
printf( "%d, ", i );
}
printf( "\n" );
}
static void PrintUsed( void *list ) {
printf( "used: " );
for ( int i = ML_First( list ); i; i = ML_Next( list, i ) ) {
printf( "%d, ", i );
}
printf( "\n" );
}
typedef struct {
int a, b, c, d;
} sample_t;
#define NUMX 17
static sample_t g_list[NUMX];
static void ML_Example( void ) {
int rr;
PrintFree( g_list );
PrintUsed( g_list );
if ( ( rr = ML_Remove( g_list, NUMX - 2 ) ) != 0 ) {
printf( "remove from empty list test result: %d\n", rr );
}
for ( int j = 0; j < 8; j++ ) {
int n0 = rand() % ( NUMX * 2 );
for ( int i = 0; i < n0; i++ ) {
sample_t xxx = {
.a = rand () & 255,
.b = rand () & 255,
.c = rand () & 255,
.d = rand () & 255,
};
int added = ML_Add( g_list, xxx );
if ( added == -1 ) {
printf( "failed to add element, LIST IS FULL\n" );
} else {
printf( "added element at %d\n", added );
}
PrintFree( g_list );
PrintUsed( g_list );
}
int n1 = rand() % ( ( n0 + 1 ) * 2 );
for ( int i = 0; i < n1; i++ ) {
int removed = rand() % NUMX;
printf( "removing %d...\n", removed );
if ( ( rr = ML_Remove( g_list, removed ) ) != 0 ) {
printf( "failed to remove, error: '%s'\n",
rr == 1 ? "BAD_INDEX" : "DOUBLE_REMOVE" );
}
PrintFree( g_list );
PrintUsed( g_list );
}
}
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment