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.

minilist.h

// 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