<commit_before>#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <math.h>

#include <base/wbuf.h>
#include <base/mem.h>

#include "include/triangulate.h"

#define X 0
#define Y 1
#define XY 2

#define EPSILON 1e-8
#define MSB (1 << (CHAR_BIT - 1))

typedef unsigned triangle_indices[3];
typedef int eref;
typedef float const float2[XY];

struct edge
{
	float2 *data;
	eref next;
};

struct eset
{
	struct wbuf edges;
	size_t count;
};

struct line
{
	double a, b, c;
};

static inline eref mkref(eref e0, unsigned r) { return (e0 & ~0x3)|(r & 0x3); }
static inline eref rot(eref e) { return mkref(e, e + 1); }
static inline eref sym(eref e) { return mkref(e, e + 2); }
static inline eref invrot(eref e) { return mkref(e, e + 3); }

static inline eref onext(struct eset *set, eref e)
{
	assert(e >= 0);
	assert((size_t)e < wbuf_nmemb(&set->edges, sizeof(struct edge)));
	return ((struct edge *)set->edges.begin)[e].next;
}

static inline eref oprev(struct eset *set, eref e)
{
	return rot(onext(set, rot(e)));
}

static inline eref lnext(struct eset *set, eref e)
{
	return rot(onext(set, invrot(e)));
}

static inline eref lprev(struct eset *set, eref e)
{
	return sym(onext(set, e));
}

static inline eref rnext(struct eset *set, eref e)
{
	return invrot(onext(set, rot(e)));
}

static inline eref rprev(struct eset *set, eref e)
{
	return onext(set, sym(e));
}

static inline float2 **org(struct eset *set, eref e)
{
	return &((struct edge *)set->edges.begin)[e].data;
}

static inline float2 **dest(struct eset *set, eref e)
{
	return org(set, sym(e));
}

static void init_eset(struct eset *set)
{
	wbuf_init(&set->edges);
	set->count = 0;
}

static eref eset_max_edge(struct eset *set)
{
	return wbuf_nmemb(&set->edges, sizeof (struct edge[4]));
}

static void term_eset(struct eset *set)
{
	wbuf_term(&set->edges);
}

/* allocate *n* empty subdivisions (edges) and store references (eref) in the
   *n* following arguments */
static int make_edges(struct eset *set, size_t n, ...)
{
	struct edge *p;
	eref e0, *q;
	size_t i;
	va_list ap;

	p = wbuf_alloc(&set->edges, n * sizeof (struct edge[4]));
	set->count += n;
	if (!p) { return -1; }
	va_start(ap, n);
	for (i = 0; i < n; i++) {
		q = va_arg(ap, eref *);
		*q = e0 = p - (struct edge *)set->edges.begin;
		p[0].data = p[1].data = p[2].data = p[3].data = 0;
		p[0].next = mkref(e0, 0);
		p[1].next = mkref(e0, 3);
		p[2].next = mkref(e0, 2);
		p[3].next = mkref(e0, 1);
		p += 4;
	}
	va_end(ap);
	return 0;
}

static void splice(struct eset *set, eref a, eref b)
{
	eref alpha, beta, tmp;
	struct edge *edges;

	edges = set->edges.begin;
	alpha = rot(onext(set, a));
	beta = rot(onext(set, b));

	tmp = edges[a].next;
	edges[a].next = edges[b].next;
	edges[b].next = tmp;

	tmp = edges[alpha].next;
	edges[alpha].next = edges[beta].next;
	edges[beta].next = tmp;
}

/* connect the destination of `a` to the origin of `b` with the new edge `c` so
   that left(a) = left(b) = left(c) */
static void connect(struct eset *set, eref a, eref b, eref c)
{
	*org(set, c) = *dest(set, a);
	*dest(set, c) = *org(set, b);
	splice(set, c, lnext(set, a));
	splice(set, sym(c), b);
}

static void delete_edge(struct eset *set, eref e)
{
	/* TODO: free list */
	set->count--;
	splice(set, e, oprev(set, e));
	splice(set, sym(e), oprev(set, sym(e)));
}

/*
static void swap(struct eset *set, eref e)
{
	eref a = oprev(set, e);
	eref b = oprev(set, sym(e));
	splice(set, e, a);
	splice(set, sym(e), b);
	splice(set, e, lnext(set, a));
	splice(set, sym(e), lnext(b));
	*org(set, e) = *dest(set, a);
	*dest(set, e) = *dest(set, b);
}
*/

static double line_det(float2 a, float2 b, float2 c)
{
	/* The determinant D of the linear inequality specifies on which side
	   of line `b->c` that point `a` lies

		| X[a] Y[a] 1 |
		| X[b] Y[b] 1 | = D<commit_msg>Re-allocate edges from free list<commit_after>#include <stddef.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
#include <math.h>

#include <base/wbuf.h>
#include <base/mem.h>

#include "include/triangulate.h"

#define X 0
#define Y 1
#define XY 2

#define EPSILON 1e-8
#define MSB (1 << (CHAR_BIT - 1))

typedef unsigned triangle_indices[3];
typedef int eref;
typedef float const float2[XY];

struct edge
{
	float2 *data;
	eref next;
};

struct eset
{
	struct wbuf edges;
	eref free;
};

struct line
{
	double a, b, c;
};

static inline eref mkref(eref e0, unsigned r) { return (e0 & ~0x3)|(r & 0x3); }
static inline eref rot(eref e) { return mkref(e, e + 1); }
static inline eref sym(eref e) { return mkref(e, e + 2); }
static inline eref invrot(eref e) { return mkref(e, e + 3); }

static inline eref onext(struct eset *set, eref e)
{
	assert(e >= 0);
	assert((size_t)e < wbuf_nmemb(&set->edges, sizeof(struct edge)));
	return ((struct edge *)set->edges.begin)[e].next;
}

static inline eref oprev(struct eset *set, eref e)
{
	return rot(onext(set, rot(e)));
}

static inline eref lnext(struct eset *set, eref e)
{
	return rot(onext(set, invrot(e)));
}

static inline eref lprev(struct eset *set, eref e)
{
	return sym(onext(set, e));
}

static inline eref rnext(struct eset *set, eref e)
{
	return invrot(onext(set, rot(e)));
}

static inline eref rprev(struct eset *set, eref e)
{
	return onext(set, sym(e));
}

static inline float2 **org(struct eset *set, eref e)
{
	return &((struct edge *)set->edges.begin)[e].data;
}

static inline float2 **dest(struct eset *set, eref e)
{
	return org(set, sym(e));
}

static void init_eset(struct eset *set)
{
	wbuf_init(&set->edges);
	set->free = -1;
}

static eref eset_max_edge(struct eset *set)
{
	return wbuf_nmemb(&set->edges, sizeof (struct edge[4]));
}

static void term_eset(struct eset *set)
{
	wbuf_term(&set->edges);
}

static void init_quad_edge(struct edge *qe, eref e0)
{
	qe[0].next = mkref(e0, 0);
	qe[1].next = mkref(e0, 3);
	qe[2].next = mkref(e0, 2);
	qe[3].next = mkref(e0, 1);
}

/* allocate *n* empty subdivisions (edges) and store references (eref) in the
   *n* following arguments */
static int make_edges(struct eset *set, size_t n, ...)
{
	struct edge *alloc, *p, *edges;
	eref e0;
	size_t i, j, nfree;
	va_list ap;

	/* look in free list first */
	e0 = set->free;
	edges = set->edges.begin;
	nfree = 0;
	while (e0 >= 0 && nfree < n) {
		e0 = edges[e0].next;
		nfree++;
	}
	/* allocate the rest */
	alloc = wbuf_alloc(&set->edges, (n - nfree) * sizeof (struct edge[4]));
	if (!alloc) { return -1; }
	edges = set->edges.begin;

	va_start(ap, n);
	for (i = 0, j = 0; i < n; i++) {
		if (j < nfree) {
			e0 = set->free;
			set->free = edges[e0].next;
			p = edges + e0;
			j++;
		} else {
			p = alloc + 4*(i - j);
			e0 = p - edges;
		}
		*va_arg(ap, eref *) = e0;
		p[0].data = p[1].data = p[2].data = p[3].data = 0;
		init_quad_edge(p, e0);
	}
	va_end(ap);
	return 0;
}

static void splice(struct eset *set, eref a, eref b)
{
	eref alpha, beta, tmp;
	struct edge *edges;

	edges = set->edges.begin;
	alpha = rot(onext(set, a));
	beta = rot(onext(set, b));

	tmp = edges[a].next;
	edges[a].next = edges[b].next;
	edges[b].next = tmp;

	tmp = edges[alpha].next;
	edges[alpha].next = edges[beta].next;
	edges[beta].next = tmp;
}

/* connect the destination of `a` to the origin of `b` with the new edge `c` so
   that left(a) = left(b) = left(c) */
static void connect(struct eset *set, eref a, eref b, eref c)
{
	*org(set, c) = *dest(set, a);
	*dest(set, c) = *org(set, b);
	splice(set, c, lnext(set, a));
	splice(set, sym(c), b);
}

static void delete_edge(struct eset *set, eref e)
{
	splice(set, e, oprev(set, e));
	splice(set, sym(e), oprev(set, sym(e)));

	/* add to free list */
	((struct edge *)set->edges.begin)[e & ~0x3].next = set->free;
	set->free = e & ~0x3;
}

static double line_det(float2 a, float2 b, float2 c)
{
	/* The determinant D of the linear inequality specifies on which side
	   of line `b->c` that point `a` lies

		| X[a] Y[a] 1 |
		| X[b] Y[b] 1 | = D
{'fraction_non_alphanumeric': 0.18019359642591215, 'fraction_numerical': 0.01526433358153388, 'mean_word_length': 3.9020681265206814, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 59, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7281790', 'n_tokens_mistral': 3536, 'n_tokens_neox': 3413, 'n_words': 983}