Bulk list data structure.

bulk_list.c

#include "bulk_list.h"

#include <stdio.h>
#include <stdlib.h>

bulk_list_t bulk_list_create(int32_t initial_capacity, bulk_list_item_id_t item_size)
{
  bulk_list_t result = { NULL, item_size, initial_capacity, 1, 0, 0, 1 };
  result.items = (uint8_t*)realloc(result.items, result.capacity * result.item_size);
  ((bulk_list_item_t*)&result.items[0])->next = 0;
  return result;
}

void bulk_list_destroy(bulk_list_t* list)
{
  free(list->items);
}

void bulk_list_print_stats(bulk_list_t* list)
{
  printf(
    "%d capacity, %d used, %ld allocs, %ld inserts, %ld deletes\n",
    list->capacity,
    list->used,
    list->num_allocs,
    list->num_inserts,
    list->num_deletes
  );
}

int32_t bulk_list_alloc(bulk_list_t* list)
{
  bulk_list_item_t* first_item = (bulk_list_item_t*)&list->items[0];
  int32_t slot = first_item->next;

  bulk_list_item_t* slot_item = NULL;
  if (slot) {
    slot_item = (bulk_list_item_t*)(list->items + (list->item_size * slot));
    first_item->next = slot_item->next;
  } else if (list->used < list->capacity) {
    slot = list->used++;
    slot_item = (bulk_list_item_t*)(list->items + (list->item_size * slot));
  } else {
    list->capacity++;
    list->num_allocs++;
    list->items = (uint8_t*)realloc(list->items, list->capacity * list->item_size);

    slot = list->used++;
    slot_item = (bulk_list_item_t*)(list->items + (list->item_size * slot));
  }

  list->num_inserts++;
  slot_item->next = -1;
  return slot;
}

void bulk_list_delete(bulk_list_t* list, bulk_list_item_id_t index)
{
  if (index >= list->capacity) return;

  bulk_list_item_t* slot_item = (bulk_list_item_t*)(list->items + (list->item_size * index));
  if (slot_item->next != -1) return;

  bulk_list_item_t* first_item = (bulk_list_item_t*)&list->items[0];
  slot_item->next = first_item->next;
  first_item->next = index;
  list->num_deletes++;
}

bulk_list.h

#ifndef SCAFFOLD_BULK_LIST_H
#define SCAFFOLD_BULK_LIST_H

// Implements a generic, growable list interface for managing lists of
// identical objects where evictions happen at random locations. This is ideal
// for storing game objects like projectiles, sounds, etc.
//
// The underlying data structure allocates an initial fixed-size space which is
// resized as needed. Items are then allocated from within that space with
// evictions leaving "holes" that become part of a "free list" that is used to
// fulfill future insertions rather than using new space.
//
// Usage:
//
// First, you'll need to ensure that whatever data item your munging into a
// list looks as follows:
//
//   typedef struct {
//     bulk_list_item_t _la; // Should not be accessed, must be at top.
//     ...
//   } my_type_t;
//
// This should be all you need to get started and you can now start playing
// with bulk lists of this item.
//
//   bulk_list_t my_list = bulk_list_create(255, sizeof(my_type_t));
//   my_type_t* new_item = bulk_list_add(&my_list, my_type_t);
//   new_item->field = x;
//
// You can also iterate over all the items you've added:
//
//   my_type_t* item; 
//   bulk_list_item_id_t item_id;
//   bulk_list_foreach(&my_list, my_data_t, item, item_id) {
//     printf("%s\n", my_item->field);
//     if (item->odd_number % 2 == 0) {
//       bulk_list_delete(&bd, item_id);
//     }
//   } endeach;
//
// In addition, the structure itself collects some basic metrics on inserts,
// deletes, and allocations for performance tuning if need by.

// TODO(eric): Some nice possible future improvements here.
//   * Make the profiling stuff optional to reduce the size of bulk_list_t
//     structure.

// NOTE(eric): I'm not fully happy with this interface, but it should work well
// enough for a game and save redundant resource management code for various
// things. A few things that are lost in generalizing this implementation:
// 
//   * Access is not nearly as nice, cannot do my_list->items[item_id] but
//     instead have to do (my_data_t*)bulk_list_get(my_list, item_id) which is
//     ultimately translated into roughly the same thing as above, but much
//     more verbose and much less idomatic. This also makes the item ids much
//     less useful.
//   * Having to pass around the data type everywhere is a bit too much. This
//     could probably alleviated by using C++ and then using templates, but
//     this is meant to be pure, high-octane C for now.
//   * bulk_list_foreach is still a bit clunky and requires that users
//     explicitly remember the `endeach` clause.

#include <stdint.h>

typedef int32_t bulk_list_item_id_t;

typedef struct {
  bulk_list_item_id_t next;
} bulk_list_item_t;

typedef struct {
  uint8_t* items;
  int32_t item_size;
  int32_t capacity;
  int32_t used;
  uint64_t num_inserts;
  uint64_t num_deletes;
  uint64_t num_allocs;
} bulk_list_t;

bulk_list_t bulk_list_create(int32_t initial_capacity, int32_t item_size);
void bulk_list_destroy(bulk_list_t* list);
void bulk_list_print_stats(bulk_list_t* list);

bulk_list_item_id_t bulk_list_alloc(bulk_list_t* list);
void bulk_list_delete(bulk_list_t* list, bulk_list_item_id_t index);

#define bulk_list_items(List, Type) ((Type*)(List)->items)
#define bulk_list_get(List, ItemId) ((List)->items + (ItemId * (List)->item_size))
#define bulk_list_add(List) bulk_list_get(List, bulk_list_alloc(List));
#define bulk_list_foreach(List, Type, Item, ItemId)     \
  for (ItemId = 1; ItemId < (List)->used; ItemId++) {   \
    Item = &(((Type*)(List)->items)[ItemId]);             \
    if (((bulk_list_item_t*)Item)->next != -1) continue;
#define endeach }

#endif // SCAFFOLD_BULK_LIST_H