githubmirror/redis

src/vector.c
173 строки5 KB
Moti Cohen
Introduce internal append-only pointer vector DS (#15039)
14 апр 2026, 18:45
14 апр 2026, 18:453f810d3
/* vector.c - Simple append-only vector implementation
 *
 * Copyright (c) 2026-Present, Redis Ltd.
 * All rights reserved.
 *
 * Licensed under your choice of (a) the Redis Source Available License 2.0
 * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the
 * GNU Affero General Public License v3 (AGPLv3).
 */

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "vector.h"
#include "redisassert.h"
#include "zmalloc.h"

#define VEC_DEFAULT_INITCAP 8

/*
 * Vector initialization.
 *
 * Modes:
 * - stack != NULL: use caller-provided storage for the first initcap items.
 * - stack == NULL && initcap > 0: start heap-backed with an initial 'initcap' capacity.
 * - stack == NULL && initcap == 0: start heap-backed with no initial storage.
 */
void vecInit(vec *v, void **stack, size_t initcap) {
    /* If stack is provided, initcap must be > 0 and at the size of the stack */
    assert(initcap > 0 || stack == NULL);
    
    v->size = 0;
    v->cap = initcap;
    v->stack = stack; /* stack is NULL if not used */
    
    /* now init data either stack, heap or NULL */
    v->data = (stack) ? stack : ((initcap > 0) ? zmalloc(initcap * sizeof(void *)) : NULL);
}

/* Free only heap storage if any */
void vecRelease(vec *v) {
    /* if data is not stack-allocated and is not NULL, free it */
    if (v->data && v->data != v->stack)
        zfree(v->data);
    v->size = 0;
    v->cap = 0;
    v->data = NULL;
    v->stack = NULL;
}

/* Reset the logical length to zero while preserving allocated storage. */
void vecClear(vec *v) {
    v->size = 0;
}

/* Return the number of elements in the vector. */
size_t vecSize(const vec *v) {
    return v->size;
}

/* Get element at index. index must be < vecSize(v). */
void *vecGet(const vec *v, size_t index) {
    assert(index < v->size);
    return v->data[index];
}

/* Return the contiguous backing array. */
void **vecData(vec *v) {
    return v->data;
}

/* Ensure capacity is at least mincap. */
void vecReserve(vec *v, size_t mincap) {
    void **newdata;

    if (mincap <= v->cap) return;

    /* If no heap storage is used yet, allocate and copy from stack if needed. */
    if (v->data == v->stack) {
        newdata = zmalloc(mincap * sizeof(void *));
        if (v->size) memcpy(newdata, v->data, v->size * sizeof(void *));
    } else {
        newdata = zrealloc(v->data, mincap * sizeof(void *));
    }

    v->data = newdata;
    v->cap = mincap;
}

/* Append one element, growing storage as needed. */
void vecPush(vec *v, void *value) {
    if (v->size == v->cap) {
        size_t newcap = (v->cap > 0) ? v->cap * 2 : VEC_DEFAULT_INITCAP;
        vecReserve(v, newcap);
    }

    v->data[v->size++] = value;
}

#ifdef REDIS_TEST

#include <stdio.h>
#include <stdlib.h>

#include "testhelp.h"

#define UNUSED(x) (void)(x)

int vectorTest(int argc, char **argv, int flags)
{
    UNUSED(argc);
    UNUSED(argv);
    UNUSED(flags);

    vec v;
    void *vstack[2];
    int one = 1, two = 2, three = 3, four = 4, five = 5, six = 6;

    vecInit(&v, vstack, 2);
    test_cond("vecInit() stack-backed size is 0", vecSize(&v) == 0);
    test_cond("vecInit() uses stack buffer", vecData(&v) == vstack);
    vecReserve(&v, 1);
    test_cond("vecReserve() no-ops when capacity is already sufficient",
              v.cap == 2 && vecData(&v) == vstack);
    vecPush(&v, &one);
    vecPush(&v, &two);
    test_cond("vecPush() appends into stack storage",
              vecSize(&v) == 2 && vecData(&v) == vstack &&
              vecGet(&v, 0) == &one && vecGet(&v, 1) == &two);
    vecReserve(&v, 4);
    test_cond("vecReserve() spills from stack to heap preserving values",
              v.cap == 4 && vecData(&v) != vstack &&
              vecGet(&v, 0) == &one && vecGet(&v, 1) == &two);
    vecPush(&v, &three);
    test_cond("vecPush() spills from stack to heap preserving values",
              vecSize(&v) == 3 &&
              vecData(&v) != vstack && vecGet(&v, 0) == &one &&
              vecGet(&v, 1) == &two && vecGet(&v, 2) == &three);

    void **heap_data = vecData(&v);
    vecClear(&v);
    test_cond("vecClear() resets size but preserves storage",
              vecSize(&v) == 0 && vecData(&v) == heap_data);
    vecRelease(&v);
    test_cond("vecRelease() resets vector state",
              vecSize(&v) == 0 && vecData(&v) == NULL && v.cap == 0);

    vecInit(&v, NULL, 4);
    test_cond("vecInit() heap-backed hint allocates storage",
              vecSize(&v) == 0 && vecData(&v) != NULL && v.cap == 4);
    vecPush(&v, &four);
    test_cond("vecPush() works in heap-backed mode",
              vecGet(&v, 0) == &four);
    vecReserve(&v, 8);
    test_cond("vecReserve() grows heap-backed storage preserving values",
              v.cap == 8 && vecGet(&v, 0) == &four);
    vecRelease(&v);

    vecInit(&v, NULL, 0);
    vecReserve(&v, 6);
    test_cond("vecReserve() allocates heap storage from empty vector",
              v.cap == 6 && vecData(&v) != NULL);
    vecPush(&v, &five);
    vecPush(&v, &six);
    test_cond("vecPush() works after vecReserve() on empty vector",
              vecSize(&v) == 2 &&
              vecGet(&v, 0) == &five && vecGet(&v, 1) == &six);
    vecRelease(&v);

    return 0;
}
#endif