pheap_test_dijkstra.c

#define _POSIX_C_SOURCE 200809L//getline
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include "pheap.h"
#include "sla.h"

typedef struct{
	uint64_t distance;
	size_t i, j;
} graph_node;

static int cmp_graph_nodes(const void *data, const void *_a, const void *_b){
	uint64_t a = ((const graph_node*)_a)->distance;
	uint64_t b = ((const graph_node*)_b)->distance;
	if(a < b){
		return -1;
	}else if(a > b){
		return +1;
	}
	return 0;
}

pheap_ft dijkstra_ft = {
	.size=sizeof(graph_node),
	.cmp=cmp_graph_nodes,
	.alloc=(void*(*)(void*))sla_alloc,
	.free=(void(*)(void*, void*))sla_free
};

static uint64_t (*read_graph(size_t *width, size_t *height))[2]{
	FILE *graph_file = fopen("matrix.txt", "r");
	if(!graph_file){
		printf("\e[1;31mERROR: Could not open \"matrix.txt\".\e[0m\n");
		return NULL;
	}
	uint64_t (*matrix)[2] = NULL, (*tmp)[2];
	char *line = NULL;
	size_t line_cap = 0, matrix_cap = 0;
	ssize_t line_len;
	*width = *height = 0;
	for(size_t i = 0, j; (line_len = getline(&line, &line_cap, graph_file)) > 1; ++i){
		if(!matrix_cap){
			matrix_cap = line_len/2;
			if(!(matrix = malloc(matrix_cap*2*sizeof(uint64_t)))){
				printf("\e[1;31mERROR: Could not allocate memory for matrix.\e[0m\n");
				fclose(graph_file);
				return NULL;
			}
		}
		++*height;
		const char *curr = line;
		uint64_t x;
		int set_width = !*width;
		if(!set_width && matrix_cap < *width * *height){
			tmp = realloc(matrix, matrix_cap*4*sizeof(uint64_t));
			if(!tmp){
				printf("\e[1;31mERROR: Could not allocate memory for matrix.\e[0m\n");
				free(matrix);
				fclose(graph_file);
				return NULL;
			}
			matrix = tmp;
			matrix_cap *= 2;
		}
		int scn_len;
		for(j = 0; *curr && *curr != '\n' && sscanf(curr, "%"SCNu64"%*[,\n]%n", &x, &scn_len); ++j){
			curr += scn_len;
			if(set_width){
				++*width;
			}else if(j == *width){
				printf("\e[1;31mERROR: Matrix row wider than %"PRIu64".\e[0m\n", *width);
				free(matrix);
				fclose(graph_file);
				return NULL;
			}
			matrix[j + i * *width][0] = x;
			matrix[j + i * *width][1] = UINT64_MAX;
		}
		if(j != *width){
			if(!j){
				--height;
			}else{
				printf("\e[1;31mERROR: Matrix row shorter than %"PRIu64".\e[0m\n", *width);
				free(matrix);
				fclose(graph_file);
				return NULL;
			}
		}
	}
	fclose(graph_file);
	free(line);
	tmp = realloc(matrix, *width * *height * 2*sizeof(uint64_t));
	return tmp ? tmp : matrix;
}

int main(void){
	size_t width, height;
	uint64_t (*_matrix)[2] = read_graph(&width, &height), (*matrix)[width][2] = (uint64_t(*)[width][2])_matrix;
	if(!matrix){
		return 1;
	}
	printf("Matrix is %zux%zu\n", width, height);
	if(!(dijkstra_ft.data = sla_new(sizeof(pheap_node) + sizeof(graph_node), 8*(width + height)))){
		printf("\e[1;31mERROR: Could not create slab allocator.\e[0m\n");
		free(matrix);
		return 1;
	}
	matrix[0][0][1] = matrix[0][0][0];
	pheap_node *fringe = pheap_new(&(graph_node){.distance=matrix[0][0][1],.i=0,.j=0}, NULL, NULL, &dijkstra_ft), *cur;
	while(1){
		cur = pheap_pop(&fringe, &dijkstra_ft);
		graph_node *n = PHEAP_DATA(graph_node*, cur);
		size_t i = n->i, j = n->j;
		uint64_t distance = n->distance;
		if(distance > matrix[j][i][1]){
			pheap_delete(cur, &dijkstra_ft);
			continue;
		}
		if(i == width - 1 && j == height - 1){
			printf("%"PRIu64"\n", distance);
			pheap_delete(cur, &dijkstra_ft);
			break;
		}
		if(i){
			if(distance + matrix[j][i - 1][0] < matrix[j][i - 1][1]){
				fringe = pheap_push(fringe, &(graph_node){.distance=matrix[j][i - 1][1]=distance + matrix[j][i - 1][0], .i=i - 1, .j=j}, &dijkstra_ft);
			}
		}
		if(j){
			if(distance + matrix[j - 1][i][0] < matrix[j - 1][i][1]){
				fringe = pheap_push(fringe, &(graph_node){.distance=matrix[j - 1][i][1]=distance + matrix[j - 1][i][0], .i=i, .j=j - 1}, &dijkstra_ft);
			}
		}
		if(i < width - 1){
			if(distance + matrix[j][i + 1][0] < matrix[j][i + 1][1]){
				fringe = pheap_push(fringe, &(graph_node){.distance=matrix[j][i + 1][1]=distance + matrix[j][i + 1][0], .i=i + 1, .j=j}, &dijkstra_ft);
			}
		}
		if(j < height - 1){
			if(distance + matrix[j + 1][i][0] < matrix[j + 1][i][1]){
				fringe = pheap_push(fringe, &(graph_node){.distance=matrix[j + 1][i][1]=distance + matrix[j + 1][i][0], .i=i, .j=j + 1}, &dijkstra_ft);
			}
		}
		pheap_delete(cur, &dijkstra_ft);
	}
	free(matrix);
	pheap_delete(fringe, &dijkstra_ft);
	sla_delete(dijkstra_ft.data);
}

pheap_test_primes.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include "pheap.h"
#include "sla.h"

typedef struct{
	uint64_t multiple, prime;
} generator;

int cmp_generators(const void *data, const void *_a, const void *_b){
	uint64_t a = ((const generator*)_a)->multiple, b = ((const generator*)_b)->multiple;
	if(a < b){
		return -1;
	}else if(a > b){
		return +1;
	}
	return 0;
}

pheap_ft generator_ft = {
	.size=sizeof(generator),
	.cmp=cmp_generators,
	.alloc=(void*(*)(void*))sla_alloc,
	.free=(void(*)(void*,void*))sla_free
};

uint64_t next_prime(pheap_node **generators, uint64_t *n){
	while(1){
		generator *g = PHEAP_DATA(generator*, *generators);
		if(*n >= g->multiple){
			if(*n == g->multiple){
				*n += 2;
			}
			g->multiple += g->prime;
			pheap_node *t = pheap_pop(generators, &generator_ft);
			*generators = pheap_meld(*generators, t, &generator_ft);
		}else{
			*generators = pheap_push(*generators, &(generator){.multiple=*n**n, .prime=*n}, &generator_ft);
			*n += 2;
			return *n - 2;
		}
	}
}

int main(void){
	if(!(generator_ft.data = sla_new(sizeof(pheap_node) + sizeof(generator), 64))){
		printf("\e[1;31mERROR: Could not create slab allocator.\e[0m\n");
		return 1;
	}
	pheap_node *generators = pheap_new(&(generator){.multiple=4, .prime=2}, NULL, NULL, &generator_ft);
	for(uint64_t p = 2, n = 3; p < 100; p = next_prime(&generators, &n)){
		printf("%"PRIu64",", p);
	}
	fputc('\n', stdout);
	pheap_delete(generators, &generator_ft);
	sla_delete(generator_ft.data);
}

sla.c

#include <stdlib.h>
#include <string.h>
#include "sla.h"

slab_allocator *sla_new(size_t elem_size, size_t elems_cap){
	slab_allocator *ret = malloc(1*sizeof(slab_allocator));
	if(!ret){
		return NULL;
	}
	*ret = (slab_allocator){NULL, NULL, 1, elems_cap, elems_cap, elems_cap, elem_size};
	void *slab = malloc(elems_cap*elem_size);//start the allocator with one block of length elems_cap
	if(!slab){
		free(ret);
		return NULL;
	}else if(!(ret->elems = malloc(elems_cap*sizeof(void*)))){//create a stack with a pointer to every elem_size offset in slab
		free(ret);
		free(slab);
		return NULL;
	}else if(!(ret->slabs = malloc(1*sizeof(void*)))){//put slab in an array
		free(ret);
		free(slab);
		free(ret->elems);
		return NULL;
	}
	ret->slabs[0] = slab;
	for(size_t i = 0; i < elems_cap; ++i){//fill the stack with the pointers
		ret->elems[i] = slab + i*ret->elem_size;
	}
	return ret;
}

void sla_delete(slab_allocator *sla){
	for(size_t i = 0; i < sla->slabs_len; ++i){
		free(sla->slabs[i]);
	}
	free(sla->slabs);
	free(sla->elems);
	free(sla);
}

void *sla_alloc(slab_allocator *sla){
	if(sla->elems_len == 0){
		size_t slab_size = sla->slab_size*1.618, elems_cap = sla->elems_cap + slab_size;//1.618 because the golden ratio is the best ratio
		void *slab = malloc(slab_size*sla->elem_size), **elems, **slabs;
		if(!slab){
			return NULL;
		}else if(!(elems = realloc(sla->elems, elems_cap*sizeof(void*)))){
			free(slab);
			return NULL;
		}else if(!(slabs = realloc(sla->slabs, (sla->slabs_len + 1)*sizeof(void*)))){
			free(slab);
			if((elems = realloc(sla->elems, sla->elems_cap*sizeof(void*)))){//although if shrinking with realloc fails ... good luck
				sla->elems = elems;
			}
			return NULL;
		}
		slabs[sla->slabs_len++] = slab;
		sla->slabs = slabs;
		for(size_t i = 0; i < elems_cap - sla->elems_cap; ++i){
			elems[i] = slab + i*sla->elem_size;
		}
		sla->elems = elems;
		sla->slab_size = slab_size;
		sla->elems_len = elems_cap - sla->elems_cap;
		sla->elems_cap = elems_cap;
	}
	return sla->elems[--sla->elems_len];
}

void sla_free(slab_allocator *sla, void *p){
	sla->elems[sla->elems_len++] = p;//Can't overflow if only un- sla_free'd sla_alloc'd pointers are passed in
}

sla.h

//sla.h
#ifndef __SLA_H__
#define __SLA_H__
#include <stddef.h>

typedef struct{
	void **slabs, **elems;//slabs is an array of pointers to exponentially growing blocks; elems is an array used as a stack of pointers into them
	size_t slabs_len, slab_size, elems_len, elems_cap, elem_size;
} slab_allocator;//slab allocator: aggregates small, single allocations to decrease dynamic memory requests.

slab_allocator *sla_new(size_t elem_size, size_t elems_cap);
void sla_delete(slab_allocator *sla);
void *sla_alloc(slab_allocator *sla);
void sla_free(slab_allocator *sla, void *p);

#endif