146 lines
3.4 KiB
C
146 lines
3.4 KiB
C
/* copyright (c) 2022 - 2026 grunfink et al. / MIT license */
|
|
|
|
#ifndef _XS_LIST_TOOLS_H
|
|
|
|
#define _XS_LIST_TOOLS_H
|
|
|
|
xs_list *xs_list_insert_sorted(xs_list *list, const xs_val *nv);
|
|
xs_val **xs_list_to_array(const xs_list *l, int *len);
|
|
int xs_list_sort_cmp(const void *p1, const void *p2);
|
|
int xs_list_sort_inv_cmp(const void *p1, const void *p2);
|
|
int xs_list_sort_dict_cmp(const char *field, const void *p1, const void *p2);
|
|
xs_list *xs_list_sort(const xs_list *l, int (*cmp)(const void *, const void *));
|
|
xs_list *xs_list_shuffle(const xs_list *l);
|
|
|
|
#ifdef XS_IMPLEMENTATION
|
|
|
|
#include "xs_random.h"
|
|
|
|
xs_list *xs_list_insert_sorted(xs_list *list, const xs_val *nv)
|
|
/* inserts a string in the list in its ordered position */
|
|
{
|
|
XS_ASSERT_TYPE(list, XSTYPE_LIST);
|
|
|
|
int offset = xs_size(list);
|
|
|
|
const xs_val *v;
|
|
xs_list_foreach(list, v) {
|
|
/* if this element is greater or equal, insert here */
|
|
if (xs_cmp(v, nv) >= 0) {
|
|
offset = v - list;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return _xs_list_write_litem(list, offset - 1, nv, xs_size(nv));
|
|
}
|
|
|
|
|
|
xs_val **xs_list_to_array(const xs_list *l, int *len)
|
|
/* converts a list to an array of values */
|
|
/* must be freed after use */
|
|
{
|
|
*len = xs_list_len(l);
|
|
xs_val **a = xs_realloc(NULL, *len * sizeof(xs_val *));
|
|
const xs_val *v;
|
|
int n = 0;
|
|
|
|
xs_list_foreach(l, v)
|
|
a[n++] = (xs_val *)v;
|
|
|
|
return a;
|
|
}
|
|
|
|
|
|
int xs_list_sort_cmp(const void *p1, const void *p2)
|
|
/* default list sorting function */
|
|
{
|
|
const xs_val *v1 = *(xs_val **)p1;
|
|
const xs_val *v2 = *(xs_val **)p2;
|
|
|
|
return xs_cmp(v1, v2);
|
|
}
|
|
|
|
|
|
int xs_list_sort_inv_cmp(const void *p1, const void *p2)
|
|
/* default list inverse sorting function */
|
|
{
|
|
const xs_val *v1 = *(xs_val **)p1;
|
|
const xs_val *v2 = *(xs_val **)p2;
|
|
|
|
return xs_cmp(v2, v1);
|
|
}
|
|
|
|
|
|
int xs_list_sort_dict_cmp(const char *field, const void *p1, const void *p2)
|
|
/* compare sorting function for a field an array of dicts */
|
|
{
|
|
const xs_dict *d1 = *(xs_val **)p1;
|
|
const xs_dict *d2 = *(xs_val **)p2;
|
|
|
|
if (xs_type(d1) != XSTYPE_DICT || xs_type(d2) != XSTYPE_DICT)
|
|
return 0;
|
|
|
|
return xs_cmp(xs_dict_get_def(d1, field, ""),
|
|
xs_dict_get_def(d2, field, ""));
|
|
}
|
|
|
|
|
|
xs_list *xs_list_sort(const xs_list *l, int (*cmp)(const void *, const void *))
|
|
/* returns a sorted copy of l. cmp can be null for standard sorting */
|
|
{
|
|
int sz;
|
|
xs_val **a = xs_list_to_array(l, &sz);
|
|
xs_list *nl = xs_dup(l);
|
|
char *p = nl + 1 + _XS_TYPE_SIZE;
|
|
|
|
/* sort the array */
|
|
qsort(a, sz, sizeof(xs_val *), cmp ? cmp : xs_list_sort_cmp);
|
|
|
|
/* transfer the sorted list over the copy */
|
|
for (int n = 0; n < sz; n++) {
|
|
/* get the litem */
|
|
const char *e = a[n] - 1;
|
|
int z = xs_size(e);
|
|
|
|
memcpy(p, e, z);
|
|
p += z;
|
|
}
|
|
|
|
xs_free(a);
|
|
|
|
return nl;
|
|
}
|
|
|
|
|
|
xs_list *xs_list_shuffle(const xs_list *l)
|
|
/* returns a shuffled list */
|
|
{
|
|
int sz;
|
|
xs_val **a = xs_list_to_array(l, &sz);
|
|
xs_list *nl = xs_list_new();
|
|
unsigned int seed = 0;
|
|
|
|
xs_rnd_buf(&seed, sizeof(seed));
|
|
|
|
/* shuffle */
|
|
for (int n = sz - 1; n > 0; n--) {
|
|
int m = xs_rnd_int32_d(&seed) % n;
|
|
void *p = a[n];
|
|
a[n] = a[m];
|
|
a[m] = p;
|
|
}
|
|
|
|
for (int n = 0; n < sz; n++)
|
|
nl = xs_list_append(nl, a[n]);
|
|
|
|
xs_free(a);
|
|
|
|
return nl;
|
|
}
|
|
|
|
|
|
#endif /* XS_IMPLEMENTATION */
|
|
|
|
#endif /* XS_LIST_TOOLS_H */
|