<commit_before>/*
 * $Id$
 *
 * Implementation of a binary heap API
 *
 * We use a malloc(3)/realloc(3) array to store the pointers using the
 * classical FORTRAN strategy.
 *
 * XXX: the array is not scaled back when items are deleted.
 */

#include <assert.h>
#include <unistd.h>
#include <stdlib.h>

#include "binary_heap.h"

/* Private definitions -----------------------------------------------*/

#define MIN_LENGTH		16

#define ROOT_IDX		1

struct binheap {
	unsigned		magic;
#define BINHEAP_MAGIC		0xf581581aU	/* from /dev/random */
	void			*priv;
	binheap_cmp_t		*cmp;
	binheap_update_t	*update;
	void			**array;
	unsigned		length;
	unsigned		next;
	unsigned		granularity;
};

#define PARENT(u)	((u) / 2)
#define CHILD(u,n)	((u) * 2 + (n))

/* Implementation ----------------------------------------------------*/

static void
binheap_update(struct binheap *bh, unsigned u)
{
	assert(bh->magic == BINHEAP_MAGIC);
	assert(u < bh->next);
	assert(bh->array[u] != NULL);
	if (bh->update == NULL)
		return;
	bh->update(bh->priv, bh->array[u], u);
}

struct binheap *
binheap_new(void *priv, binheap_cmp_t *cmp_f, binheap_update_t *update_f)
{
	struct binheap *bh;

	bh = calloc(sizeof *bh, 1);
	if (bh == NULL)
		return (bh);
	bh->priv = priv;
	bh->cmp = cmp_f;
	bh->update = update_f;
	bh->next = ROOT_IDX;
	bh->length = MIN_LENGTH;
	bh->array = calloc(sizeof *bh->array, bh->length);
	assert(bh->array != NULL);
	bh->granularity = getpagesize() / sizeof *bh->array;
	bh->magic = BINHEAP_MAGIC;
	return (bh);
}

static void
binhead_swap(struct binheap *bh, unsigned u, unsigned v)
{
	void *p;

	assert(bh->magic == BINHEAP_MAGIC);
	assert(u < bh->next);
	assert(v < bh->next);
	p = bh->array[u];
	bh->array[u] = bh->array[v];
	bh->array[v] = p;
	binheap_update(bh, u);
	binheap_update(bh, v);
}

static unsigned
binheap_trickleup(struct binheap *bh, unsigned u)
{
	unsigned v;

	assert(bh->magic == BINHEAP_MAGIC);
	while (u > ROOT_IDX) {
		v = PARENT(u);
		if (bh->cmp(bh->priv, bh->array[u], bh->array[v])) {
			binhead_swap(bh, u, v);
			u = v;
		} else
			break;
	}
	return (u);
}

static void
binheap_trickledown(struct binheap *bh, unsigned u)
{
	unsigned v1, v2;

	assert(bh->magic == BINHEAP_MAGIC);
	while (1) {
		v1 = CHILD(u, 0);
		v2 = CHILD(u, 1);
		if (v1 >= bh->next)
			return;
		if (v2 >= bh->next) {
			if (!bh->cmp(bh->priv, bh->array[u], bh->array[v1]))
				binhead_swap(bh, u, v1);
			return;
		}
		if (bh->cmp(bh->priv, bh->array[v1], bh->array[v2])) {
			if (!bh->cmp(bh->priv, bh->array[u], bh->array[v1])) {
				binhead_swap(bh, u, v1);
				u = v1;
				continue;
			}
		} else {
			if (!bh->cmp(bh->priv, bh->array[u], bh->array[v2])) {
				binhead_swap(bh, u, v2);
				u = v2;
				continue;
			}
		}
		return;
	}
}

void
binheap_insert(struct binheap *bh, void *p)
{
	unsigned u;

	assert(bh != NULL);
	assert(bh->magic == BINHEAP_MAGIC);
	assert(bh->length >= bh->next);
	if (bh->length == bh->next) {
		if (bh->length >= bh->granularity * 32)
			bh->length += bh->granularity * 32;
		else if (bh->length > bh->granularity)
			bh->length += bh->granularity;
		else
			bh->length += bh->length;
		bh->array = realloc(bh->array, bh->length * sizeof *bh->array);
		assert(bh->array != NULL);
	}
	u = bh->next++;
	bh->array[u] = p;
	binheap_update(bh, u);
	binheap_trickleup(bh, u);
}

void *
binheap_root(struct binheap *bh)
{

	assert(bh != NULL);
	assert(bh->magic == BINHEAP_MAGIC);
	if(bh->next == ROOT_IDX)
		return (NULL);
	return (bh->array[ROOT_IDX]);
}

void
binheap_delete(struct binheap *bh, unsigned idx)
{

	assert(bh != NULL);
	assert(bh->magic == BINHEAP_MAGIC);
	assert(bh->next > ROOT_IDX);
	assert(idx < bh->next);
	assert(idx > 0);
	bh->update(bh->priv, bh->array[idx], 0);
	if (idx == --bh->next)
		return;
	bh->array[idx] = bh->array[bh->next];
	binheap_update(bh, idx);
	idx = binheap_trickleup(bh, idx);
	binheap_trickledown(bh, idx);
	/* XXX: free part of array ? */
}


#ifdef TEST_DRIVER
/* Test driver -------------------------------------------------------*/

#include <stdio.h>

#if 0

static int
cmp(void *priv, void *a, void *b)
{

	return (*(unsigned *)a < *(unsigned *)b);
}

void
update(void *priv, void *a, unsigned u)
{<commit_msg>More defensive coding.<commit_after>/*
 * $Id$
 *
 * Implementation of a binary heap API
 *
 * We use a malloc(3)/realloc(3) array to store the pointers using the
 * classical FORTRAN strategy.
 *
 * XXX: the array is not scaled back when items are deleted.
 */

#include <assert.h>
#include <unistd.h>
#include <stdlib.h>

#include "binary_heap.h"

/* Private definitions -----------------------------------------------*/

#define MIN_LENGTH		16

#define ROOT_IDX		1

struct binheap {
	unsigned		magic;
#define BINHEAP_MAGIC		0xf581581aU	/* from /dev/random */
	void			*priv;
	binheap_cmp_t		*cmp;
	binheap_update_t	*update;
	void			**array;
	unsigned		length;
	unsigned		next;
	unsigned		granularity;
};

#define PARENT(u)	((u) / 2)
#define CHILD(u,n)	((u) * 2 + (n))

/* Implementation ----------------------------------------------------*/

static void
binheap_update(struct binheap *bh, unsigned u)
{
	assert(bh->magic == BINHEAP_MAGIC);
	assert(u < bh->next);
	assert(bh->array[u] != NULL);
	if (bh->update == NULL)
		return;
	bh->update(bh->priv, bh->array[u], u);
}

struct binheap *
binheap_new(void *priv, binheap_cmp_t *cmp_f, binheap_update_t *update_f)
{
	struct binheap *bh;

	bh = calloc(sizeof *bh, 1);
	if (bh == NULL)
		return (bh);
	bh->priv = priv;
	bh->cmp = cmp_f;
	bh->update = update_f;
	bh->next = ROOT_IDX;
	bh->length = MIN_LENGTH;
	bh->array = calloc(sizeof *bh->array, bh->length);
	assert(bh->array != NULL);
	bh->granularity = getpagesize() / sizeof *bh->array;
	bh->magic = BINHEAP_MAGIC;
	return (bh);
}

static void
binhead_swap(struct binheap *bh, unsigned u, unsigned v)
{
	void *p;

	assert(bh->magic == BINHEAP_MAGIC);
	assert(u < bh->next);
	assert(v < bh->next);
	p = bh->array[u];
	bh->array[u] = bh->array[v];
	bh->array[v] = p;
	binheap_update(bh, u);
	binheap_update(bh, v);
}

static unsigned
binheap_trickleup(struct binheap *bh, unsigned u)
{
	unsigned v;

	assert(bh->magic == BINHEAP_MAGIC);
	while (u > ROOT_IDX) {
		v = PARENT(u);
		if (bh->cmp(bh->priv, bh->array[u], bh->array[v])) {
			binhead_swap(bh, u, v);
			u = v;
		} else
			break;
	}
	return (u);
}

static void
binheap_trickledown(struct binheap *bh, unsigned u)
{
	unsigned v1, v2;

	assert(bh->magic == BINHEAP_MAGIC);
	while (1) {
		v1 = CHILD(u, 0);
		v2 = CHILD(u, 1);
		if (v1 >= bh->next)
			return;
		if (v2 >= bh->next) {
			if (!bh->cmp(bh->priv, bh->array[u], bh->array[v1]))
				binhead_swap(bh, u, v1);
			return;
		}
		if (bh->cmp(bh->priv, bh->array[v1], bh->array[v2])) {
			if (!bh->cmp(bh->priv, bh->array[u], bh->array[v1])) {
				binhead_swap(bh, u, v1);
				u = v1;
				continue;
			}
		} else {
			if (!bh->cmp(bh->priv, bh->array[u], bh->array[v2])) {
				binhead_swap(bh, u, v2);
				u = v2;
				continue;
			}
		}
		return;
	}
}

void
binheap_insert(struct binheap *bh, void *p)
{
	unsigned u;

	assert(bh != NULL);
	assert(bh->magic == BINHEAP_MAGIC);
	assert(bh->length >= bh->next);
	if (bh->length == bh->next) {
		if (bh->length >= bh->granularity * 32)
			bh->length += bh->granularity * 32;
		else if (bh->length > bh->granularity)
			bh->length += bh->granularity;
		else
			bh->length += bh->length;
		bh->array = realloc(bh->array, bh->length * sizeof *bh->array);
		assert(bh->array != NULL);
	}
	u = bh->next++;
	bh->array[u] = p;
	binheap_update(bh, u);
	binheap_trickleup(bh, u);
}

void *
binheap_root(struct binheap *bh)
{

	assert(bh != NULL);
	assert(bh->magic == BINHEAP_MAGIC);
	if(bh->next == ROOT_IDX)
		return (NULL);
	return (bh->array[ROOT_IDX]);
}

void
binheap_delete(struct binheap *bh, unsigned idx)
{

	assert(bh != NULL);
	assert(bh->magic == BINHEAP_MAGIC);
	assert(bh->next > ROOT_IDX);
	assert(idx < bh->next);
	assert(idx > 0);
	assert(bh->array[idx] != NULL);
	bh->update(bh->priv, bh->array[idx], 0);
	if (idx == --bh->next) { 
		bh->array[bh->next] = NULL;
		return;
	}
	bh->array[idx] = bh->array[bh->next];
	bh->array[bh->next] = NULL;
	binheap_update(bh, idx);
	idx = binheap_trickleup(bh, idx);
	binheap_trickledown(bh, idx);
	/* XXX: free part of array ? */
}


#ifdef TEST_DRIVER
/* Test driver -------------------------------------------------------*/

#include <stdio.h>

#if 0

static int
cmp(void *priv, void *a, void *b)
{

	return (*(unsigned *)a < *(unsigned *)b);
}

void
update(void *priv, void *a, unsigned u)
{
{'fraction_non_alphanumeric': 0.21908459818802212, 'fraction_numerical': 0.009648193905165314, 'mean_word_length': 3.1544477028347995, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 202, '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': '4011899', 'n_tokens_mistral': 3762, 'n_tokens_neox': 3521, 'n_words': 788}