string.h — SDS-Style Dynamic String

Introduction

string.h provides an SDS-style dynamic string (XString) that is fully compatible with all C string functions (printf %s, strcmp, strlen, …). The header (length + capacity) is hidden before the user-facing pointer, so every XString is a char* — zero interop friction.

Inspired by Redis SDS (Simple Dynamic Strings).

Typical usage:

XString s = XStringCreate("hello");
s = XStringAppend(s, " world");
printf("%s (len=%zu)\n", s, XStringLen(s));

size_t pos = XStringFindStr(s, "world");
if (pos != XSTRING_NONE) {
  printf("found at index %zu\n", pos);
}

XStringDestroy(s);

Design Philosophy

1. Binary-Compatible with C Strings — XString is a typedef char *. Every XString can be passed directly to any C string API without conversion. It is always NUL-terminated.

2. Hidden Header — The metadata (length, capacity) lives in a header placed before the user pointer. This means XString is indistinguishable from a regular char* at the call site, yet length queries are O(1).

3. Auto-Growing — Append operations automatically reallocate when capacity is exhausted. Callers must use the return value (s = XStringAppend(s, "x")) because reallocation may move the string.

4. Binary-Safe — Embedded NUL bytes are supported. XStringCreateLen and XStringAppendLen treat the input as raw bytes. Length is tracked explicitly, not via strlen.

5. Dual-Strategy Search — XStringFind uses naive memcmp for short patterns (below a threshold) and platform memmem for longer ones, balancing call overhead against algorithmic advantage.

Architecture

graph TD
    CREATE["XStringCreate(init)"] --> S["XString<br/>(char*)"]
    CREATELEN["XStringCreateLen(data, len)"] --> S
    APPEND["XStringAppend(s, str)"] --> GROW["Grow if needed"]
    APPENDLEN["XStringAppendLen(s, data, len)"] --> GROW
    APPENDFMT["XStringAppendFormat(s, fmt, ...)"] --> GROW
    GROW --> UPDATE["Return updated pointer"]
    FIND["XStringFind(haystack, needle, len)"] --> THRESH{"needle_len < 32?"}
    THRESH -->|Yes| NAIVE["Naive memcmp scan"]
    THRESH -->|No| MEMMEM["memmem (platform Two-Way)"]
    DUP["XStringDup(s)"] --> S
    TRUNCATE["XStringTruncate(s, new_len)"] --> S
    CLEAR["XStringClear(s)"] --> S
    DESTROY["XStringDestroy(s)"] --> FREE["free(header + data)"]

    S --> APPEND
    S --> APPENDLEN
    S --> APPENDFMT
    S --> FIND
    S --> DUP
    S --> TRUNCATE
    S --> CLEAR
    S --> DESTROY

    style CREATE fill:#4a90d9,color:#fff
    style CREATELEN fill:#4a90d9,color:#fff
    style APPEND fill:#50b86c,color:#fff
    style APPENDLEN fill:#50b86c,color:#fff
    style APPENDFMT fill:#50b86c,color:#fff
    style FIND fill:#f5a623,color:#fff
    style DESTROY fill:#e74c3c,color:#fff

Implementation Details

Memory Layout

                    XStringHeader
                 ┌──────────────┐
                 │ len (size_t) │
                 │ cap (size_t) │
                 └──────────────┘ ← hdr + 1 = user pointer
                 ┌──────────────┐
  XString (char*) → │  data …      │ ← always NUL-terminated
                 │  cap + 1     │
                 └──────────────┘

The XStringHeader is allocated as part of a single malloc block: malloc(sizeof(XStringHeader) + cap + 1). The user receives a pointer to the data area, which is (XStringHeader*)ptr + 1. This layout means:

• XStringLen(s) is O(1) — reads hdr->len directly.
• s can be passed to any const char* API.
• The NUL terminator is always written after len bytes.

Growth Strategy

When an append exceeds current capacity:

1. If current capacity < 1 MB → double the capacity.
2. If current capacity ≥ 1 MB → add 1 MB.
3. Minimum capacity is XSTRING_MIN_CAP = 64 bytes.

This mirrors the Redis SDS growth policy and provides good amortised O(1) appends without wasting memory on large strings.

Search Strategy

xStringFind uses a threshold-based approach:

Not-found results return XSTRING_NONE ((size_t)-1), consistent with the ARRAY_NPOS convention used elsewhere in xbase.

Operations and Complexity

API Reference

Types and Constants

Lifecycle Functions

Append Functions

Truncate / Clear

Accessor Functions

Memory Control Functions

Search Functions

Comparison Functions

Usage Examples

Basic Create / Append / Destroy

#include <stdio.h>
#include <xbase/string.h>

int main(void) {
  xString s = xStringCreate("hello");
  s = xStringAppend(s, " world");

  printf("%s (len=%zu, cap=%zu)\n", s, xStringLen(s), xStringCap(s));
  /* Output: hello world (len=11, cap=64) */

  xStringDestroy(s);
  return 0;
}

Binary-Safe String (Embedded NUL)

#include <stdio.h>
#include <xbase/string.h>

int main(void) {
  char data[] = { 'a', 'b', 'c', '\0', 'd', 'e', 'f' };
  xString s = xStringCreateLen(data, 7);

  printf("len=%zu\n", xStringLen(s));  /* len=7, NOT 3 */

  size_t pos = xStringFind(s, "def", 3);
  if (pos != XSTRING_NONE) {
    printf("found 'def' at index %zu\n", pos);  /* found 'def' at index 4 */
  }

  xStringDestroy(s);
  return 0;
}

Formatted Append

#include <stdio.h>
#include <xbase/string.h>

int main(void) {
  xString s = xStringCreate("count: ");
  s = xStringAppendFormat(s, "%d items", 42);

  printf("%s\n", s);  /* count: 42 items */

  xStringDestroy(s);
  return 0;
}

Search with XSTRING_NONE

#include <stdio.h>
#include <xbase/string.h>

int main(void) {
  xString s = xStringCreate("the quick brown fox");

  size_t pos = xStringFindStr(s, "brown");
  if (pos != XSTRING_NONE) {
    printf("'brown' at index %zu\n", pos);  /* 'brown' at index 10 */
  }

  pos = xStringFindStr(s, "cat");
  if (pos == XSTRING_NONE) {
    printf("'cat' not found\n");
  }

  xStringDestroy(s);
  return 0;
}

Pre-allocation and Shrink

#include <stdio.h>
#include <xbase/string.h>

int main(void) {
  xString s = xStringCreate("hello");

  /* Pre-allocate 1 KB to avoid repeated reallocs. */
  s = xStringGrow(s, 1024);
  printf("avail=%zu\n", xStringAvail(s));  /* >= 1024 */

  s = xStringAppend(s, " world");
  s = xStringShrinkToFit(s);
  printf("cap=%zu, len=%zu\n", xStringCap(s), xStringLen(s));
  /* cap=11, len=11 */

  xStringDestroy(s);
  return 0;
}

Comparison and Equality

#include <stdio.h>
#include <xbase/string.h>

int main(void) {
  xString a = xStringCreate("abc");
  xString b = xStringCreate("abc");
  xString c = xStringCreate("abd");

  printf("a == b: %d\n", xStringEq(a, b));   /* 1 (true) */
  printf("a == c: %d\n", xStringEq(a, c));   /* 0 (false) */
  printf("a cmp c: %d\n", xStringCmp(a, c)); /* <0 */

  xStringDestroy(a);
  xStringDestroy(b);
  xStringDestroy(c);
  return 0;
}

Use Cases

1. Network Protocol Buffers — xString's binary safety and O(1) length make it ideal for building wire-format messages (HTTP headers, WebSocket frames, STUN attributes) where embedded NULs occur and strlen is unreliable.

2. Log Message Assembly — xStringAppendFormat provides a convenient way to build structured log lines incrementally, with automatic growth and no fixed-size buffer overflow risk.

3. Configuration String Handling — xString can hold user-provided configuration values, supporting both C-string APIs and explicit-length operations. xStringFindStr enables simple key-value parsing.

4. General String Builder — Any module that needs to concatenate multiple strings or formatted output can use xString as a safer, more ergonomic alternative to manual malloc/realloc/snprintf management.

Best Practices

• Always use the return value from append/grow functions. s = xStringAppend(s, "x") — the pointer may change after reallocation. The old pointer remains valid on failure, so you can still use it, but the new data won't be appended.
• Use XSTRING_NONE to check search results. if (xStringFindStr(s, "key") != XSTRING_NONE) is clearer and more idiomatic than comparing against (size_t)-1.
• Prefer xStringCreateLen for binary data. xStringCreate uses strlen internally and will stop at the first NUL byte. xStringCreateLen copies exactly the bytes you specify.
• Use xStringClear instead of Destroy+Create for reuse. xStringClear resets to an empty string while preserving the allocated capacity, avoiding a fresh allocation cycle.
• Pre-allocate with xStringGrow for known sizes. If you know the approximate final size, xStringGrow avoids multiple intermediate reallocations during incremental appends.
• Don't store derived pointers across mutations. Pointers obtained from the xString (e.g. s + offset) are invalidated by any append or grow operation that triggers reallocation.

Comparison with Other Libraries

Key Differentiator: xString combines Redis SDS's zero-friction char* compatibility with a threshold-based search strategy and printf-style formatted append — a practical middle ground between the minimalism of Redis SDS and the full feature set of C++ std::string.