aboutsummaryrefslogtreecommitdiff
path: root/src_c
diff options
context:
space:
mode:
Diffstat (limited to 'src_c')
-rw-r--r--src_c/common.c12
-rw-r--r--src_c/common.h6
-rw-r--r--src_c/csp.c57
-rw-r--r--src_c/main.c19
-rw-r--r--src_c/pool.c18
-rw-r--r--src_c/pool.h3
6 files changed, 74 insertions, 41 deletions
diff --git a/src_c/common.c b/src_c/common.c
index 403fe87..66b826d 100644
--- a/src_c/common.c
+++ b/src_c/common.c
@@ -392,8 +392,9 @@ static int read_params(opcut_params_t *params, char *json, jsmntok_t *tokens,
}
-int opcut_params_init(opcut_params_t *params, opcut_pool_t *panel_pool,
- opcut_pool_t *item_pool, opcut_str_t *json) {
+int opcut_params_init(hat_allocator_t *a, opcut_params_t *params,
+ opcut_pool_t *panel_pool, opcut_pool_t *item_pool,
+ opcut_str_t *json) {
params->panel_pool = panel_pool;
params->item_pool = item_pool;
@@ -405,21 +406,22 @@ int opcut_params_init(opcut_params_t *params, opcut_pool_t *panel_pool,
if (tokens_len < 0)
return OPCUT_ERROR;
- jsmntok_t *tokens = malloc(tokens_len * sizeof(jsmntok_t));
+ jsmntok_t *tokens =
+ hat_allocator_alloc(a, tokens_len * sizeof(jsmntok_t), NULL);
if (!tokens)
return OPCUT_ERROR;
jsmn_init(&parser);
tokens_len = jsmn_parse(&parser, json->data, json->len, tokens, tokens_len);
if (tokens_len < 0) {
- free(tokens);
+ hat_allocator_free(a, tokens);
return OPCUT_ERROR;
}
size_t pos = 0;
int err = read_params(params, json->data, tokens, &pos);
- free(tokens);
+ hat_allocator_free(a, tokens);
return err;
}
diff --git a/src_c/common.h b/src_c/common.h
index 3464a61..22e6a88 100644
--- a/src_c/common.h
+++ b/src_c/common.h
@@ -3,6 +3,7 @@
#include <stdbool.h>
#include <stdio.h>
+#include <hat/allocator.h>
#include "pool.h"
#define OPCUT_SUCCESS 0
@@ -86,8 +87,9 @@ typedef struct {
} opcut_result_t;
-int opcut_params_init(opcut_params_t *params, opcut_pool_t *panel_pool,
- opcut_pool_t *item_pool, opcut_str_t *json);
+int opcut_params_init(hat_allocator_t *a, opcut_params_t *params,
+ opcut_pool_t *panel_pool, opcut_pool_t *item_pool,
+ opcut_str_t *json);
int opcut_result_write(opcut_result_t *result, FILE *stream);
#ifdef __cplusplus
diff --git a/src_c/csp.c b/src_c/csp.c
index 9cd25ec..7d837bf 100644
--- a/src_c/csp.c
+++ b/src_c/csp.c
@@ -1,4 +1,5 @@
#include "csp.h"
+#include "common.h"
#define FITNESS_K 0.03
@@ -252,12 +253,17 @@ static void free_unused(opcut_result_t *result) {
}
-static void free_last_used(opcut_result_t *result) {
- opcut_pool_free(result->used_pool, result->used);
+static void free_used(opcut_result_t *result, opcut_used_t *last_used) {
+ while (result->used && result->used != last_used) {
+ opcut_used_t *next = result->used->next;
+ opcut_pool_free(result->used_pool, result->used);
+ result->used = next;
+ }
}
-static int calculate_greedy(opcut_result_t *result, opcut_item_t *items) {
+static int calculate_greedy(opcut_result_t *result, opcut_item_t *items,
+ bool forward_greedy) {
for (opcut_item_t *item = items; item; item = item->next) {
opcut_result_t best_result;
fitness_t best_fitness;
@@ -279,7 +285,33 @@ static int calculate_greedy(opcut_result_t *result, opcut_item_t *items) {
return OPCUT_ERROR;
fitness_t temp_fitness;
- calculate_fitness(&temp_result, &temp_fitness);
+ if (!forward_greedy) {
+ calculate_fitness(&temp_result, &temp_fitness);
+
+ } else {
+ opcut_result_t greedy_result = temp_result;
+ if (copy_unused(&greedy_result, temp_result.unused))
+ return OPCUT_ERROR;
+
+ int err =
+ calculate_greedy(&greedy_result, item->next, false);
+
+ if (!err) {
+ calculate_fitness(&greedy_result, &temp_fitness);
+ free_used(&greedy_result, temp_result.used);
+ free_unused(&greedy_result);
+
+ } else if (err == OPCUT_UNSOLVABLE) {
+ free_used(&greedy_result, temp_result.used);
+ free_used(&temp_result, result->used);
+ free_unused(&greedy_result);
+ free_unused(&temp_result);
+ continue;
+
+ } else {
+ return err;
+ }
+ }
if (!solvable) {
best_result = temp_result;
@@ -288,13 +320,13 @@ static int calculate_greedy(opcut_result_t *result, opcut_item_t *items) {
} else if (compare_fitness(&temp_fitness, &best_fitness) <
0) {
- free_last_used(&best_result);
+ free_used(&best_result, result->used);
free_unused(&best_result);
best_result = temp_result;
best_fitness = temp_fitness;
} else {
- free_last_used(&temp_result);
+ free_used(&temp_result, result->used);
free_unused(&temp_result);
}
}
@@ -312,15 +344,6 @@ static int calculate_greedy(opcut_result_t *result, opcut_item_t *items) {
}
-static int calculate_forward_greedy(opcut_result_t *result,
- opcut_item_t *items) {
- for (opcut_item_t *item = items; item; item = item->next) {
- }
-
- return OPCUT_SUCCESS;
-}
-
-
int opcut_calculate(opcut_pool_t *used_pool, opcut_pool_t *unused_pool,
opcut_method_t method, opcut_params_t *params,
opcut_result_t *result) {
@@ -350,10 +373,10 @@ int opcut_calculate(opcut_pool_t *used_pool, opcut_pool_t *unused_pool,
}
if (method == OPCUT_METHOD_GREEDY)
- return calculate_greedy(result, params->items);
+ return calculate_greedy(result, params->items, false);
if (method == OPCUT_METHOD_FORWARD_GREEDY)
- return calculate_forward_greedy(result, params->items);
+ return calculate_greedy(result, params->items, true);
return OPCUT_ERROR;
}
diff --git a/src_c/main.c b/src_c/main.c
index bf0b117..5532de0 100644
--- a/src_c/main.c
+++ b/src_c/main.c
@@ -59,12 +59,12 @@ static int parse_args(args_t *args, int argc, char **argv) {
}
-static int read_stream(FILE *stream, opcut_str_t *json) {
+static int read_stream(hat_allocator_t *a, FILE *stream, opcut_str_t *json) {
size_t size = 0;
while (!(json->len < size)) {
size += 4096;
- char *data = realloc(json->data, size);
+ char *data = hat_allocator_alloc(a, size, json->data);
if (!data)
return OPCUT_ERROR;
@@ -77,10 +77,11 @@ static int read_stream(FILE *stream, opcut_str_t *json) {
int main(int argc, char **argv) {
- opcut_pool_t *panel_pool = opcut_pool_create(sizeof(opcut_panel_t));
- opcut_pool_t *item_pool = opcut_pool_create(sizeof(opcut_item_t));
- opcut_pool_t *used_pool = opcut_pool_create(sizeof(opcut_used_t));
- opcut_pool_t *unused_pool = opcut_pool_create(sizeof(opcut_unused_t));
+ hat_allocator_t *a = &hat_allocator_libc;
+ opcut_pool_t *panel_pool = opcut_pool_create(a, sizeof(opcut_panel_t));
+ opcut_pool_t *item_pool = opcut_pool_create(a, sizeof(opcut_item_t));
+ opcut_pool_t *used_pool = opcut_pool_create(a, sizeof(opcut_used_t));
+ opcut_pool_t *unused_pool = opcut_pool_create(a, sizeof(opcut_unused_t));
args_t args;
FILE *input_stream = NULL;
@@ -115,13 +116,13 @@ int main(int argc, char **argv) {
goto cleanup;
}
- exit_code = read_stream(input_stream, &json);
+ exit_code = read_stream(a, input_stream, &json);
if (exit_code) {
fprintf(stderr, "error reading input stream\n");
goto cleanup;
}
- exit_code = opcut_params_init(&params, panel_pool, item_pool, &json);
+ exit_code = opcut_params_init(a, &params, panel_pool, item_pool, &json);
if (exit_code) {
fprintf(stderr, "error parsing calculation parameters\n");
goto cleanup;
@@ -139,7 +140,7 @@ int main(int argc, char **argv) {
cleanup:
if (json.data)
- free(json.data);
+ hat_allocator_free(a, json.data);
if (output_stream)
fclose(output_stream);
if (input_stream)
diff --git a/src_c/pool.c b/src_c/pool.c
index 04968c8..7e2bd02 100644
--- a/src_c/pool.c
+++ b/src_c/pool.c
@@ -11,6 +11,7 @@ typedef struct header_t {
struct opcut_pool_t {
+ hat_allocator_t *a;
size_t item_size;
header_t *blocks;
header_t *items;
@@ -23,9 +24,11 @@ static void allocate_block(opcut_pool_t *pool) {
if (items_per_block < 1)
items_per_block = 1;
- header_t *block =
- malloc(sizeof(header_t) +
- items_per_block * (sizeof(header_t) + pool->item_size));
+ header_t *block = hat_allocator_alloc(
+ pool->a,
+ sizeof(header_t) +
+ items_per_block * (sizeof(header_t) + pool->item_size),
+ NULL);
if (!block)
return;
block->next = pool->blocks;
@@ -40,14 +43,15 @@ static void allocate_block(opcut_pool_t *pool) {
}
-opcut_pool_t *opcut_pool_create(size_t item_size) {
- opcut_pool_t *pool = malloc(sizeof(opcut_pool_t));
+opcut_pool_t *opcut_pool_create(hat_allocator_t *a, size_t item_size) {
+ opcut_pool_t *pool = hat_allocator_alloc(a, sizeof(opcut_pool_t), NULL);
if (!pool)
return NULL;
if (item_size % sizeof(void *) != 0)
item_size += sizeof(void *) - (item_size % sizeof(void *));
+ pool->a = a;
pool->item_size = item_size;
pool->blocks = NULL;
pool->items = NULL;
@@ -60,9 +64,9 @@ void opcut_pool_destroy(opcut_pool_t *pool) {
while (pool->blocks) {
header_t *block = pool->blocks;
pool->blocks = block->next;
- free(block);
+ hat_allocator_free(pool->a, block);
}
- free(pool);
+ hat_allocator_free(pool->a, pool);
}
diff --git a/src_c/pool.h b/src_c/pool.h
index 6998df6..e6ac0b2 100644
--- a/src_c/pool.h
+++ b/src_c/pool.h
@@ -2,6 +2,7 @@
#define OPCUT_POOL_H
#include <stddef.h>
+#include <hat/allocator.h>
#ifdef __cplusplus
extern "C" {
@@ -9,7 +10,7 @@ extern "C" {
typedef struct opcut_pool_t opcut_pool_t;
-opcut_pool_t *opcut_pool_create(size_t item_size);
+opcut_pool_t *opcut_pool_create(hat_allocator_t *a, size_t item_size);
void opcut_pool_destroy(opcut_pool_t *pool);
void *opcut_pool_alloc(opcut_pool_t *pool);
void opcut_pool_free(opcut_pool_t *pool, void *item);
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-02-11 15:05:52 +0000