bucket array

bucket_array.c

// See bucket_array.h
// Define the same variables, include the .h file and then include this file in one .c file.

#ifndef BA_PREFIX
#error "BA_PREFIX must be defined"
#endif

#ifndef BA_TYPEDEF_NAME
#error "BA_TYPEDEF_NAME must be defined"
#endif

#ifndef BA_TYPE
#error "BA_TYPE must be defined"
#endif

#ifndef BA_BUCKET_SIZE
#define BA_BUCKET_SIZE 64
#endif

#include "arena.h"

BA_ALLOC_FUNCTION(BA_PREFIX, BA_TYPEDEF_NAME, BA_TYPE) {
  BA_TYPEDEF_NAME *ba = arena_push_size(arena, sizeof(BA_TYPEDEF_NAME));
  ba->arena = arena;
  ba->buckets = NULL;
  ba->buckets_count = 0;
  ba->buckets_capacity = 0;
  ba->count = 0;
  ba->capacity = 0;
  return ba;
}

BA_AT_FUNCTION(BA_PREFIX, BA_TYPEDEF_NAME, BA_TYPE) {
  return &ba->buckets[i / BA_VALS_PER_BUCKET(BA_BUCKET_SIZE, BA_TYPE)]->e[i % BA_VALS_PER_BUCKET(BA_BUCKET_SIZE, BA_TYPE)];
}

BA_PUSH_FUNCTION(BA_PREFIX, BA_TYPEDEF_NAME, BA_TYPE) {
  if (ba->count >= ba->capacity) {
    if (ba->buckets_count >= ba->buckets_capacity) {
      // realloc the pointer array.
      if (ba->buckets_capacity == 0) {
        ba->buckets_capacity = 2;
      } else {
        ba->buckets_capacity *= 2;
      }
      typeof(ba->buckets) prev_buckets = ba->buckets;
      // todo: arena_push_array probabay.
      ba->buckets = arena_push_size(ba->arena, sizeof(*ba->buckets) *
                                                   ba->buckets_capacity);
      if (prev_buckets) {
        for (size_t i = 0; i < ba->buckets_count; i++) {
          ba->buckets[i] = prev_buckets[i];
        }
      }
    }
    // add a new bucket.
    ba->buckets[ba->buckets_count++] =
        arena_push_size(ba->arena, BA_BUCKET_SIZE);
    ba->capacity += BA_VALS_PER_BUCKET(BA_BUCKET_SIZE, BA_TYPE);
  }

  size_t bucket_i = ba->count / BA_VALS_PER_BUCKET(BA_BUCKET_SIZE, BA_TYPE);
  size_t bucket_slot = ba->count % BA_VALS_PER_BUCKET(BA_BUCKET_SIZE, BA_TYPE);
  ba->buckets[bucket_i]->e[bucket_slot] = val;
  ba->count++;
  return &ba->buckets[bucket_i]->e[bucket_slot];
}

bucket_array.h

// Bucket Array
// An dynamic array that stores elements in buckets of a fixed size.
// Works better than a normal dynamic array with arenas because the elements
// never get reallocated as the array grows. Pointers to elements share the same
// lifetime as the arena.
// Biggest downside is that you can't overload indexing in c, so you have to use
// the ba_type_at(ba, i) macro to access elements.

// This header is a "meta program" or a "generic" implementation. To use it you
// must define
// * BA_PREFIX as the function prefix. e.g. ba_i for ba_i_push and ba_i_at
// * BA_TYPEDEF_NAME as the name for the bucket array type. e.g. IntBA
// * BA_TYPE as the type of the elements in the bucket array. e.g. int

// The bucket size defaults to 64 bytes, but you can change it by defining
// BA_BUCKET_SIZE before including this header.

// There are no include guards yet so you must only include this header in one
// file. Typically done by including from another header that does have guards.
// To get the implementation you need to also define the same variables and then
// include "bucket_array.c" in one .c file.

// This is not a standalone library right now. It depends on "arena.h".
// @todo(steve): Add defines for the allocator so it can be used in other
// contexts.

// todo: Create a way to specify all the types you've used and create _Generic
// versions of each function.
#define CONCAT_INNER(a, b) a##b
#define CONCAT(a, b) CONCAT_INNER(a, b)

#define BA_VALS_PER_BUCKET(bucket_size, type) (bucket_size / sizeof(type))

#define BA_ALLOC_FUNCTION(prefix, typedef_name, type)                          \
typedef_name *CONCAT(prefix, _alloc)(Arena * arena)
#define BA_AT_FUNCTION(prefix, typedef_name, type)                             \
type *CONCAT(prefix, _at)(typedef_name * ba, size_t i)
#define BA_PUSH_FUNCTION(prefix, typedef_name, type)                           \
type *CONCAT(prefix, _push)(typedef_name * ba, type val)

#ifndef BA_PREFIX
#error "BA_PREFIX must be defined"
#endif

#ifndef BA_TYPEDEF_NAME
#error "BA_TYPEDEF_NAME must be defined"
#endif

#ifndef BA_TYPE
#error "BA_TYPE must be defined"
#endif

#ifndef BA_BUCKET_SIZE
#define BA_BUCKET_SIZE 64
#endif

#include "stddef.h"
#include "stdint.h"

#include "arena.h"

typedef struct {
  Arena *arena;
  struct {
    BA_TYPE e[BA_VALS_PER_BUCKET(BA_BUCKET_SIZE, BA_TYPE)];
  } **buckets;
  size_t buckets_count;
  size_t buckets_capacity;
  size_t count;
  size_t capacity;
} BA_TYPEDEF_NAME;

BA_ALLOC_FUNCTION(BA_PREFIX, BA_TYPEDEF_NAME, BA_TYPE);
BA_AT_FUNCTION(BA_PREFIX, BA_TYPEDEF_NAME, BA_TYPE);
BA_PUSH_FUNCTION(BA_PREFIX, BA_TYPEDEF_NAME, BA_TYPE);