Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Bulk list data structure.
#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++;
}
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.