FIFO Buffer in C

fifo.c

/**
 * @file fifo.c
 * @author storca (storca@mail.com)
 * @brief Minimal implemntation of a FIFO Buffer in C using pointers
 * @date 2022-10-13
 * 
 * @copyright Copyright (c) 2022
 * 
 *                 -> |first| -> |cell| -> |cell| -> ... -> |cell| -> |last| -> NULL 
 * {FIFO Buffer}   -> [last|  -> NULL
 * 
 * Time complexity (roughly) where n is the number of elements:
 * Base operations are : affectations, memory allocations and dealocations, incrementations
 *      FIFO_init : O(5)
 *      FIFO_enqueue : O(6)
 *      FIFO_dequeue : O(6)
 *      FIFO_close : O(6n)
 * 
 * Spatial complexity (roughly)
 * Each element added to the buffer allocates two new pointers, so that would be 
 *      O(2 * ptr_byte_size * n)
 */

#include <stddef.h> //size_t
#include <stdlib.h> //malloc
#include <stdio.h>

typedef struct Cell Cell;

struct Cell{
    Cell *prev;
    void *content;
};

typedef struct {
    Cell *first; // the first in the queue
    Cell *last; // the one which was added last in the queue
    size_t length;
} FIFOBuffer;

FIFOBuffer* FIFO_init() {
    FIFOBuffer *buff = (FIFOBuffer*) malloc(sizeof(FIFOBuffer));
    buff->first = NULL;
    buff->last = NULL;
    buff->length = 0;
    return buff;
}

/**
 * @brief Enqueue element in FIFO buffer
 * 
 * @param buff FIFOBuffer
 * @param element pointer to the element to enqueue
 */
void FIFO_enqueue(FIFOBuffer *buff, void* element) {
    Cell *cell = (Cell*) malloc(sizeof(Cell));
    cell->content = element;
    cell->prev = NULL;
    
    if (buff->length == 0)
    {
        buff->first = cell;
        buff->length++;
    }
    else if(buff->length == 1)
    {
        buff->first->prev = cell;
        buff->last = cell;
        buff->length++;
    }
    else
    {
        buff->last->prev = cell; //tell the last in the queue that he has someone before him
        buff->last = cell; //change the last cell in queue to the current one
        buff->length++;
    }
}

/**
 * @brief Dequeue item from FIFO buffer
 * 
 * Returns NULL when the buffer is empty
 * @param buff FIFO Buffer
 * @return void* pointer to element, NULL if buffer is empty
 */
void* FIFO_dequeue(FIFOBuffer *buff) {
    Cell* cell = buff->first;
    buff->first = cell->prev;
    void *content = cell->content;
    free(cell);
    buff->length--;
    return content;
}

void FIFO_close(FIFOBuffer *buff)
{
    while(buff->first != NULL)
    {
        FIFO_dequeue(buff);
    }
    free(buff);
}

int main() {
    FIFOBuffer *buff = FIFO_init();
    int vals[100];
    for(int i=0;i<100;++i)
    {
        vals[i] = i+1;
        FIFO_enqueue(buff, (void*) &vals[i]);

        // How to confuse beginers 101 "simple_pointer_trick.c"
        // FIFO_enqueue(buff, (void*) (vals + i*sizeof(int))) //goofy ahh pointer
    }
    for (int i = 0; i < 50; ++i)
    {
        int *val = (int*) FIFO_dequeue(buff);
        printf("%i \t", *val);
    }
    
    FIFO_close(buff);
}

/**
 * @brief Valgrind check
    ==14042== Memcheck, a memory error detector
    ==14042== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
    ==14042== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
    ==14042== Command: ./fifo
    ==14042== 
    --14042-- WARNING: unhandled amd64-linux syscall: 334
    --14042-- You may be able to write your own handler.
    --14042-- Read the file README_MISSING_SYSCALL_OR_IOCTL.
    --14042-- Nevertheless we consider this a bug.  Please report
    --14042-- it at http://valgrind.org/support/bug_reports.html.
    1       2       3       4       5       6       7       8       9       10      11      12      13      14      15      16      17      18      19      20      21      22      23      24   25       26      27      28      29      30      31      32      33      34      35      36      37      38      39      40      41      42      43      44      45      46      47      48   49       50      ==14042== 
    ==14042== HEAP SUMMARY:
    ==14042==     in use at exit: 0 bytes in 0 blocks
    ==14042==   total heap usage: 102 allocs, 102 frees, 2,648 bytes allocated
    ==14042== 
    ==14042== All heap blocks were freed -- no leaks are possible
    ==14042== 
    ==14042== For lists of detected and suppressed errors, rerun with: -s
    ==14042== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
 * 
 */