src/stdlib/lists.h


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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

// Functions that operate on lists

#pragma once

#include <stdbool.h>

#include "datatypes.h"
#include "integers.h"
#include "types.h"
#include "util.h"

// Convert negative indices to back-indexed without branching: index0 = index + (index < 0)*(len+1)) - 1
#define List_get_checked(list_expr, index_expr, item_type, start, end)                                                 \
    ({                                                                                                                 \
        const List_t list = list_expr;                                                                                 \
        int64_t index = index_expr;                                                                                    \
        int64_t off = index + (index < 0) * (list.length + 1) - 1;                                                     \
        if (unlikely(off < 0 || off >= list.length))                                                                   \
            fail_source(__SOURCE_FILE__, start, end, "Invalid list index: ", index, " (list has length ",              \
                        (int64_t)list.length, ")\n");                                                                  \
        *(item_type *)(list.data + list.stride * off);                                                                 \
    })
#define List_get(list_expr, index_expr, item_type, var, optional_expr, none_expr)                                      \
    ({                                                                                                                 \
        const List_t list = list_expr;                                                                                 \
        int64_t index = index_expr;                                                                                    \
        int64_t offset = index + (index < 0) * (list.length + 1) - 1;                                                  \
        unlikely(offset < 0 || offset >= list.length) ? none_expr : ({                                                 \
            item_type var = *(item_type *)(list.data + list.stride * offset);                                          \
            optional_expr;                                                                                             \
        });                                                                                                            \
    })
#define List_lvalue(item_type, list_expr, index_expr, start, end)                                                      \
    *({                                                                                                                \
        List_t *list = list_expr;                                                                                      \
        int64_t index = index_expr;                                                                                    \
        int64_t off = index + (index < 0) * (list->length + 1) - 1;                                                    \
        if (unlikely(off < 0 || off >= list->length))                                                                  \
            fail_source(__SOURCE_FILE__, start, end, "Invalid list index: ", index, " (list has length ",              \
                        (int64_t)list->length, ")\n");                                                                 \
        if (list->data_refcount > 0) List$compact(list, sizeof(item_type));                                            \
        (item_type *)(list->data + list->stride * off);                                                                \
    })
#define List_set(item_type, list, index, value, start, end) List_lvalue(item_type, list_expr, index, start, end) = value
#define is_atomic(x)                                                                                                   \
    _Generic(x,                                                                                                        \
        bool: true,                                                                                                    \
        int8_t: true,                                                                                                  \
        int16_t: true,                                                                                                 \
        int32_t: true,                                                                                                 \
        int64_t: true,                                                                                                 \
        float: true,                                                                                                   \
        double: true,                                                                                                  \
        default: false)
#define TypedList(t, ...)                                                                                              \
    ({                                                                                                                 \
        t items[] = {__VA_ARGS__};                                                                                     \
        (List_t){.length = sizeof(items) / sizeof(items[0]),                                                           \
                 .stride = (int64_t)&items[1] - (int64_t)&items[0],                                                    \
                 .data = memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)),                                       \
                 .atomic = 0,                                                                                          \
                 .data_refcount = 0};                                                                                  \
    })
#define TypedListN(t, N, ...)                                                                                          \
    ({                                                                                                                 \
        t items[N] = {__VA_ARGS__};                                                                                    \
        (List_t){.length = N,                                                                                          \
                 .stride = (int64_t)&items[1] - (int64_t)&items[0],                                                    \
                 .data = memcpy(GC_MALLOC(sizeof(items)), items, sizeof(items)),                                       \
                 .atomic = 0,                                                                                          \
                 .data_refcount = 0};                                                                                  \
    })
#define List(x, ...)                                                                                                   \
    ({                                                                                                                 \
        __typeof(x) items[] = {x, __VA_ARGS__};                                                                        \
        (List_t){.length = sizeof(items) / sizeof(items[0]),                                                           \
                 .stride = (int64_t)&items[1] - (int64_t)&items[0],                                                    \
                 .data = memcpy(is_atomic(x) ? GC_MALLOC_ATOMIC(sizeof(items)) : GC_MALLOC(sizeof(items)), items,      \
                                sizeof(items)),                                                                        \
                 .atomic = is_atomic(x),                                                                               \
                 .data_refcount = 0};                                                                                  \
    })
// List refcounts use a saturating add, where once it's at the max value, it stays there.
#define LIST_INCREF(list) (list).data_refcount += ((list).data_refcount < LIST_MAX_DATA_REFCOUNT)
#define LIST_DECREF(list) (list).data_refcount -= ((list).data_refcount < LIST_MAX_DATA_REFCOUNT)
#define LIST_COPY(list)                                                                                                \
    ({                                                                                                                 \
        LIST_INCREF(list);                                                                                             \
        list;                                                                                                          \
    })

#define List$insert_value(list, item_expr, index, padded_item_size)                                                    \
    List$insert(list, (__typeof(item_expr)[1]){item_expr}, index, padded_item_size)
void List$insert(List_t *list, const void *item, Int_t index, int64_t padded_item_size);
void List$insert_all(List_t *list, List_t to_insert, Int_t index, int64_t padded_item_size);
void List$remove_at(List_t *list, Int_t index, Int_t count, int64_t padded_item_size);
void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type);
#define List$remove_item_value(list, item_expr, max, type)                                                             \
    List$remove_item(list, (__typeof(item_expr)[1]){item_expr}, max, type)

#define List$pop(list_expr, index_expr, item_type, nonnone_var, nonnone_expr, none_expr)                               \
    ({                                                                                                                 \
        List_t *list = list_expr;                                                                                      \
        Int_t index = index_expr;                                                                                      \
        int64_t index64 = Int64$from_int(index, false);                                                                \
        int64_t off = index64 + (index64 < 0) * (list->length + 1) - 1;                                                \
        (off >= 0 && off < list->length) ? ({                                                                          \
            item_type nonnone_var = *(item_type *)(list->data + off * list->stride);                                   \
            List$remove_at(list, index, I_small(1), sizeof(item_type));                                                \
            nonnone_expr;                                                                                              \
        })                                                                                                             \
                                         : none_expr;                                                                  \
    })

OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type);
#define List$find_value(list, item_expr, type)                                                                         \
    ({                                                                                                                 \
        __typeof(item_expr) item = item_expr;                                                                          \
        List$find(list, &item, type);                                                                                  \
    })
OptionalInt_t List$first(List_t list, Closure_t predicate);
void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size);
List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size);
void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size);
List_t List$shuffled(List_t list, OptionalClosure_t random_int64, int64_t padded_item_size);
void *List$random(List_t list, OptionalClosure_t random_int64);
#define List$random_value(list, random_int64, t)                                                                       \
    ({                                                                                                                 \
        List_t _list_expr = list;                                                                                      \
        if (_list_expr.length == 0) fail("Cannot get a random value from an empty list!");                             \
        *(t *)List$random(_list_expr, random_int64);                                                                   \
    })
List_t List$sample(List_t list, Int_t n, List_t weights, Closure_t random_num, int64_t padded_item_size);
Table_t List$counts(List_t list, const TypeInfo_t *type);
void List$clear(List_t *list);
void List$compact(List_t *list, int64_t padded_item_size);
PUREFUNC bool List$has(List_t list, void *item, const TypeInfo_t *type);
#define List$has_value(list, item_expr, type)                                                                          \
    ({                                                                                                                 \
        __typeof(item_expr) item = item_expr;                                                                          \
        List$has(list, &item, type);                                                                                   \
    })
PUREFUNC List_t List$from(List_t list, Int_t first);
PUREFUNC List_t List$to(List_t list, Int_t last);
PUREFUNC List_t List$by(List_t list, Int_t stride, int64_t padded_item_size);
PUREFUNC List_t List$slice(List_t list, Int_t int_first, Int_t int_last);
PUREFUNC List_t List$reversed(List_t list, int64_t padded_item_size);
List_t List$concat(List_t x, List_t y, int64_t padded_item_size);
PUREFUNC uint64_t List$hash(const void *list, const TypeInfo_t *type);
PUREFUNC int32_t List$compare(const void *x, const void *y, const TypeInfo_t *type);
PUREFUNC bool List$equal(const void *x, const void *y, const TypeInfo_t *type);
PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t *);
Text_t List$as_text(const void *list, bool colorize, const TypeInfo_t *type);
void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size);
void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size);
#define List$heap_push_value(heap, _value, comparison, padded_item_size)                                               \
    ({                                                                                                                 \
        __typeof(_value) value = _value;                                                                               \
        List$heap_push(heap, &value, comparison, padded_item_size);                                                    \
    })
void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size);
#define List$heap_pop_value(heap, comparison, type, nonnone_var, nonnone_expr, none_expr)                              \
    ({                                                                                                                 \
        List_t *_heap = heap;                                                                                          \
        (_heap->length > 0) ? ({                                                                                       \
            type nonnone_var = *(type *)_heap->data;                                                                   \
            List$heap_pop(_heap, comparison, sizeof(type));                                                            \
            nonnone_expr;                                                                                              \
        })                                                                                                             \
                            : none_expr;                                                                               \
    })
Int_t List$binary_search(List_t list, void *target, Closure_t comparison);
#define List$binary_search_value(list, target, comparison)                                                             \
    ({                                                                                                                 \
        __typeof(target) _target = target;                                                                             \
        List$binary_search(list, &_target, comparison);                                                                \
    })
void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type);
void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type);

#define List$metamethods                                                                                               \
    {                                                                                                                  \
        .as_text = List$as_text,                                                                                       \
        .compare = List$compare,                                                                                       \
        .equal = List$equal,                                                                                           \
        .hash = List$hash,                                                                                             \
        .is_none = List$is_none,                                                                                       \
        .serialize = List$serialize,                                                                                   \
        .deserialize = List$deserialize,                                                                               \
    }

#define List$info(item_info)                                                                                           \
    &((TypeInfo_t){.size = sizeof(List_t),                                                                             \
                   .align = __alignof__(List_t),                                                                       \
                   .tag = ListInfo,                                                                                    \
                   .ListInfo.item = item_info,                                                                         \
                   .metamethods = List$metamethods})