# slab.inl ## Overview
Implements a "slab" container. The slab container stores items in a linked list of fixed-size slabs, where each slab holds as many items as will fit. Items in the slab container have fixed pointers that are valid until the item is removed from the slab. Typical use: ~~~c my_type_t *slab = 0; tm_slab_create(&slab, allocator, 64*1024); my_type_t *item_1 = tm_slab_add(slab); my_type_t *item_2 = tm_slab_add(slab); for (my_type_t *i = slab; i != tm_slab_end(slab); i = tm_slab_next(i)) { if (!tm_slab_is_valid(i)) continue; ... } tm_slab_remove(slab, item_1); tm_slab_destroy(slab); ~~~ The slab uses the same trick as the `carray` -- a slab is represented by a pointer to the first item in the slab. This lets the slab "handle" keep track of the item type. The first slab in the list stores a header with general information about the slab. The remaining slabs just hold items. The last item of each slab is a "pseudo-item" that just holds a pointer to the next slab: ************************************************************************************** * * +-----+---+---+---+-----+ +---+---+---+---+-----+ * | hdr | i | i | i | ptr | --> | i | i | i | i | ptr | --> ... * +-----+---+---+---+-----+ +---+---+---+---+-----+ * ************************************************************************************** The container grows by adding more slabs to the end. Typically, these slabs are allocated directly from the VM. Removed items are put on a freelist. Since the individual slabs never get re-allocated and never move, pointers to items in the slab container are permanent. In addition, each item also has a permanent ID. This can be used to detect situations where an item has been removed and a new one has been allocated at the same location. The slab container is useful for storing "bulk data" -- big arrays of items. It's similar to storing data in a carray backed by a fixed VM allocator. Main differences: * Unlike when you use a fixed VM allocated array, you don't have to set a maximum size for the container. * The slab container automatically manages a freelist and an item ID for you. * Elements in the slab are not stored continuously in memory, so you can't access individual items with `slab[i]`. Note that the slab container stores items [with holes](https://ourmachinery.com/post/data-structures-part-1-bulk-data/), so iterating is less efficient than in a tightly packed array.
## Index
`struct tm_slab_item_t`
`tm_slab_create()`
`tm_slab_create()`
`tm_slab_create()`
`tm_slab_create()`
`tm_slab_destroy()`
`tm_slab_add()`
`tm_slab_remove()`
`tm_slab_remove_all()`
`tm_slab_next()`
`tm_slab_end()`
`tm_slab_is_valid()`
`tm_slab_id()`
## API
### `struct tm_slab_item_t`
Sample type for items in the slab. Note that there is no need to use or inherit from this type, you just need to ensure that the items you store in the slab have a `next` field, just like this struct. The `next` field can be a `void *` or a pointer to your item type. You shouldn't touch the `next` field, it is managed by the slab. Be careful about using a designated initializer to initialize your slab item, like this: ~~~c struct my_slab_item { int x; void *next; }; struct my_slab_item *item = tb_slab_add(slab); *item = (struct my_slab_item){.x = 7}; ~~~ This initialization will clear out the `next` field. In allocated items, the `next` field is used to store item IDs. If you don't care about item IDs, clearing the `next` field for an allocated item is harmless, but if you want the IDs, you should make sure to preserve the value of the `next` field in your designated initializer. ~~~c *item = (struct my_slab_item){.x = 7, .next = item->next}; ~~~ !!! TODO: API-REVIEW Maybe rename `void *next` to `unit64_t id`, that makes it clearer for users of the type that it must be saved to preserve the ID. ~~~c struct tm_slab_item_t { // The `next` field is used for multiple purposes: // // * For items on the freelist, it points to the next item on the list. // * For the last item in a slab, it points to the next slab. // * For actually used items, it stores the ID of the item. // // We distinguish between these cases by storing different values in the lower two bits of the // `next` pointer. Since our allocations are four bytes aligned, these bits are always zero, so // we can use them to store extra data. // // We use the following values for the last two bits: // // * 0 -- item is a valid item added by [[tm_slab_add()]] // * 1 -- item is on the freelist. // * 2 -- item is a pointer to the next slab in the sequence of slabs. // // Having this data stored directly in each item is useful when we iterate over the items. It // means we know which items are valid and we can get to the next slab in the list without // having to look at any header data. struct tm_slab_item_t *next; } ~~~
### `tm_slab_create()`
~~~c #define tm_slab_create(slab, a, slab_size) *slab = tm_slab_create_impl((a), (slab_size), sizeof(*((*slab))), tm_offset_of(typeof(**slab), next)) ~~~
### `tm_slab_create()`
~~~c #define tm_slab_create(slab, a, slab_size) *slab = tm_slab_create_impl((a), (slab_size), sizeof(*((*slab))), (char *)&((*slab))->next - (char *)((*slab))) ~~~
### `tm_slab_create()`
~~~c #define tm_slab_create(slab, a, slab_size) *slab = (std::remove_reference<decltype(*slab)>::type)tm_slab_create_impl((a), (slab_size), sizeof(*((*slab))), tm_offset_of(__typeof(**slab), next)) ~~~
### `tm_slab_create()`
~~~c #define tm_slab_create(slab, a, slab_size) *slab = (std::remove_reference<decltype(*slab)>::type)tm_slab_create_impl((a), (slab_size), sizeof(*((*slab))), (char *)&((*slab))->next - (char *)((*slab))) ~~~
### `tm_slab_destroy()`
~~~c #define tm_slab_destroy(slab) tm_slab_destroy_impl((slab), sizeof(*(slab)), (char *)&(slab)->next - (char *)(slab)) ~~~ Destroys a slab created by `tm_slab_create()`.
### `tm_slab_add()`
~~~c #define tm_slab_add(slab) TM_CAST_PTR_TO_TYPE_OF(slab, tm_slab_add_impl((slab), sizeof(*(slab)), (char *)&(slab)->next - (char *)(slab))) ~~~ Adds a new item to the slab and returns a pointer to it.
### `tm_slab_remove()`
~~~c #define tm_slab_remove(slab, item) tm_slab_remove_impl((slab), (item), (void **)&(item)->next) ~~~ Removes the specified item from the slab.
### `tm_slab_remove_all()`
~~~c #define tm_slab_remove_all(slab) {...} ~~~ Removes all items from the slab.
### `tm_slab_next()`
~~~c #define tm_slab_next(item) (TM_CAST_PTR_TO_TYPE_OF(item, (TM_SLAB__IS_SLABPTR(item->next) ? TM_SLAB__REMOVE_TAG(item->next) : (item + 1)))) ~~~ Returns the next item in the slab after `item`. Note that the returned item is not necessary a valid item (it could be on the freelist or the pseudoitem at the end of the slab) so you should check with `tm_slab_is_valid()`. `tm_slab_next()` can be used to iterate over all items in the slab using this pattern: ~~~c for (T *i = slab; i != tm_slab_end(slab); i = tm_slab_next(i)) { if (!tm_slab_is_valid(i)) continue; ... } ~~~
### `tm_slab_end()`
~~~c #define tm_slab_end(slab) (tm_slab_header(slab)->end) ~~~ Returns the item at the end of the slab container.
### `tm_slab_is_valid()`
~~~c #define tm_slab_is_valid(item) TM_SLAB__IS_VALID(item->next) ~~~ Returns `true` if `item` is a valid item and `false` if it's on the freelist or a pseudo-item.
### `tm_slab_id()`
~~~c #define tm_slab_id(item) (tm_slab_is_valid(item) ? TM_SLAB__TO_ID(item->next) : 0) ~~~ Returns the ID of `item`. This is a unique item identifier which is always non-zero for a valid item. (Item pointers are unique for "living" items, but if you destroy an item and create a new one, the new item may be allocated at the same pointer location as the old one. IDs can be used to check for this scenario.)