Example implementation contiguous list in C

contiguous_list.c

#include <stdlib.h>
#include <string.h>
#include "contiguous_list.h"

contiguous_list_t* create_new_list(const size_t size_of_elem) {
  return create_new_list_with_cap(size_of_elem, 2);
}

contiguous_list_t* create_new_list_with_cap(const size_t s, const size_t cap) {
  contiguous_list_t mlist = {
    .size_of_elem = s,
    .size = 0,
    .capacity = cap,
    .elems = NULL
  };
  contiguous_list_t* list = (contiguous_list_t*)malloc(sizeof(contiguous_list_t));
  memcpy(list, &mlist, sizeof(contiguous_list_t));
  list->elems = malloc(list->size_of_elem * list->capacity);
  memset(list->elems, 0, list->capacity * list->size_of_elem);
  return list;
}

void free_list(contiguous_list_t* lst) {
  free(lst->elems);
  lst->size = 0;
  lst->capacity = 0;
  free(lst);
}

void* list_first(contiguous_list_t const* lst) {
  return lst->elems;
}

void* list_last(contiguous_list_t const* lst) {
  if (lst->size == 0) return NULL;
  return (char*)lst->elems + (lst->size_of_elem * (lst->size - 1));
}

size_t list_size(contiguous_list_t const* lst) {
  return lst->size;
}

size_t list_capacity(contiguous_list_t const* lst) {
  return lst->capacity;
}

int memcpr_two_elems(void* lhs, void const* rhs, size_t size) {
  return memcmp(lhs, rhs, size);
}

size_t list_find_index(contiguous_list_t* lst, const void* element) {
  size_t it = 0;
  for (it = 0; it < (lst->size * lst->size_of_elem); it += lst->size_of_elem) {
    void* elm = (char*)lst->elems + it;
    if (memcmp(elm, element, lst->size_of_elem) == 0)
      break;
  }
  return it;
}

size_t list_find_index_cmp(
  contiguous_list_t* lst, 
  cmpr_cb cmpr, 
  void const* rhs) 
{
  // buradaki trade-off u iyi bulmak lazim
  if (lst->size > 1000) {
    void* item = bsearch(rhs, lst->elems, lst->size, lst->size_of_elem, cmpr);
    if (item != NULL)
      return ((char*)item - (char*)lst->elems);
    else
      return 0;
  }
  size_t it = 0;
  for (it = 0; it < (lst->size * lst->size_of_elem); it += lst->size_of_elem) {
    void* elm = (char*)lst->elems + it;
    if (cmpr(elm, rhs) == 0)
      break;
  }
  return it;
}

void realloc_contiguous_list(contiguous_list_t* lst) {
  size_t new_capacity = lst->capacity * 2;
  // try realloc in memory first:
  void* realloced_ptr = realloc((void*)lst->elems, new_capacity * lst->size_of_elem);
  // if cannot realloc then malloc new mem block
  if (realloced_ptr == NULL) {
    realloced_ptr = malloc(lst->size_of_elem * new_capacity);
    // consider to use memmove ?
    memcpy(realloced_ptr, lst->elems, lst->size * lst->size_of_elem);
    free(lst->elems);
  }
  lst->elems = realloced_ptr;
  lst->capacity = new_capacity;
}

void* list_add(contiguous_list_t* lst, void* element) {
  if (lst->size == lst->capacity) {
    realloc_contiguous_list(lst);
  }
  void* new_slot = (char*)lst->elems + (lst->size_of_elem * lst->size++);
  memcpy(new_slot, element, lst->size_of_elem);
  return new_slot;
}

void* list_remove_cmp(
  contiguous_list_t* lst, 
  cmpr_cb cmpr,
  void const* rhs) 
{
  size_t it = 0;
  void* item = bsearch(rhs, lst->elems, lst->size, lst->size_of_elem, cmpr);
  if (item == NULL) return NULL;
  it = ((char*)item - (char*)lst->elems);

  size_t new_size = --lst->size;
  size_t remain = (new_size * lst->size_of_elem) - it;

  void* del = (char*)lst->elems + it;
  void* next = (char*)lst->elems + it + lst->size_of_elem;

  memmove(del, next, remain);
  return del;
}

contiguous_list.h

#ifndef CONT_LIST_H_
#define CONT_LIST_H_

#ifdef __cplusplus
extern "C" {
#endif

#include <stdint.h>

typedef int (*cmpr_cb)(void const* key, void const* searching);

typedef struct contiguous_list {
  void* elems;
  const size_t size_of_elem;
  size_t size;
  size_t capacity;
} contiguous_list_t;

contiguous_list_t* create_new_list(const size_t size_of_elem);

contiguous_list_t* create_new_list_with_cap(const size_t size_of_elem, const size_t cap);

void free_list(contiguous_list_t* lst);

void* list_first(contiguous_list_t const* lst);

void* list_last(contiguous_list_t const* lst);

void* list_add(contiguous_list_t* lst, void* element);

//void* list_remove(contiguous_list_t* lst, const void* element);

void* list_remove_cmp(contiguous_list_t* lst, cmpr_cb cmpr, void const* rsh);

size_t list_size(contiguous_list_t const* lst);

size_t list_capacity(contiguous_list_t const* lst);

size_t list_find_index(contiguous_list_t* lst, const void* element);

size_t list_find_index_cmp(contiguous_list_t* lst, cmpr_cb cmpr, void const* rsh);

#ifdef __cplusplus
}
#endif

#endif // !LIST_H_

test.c

#include <stdio.h>
#include "contiguous_list.h"
typedef struct event {
  int id;
  int priority;
} event_t;

event_t create_new_event(int priority) {
  static int evnt_id = 0;
  event_t evnt;
  evnt.id = evnt_id++;
  evnt.priority = priority;
  return evnt;
}
volatile event_t* test_it;

int compare_events_with_id(const void* key, const void* ev) {
  return *(const int*)key - ((const event_t *)ev)->id;
}

void main() {

    contiguous_list_t* list = create_new_list_with_cap(sizeof(event_t), 25);
    for (size_t i = 0; i < 100; i++) {
      event_t new_event = create_new_event(i);
      test_it = list_add(list, &new_event);
    }

    int rnd_id = rand() % 100;
    size_t t_ind = list_find_index_cmp(list, compare_events_with_id, &rnd_id);
    printf("\n found index of %d: %d", rnd_id, t_ind);

    rnd_id = rand() % 100;
    test_it = list_remove_cmp(list, compare_events_with_id, &rnd_id);
    printf("\n removed event %d, replaced with %d", rnd_id, test_it->id);

    free_list(list);
}

working example can be found in here