# Memory Operations

> StringZilla for C

### Memory Ownership and Small String Optimization

Most operations in StringZilla don't assume any memory ownership.
But in addition to the read-only search-like operations StringZilla provides a minimalistic C and C++ implementations for a memory owning string "class".
Like other efficient string implementations, it uses the [Small String Optimization][faq-sso] (SSO) to avoid heap allocations for short strings.
The owning `sz_string_t` container, its union layout, and the full lifecycle API are documented under [String Collections and Containers](https://www.unum.cloud/docs/stringzilla/c/sorting-and-sets.md#string-collections-and-containers); this section covers the design rationale behind that layout.

[faq-sso]: https://cpp-optimizations.netlify.app/small_strings/

A short string can be kept on the stack, if it fits within the inline character array.
Before 2015 GCC string implementation was just 8 bytes, and could only fit 7 characters.
Different STL implementations today have different thresholds for the Small String Optimization.
Similar to GCC, StringZilla is 32 bytes in size, and similar to Clang it can fit 22 characters on stack.
Our layout might be preferential, if you want to avoid branches.
If you use a different compiler, you may want to check its SSO buffer size with a [simple Gist](https://gist.github.com/ashvardanian/c197f15732d9855c4e070797adf17b21).

|                 | `libstdc++` in GCC 13 | `libc++` in Clang 17 | StringZilla |
| :-------------- | --------------------: | -------------------: | ----------: |
| String `sizeof` |                    32 |                   24 |          32 |
| Inner Capacity  |                    15 |               __22__ |      __22__ |

This design has been since ported to many high-level programming languages.
Swift, for example, [can store 15 bytes](https://developer.apple.com/documentation/swift/substring/withutf8(_:)#discussion) in the `String` instance itself.
StringZilla implements SSO at the C level, providing the `sz_string_t` union and a simple API for primary operations, covered with a worked example under [String Collections and Containers](https://www.unum.cloud/docs/stringzilla/c/sorting-and-sets.md#string-collections-and-containers).

Unlike the conventional C strings, the `sz_string_t` is allowed to contain null characters.
To safely print those, pass the unpacked length to `printf` as well.

```c
sz_ptr_t string_start;
sz_size_t string_length;
sz_string_range(&string, &string_start, &string_length);
printf("%.*s\n", (int)string_length, string_start);
```

`#include <stringzilla/types.h>`

`#include <stringzilla/strings.h>`

## sz_allocator_t

Some complex pattern matching algorithms may require memory allocations.

```c
struct sz_allocator_t
```

This structure passes the memory allocator to those functions.

Every function takes the caller's stream, which on a GPU names the device a block is made on and the work a release waits behind; host allocators ignore it, and on the CPU it is null. The optional `reallocate` keeps the first `min(old_bytes, new_bytes)` bytes, resizing the block where it lies when it can and moving it otherwise, and leaves the block as it was on failure. Without it, a block that must change size moves through `allocate` and `free`.

- `allocate` `sz_allocate_t`
- `reallocate` `sz_reallocate_t`
- `free` `sz_free_t`
- `handle` `void *`

See also: [sz_allocator_init_arena](#sz_allocator_init_arena), [sz_allocator_init_unified_best](#sz_allocator_init_unified_best)

## sz_u16_load

Load a 16-bit unsigned integer from a potentially unaligned pointer, slow on some platforms.

```c
sz_u16_vec_t sz_u16_load(sz_cptr_t ptr);
```

## sz_u32_load

Load a 32-bit unsigned integer from a potentially unaligned pointer, slow on some platforms.

```c
sz_u32_vec_t sz_u32_load(sz_cptr_t ptr);
```

## sz_u64_load

Load a 64-bit unsigned integer from a potentially unaligned pointer, slow on some platforms.

```c
sz_u64_vec_t sz_u64_load(sz_cptr_t ptr);
```

## sz_u16_store

Store a 16-bit unsigned integer to a potentially unaligned pointer, slow on some platforms.

```c
void sz_u16_store(sz_ptr_t ptr, sz_u16_t value);
```

## sz_u32_store

Store a 32-bit unsigned integer to a potentially unaligned pointer, slow on some platforms.

```c
void sz_u32_store(sz_ptr_t ptr, sz_u32_t value);
```

## sz_u64_store

Store a 64-bit unsigned integer to a potentially unaligned pointer, slow on some platforms.

```c
void sz_u64_store(sz_ptr_t ptr, sz_u64_t value);
```

## sz_allocator_init_heap

Initializes a memory allocator to use the system default `malloc` and `free`.

```c
sz_status_t sz_allocator_init_heap(sz_allocator_t *allocator);
```

- `allocator` (out): Memory allocator to initialize.

Notes: Unlike the C standard library, `malloc(0)` is guaranteed to return a null pointer.

See also: malloc: [https://en.cppreference.com/w/c/memory/malloc](https://en.cppreference.com/w/c/memory/malloc)

Statuses: - [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k) Without libc. Failure preserves the allocator.

## sz_allocator_init_arena

Initializes a memory allocator that serves every request from a static-capacity buffer, __without__ any dynamic allocations.

```c
sz_status_t sz_allocator_init_arena(
    sz_allocator_t *allocator,
    void *buffer,
    sz_size_t bytes,
    sz_size_t alignment);
```

Failure leaves both the allocator and buffer unchanged. Three aligned `[sz_size_t](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_size_t)` values store capacity, consumption and alignment inside the buffer.

- `allocator` (out): Memory allocator to initialize.
- `buffer` (in): Buffer to use for allocations.
- `bytes` (in): Buffer size, including metadata and alignment padding.
- `alignment` (in): Nonzero power-of-two alignment guaranteed for every returned block.

Statuses: - [`sz_unexpected_dimensions_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_unexpected_dimensions_k) Invalid alignment.
- [`sz_bad_alloc_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_bad_alloc_k) Missing storage.
- [`sz_overflow_risk_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_overflow_risk_k) An overflowing address range.

## sz_allocator_equal

Checks if two memory allocators are equivalent.

```c
sz_bool_t sz_allocator_equal(
    sz_allocator_t const *a,
    sz_allocator_t const *b);
```

- `a` (in): First memory allocator.
- `b` (in): Second memory allocator.

## sz_allocator_init_unified_best

Initializes an allocator whose blocks both the host and the device of `capabilities` address: the host heap on the CPU, managed memory on CUDA and ROCm, shared buffers on Metal.

```c
sz_status_t sz_allocator_init_unified_best(
    sz_allocator_t *allocator,
    sz_capability_t capabilities);
```

- `sz_allocator_init_unified` backends: serial

The allocator is stateless, its `handle` null, and each call allocates on the device of the stream it is given, so one allocator serves every device of its vendor.

- `allocator` (out): The allocator to initialize.
- `capabilities` (in): One device's capabilities, like [`sz_capabilities_enabled_cuda`](https://www.unum.cloud/docs/stringzilla/c/runtime-dispatch.md#sz_capabilities_enabled_cuda) reports; its group picks the CPU or a GPU vendor.

Statuses: - [`sz_missing_gpu_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_gpu_k) A GPU vendor this library was built without.

## sz_allocator_init_device_best

Initializes device storage on CUDA and ROCm, or unified storage on Metal.

```c
sz_status_t sz_allocator_init_device_best(
    sz_allocator_t *allocator,
    sz_capability_t capabilities);
```

Each callback uses its stream's device. CPU returns [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k); GPU vendors omitted from the build return [`sz_missing_gpu_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_gpu_k).

## sz_allocator_init_pinned_best

Initializes page-locked CUDA or ROCm host storage, using each callback's stream.

```c
sz_status_t sz_allocator_init_pinned_best(
    sz_allocator_t *allocator,
    sz_capability_t capabilities);
```

CPU and Metal return [`sz_missing_kernel_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_kernel_k); unbuilt GPU vendors return [`sz_missing_gpu_k`](https://www.unum.cloud/docs/stringzilla/c/types.md#sz_missing_gpu_k).