aboutsummaryrefslogtreecommitdiff
path: root/src/stdlib/lists.c
diff options
context:
space:
mode:
authorBruce Hill <bruce@bruce-hill.com>2025-08-23 19:28:08 -0400
committerBruce Hill <bruce@bruce-hill.com>2025-08-23 19:28:08 -0400
commitfcda36561d668f43bac91ea31cd55cbbd605d330 (patch)
treeeb74c0b17df584af0fd8154422ad924e04c96cc2 /src/stdlib/lists.c
parent414b0c7472c87c5a013029aefef49e2dbc41e700 (diff)
Autoformat everything with clang-format
Diffstat (limited to 'src/stdlib/lists.c')
-rw-r--r--src/stdlib/lists.c569
1 files changed, 261 insertions, 308 deletions
diff --git a/src/stdlib/lists.c b/src/stdlib/lists.c
index ce27f822..415e28a5 100644
--- a/src/stdlib/lists.c
+++ b/src/stdlib/lists.c
@@ -6,8 +6,8 @@
#include <stdint.h>
#include <sys/param.h>
-#include "lists.h"
#include "integers.h"
+#include "lists.h"
#include "math.h"
#include "metamethods.h"
#include "optionals.h"
@@ -18,39 +18,37 @@
// Use inline version of siphash code:
#include "siphash-internals.h"
-PUREFUNC static INLINE int64_t get_padded_item_size(const TypeInfo_t *info)
-{
+PUREFUNC static INLINE int64_t get_padded_item_size(const TypeInfo_t *info) {
int64_t size = info->ListInfo.item->size;
- if (info->ListInfo.item->align > 1 && size % info->ListInfo.item->align)
- errx(1, "Item size is not padded!");
+ if (info->ListInfo.item->align > 1 && size % info->ListInfo.item->align) errx(1, "Item size is not padded!");
return size;
}
// Replace the list's .data pointer with a new pointer to a copy of the
// data that is compacted and has a stride of exactly `padded_item_size`
-public void List$compact(List_t *list, int64_t padded_item_size)
-{
+public
+void List$compact(List_t *list, int64_t padded_item_size) {
void *copy = NULL;
if (list->length > 0) {
copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)list->length * (size_t)padded_item_size)
- : GC_MALLOC((size_t)list->length * (size_t)padded_item_size);
+ : GC_MALLOC((size_t)list->length * (size_t)padded_item_size);
if ((int64_t)list->stride == padded_item_size) {
memcpy(copy, list->data, (size_t)list->length * (size_t)padded_item_size);
} else {
for (int64_t i = 0; i < list->length; i++)
- memcpy(copy + i*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size);
+ memcpy(copy + i * padded_item_size, list->data + list->stride * i, (size_t)padded_item_size);
}
}
*list = (List_t){
- .data=copy,
- .length=list->length,
- .stride=padded_item_size,
- .atomic=list->atomic,
+ .data = copy,
+ .length = list->length,
+ .stride = padded_item_size,
+ .atomic = list->atomic,
};
}
-public void List$insert(List_t *list, const void *item, Int_t int_index, int64_t padded_item_size)
-{
+public
+void List$insert(List_t *list, const void *item, Int_t int_index, int64_t padded_item_size) {
int64_t index = Int64$from_int(int_index, false);
if (index <= 0) index = list->length + index + 1;
@@ -61,42 +59,38 @@ public void List$insert(List_t *list, const void *item, Int_t int_index, int64_t
if (!list->data) {
list->free = 4;
list->data = list->atomic ? GC_MALLOC_ATOMIC((size_t)list->free * (size_t)padded_item_size)
- : GC_MALLOC((size_t)list->free * (size_t)padded_item_size);
+ : GC_MALLOC((size_t)list->free * (size_t)padded_item_size);
list->stride = padded_item_size;
} else if (list->free < 1 || list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) {
// Resize policy: +50% growth (clamped between 8 and LIST_MAX_FREE_ENTRIES)
- list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, list->length)/2);
+ list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, list->length) / 2);
void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)(list->length + list->free) * (size_t)padded_item_size)
- : GC_MALLOC((size_t)(list->length + list->free) * (size_t)padded_item_size);
- for (int64_t i = 0; i < index-1; i++)
- memcpy(copy + i*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size);
- for (int64_t i = index-1; i < (int64_t)list->length; i++)
- memcpy(copy + (i+1)*padded_item_size, list->data + list->stride*i, (size_t)padded_item_size);
+ : GC_MALLOC((size_t)(list->length + list->free) * (size_t)padded_item_size);
+ for (int64_t i = 0; i < index - 1; i++)
+ memcpy(copy + i * padded_item_size, list->data + list->stride * i, (size_t)padded_item_size);
+ for (int64_t i = index - 1; i < (int64_t)list->length; i++)
+ memcpy(copy + (i + 1) * padded_item_size, list->data + list->stride * i, (size_t)padded_item_size);
list->data = copy;
list->data_refcount = 0;
list->stride = padded_item_size;
} else {
- if (index != list->length+1) {
+ if (index != list->length + 1) {
assert(list->length >= index);
- size_t size = (size_t)((list->length - index + 1)*padded_item_size);
+ size_t size = (size_t)((list->length - index + 1) * padded_item_size);
assert(size < SIZE_MAX);
- memmove(
- list->data + index*padded_item_size,
- list->data + (index-1)*padded_item_size,
- size);
+ memmove(list->data + index * padded_item_size, list->data + (index - 1) * padded_item_size, size);
}
}
assert(list->free > 0);
--list->free;
++list->length;
- memcpy((void*)list->data + (index-1)*padded_item_size, item, (size_t)padded_item_size);
+ memcpy((void *)list->data + (index - 1) * padded_item_size, item, (size_t)padded_item_size);
}
-public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int64_t padded_item_size)
-{
+public
+void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int64_t padded_item_size) {
int64_t index = Int64$from_int(int_index, false);
- if (to_insert.length == 0)
- return;
+ if (to_insert.length == 0) return;
if (!list->data) {
*list = to_insert;
@@ -111,34 +105,33 @@ public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int
fail("Invalid insertion index ", index, " for a list with length ", (int64_t)list->length);
if ((int64_t)list->free >= (int64_t)to_insert.length // Adequate free space
- && list->data_refcount == 0 // Not aliased memory
- && (int64_t)list->stride == padded_item_size) { // Contiguous list
+ && list->data_refcount == 0 // Not aliased memory
+ && (int64_t)list->stride == padded_item_size) { // Contiguous list
// If we can fit this within the list's preallocated free space, do that:
list->free -= to_insert.length;
list->length += to_insert.length;
- if (index != list->length+1)
- memmove((void*)list->data + index*padded_item_size,
- list->data + (index-1)*padded_item_size,
- (size_t)((list->length - index + to_insert.length-1)*padded_item_size));
+ if (index != list->length + 1)
+ memmove((void *)list->data + index * padded_item_size, list->data + (index - 1) * padded_item_size,
+ (size_t)((list->length - index + to_insert.length - 1) * padded_item_size));
for (int64_t i = 0; i < to_insert.length; i++)
- memcpy((void*)list->data + (index-1 + i)*padded_item_size,
- to_insert.data + i*to_insert.stride, (size_t)padded_item_size);
+ memcpy((void *)list->data + (index - 1 + i) * padded_item_size, to_insert.data + i * to_insert.stride,
+ (size_t)padded_item_size);
} else {
// Otherwise, allocate a new chunk of memory for the list and populate it:
int64_t new_len = list->length + to_insert.length;
- list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, new_len/4));
+ list->free = MIN(LIST_MAX_FREE_ENTRIES, MAX(8, new_len / 4));
void *data = list->atomic ? GC_MALLOC_ATOMIC((size_t)((new_len + list->free) * padded_item_size))
- : GC_MALLOC((size_t)((new_len + list->free) * padded_item_size));
+ : GC_MALLOC((size_t)((new_len + list->free) * padded_item_size));
void *p = data;
// Copy first chunk of `list` if needed:
if (index > 1) {
if (list->stride == padded_item_size) {
- memcpy(p, list->data, (size_t)((index-1)*padded_item_size));
- p += (index-1)*padded_item_size;
+ memcpy(p, list->data, (size_t)((index - 1) * padded_item_size));
+ p += (index - 1) * padded_item_size;
} else {
- for (int64_t i = 0; i < index-1; i++) {
- memcpy(p, list->data + list->stride*i, (size_t)padded_item_size);
+ for (int64_t i = 0; i < index - 1; i++) {
+ memcpy(p, list->data + list->stride * i, (size_t)padded_item_size);
p += padded_item_size;
}
}
@@ -146,11 +139,11 @@ public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int
// Copy `to_insert`
if (to_insert.stride == padded_item_size) {
- memcpy(p, to_insert.data, (size_t)(to_insert.length*padded_item_size));
- p += to_insert.length*padded_item_size;
+ memcpy(p, to_insert.data, (size_t)(to_insert.length * padded_item_size));
+ p += to_insert.length * padded_item_size;
} else {
- for (int64_t i = 0; i < index-1; i++) {
- memcpy(p, to_insert.data + to_insert.stride*i, (size_t)padded_item_size);
+ for (int64_t i = 0; i < index - 1; i++) {
+ memcpy(p, to_insert.data + to_insert.stride * i, (size_t)padded_item_size);
p += padded_item_size;
}
}
@@ -158,11 +151,12 @@ public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int
// Copy last chunk of `list` if needed:
if (index < list->length + 1) {
if (list->stride == padded_item_size) {
- memcpy(p, list->data + padded_item_size*(index-1), (size_t)((list->length - index + 1)*padded_item_size));
- p += (list->length - index + 1)*padded_item_size;
+ memcpy(p, list->data + padded_item_size * (index - 1),
+ (size_t)((list->length - index + 1) * padded_item_size));
+ p += (list->length - index + 1) * padded_item_size;
} else {
- for (int64_t i = index-1; i < list->length-1; i++) {
- memcpy(p, list->data + list->stride*i, (size_t)padded_item_size);
+ for (int64_t i = index - 1; i < list->length - 1; i++) {
+ memcpy(p, list->data + list->stride * i, (size_t)padded_item_size);
p += padded_item_size;
}
}
@@ -174,27 +168,27 @@ public void List$insert_all(List_t *list, List_t to_insert, Int_t int_index, int
}
}
-public void List$remove_at(List_t *list, Int_t int_index, Int_t int_count, int64_t padded_item_size)
-{
+public
+void List$remove_at(List_t *list, Int_t int_index, Int_t int_count, int64_t padded_item_size) {
int64_t index = Int64$from_int(int_index, false);
if (index < 1) index = list->length + index + 1;
int64_t count = Int64$from_int(int_count, false);
if (index < 1 || index > (int64_t)list->length || count < 1) return;
- if (count > list->length - index + 1)
- count = (list->length - index) + 1;
+ if (count > list->length - index + 1) count = (list->length - index) + 1;
if (index == 1) {
list->data += list->stride * count;
} else if (index + count > list->length) {
list->free += count;
} else if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) {
- void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)((list->length-1) * padded_item_size))
- : GC_MALLOC((size_t)((list->length-1) * padded_item_size));
+ void *copy = list->atomic ? GC_MALLOC_ATOMIC((size_t)((list->length - 1) * padded_item_size))
+ : GC_MALLOC((size_t)((list->length - 1) * padded_item_size));
for (int64_t src = 1, dest = 1; src <= (int64_t)list->length; src++) {
if (src < index || src >= index + count) {
- memcpy(copy + (dest - 1)*padded_item_size, list->data + list->stride*(src - 1), (size_t)padded_item_size);
+ memcpy(copy + (dest - 1) * padded_item_size, list->data + list->stride * (src - 1),
+ (size_t)padded_item_size);
++dest;
}
}
@@ -202,26 +196,27 @@ public void List$remove_at(List_t *list, Int_t int_index, Int_t int_count, int64
list->free = 0;
list->data_refcount = 0;
} else {
- memmove((void*)list->data + (index-1)*padded_item_size, list->data + (index-1 + count)*padded_item_size,
- (size_t)((list->length - index + count - 1)*padded_item_size));
+ memmove((void *)list->data + (index - 1) * padded_item_size,
+ list->data + (index - 1 + count) * padded_item_size,
+ (size_t)((list->length - index + count - 1) * padded_item_size));
list->free += count;
}
list->length -= count;
if (list->length == 0) list->data = NULL;
}
-public void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type)
-{
+public
+void List$remove_item(List_t *list, void *item, Int_t max_removals, const TypeInfo_t *type) {
int64_t padded_item_size = get_padded_item_size(type);
- const Int_t ZERO = (Int_t){.small=(0<<2)|1};
- const Int_t ONE = (Int_t){.small=(1<<2)|1};
+ const Int_t ZERO = (Int_t){.small = (0 << 2) | 1};
+ const Int_t ONE = (Int_t){.small = (1 << 2) | 1};
const TypeInfo_t *item_type = type->ListInfo.item;
- for (int64_t i = 0; i < list->length; ) {
+ for (int64_t i = 0; i < list->length;) {
if (max_removals.small == ZERO.small) // zero
break;
- if (generic_equal(item, list->data + i*list->stride, item_type)) {
- List$remove_at(list, I(i+1), ONE, padded_item_size);
+ if (generic_equal(item, list->data + i * list->stride, item_type)) {
+ List$remove_at(list, I(i + 1), ONE, padded_item_size);
max_removals = Int$minus(max_removals, ONE);
} else {
i++;
@@ -229,45 +224,41 @@ public void List$remove_item(List_t *list, void *item, Int_t max_removals, const
}
}
-public OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type)
-{
+public
+OptionalInt_t List$find(List_t list, void *item, const TypeInfo_t *type) {
const TypeInfo_t *item_type = type->ListInfo.item;
for (int64_t i = 0; i < list.length; i++) {
- if (generic_equal(item, list.data + i*list.stride, item_type))
- return I(i+1);
+ if (generic_equal(item, list.data + i * list.stride, item_type)) return I(i + 1);
}
return NONE_INT;
}
-public OptionalInt_t List$first(List_t list, Closure_t predicate)
-{
- bool (*is_good)(void*, void*) = (void*)predicate.fn;
+public
+OptionalInt_t List$first(List_t list, Closure_t predicate) {
+ bool (*is_good)(void *, void *) = (void *)predicate.fn;
for (int64_t i = 0; i < list.length; i++) {
- if (is_good(list.data + i*list.stride, predicate.userdata))
- return I(i+1);
+ if (is_good(list.data + i * list.stride, predicate.userdata)) return I(i + 1);
}
return NONE_INT;
}
-static Closure_t _sort_comparison = {.fn=NULL};
+static Closure_t _sort_comparison = {.fn = NULL};
-int _compare_closure(const void *a, const void *b)
-{
- typedef int (*comparison_t)(const void*, const void*, void*);
+int _compare_closure(const void *a, const void *b) {
+ typedef int (*comparison_t)(const void *, const void *, void *);
return ((comparison_t)_sort_comparison.fn)(a, b, _sort_comparison.userdata);
}
-public void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size)
-{
- if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size)
- List$compact(list, padded_item_size);
+public
+void List$sort(List_t *list, Closure_t comparison, int64_t padded_item_size) {
+ if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) List$compact(list, padded_item_size);
_sort_comparison = comparison;
qsort(list->data, (size_t)list->length, (size_t)padded_item_size, _compare_closure);
}
-public List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size)
-{
+public
+List_t List$sorted(List_t list, Closure_t comparison, int64_t padded_item_size) {
List$compact(&list, padded_item_size);
_sort_comparison = comparison;
qsort(list.data, (size_t)list.length, (size_t)padded_item_size, _compare_closure);
@@ -283,13 +274,12 @@ static ssize_t getrandom(void *buf, size_t buflen, unsigned int flags) {
}
#elif defined(__linux__)
// Use getrandom()
-# include <sys/random.h>
+#include <sys/random.h>
#else
- #error "Unsupported platform for secure random number generation"
+#error "Unsupported platform for secure random number generation"
#endif
-static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata)
-{
+static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata) {
(void)userdata;
if (min > max) fail("Random minimum value (", min, ") is larger than the maximum value (", max, ")");
if (min == max) return min;
@@ -303,50 +293,49 @@ static int64_t _default_random_int64(int64_t min, int64_t max, void *userdata)
return (int64_t)((uint64_t)min + (r % range));
}
-public void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size)
-{
- if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size)
- List$compact(list, padded_item_size);
+public
+void List$shuffle(List_t *list, OptionalClosure_t random_int64, int64_t padded_item_size) {
+ if (list->data_refcount != 0 || (int64_t)list->stride != padded_item_size) List$compact(list, padded_item_size);
- typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*);
+ typedef int64_t (*rng_fn_t)(int64_t, int64_t, void *);
rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64;
char tmp[padded_item_size];
- for (int64_t i = list->length-1; i > 1; i--) {
+ for (int64_t i = list->length - 1; i > 1; i--) {
int64_t j = rng_fn(0, i, random_int64.userdata);
- if unlikely (j < 0 || j > list->length-1)
+ if unlikely (j < 0 || j > list->length - 1)
fail("The provided random number function returned an invalid value: ", j, " (not between 0 and ", i, ")");
- memcpy(tmp, list->data + i*padded_item_size, (size_t)padded_item_size);
- memcpy((void*)list->data + i*padded_item_size, list->data + j*padded_item_size, (size_t)padded_item_size);
- memcpy((void*)list->data + j*padded_item_size, tmp, (size_t)padded_item_size);
+ memcpy(tmp, list->data + i * padded_item_size, (size_t)padded_item_size);
+ memcpy((void *)list->data + i * padded_item_size, list->data + j * padded_item_size, (size_t)padded_item_size);
+ memcpy((void *)list->data + j * padded_item_size, tmp, (size_t)padded_item_size);
}
}
-public List_t List$shuffled(List_t list, Closure_t random_int64, int64_t padded_item_size)
-{
+public
+List_t List$shuffled(List_t list, Closure_t random_int64, int64_t padded_item_size) {
List$compact(&list, padded_item_size);
List$shuffle(&list, random_int64, padded_item_size);
return list;
}
-public void *List$random(List_t list, OptionalClosure_t random_int64)
-{
- if (list.length == 0)
- return NULL; // fail("Cannot get a random item from an empty list!");
+public
+void *List$random(List_t list, OptionalClosure_t random_int64) {
+ if (list.length == 0) return NULL; // fail("Cannot get a random item from an empty list!");
- typedef int64_t (*rng_fn_t)(int64_t, int64_t, void*);
+ typedef int64_t (*rng_fn_t)(int64_t, int64_t, void *);
rng_fn_t rng_fn = random_int64.fn ? (rng_fn_t)random_int64.fn : _default_random_int64;
- int64_t index = rng_fn(0, list.length-1, random_int64.userdata);
- if unlikely (index < 0 || index > list.length-1)
- fail("The provided random number function returned an invalid value: ", index, " (not between 0 and ", (int64_t)list.length, ")");
- return list.data + list.stride*index;
+ int64_t index = rng_fn(0, list.length - 1, random_int64.userdata);
+ if unlikely (index < 0 || index > list.length - 1)
+ fail("The provided random number function returned an invalid value: ", index, " (not between 0 and ",
+ (int64_t)list.length, ")");
+ return list.data + list.stride * index;
}
-public Table_t List$counts(List_t list, const TypeInfo_t *type)
-{
+public
+Table_t List$counts(List_t list, const TypeInfo_t *type) {
Table_t counts = {};
const TypeInfo_t count_type = *Table$info(type->ListInfo.item, &Int$info);
for (int64_t i = 0; i < list.length; i++) {
- void *key = list.data + i*list.stride;
+ void *key = list.data + i * list.stride;
int64_t *count = Table$get(counts, key, &count_type);
int64_t val = count ? *count + 1 : 1;
Table$set(&counts, key, &val, &count_type);
@@ -354,14 +343,13 @@ public Table_t List$counts(List_t list, const TypeInfo_t *type)
return counts;
}
-static double _default_random_num(void *userdata)
-{
+static double _default_random_num(void *userdata) {
(void)userdata;
union {
Num_t num;
uint64_t bits;
- } r = {.bits=0}, one = {.num=1.0};
- assert(getrandom((uint8_t*)&r, sizeof(r), 0) == sizeof(r));
+ } r = {.bits = 0}, one = {.num = 1.0};
+ assert(getrandom((uint8_t *)&r, sizeof(r), 0) == sizeof(r));
// Set r.num to 1.<random-bits>
r.bits &= ~(0xFFFULL << 52);
@@ -369,39 +357,30 @@ static double _default_random_num(void *userdata)
return r.num - 1.0;
}
-public List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClosure_t random_num, int64_t padded_item_size)
-{
+public
+List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClosure_t random_num, int64_t padded_item_size) {
int64_t n = Int64$from_int(int_n, false);
- if (n < 0)
- fail("Cannot select a negative number of values");
+ if (n < 0) fail("Cannot select a negative number of values");
- if (n == 0)
- return (List_t){};
+ if (n == 0) return (List_t){};
- if (list.length == 0)
- fail("There are no elements in this list!");
+ if (list.length == 0) fail("There are no elements in this list!");
if (weights.length != list.length)
fail("List has ", (int64_t)list.length, " elements, but there are ", (int64_t)weights.length, " weights given");
double total = 0.0;
for (int64_t i = 0; i < weights.length && i < list.length; i++) {
- double weight = *(double*)(weights.data + weights.stride*i);
- if (isinf(weight))
- fail("Infinite weight!");
- else if (isnan(weight))
- fail("NaN weight!");
- else if (weight < 0.0)
- fail("Negative weight!");
- else
- total += weight;
+ double weight = *(double *)(weights.data + weights.stride * i);
+ if (isinf(weight)) fail("Infinite weight!");
+ else if (isnan(weight)) fail("NaN weight!");
+ else if (weight < 0.0) fail("Negative weight!");
+ else total += weight;
}
- if (isinf(total))
- fail("Sample weights have overflowed to infinity");
+ if (isinf(total)) fail("Sample weights have overflowed to infinity");
- if (total == 0.0)
- fail("None of the given weights are nonzero");
+ if (total == 0.0) fail("None of the given weights are nonzero");
double inverse_average = (double)list.length / total;
@@ -411,7 +390,7 @@ public List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClos
} aliases[list.length];
for (int64_t i = 0; i < list.length; i++) {
- double weight = i >= weights.length ? 0.0 : *(double*)(weights.data + weights.stride*i);
+ double weight = i >= weights.length ? 0.0 : *(double *)(weights.data + weights.stride * i);
aliases[i].odds = weight * inverse_average;
aliases[i].alias = -1;
}
@@ -435,16 +414,16 @@ public List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClos
}
for (int64_t i = small; i < list.length; i++)
- if (aliases[i].alias == -1)
- aliases[i].alias = i;
+ if (aliases[i].alias == -1) aliases[i].alias = i;
- typedef double (*rng_fn_t)(void*);
+ typedef double (*rng_fn_t)(void *);
rng_fn_t rng_fn = random_num.fn ? (rng_fn_t)random_num.fn : _default_random_num;
- List_t selected = {
- .data=list.atomic ? GC_MALLOC_ATOMIC((size_t)(n * padded_item_size)) : GC_MALLOC((size_t)(n * padded_item_size)),
- .length=n,
- .stride=padded_item_size, .atomic=list.atomic};
+ List_t selected = {.data = list.atomic ? GC_MALLOC_ATOMIC((size_t)(n * padded_item_size))
+ : GC_MALLOC((size_t)(n * padded_item_size)),
+ .length = n,
+ .stride = padded_item_size,
+ .atomic = list.atomic};
for (int64_t i = 0; i < n; i++) {
double r = rng_fn(random_num.userdata);
if unlikely (r < 0.0 || r >= 1.0)
@@ -452,85 +431,77 @@ public List_t List$sample(List_t list, Int_t int_n, List_t weights, OptionalClos
r *= (double)list.length;
int64_t index = (int64_t)r;
assert(index >= 0 && index < list.length);
- if ((r - (double)index) > aliases[index].odds)
- index = aliases[index].alias;
- memcpy(selected.data + i*selected.stride, list.data + index*list.stride, (size_t)padded_item_size);
+ if ((r - (double)index) > aliases[index].odds) index = aliases[index].alias;
+ memcpy(selected.data + i * selected.stride, list.data + index * list.stride, (size_t)padded_item_size);
}
return selected;
}
-public List_t List$from(List_t list, Int_t first)
-{
- return List$slice(list, first, I_small(-1));
-}
+public
+List_t List$from(List_t list, Int_t first) { return List$slice(list, first, I_small(-1)); }
-public List_t List$to(List_t list, Int_t last)
-{
- return List$slice(list, I_small(1), last);
-}
+public
+List_t List$to(List_t list, Int_t last) { return List$slice(list, I_small(1), last); }
-public List_t List$by(List_t list, Int_t int_stride, int64_t padded_item_size)
-{
+public
+List_t List$by(List_t list, Int_t int_stride, int64_t padded_item_size) {
int64_t stride = Int64$from_int(int_stride, false);
// In the unlikely event that the stride value would be too large to fit in
// a 15-bit integer, fall back to creating a copy of the list:
- if (unlikely(list.stride*stride < LIST_MIN_STRIDE || list.stride*stride > LIST_MAX_STRIDE)) {
+ if (unlikely(list.stride * stride < LIST_MIN_STRIDE || list.stride * stride > LIST_MAX_STRIDE)) {
void *copy = NULL;
int64_t len = (stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0);
if (len > 0) {
- copy = list.atomic ? GC_MALLOC_ATOMIC((size_t)(len * padded_item_size)) : GC_MALLOC((size_t)(len * padded_item_size));
+ copy = list.atomic ? GC_MALLOC_ATOMIC((size_t)(len * padded_item_size))
+ : GC_MALLOC((size_t)(len * padded_item_size));
void *start = (stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data);
for (int64_t i = 0; i < len; i++)
- memcpy(copy + i*padded_item_size, start + list.stride*stride*i, (size_t)padded_item_size);
+ memcpy(copy + i * padded_item_size, start + list.stride * stride * i, (size_t)padded_item_size);
}
return (List_t){
- .data=copy,
- .length=len,
- .stride=padded_item_size,
- .atomic=list.atomic,
+ .data = copy,
+ .length = len,
+ .stride = padded_item_size,
+ .atomic = list.atomic,
};
}
- if (stride == 0)
- return (List_t){.atomic=list.atomic};
+ if (stride == 0) return (List_t){.atomic = list.atomic};
return (List_t){
- .atomic=list.atomic,
- .data=(stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data),
- .length=(stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0),
- .stride=list.stride * stride,
- .data_refcount=list.data_refcount,
+ .atomic = list.atomic,
+ .data = (stride < 0 ? list.data + (list.stride * (list.length - 1)) : list.data),
+ .length = (stride < 0 ? list.length / -stride : list.length / stride) + ((list.length % stride) != 0),
+ .stride = list.stride * stride,
+ .data_refcount = list.data_refcount,
};
}
-public List_t List$slice(List_t list, Int_t int_first, Int_t int_last)
+public
+List_t List$slice(List_t list, Int_t int_first, Int_t int_last)
{
int64_t first = Int64$from_int(int_first, false);
- if (first < 0)
- first = list.length + first + 1;
+ if (first < 0) first = list.length + first + 1;
int64_t last = Int64$from_int(int_last, false);
- if (last < 0)
- last = list.length + last + 1;
+ if (last < 0) last = list.length + last + 1;
- if (last > list.length)
- last = list.length;
+ if (last > list.length) last = list.length;
- if (first < 1 || first > list.length || last == 0)
- return (List_t){.atomic=list.atomic};
+ if (first < 1 || first > list.length || last == 0) return (List_t){.atomic = list.atomic};
return (List_t){
- .atomic=list.atomic,
- .data=list.data + list.stride*(first-1),
- .length=last - first + 1,
- .stride=list.stride,
- .data_refcount=list.data_refcount,
+ .atomic = list.atomic,
+ .data = list.data + list.stride * (first - 1),
+ .length = last - first + 1,
+ .stride = list.stride,
+ .data_refcount = list.data_refcount,
};
}
-public List_t List$reversed(List_t list, int64_t padded_item_size)
-{
+public
+List_t List$reversed(List_t list, int64_t padded_item_size) {
// Just in case negating the stride gives a value that doesn't fit into a
// 15-bit integer, fall back to List$by()'s more general method of copying
// the list. This should only happen if list.stride is MIN_STRIDE to
@@ -540,58 +511,54 @@ public List_t List$reversed(List_t list, int64_t padded_item_size)
List_t reversed = list;
reversed.stride = -list.stride;
- reversed.data = list.data + (list.length-1)*list.stride;
+ reversed.data = list.data + (list.length - 1) * list.stride;
return reversed;
}
-public List_t List$concat(List_t x, List_t y, int64_t padded_item_size)
-{
- void *data = x.atomic ? GC_MALLOC_ATOMIC((size_t)(padded_item_size*(x.length + y.length)))
- : GC_MALLOC((size_t)(padded_item_size*(x.length + y.length)));
+public
+List_t List$concat(List_t x, List_t y, int64_t padded_item_size) {
+ void *data = x.atomic ? GC_MALLOC_ATOMIC((size_t)(padded_item_size * (x.length + y.length)))
+ : GC_MALLOC((size_t)(padded_item_size * (x.length + y.length)));
if (x.stride == padded_item_size) {
- memcpy(data, x.data, (size_t)(padded_item_size*x.length));
+ memcpy(data, x.data, (size_t)(padded_item_size * x.length));
} else {
for (int64_t i = 0; i < x.length; i++)
- memcpy(data + i*padded_item_size, x.data + i*padded_item_size, (size_t)padded_item_size);
+ memcpy(data + i * padded_item_size, x.data + i * padded_item_size, (size_t)padded_item_size);
}
- void *dest = data + padded_item_size*x.length;
+ void *dest = data + padded_item_size * x.length;
if (y.stride == padded_item_size) {
- memcpy(dest, y.data, (size_t)(padded_item_size*y.length));
+ memcpy(dest, y.data, (size_t)(padded_item_size * y.length));
} else {
for (int64_t i = 0; i < y.length; i++)
- memcpy(dest + i*padded_item_size, y.data + i*y.stride, (size_t)padded_item_size);
+ memcpy(dest + i * padded_item_size, y.data + i * y.stride, (size_t)padded_item_size);
}
return (List_t){
- .data=data,
- .length=x.length + y.length,
- .stride=padded_item_size,
- .atomic=x.atomic,
+ .data = data,
+ .length = x.length + y.length,
+ .stride = padded_item_size,
+ .atomic = x.atomic,
};
}
-public bool List$has(List_t list, void *item, const TypeInfo_t *type)
-{
+public
+bool List$has(List_t list, void *item, const TypeInfo_t *type) {
const TypeInfo_t *item_type = type->ListInfo.item;
for (int64_t i = 0; i < list.length; i++) {
- if (generic_equal(list.data + i*list.stride, item, item_type))
- return true;
+ if (generic_equal(list.data + i * list.stride, item, item_type)) return true;
}
return false;
}
-public void List$clear(List_t *list)
-{
- *list = (List_t){.data=0, .length=0};
-}
+public
+void List$clear(List_t *list) { *list = (List_t){.data = 0, .length = 0}; }
-public int32_t List$compare(const void *vx, const void *vy, const TypeInfo_t *type)
-{
- const List_t *x = (List_t*)vx, *y = (List_t*)vy;
+public
+int32_t List$compare(const void *vx, const void *vy, const TypeInfo_t *type) {
+ const List_t *x = (List_t *)vx, *y = (List_t *)vy;
// Early out for lists with the same data, e.g. two copies of the same list:
- if (x->data == y->data && x->stride == y->stride)
- return (x->length > y->length) - (x->length < y->length);
+ if (x->data == y->data && x->stride == y->stride) return (x->length > y->length) - (x->length < y->length);
const TypeInfo_t *item = type->ListInfo.item;
if (item->tag == PointerInfo || !item->metamethods.compare) { // data comparison
@@ -599,128 +566,120 @@ public int32_t List$compare(const void *vx, const void *vy, const TypeInfo_t *ty
if (type->ListInfo.item->align > 1 && item_padded_size % type->ListInfo.item->align)
errx(1, "Item size is not padded!");
- if ((int64_t)x->stride == item_padded_size && (int64_t)y->stride == item_padded_size && item->size == item_padded_size) {
- int32_t cmp = (int32_t)memcmp(x->data, y->data, (size_t)(MIN(x->length, y->length)*item_padded_size));
+ if ((int64_t)x->stride == item_padded_size && (int64_t)y->stride == item_padded_size
+ && item->size == item_padded_size) {
+ int32_t cmp = (int32_t)memcmp(x->data, y->data, (size_t)(MIN(x->length, y->length) * item_padded_size));
if (cmp != 0) return cmp;
} else {
for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) {
- int32_t cmp = (int32_t)memcmp(x->data+ x->stride*i, y->data + y->stride*i, (size_t)(item->size));
+ int32_t cmp = (int32_t)memcmp(x->data + x->stride * i, y->data + y->stride * i, (size_t)(item->size));
if (cmp != 0) return cmp;
}
}
} else {
for (int32_t i = 0, len = MIN(x->length, y->length); i < len; i++) {
- int32_t cmp = generic_compare(x->data + x->stride*i, y->data + y->stride*i, item);
+ int32_t cmp = generic_compare(x->data + x->stride * i, y->data + y->stride * i, item);
if (cmp != 0) return cmp;
}
}
return (x->length > y->length) - (x->length < y->length);
}
-public bool List$equal(const void *x, const void *y, const TypeInfo_t *type)
-{
- return x == y || (((List_t*)x)->length == ((List_t*)y)->length && List$compare(x, y, type) == 0);
+public
+bool List$equal(const void *x, const void *y, const TypeInfo_t *type) {
+ return x == y || (((List_t *)x)->length == ((List_t *)y)->length && List$compare(x, y, type) == 0);
}
-public Text_t List$as_text(const void *obj, bool colorize, const TypeInfo_t *type)
-{
- List_t *list = (List_t*)obj;
- if (!list)
- return Text$concat(Text("["), generic_as_text(NULL, false, type->ListInfo.item), Text("]"));
+public
+Text_t List$as_text(const void *obj, bool colorize, const TypeInfo_t *type) {
+ List_t *list = (List_t *)obj;
+ if (!list) return Text$concat(Text("["), generic_as_text(NULL, false, type->ListInfo.item), Text("]"));
const TypeInfo_t *item_type = type->ListInfo.item;
Text_t text = Text("[");
for (int64_t i = 0; i < list->length; i++) {
- if (i > 0)
- text = Text$concat(text, Text(", "));
- Text_t item_text = generic_as_text(list->data + i*list->stride, colorize, item_type);
+ if (i > 0) text = Text$concat(text, Text(", "));
+ Text_t item_text = generic_as_text(list->data + i * list->stride, colorize, item_type);
text = Text$concat(text, item_text);
}
text = Text$concat(text, Text("]"));
return text;
}
-public uint64_t List$hash(const void *obj, const TypeInfo_t *type)
-{
- const List_t *list = (List_t*)obj;
+public
+uint64_t List$hash(const void *obj, const TypeInfo_t *type) {
+ const List_t *list = (List_t *)obj;
const TypeInfo_t *item = type->ListInfo.item;
siphash sh;
siphashinit(&sh, sizeof(uint64_t[list->length]));
- if (item->tag == PointerInfo || (!item->metamethods.hash && item->size == sizeof(void*))) { // Raw data hash
+ if (item->tag == PointerInfo || (!item->metamethods.hash && item->size == sizeof(void *))) { // Raw data hash
for (int64_t i = 0; i < list->length; i++)
- siphashadd64bits(&sh, (uint64_t)(list->data + i*list->stride));
+ siphashadd64bits(&sh, (uint64_t)(list->data + i * list->stride));
} else {
for (int64_t i = 0; i < list->length; i++) {
- uint64_t item_hash = generic_hash(list->data + i*list->stride, item);
+ uint64_t item_hash = generic_hash(list->data + i * list->stride, item);
siphashadd64bits(&sh, item_hash);
}
}
return siphashfinish_last_part(&sh, 0);
}
-static void siftdown(List_t *heap, int64_t startpos, int64_t pos, Closure_t comparison, int64_t padded_item_size)
-{
+static void siftdown(List_t *heap, int64_t startpos, int64_t pos, Closure_t comparison, int64_t padded_item_size) {
assert(pos > 0 && pos < heap->length);
char newitem[padded_item_size];
- memcpy(newitem, heap->data + heap->stride*pos, (size_t)(padded_item_size));
+ memcpy(newitem, heap->data + heap->stride * pos, (size_t)(padded_item_size));
while (pos > startpos) {
int64_t parentpos = (pos - 1) >> 1;
- typedef int32_t (*cmp_fn_t)(void*, void*, void*);
- int32_t cmp = ((cmp_fn_t)comparison.fn)(newitem, heap->data + heap->stride*parentpos, comparison.userdata);
- if (cmp >= 0)
- break;
+ typedef int32_t (*cmp_fn_t)(void *, void *, void *);
+ int32_t cmp = ((cmp_fn_t)comparison.fn)(newitem, heap->data + heap->stride * parentpos, comparison.userdata);
+ if (cmp >= 0) break;
- memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*parentpos, (size_t)(padded_item_size));
+ memcpy(heap->data + heap->stride * pos, heap->data + heap->stride * parentpos, (size_t)(padded_item_size));
pos = parentpos;
}
- memcpy(heap->data + heap->stride*pos, newitem, (size_t)(padded_item_size));
+ memcpy(heap->data + heap->stride * pos, newitem, (size_t)(padded_item_size));
}
-static void siftup(List_t *heap, int64_t pos, Closure_t comparison, int64_t padded_item_size)
-{
+static void siftup(List_t *heap, int64_t pos, Closure_t comparison, int64_t padded_item_size) {
int64_t endpos = heap->length;
int64_t startpos = pos;
assert(pos < endpos);
char old_top[padded_item_size];
- memcpy(old_top, heap->data + heap->stride*pos, (size_t)(padded_item_size));
+ memcpy(old_top, heap->data + heap->stride * pos, (size_t)(padded_item_size));
// Bubble up the smallest leaf node
int64_t limit = endpos >> 1;
while (pos < limit) {
- int64_t childpos = 2*pos + 1; // Smaller of the two child nodes
+ int64_t childpos = 2 * pos + 1; // Smaller of the two child nodes
if (childpos + 1 < endpos) {
- typedef int32_t (*cmp_fn_t)(void*, void*, void*);
- int32_t cmp = ((cmp_fn_t)comparison.fn)(
- heap->data + heap->stride*childpos,
- heap->data + heap->stride*(childpos + 1),
- comparison.userdata);
+ typedef int32_t (*cmp_fn_t)(void *, void *, void *);
+ int32_t cmp = ((cmp_fn_t)comparison.fn)(heap->data + heap->stride * childpos,
+ heap->data + heap->stride * (childpos + 1), comparison.userdata);
childpos += (cmp >= 0);
}
// Move the child node up:
- memcpy(heap->data + heap->stride*pos, heap->data + heap->stride*childpos, (size_t)(padded_item_size));
+ memcpy(heap->data + heap->stride * pos, heap->data + heap->stride * childpos, (size_t)(padded_item_size));
pos = childpos;
}
- memcpy(heap->data + heap->stride*pos, old_top, (size_t)(padded_item_size));
+ memcpy(heap->data + heap->stride * pos, old_top, (size_t)(padded_item_size));
// Shift the node's parents down:
siftdown(heap, startpos, pos, comparison, padded_item_size);
}
-public void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size)
-{
+public
+void List$heap_push(List_t *heap, const void *item, Closure_t comparison, int64_t padded_item_size) {
List$insert(heap, item, I(0), padded_item_size);
if (heap->length > 1) {
- if (heap->data_refcount != 0)
- List$compact(heap, padded_item_size);
- siftdown(heap, 0, heap->length-1, comparison, padded_item_size);
+ if (heap->data_refcount != 0) List$compact(heap, padded_item_size);
+ siftdown(heap, 0, heap->length - 1, comparison, padded_item_size);
}
}
-public void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size)
-{
- if (heap->length == 0)
- fail("Attempt to pop from an empty list");
+public
+void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_item_size) {
+ if (heap->length == 0) fail("Attempt to pop from an empty list");
if (heap->length == 1) {
*heap = (List_t){};
@@ -728,96 +687,90 @@ public void List$heap_pop(List_t *heap, Closure_t comparison, int64_t padded_ite
heap->data += heap->stride;
--heap->length;
} else {
- if (heap->data_refcount != 0)
- List$compact(heap, padded_item_size);
- memcpy(heap->data, heap->data + heap->stride*(heap->length-1), (size_t)(padded_item_size));
+ if (heap->data_refcount != 0) List$compact(heap, padded_item_size);
+ memcpy(heap->data, heap->data + heap->stride * (heap->length - 1), (size_t)(padded_item_size));
--heap->length;
siftup(heap, 0, comparison, padded_item_size);
}
}
-public void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size)
-{
- if (heap->data_refcount != 0)
- List$compact(heap, padded_item_size);
+public
+void List$heapify(List_t *heap, Closure_t comparison, int64_t padded_item_size) {
+ if (heap->data_refcount != 0) List$compact(heap, padded_item_size);
// It's necessary to bump the refcount because the user's comparison
// function could do stuff that modifies the heap's data.
LIST_INCREF(*heap);
int64_t i, n = heap->length;
- for (i = (n >> 1) - 1 ; i >= 0 ; i--)
+ for (i = (n >> 1) - 1; i >= 0; i--)
siftup(heap, i, comparison, padded_item_size);
LIST_DECREF(*heap);
}
-public Int_t List$binary_search(List_t list, void *target, Closure_t comparison)
-{
- typedef int32_t (*cmp_fn_t)(void*, void*, void*);
- int64_t lo = 0, hi = list.length-1;
+public
+Int_t List$binary_search(List_t list, void *target, Closure_t comparison) {
+ typedef int32_t (*cmp_fn_t)(void *, void *, void *);
+ int64_t lo = 0, hi = list.length - 1;
while (lo <= hi) {
int64_t mid = (lo + hi) / 2;
- int32_t cmp = ((cmp_fn_t)comparison.fn)(
- list.data + list.stride*mid, target, comparison.userdata);
- if (cmp == 0)
- return I(mid+1);
- else if (cmp < 0)
- lo = mid + 1;
- else if (cmp > 0)
- hi = mid - 1;
+ int32_t cmp = ((cmp_fn_t)comparison.fn)(list.data + list.stride * mid, target, comparison.userdata);
+ if (cmp == 0) return I(mid + 1);
+ else if (cmp < 0) lo = mid + 1;
+ else if (cmp > 0) hi = mid - 1;
}
- return I(lo+1); // Return the index where the target would be inserted
+ return I(lo + 1); // Return the index where the target would be inserted
}
-public PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t *info)
-{
+public
+PUREFUNC bool List$is_none(const void *obj, const TypeInfo_t *info) {
(void)info;
- return ((List_t*)obj)->length < 0;
+ return ((List_t *)obj)->length < 0;
}
-public void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type)
-{
- List_t list = *(List_t*)obj;
+public
+void List$serialize(const void *obj, FILE *out, Table_t *pointers, const TypeInfo_t *type) {
+ List_t list = *(List_t *)obj;
int64_t len = list.length;
Int64$serialize(&len, out, pointers, &Int64$info);
serialize_fn_t item_serialize = type->ListInfo.item->metamethods.serialize;
if (item_serialize) {
for (int64_t i = 0; i < len; i++)
- item_serialize(list.data + i*list.stride, out, pointers, type->ListInfo.item);
+ item_serialize(list.data + i * list.stride, out, pointers, type->ListInfo.item);
} else if (list.stride == type->ListInfo.item->size) {
fwrite(list.data, (size_t)type->ListInfo.item->size, (size_t)len, out);
} else {
for (int64_t i = 0; i < len; i++)
- fwrite(list.data + i*list.stride, (size_t)type->ListInfo.item->size, 1, out);
+ fwrite(list.data + i * list.stride, (size_t)type->ListInfo.item->size, 1, out);
}
}
-public void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type)
-{
+public
+void List$deserialize(FILE *in, void *obj, List_t *pointers, const TypeInfo_t *type) {
int64_t len = -1;
Int64$deserialize(in, &len, pointers, &Int64$info);
int64_t padded_size = type->ListInfo.item->size;
if (type->ListInfo.item->align > 0 && padded_size % type->ListInfo.item->align > 0)
padded_size += type->ListInfo.item->align - (padded_size % type->ListInfo.item->align);
List_t list = {
- .length=len,
- .data=GC_MALLOC((size_t)(len*padded_size)),
- .stride=padded_size,
+ .length = len,
+ .data = GC_MALLOC((size_t)(len * padded_size)),
+ .stride = padded_size,
};
deserialize_fn_t item_deserialize = type->ListInfo.item->metamethods.deserialize;
if (item_deserialize) {
for (int64_t i = 0; i < len; i++)
- item_deserialize(in, list.data + i*list.stride, pointers, type->ListInfo.item);
+ item_deserialize(in, list.data + i * list.stride, pointers, type->ListInfo.item);
} else if (list.stride == type->ListInfo.item->size) {
if (fread(list.data, (size_t)type->ListInfo.item->size, (size_t)len, in) != (size_t)len)
fail("Not enough data in stream to deserialize");
} else {
size_t item_size = (size_t)type->ListInfo.item->size;
for (int64_t i = 0; i < len; i++) {
- if (fread(list.data + i*list.stride, item_size, 1, in) != 1)
+ if (fread(list.data + i * list.stride, item_size, 1, in) != 1)
fail("Not enough data in stream to deserialize");
}
}
- *(List_t*)obj = list;
+ *(List_t *)obj = list;
}
// vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0