Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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);
}
#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);
}
#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
#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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.