nwr_mem.h

## nwr_mem.h - v0.1.0 - public domain - patreon.riscy.tv
*custom allocator building blocks inspired by Andrei Alexandrescu's std.experimental.allocator*

### Quick Notes
Do this:

1	#define NWR_MEM_IMPLEMENTATION

before you include this file in *one* C or C++ file to create the implementation.
i.e. it should look like this:

    #include ...
    #include ...
    #include ...
    #define NWR_MEM_IMPLEMENTATION
    #include "nwr_mem.h"

You can `#define NWR_ASSERT(x)` before the #include to avoid using assert.h.

To override the default alignment, `#define NWR_MEM_DEFAULT_ALIGNMENT n`, where
n is the alignment you want. This should be a power of 2. Default alignment is
used whenever you pass 0 into an alignment field.

If you only want one specific allocator you can `#define NWR_ONLY_X` before the
include, where X is the allocator you want. E.g.

1
2
3

    #define NWR_MEM_IMPLEMENTATION
    #define NWR_ONLY_REGION
    #include "nwr_mem.h"

This library contains an integer constant `NWR_MEM_VERSION` which will be bumped
any time the API undergoes a change that breaks backwards compatibility.

### API Quick Reference
The actual api is all snake case, and you prefix everything with `nwr`. Functions
are prefixed by the allocator they take. For example, if I want to
call `is subregion alive?` on a `Region`, I say:

1	_Bool result = nwr_region_is_subregion_alive(&region, ptr, len);

* Region
    * create                (ptr,len,alignment,flags) -> Region
    * reset                 (Region)                  -> void
    * alloc                 (Region,len)              -> ptr
    * aligned alloc         (Region,len,alignment)    -> ptr
    * alloc all             (Region, output len)      -> ptr
    * available             (Region)                  -> len
    * dealloc               (Region,ptr,len)          -> worked?
    * expand                (Region,ptr,len,delta)    -> delta
    * grows down?           (Region)                  -> region grows down?
    * is alive?             (Region,ptr)              -> ptr is alive?
    * is empty?             (Region)                  -> region is empty?
    * is full?              (Region)                  -> region is full?
    * is inside?            (Region,ptr)              -> ptr is inside?
    * is subregion?         (Region,ptr,len)          -> ptr,len is subregion?
    * is subregion alive?   (Region,ptr,len)          -> ptr,len is subregion & alive?

### Region documentation
`Region` supports growing up or down in memory. If you want the region to grow
down (e.g. when using with memory on the stack) you can pass `NWR_REGION_GROWS_DOWN`
into `flags` when you call `create`. Note that `flags` is not const, this is done so
that you can use the unused bits in the flags field for your own hacks. If more
flags are added in the future, `NWR_MEM_VERSION` will be increased, indicating a
break in backwards compatibility.

`Expand` should not be called on a region that grows down, as this does not make
sense and is not supported.

#### Examples

##### create example

    //first we get some raw memory from the system
    size_t raw_len = 1 << 12;
    void * raw_mem = malloc(raw_len);
    //next we create a region for fast allocations from our raw mem.
    nwr_region region = nwr_region_create(raw_mem, raw_len, 0, 0);
    //by passing 0 into alignment, we get the libraries default 
    alignment.
    //by passing 0 into flags, region allocations will grow up in memory.

1
2
3

    //if you are using memory on the stack, you might want the region to grow down instead of up:
    void * stack_mem = alloca(raw_len);
    nwr_region sregion = nwr_region_create(stack_mem, raw_len, 0, NWR_REGION_GROWS_DOWN);

    //now, let's try a different alignment:
    nwr_region aregion = nwr_region_create(ptr, len, 64, 0);
    //note that alignment must be a power of 2. The region may use less memory 
    //than what is available in the backing store because the region will be aligned within it.
    //you can use nwr_region_available to see how much space the region can use

##### reset example

    //use reset to dealloc everything
    if (nwr_region_is_full(&region))
        nwr_region_reset(&region);
    assert(nwr_region_is_empty(&region));

##### alloc example

    //assume `string` is u8*, stb stretchy_buffer style, no null-terminator
    char * string_to_cstr(nwr_region * r, string s)
    {
        size_t old_len = stb_sb_count(s);
        size_t new_len = old_len + 1;
        char * cstr = nwr_region_alloc(r, new_len);
        memcpy(cstr, s, old_len);
        cstr[old_len] = '\0';
        return cstr;
    }

##### aligned alloc example

1 2	void * ptr = nwr_region_aligned_alloc(&region, 16, 32); assert(ptr && ((size_t)ptr & 31) == 0);

##### alloc all example

    //alloc all reports the size of the allocation in the `size` parameter.
    size_t size;
    void * ptr = nwr_region_alloc_all(&region, &size);
    assert(ptr && nwr_region_is_full(&region));
    printf("%zu\n", size);

1
2
3

    //you can pass NULL in for `size` if you don't care
    ptr = nwr_region_alloc_all(&region, NULL);
    assert(ptr && nwr_region_is_full(&region));

##### available example

    size_t mem_len = 1000;
    void * aligned_mem = malloc(mem_len+1);
    void * misaligned_mem = (void *)((size_t)aligned_mem + 1);
    nwr_region region = nwr_region_create(misaligned_mem, mem_len, 0, 0);
    //the memory region uses will be less than the 1000 bytes that misaligned_mem has available
    //let's find out how much space the region can actually use:
    size_t avail = nwr_region_available(&region);
    printf("%zu\n", avail);

##### dealloc example

    for (int i = 0; !nwr_region_is_full(&region); ++i)
        arr[i] = nwr_region_alloc(&region, len);
    for (size_t i = sizeof(arr)/sizeof(arr[0]) - 1; !nwr_region_is_empty(&region); --i)
        assert(nwr_region_dealloc(&region, arr[i], len));

##### expand example

    //expand allows us to grow the last allocation
    nwr_region region = nwr_region_create(mem, mem_len, 0, 0);
    size_t len = mem_len >> 1;
    void * ptr = nwr_region_alloc(&region, len);
    size_t delta = nwr_region_expand(&region, ptr, len, len);
    assert(ptr && delta == len && nwr_region_is_full(&region));

    //expand doesn't need to alloc if the delta fits within the padding of the last allocation
    len = mem_len - 16 + 1;
    ptr = nwr_region_alloc(&region, len);
    void * prev_current = region.current;
    delta = nwr_region_expand(&region, ptr, len, 15);
    assert(delta == 15 && prev_current == region.current);
    len += delta;

    //...but you can't expand if the region grows down
    nwr_region region = nwr_region_create(mem, mem_len, 0, NWR_REGION_GROWS_DOWN);
    size_t len = mem_len >> 1;
    void * ptr = nwr_region_alloc(&region, len);
    //this will NWR_ASSERT
    size_t delta = nwr_region_expand(&region, ptr, len, len);

##### grows down? example

1
2
3

    //grows down? is shorthand for checking the flags field
    nwr_region region = nwr_region_create(ptr, len, 0, 0);
    assert(!nwr_region_grows_down(&region));

1 2	region = nwr_region_create(ptr, len, 0, NWR_REGION_GROW_DOWN); assert(nwr_region_grows_down(&region));

##### is alive? example

    //is alive? tells us whether a pointer was allocated from the region and still valid
    void * ptr = nwr_region_alloc(&region, 42);
    assert(nwr_region_is_alive(&region, ptr));
    nwr_region_reset(&region);
    assert(!nwr_region_is_alive(&region, ptr));

##### is empty? example

    nwr_region region = nwr_region_create(ptr, len, 0, 0);
    assert(nwr_region_is_empty(&region));
    nwr_region_alloc(&region, 42);
    assert(!nwr_region_is_empty(&region));

##### is full? example

    nwr_region region = nwr_region_create(ptr, len, 0, 0);
    assert(!nwr_region_is_full(&region));
    nwr_region_alloc_all(&region, NULL);
    assert(nwr_region_is_full(&region));

##### is inside? example

    //is inside? tells us whether the pointer was allocated from the region,
    //but not whether it is valid
    void * ptr = nwr_region_alloc(&region, 42);
    assert(nwr_region_is_inside(&region, ptr));
    nwr_region_reset(&region);
    assert(nwr_region_is_inside(&region, ptr));

##### is subregion? example

    //is subregion? is like `is inside?` but for a ptr,len pair
    size_t len = 42;
    void * ptr = nwr_region_alloc(&region, len);
    assert(nwr_region_is_subregion(&region, ptr, len));
    nwr_region_reset(&region);
    assert(nwr_region_is_subregion(&region, ptr, len));

##### is subregion alive? example

    //is subregion alive? is like `is alive?` but for a ptr,len pair
    size_t len = 42;
    void * ptr = nwr_region_alloc(&region, len);
    assert(nwr_region_is_subregion_alive(&region, ptr, len));
    nwr_region_reset(&region);
    assert(!nwr_region_is_subregion_alive(&region, ptr, len));

### Contributors

* Allocators
    * Mio Iwakura (Region)
* Inspiration / Special Thanks
    * Andrei Alexandrescu (std.experimental.allocator)
    * Sean Barrett (stb libs)
    * All my patrons (motivation/funding)

### LICENSE
This software is available under 2 licenses -- choose whichever you prefer.

ALTERNATIVE A - MIT License
Copyright (c) 2017 Mio Iwakura
Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

ALTERNATIVE B - Public Domain (www.unlicense.org)
This is free and unencumbered software released into the public domain.
Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
software, either in source code form or as a compiled binary, for any purpose,
commercial or non-commercial, and by any means.
In jurisdictions that recognize copyright laws, the author or authors of this
software dedicate any and all copyright interest in the software to the public
domain. We make this dedication for the benefit of the public at large and to
the detriment of our heirs and successors. We intend this dedication to be an
overt act of relinquishment in perpetuity of all present and future rights to
this software under copyright law.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.