123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201 | // Functions that operate on lists
#pragma once
#include <stdbool.h>
#include "datatypes.h"
#include "integers.h"
#include "types.h"
#include "util.h"
extern char _EMPTY_LIST_SENTINEL;
#define EMPTY_LIST ((List_t){.data = &_EMPTY_LIST_SENTINEL})
#define EMPTY_ATOMIC_LIST ((List_t){.data = &_EMPTY_LIST_SENTINEL, .atomic = 1})
// 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, \
Text$concat(Text("Invalid list index: "), convert_to_text(index), Text(" (list has length "), \
convert_to_text((int64_t)list.length), Text(")\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, \
Text$concat(Text("Invalid list index: "), convert_to_text(index), Text(" (list has length "), \
convert_to_text((int64_t)list->length), Text(")\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 = sizeof(items) == 0 ? &_EMPTY_LIST_SENTINEL \
: 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 = N == 0 ? &_EMPTY_LIST_SENTINEL : 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_fn, t, nonnone_var, nonnone_expr, none_expr) \
({ \
List_t _list_expr = list; \
(_list_expr.length == 0) ? none_expr : ({ \
t nonnone_var = *(t *)List$random(_list_expr, random_fn); \
nonnone_expr; \
}); \
})
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; \
})
OptionalInt_t List$binary_search(List_t list, Closure_t 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})
|