README.md

dod

Tools to facilitate data-oriented design in C99.

If you are new to data-oriented design, this is a good place to start.

Note: This library is still a WIP; using it in production isn't recommended until there is an official release.

This library provides a collection of tools that are used frequently in data-oriented design. It currently offers the following header-only utilities -

• dodbytes.h - Byte manipulation utils
• dodvec.h - A feature-rich generic vector implementation
• dodbs.h - A feature-rich bitset implementation
• dodarr.h - Generic array with value semantics and optional bounds checking

In short, use the vector (dodvec_t) for grouping data members that are frequently accessed together. Bools have a particularly bad information density, so group them toghether in a bitset (dodbs_t). (Note C++ offers a template specialization for std::vector so use that instead of a bitset in C++). For data sets where size is known at compile time, use the array (dodarr.h).

dodbytes.h - Byte manipulation utils

This is a byte array that can grow in a logarithmic manner. It is implemented as the backend for the vector library and is not intended to be used in isolation. If you choose to use it as a standalone library make sure you understand alignment and its implications.

dodvec.h - A feature-rich generic vector implementation

The API is (almost) complaint with C++ STL's std::vector with a few exceptions (see notes section below). The implementation tries to stick to the STL implementation unless otherwise specified.

Usage

For more examples see test_dodvec.c.

dodvec_t *v = dodvec_new(int, 10);                          // Create vector of ints and reserve space for 10 ints
for (int i = 0; i < 5; ++i)                                 // Push back 5 ints
  dodvec_push_back(v, &i);                                  // >> {0, 1, 2, 3, 4}
assert(*dodvec_at(v, 2) == 2);                              // Check element at pos 2 is 2
dodvec_pop_back(v);                                         // Pop back >> {0, 1, 2, 3}
dodvec_erase(v, 0);                                         // Erase at pos 0 >> {1, 2, 3}
int vals[] = {501, 502, 503};                               // Insert range using array
dodvec_insert_range(v, dodvec_front(v), vals, vals + 3);    // at front >> {501, 502, 503, 1, 2, 3}
dodvec_free(v);                                             // free after use

Constructors

Unlike the STL std::vector, only a single constructor is implemented. Create a vector by specifying type and initial (reserve) size. The result is an empty container, with no elements. The vector must be freed after use.

dodvec_t *v = dodvec_new(int, 10);
/* ... */
dodvec_free(v);

Iterators

Only begin and end are implemented as dodvec_begin() and dodvec_end() are implemented respectively. Note also that these iterators are actually pointers to the beginning and just past the end of the vector data.

Capacity

Function Use Equivalent function in dodvec.h Notes size Return size dodvec_size(v)

max_size Return maximum size dodvec_max_size(v) This an implementation limitation, the vector is by no means guaranteed to be able to reach this size. resize Change size dodvec_resize(v, n, val) val is a pointer to the value that must be used for initialization of new elements. capacity Return size of allocated storage capacity dodvec_capacity(v)

empty Test whether vector is empty dodvec_empty(v)

reserve Request a change in capacity dodvec_reserve(v, n)

shrink_to_fit Shrink to fit dodvec_shrink_to_fit(v)

Element access

Function Use Equivalent function in dodbs.h Notes operator[] Access element Not implemented This functions uses C++ features (references and operator overloading) that are non-existent in C. Use dodvec_at(v, pos) instead. at Access element dodvec_at(v, pos) Returns a pointer to the element at pos. front Access first element dodvec_front(v) Returns a pointer to the first element. Same as dodvec_begin(v) back Access last element dodvec_back(v) Returns a pointer to the last element. data Access data dodvec_data(v)

Modifiers

Function Use Equivalent function in dodbs.h Notes assign Assign vector content dodvec_assign_range(v, start, end), dodvec_assign_fill(v, n, val) start, end and val are pointers. push_back Add element at the end dodvec_push_back(v, val) val is a pointer to the value to be pushed. Returns DODRET_OK on success. pop_back Delete last element dodvec_pop_back(v)

insert Insert elements dodvec_insert(v, pos, val), dodvec_insert_range(v, pos, start, end) pos, start, end and val are pointers. Returns DODRET_OK on success. erase Erase elements dodvec_erase(v, pos) Returns DODRET_OK on success. swap Swap content dodvec_swap(v1, v2)

clear Clear content dodvec_clear(v)

emplace Construct and insert element Not implemented

emplace_back Construct and insert element at the end Not implemented

dodbs.h - A feature-rich bitset implementation

The API is (almost) complaint with C++ STL's std::bitset with a few exceptions (see notes section below). The implementation tries to stick to the STL implementation unless otherwise specified.

Usage

For more examples see test_dodbs.c.

dodbs_t_decl(bs1, 16);              // Create bitset of length 16
dodbs_init(bs1, 43690U);            // Initialize by value - 43690 == b1010101010101010
dodbs_flipall(bs);                  // Flip all bits
assert(dodbs_any(bs) == true);      // Check if any bit is set
assert(dodbs_none(bs) == false);    // Check if no bit is set
dodbs_setall(bs);                   // Set all bits
assert(dodbs_all(bs) == true);      // Check if all bits are set

Constructors

std::bitset provides 3 types of constructors -

• default constructor - The object is initialized with zeros. For this, the library provides 2 methods, one for stack and the other for heap initialization. Note: The library relies on the declaration to zero initialize the storage, hence the unorthodox method of creation. If you do not prefer the *decl* macros, then by all means use the manual declaration method.

// Create a bitset of length 16 on the stack
dodbs_t_decl(bs, 16);
// Equivalent manual decl
// dodbs_t(16) bs = {.bytes = {0}, .len = 16 };

// Create a bitset of length 16 on the heap
dodbs_t_decl_ptr(bsptr, 16);
// Equivalent manual decl
// dodbs_t(16) *bsptr = malloc(sizeof(*bsptr));
// bsptr->bytes = {0};
// bsptr->len = 16
/* ... */
dodbs_free(bsptr);

• initialization from integer value - Initializes the object with the bit values of val. This is the dodbs_init() function.

dodbs_t_decl(bs, 16);
dodbs_init(bs, 43690U); // 43690 == b1010101010101010

• initialization from string. This is the dodbs_init_str() function.

dodbs_t_decl(bs2, 16);
dodbs_init_str(bs2, "1010101010101010");

Bit access

Function Use Equivalent function in dodbs.h Notes operator[] Access bit Not implemented This functions uses C++ features (references and operator overloading) that are non-existent in C. Use dodbs_test()/dodbs_set()/dodbs_reset() instead. count Count bits set dodbs_count(bs)

size Return size dodbs_size(bs)

test Return bit value dodbs_test(bs, pos)

any Test if any bit is set dodbs_any(bs)

none Test if no bit is set dodbs_none(bs) Opposite of dodbs_any(bs). all Test if all bits are set dodbs_all(bs)

Bit operations

Bitset operations

Note: Direct use of bitwise operators is unsupported.

Internals

This implementation is inspired by llvm-libc++'s std::bitset. The backend storage for bits comprises of an array of size_ts. This can be changed by modifying the dodbs_storage_t typedef. Most functions are macros that delegate to other functions, this allows for generic functions that can handle bitsets of all sizes. It also provides a convenient API where you don't have to always pass the length of the bitset.

dodarr.h - Generic array with value semantics

WIP