bootstrap/rtl/list.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


/*
 * Minimal bootstrap RTL (runtime library) - List class
 *
 * Copyright © 2026 Samuel Lidén Borell <samuel@kodafritt.se>
 *
 * SPDX-License-Identifier: EUPL-1.2+ OR LGPL-2.1-or-later
 */
#include <assert.h>
#include <string.h>
#include "rtl.h"
#include "internal.h"

struct List {
    SlulInt capacity;
    SlulInt append, prepend;
    union Slul__Generic *elems;
};

struct List *List_new(void)
{
    struct List *list = malloc(sizeof(struct List));
    OOM_CHECK(list);
    list->capacity = 0;
    list->append = 0;
    list->prepend = 0;
    list->elems = NULL;
    return list;
}

SlulInt List_count(const struct List *const this)
{
    return this->append + this->prepend;
}

static void grow(struct List *const this)
{
    union Slul__Generic *realloced;
    SlulInt oldcapa, newcapa;
    SlulInt count;

    count = this->append + this->prepend;
    CHECK(count < 0x7FFFFFF-1U, "Oversized List");

    oldcapa = this->capacity;
    if (!oldcapa) {
        newcapa = 8;
    } else {
        assert(oldcapa <= count);
        CHECK(oldcapa+1 < ((size_t)-1)/2/sizeof(void *), "Oversized list capacity");
        newcapa = 2*oldcapa;
    }

    realloced = realloc(this->elems, sizeof(void *) * newcapa);
    OOM_CHECK(realloced);
    if (this->prepend) {
        memcpy(&realloced[newcapa - this->prepend],
               &realloced[oldcapa - this->prepend],
               sizeof(void *) * this->prepend);
    }
    this->capacity = newcapa;
    this->elems = realloced;
}

void List_add(
        struct List *const this,
        const union Slul__Generic elem)
{
    if (this->append + this->prepend == this->capacity) {
        grow(this);
    }

    this->elems[this->append++] = elem;
}

void List_insert_first(
        struct List *const this,
        const union Slul__Generic elem)
{
    if (this->append + this->prepend == this->capacity) {
        grow(this);
    }

    this->elems[this->prepend++] = elem;
}