Contiguous list implementation in C language

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));
  if (list == NULL) return NULL;

  memcpy(list, &mlist, sizeof(contiguous_list_t));
  list->elems = malloc(list->size_of_elem * list->capacity);
  if (list->elems == NULL) return NULL;
  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);
}

void* list_at(contiguous_list_t const* lst, int index) {
  return (char*)lst->elems + index;
}

int list_find_index(contiguous_list_t* lst, const void* element) {
  int 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;
  }
  if (it >= (lst->size * lst->size_of_elem)) {
    return -1;
  }
  return it;
}

int 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 -1;
  }
  int 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;
  }
  if (it >= (lst->size * lst->size_of_elem)) {
    return -1;
  }
  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_cmp(contiguous_list_t* lst, cmpr_cb cmpr, void const* rsh);

  void* list_at(contiguous_list_t const* lst, int index);

  size_t list_size(contiguous_list_t const* lst);

  size_t list_capacity(contiguous_list_t const* lst);

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

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

#ifdef __cplusplus
}
#endif

#endif // !LIST_H_

test.c

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include "contiguous_list.h"

#include <Windows.h>
#include <time.h>

typedef struct test_t
{
  int x;
  double y;
} test_t;

test_t create_new_test_t(int i)
{
  test_t t = { 
    .x = i,
    .y = (double)i 
  };
  return t;
}

int compare_with_x(const int* key, const test_t* t) {
  //if (size != sizeof(test_t)) return -1;
  return *key - t->x;
}

volatile test_t* test_it;

int main()
{
  const size_t test_count = 100;
  {
    contiguous_list_t* list = create_new_list(sizeof(test_t));
    clock_t start = clock();

    for (size_t i = 0; i < test_count; i++) {
      test_t t = create_new_test_t(i);
      test_it = list_add(list, &t);
    }

    clock_t end = clock();
    double tm_spend = (double)(end - start) / CLOCKS_PER_SEC;
    printf("list add with zero capacity initialization: %f seconds\n", tm_spend);

    {
      srand(time(NULL));
      volatile static int t_ind = 0;
      clock_t start = clock();
      for (size_t i = 0; i < test_count; i++) {
        int rnd_id = rand() % test_count;
        t_ind = list_find_index_cmp(list, compare_with_x, &rnd_id);
        if (t_ind >= 0)
        {
          test_t* it = list_at(list, t_ind);
          assert(it->x == rnd_id);
        }
      }
      clock_t end = clock();
      double tm_spend = (double)(end - start) / CLOCKS_PER_SEC;
      printf("list find random id: %f seconds\n", tm_spend);
    }

    free_list(list);
  }

  srand(time(NULL));
  contiguous_list_t* list = create_new_list_with_cap(sizeof(test_t), test_count);
  {
    clock_t start = clock();
    for (size_t i = 0; i < test_count; i++) {
      int rnd_id = rand() % test_count;
      test_t t = create_new_test_t(rnd_id);
      test_it = list_add(list, &t);
    }
    clock_t end = clock();
    double tm_spend = (double)(end - start) / CLOCKS_PER_SEC;
    printf("list add with full capacity initialization: %f seconds\n", tm_spend);
  }

  {
    clock_t start = clock();
    for (size_t i = 0; i < test_count; i++) {
      int rnd_id = rand() % test_count;
      test_it = list_remove_cmp(list, compare_with_x, &rnd_id);
    }
    clock_t end = clock();
    double tm_spend = (double)(end - start) / CLOCKS_PER_SEC;
    printf("list remove with id: %f seconds\n", tm_spend);
  }

  free_list(list);
}