From e555c88b8107caf886da229444c2bed1aaef6c2c Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 28 Jan 2022 23:21:00 +0800 Subject: rename cnp to crf THat file implements support functions for the CNP algorithm, not the algorithm itself. --- src/crf.c | 487 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 487 insertions(+) create mode 100644 src/crf.c (limited to 'src/crf.c') diff --git a/src/crf.c b/src/crf.c new file mode 100644 index 0000000..dbcb050 --- /dev/null +++ b/src/crf.c @@ -0,0 +1,487 @@ +#include +#include +#include "util.h" +#include "list.h" +#include "crf.h" + +struct crf_s { + ht *table; +}; + +crf * +new_crf() +{ + crf *crfp = NULL; + SAFE_MALLOC(crf, crfp, 1, goto cleanup;); + + crfp->table = new_ht2(HT_INIT_CAP); + + if (crfp->table == NULL) goto cleanup; + + return crfp; + + cleanup: + + if (crfp) free(crfp); + + return NULL; +} + +BOOL +crf_add_node(crf * const restrict crfp, pair2 node) +{ + if (ht_find(crfp->table, &node)) return 0; + + pair2 *p2 = NULL; + + NEW_P2(p2, node.x, node.y, return 1;); + + ht *value_table = new_ht4(HT_INIT_CAP); + + if (value_table == NULL) { + free(p2); + return 1; + } + + if (ht_insert(crfp->table, p2, value_table)) { + fleprintf0("Fail to insert\n"); + destroy_ht(value_table, DESTROY_NONE_SELF); + free(p2); + return 1; + } + + return 0; +} + +ht * +crf_find_node(crf * const restrict crfp, pair2 node) +{ + return ht_find(crfp->table, &node); +} + +BOOL +crf_add_edge(crf * const restrict crfp, pair2 source, pair4 label) +{ + if (ht_find(crfp->table, &source) == NULL) { + fleprintf0("add the node before adding its edges\n"); + return 1; + } + + if (ht_find(ht_find(crfp->table, &source), &label)) return 0; + + pair4 *p = NULL; + + NEW_P4(p, label.x, label.y, label.z, label.w, return 1;); + + if (ht_insert(ht_find(crfp->table, &source), p, (void*)1)) { + fleprintf0("Fail to insert\n"); + free(p); + return 1; + } + + return 0; +} + +void +destroy_crf(crf * const restrict crfp) +{ + +#define SIZE (ht_size(crfp->table)) +#define VALUES ((ht**) ht_values(crfp->table)) + + for (NUM i = 0; i < SIZE;) + destroy_ht(*(VALUES+i++), DESTROY_KEY_SELF); + + destroy_ht(crfp->table, DESTROY_KEY_SELF); + + free(crfp); + +#undef SIZE +#undef VALUES + +} + +struct spa_s { + ht *table; +}; + +spa * +new_spa() +{ + spa *spap = NULL; + SAFE_MALLOC(spa, spap, 1, return NULL;); + + spap->table = new_ht2(HT_INIT_CAP); + + if (spap->table == NULL) { + free(spap); + return NULL; + } + + return spap; +} + +void +destroy_spa(spa * const restrict spap) +{ + for (NUM i = 0; i < ht_size(spap->table); i++) + destroy_ht(*((ht **) ht_values(spap->table)+i), DESTROY_KEY_SELF); + + /* fleprintf0("ho\n"); */ + + destroy_ht(spap->table, DESTROY_KEY_SELF); + + free(spap); +} + +BOOL +spa_insert(spa * const restrict spap, pair3 label) +{ + pair2 first_two = (pair2) { 0 }, *p2 = NULL; + + first_two.x = label.x; + first_two.y = label.y; + + NUM j = label.z, *np = NULL; + + ht *value_table = NULL; + + if (ht_find(spap->table, &first_two) == NULL) { + value_table = new_ht(HT_INIT_CAP, 0); + + if (value_table == NULL) { + fleprintf0("Fail to have new hash table\n"); + goto cleanup; + } + + SAFE_MALLOC(NUM, np, 1, goto cleanup;); + *np = label.z; + + if (ht_insert(value_table, np, (void*)1)) { + fleprintf0("Fail to insert\n"); + goto cleanup; + } + + np = NULL; + + NEW_P2(p2, label.x, label.y, goto cleanup;); + + if (ht_insert(spap->table, p2, value_table)) { + fleprintf0("Fail to insert\n"); + goto cleanup; + } + + p2 = NULL; + + goto success; + } + + if (ht_find(ht_find(spap->table, &first_two), &j) == NULL) { + SAFE_MALLOC(NUM, np, 1, goto cleanup;); + *np = label.z; + + if (ht_insert(ht_find(spap->table, &first_two), np, (void*)1)) { + fleprintf0("Fail to insert\n"); + goto cleanup; + } + + np = NULL; + } + + goto success; + + cleanup: + if (value_table) destroy_ht(value_table, DESTROY_KEY_SELF); + if (p2) free(p2); + if (np) free(np); + + return 1; + + success: + return 0; +} + +P_ATTR +BOOL +spa_belong(CCR_MOD(spa *) spap, pair3 label) +{ + pair2 first_two = (pair2) { 0 }; + + first_two.x = label.x; + first_two.y = label.y; + + if (ht_find(spap->table, &first_two) == NULL) return 0; + + NUM j = label.z; + + if (ht_find(ht_find(spap->table, &first_two), &j) == NULL) return 0; + + return 1; +} + +P_ATTR +ht * +spa_find(CCR_MOD(spa *) spap, pair2 label) +{ + return ht_find(spap->table, &label); +} + +typedef struct procr_array_element_s procr_array_element; + +/* The list at index k is the set R_k. */ +struct procr_array_element_s { + BOOL initialized; + List *ls; +}; + +struct procr_s { + /* input length */ + NUM len; + /* an array of lists */ + procr_array_element *array; + /* minimal grade that is non-empty */ + NUM mg; +}; + +typedef struct procu_array_element_s procu_array_element; + +/* The table at index k represents the set U_k. Its keys are those + (X, a, i, j) such that (X, a, i, j, k) belongs to U_k. */ +struct procu_array_element_s { + BOOL initialized; + ht *table; +}; + +struct procu_s { + /* input length */ + NUM len; + /* an array of hash tables */ + procu_array_element *array; +}; + +procr * +new_procr(NUM size, BOOL * const restrict errorp) +{ + *errorp = 0; + + procr *pr = NULL; + + SAFE_MALLOC(procr, pr, 1, goto cleanup;); + + pr->len = size; + pr->array = NULL; + + SAFE_MALLOC(procr_array_element, pr->array, + sizeof(procr_array_element) * size, + goto cleanup;); + + memset(pr->array, 0, sizeof(procr_array_element) * size); + + goto success; + + cleanup: + + *errorp = 1; + + if (pr && pr->array) free(pr->array); + + if (pr) free(pr); + + success: + + return pr; +} + +procu * +new_procu(NUM size, BOOL * const restrict errorp) +{ + *errorp = 0; + + procu *pu = NULL; + + SAFE_MALLOC(procu, pu, 1, goto cleanup;); + + pu->len = size; + pu->array = NULL; + + SAFE_MALLOC(procu_array_element, pu->array, + sizeof(procu_array_element) * size, + goto cleanup;); + + memset(pu->array, 0, sizeof(procu_array_element) * size); + + goto success; + + cleanup: + + *errorp = 1; + + if (pu && pu->array) free(pu->array); + + if (pu) free(pu); + + success: + + return pu; +} + +void +destroy_procr(procr * const restrict pr) +{ + for (NUM i = 0; i < pr->len; i++) + if ((pr->array+i)->initialized) + destroy_list((pr->array+i)->ls, 1); + + free(pr->array); + + free(pr); +} + +void +destroy_procu(procu * const restrict pu) +{ + for (NUM i = 0; i < pu->len; i++) + if ((pu->array+i)->initialized) + destroy_ht((pu->array+i)->table, DESTROY_KEY_SELF); + + free(pu->array); + + free(pu); +} + +BOOL +desc_add(procr * const restrict pr, procu * const restrict pu, + NUM grade, prodecor dec) +{ + if (grade < 0 || grade >= pu->len) { + fleprintf("Invalid grade: %ld\n", grade); + goto cleanup; + } + + pair4 *p4 = NULL; + +#define HELE (pu->array+grade) +#define LELE (pr->array+grade) + + if (HELE->initialized) { + /* If HELE is initialized then LELE should also be initialized. */ + if (ht_find(HELE->table, &dec) != NULL) goto success; + + NEW_P4(p4, dec.x, dec.y, dec.z, dec.w, goto cleanup;); + + if (ht_insert(HELE->table, p4, (void*)1)) { + fleprintf0("Fail to insert\n"); + goto cleanup; + } + + NEW_P4(p4, dec.x, dec.y, dec.z, dec.w, + ht_delete(HELE->table, &dec, DELETE_KEY); goto cleanup;); + + if (add_to_list(LELE->ls, p4)) { + fleprintf0("Fail to add to list\n"); + ht_delete(HELE->table, &dec, DELETE_KEY); + goto cleanup; + } + + goto success; + } + + HELE->table = new_ht4(HT_INIT_CAP); + + if (HELE->table == NULL) { + fleprintf0("Fail to have new hash table\n"); + goto cleanup; + } + + HELE->initialized = 1; + + NEW_P4(p4, dec.x, dec.y, dec.z, dec.w, + destroy_ht(HELE->table, DESTROY_KEY_SELF); + HELE->initialized = 0; + goto cleanup;); + + if (ht_insert(HELE->table, p4, (void*)1)) { + fleprintf0("Fail to insert\n"); + destroy_ht(HELE->table, DESTROY_KEY_SELF); + HELE->initialized = 0; + goto cleanup; + } + + LELE->ls = new_list(); + + if (LELE->ls == NULL) { + fleprintf0("Fail to have new list\n"); + destroy_ht(HELE->table, DESTROY_KEY_SELF); + HELE->initialized = 0; + goto cleanup; + } + + LELE->initialized = 1; + + NEW_P4(p4, dec.x, dec.y, dec.z, dec.w, + destroy_ht(HELE->table, DESTROY_KEY_SELF); + HELE->initialized = 0; + destroy_list(LELE->ls, 1); + LELE->initialized = 0; + goto cleanup;); + + if (add_to_list(LELE->ls, p4)) { + fleprintf0("Fail to add to list\n"); + destroy_ht(HELE->table, DESTROY_KEY_SELF); + HELE->initialized = 0; + destroy_list(LELE->ls, 1); + LELE->initialized = 0; + goto cleanup; + } + +#undef HELE +#undef LELE + + goto success; + + cleanup: + + return 1; + + success: + + return 0; +} + +prodecor * +pop_procr(procr * pr, procu * pu, NUM *gradep) +{ + prodecor *result = NULL; + + if (pr->mg >= pr->len) goto success; + +#define ELEMENT (pr->array+pr->mg) + + if (!(ELEMENT->initialized)) goto reset_mg; + + *gradep = pr->mg; + + result = pop_from_list(ELEMENT->ls); + + if (list_length(ELEMENT->ls) == 0) { + destroy_ht((pu->array+pr->mg)->table, DESTROY_KEY_SELF); + (pu->array+pr->mg)->initialized = 0; + (pu->array+pr->mg)->table = NULL; + + destroy_list(ELEMENT->ls, 1); + ELEMENT->initialized = 0; + ELEMENT->ls = NULL; + + /* REVIEW: Maybe we can just increment the minimal grade, as we + won't jump over two steps? */ + reset_mg: + while (++(pr->mg) < pr->len) { + if (ELEMENT->initialized) break; + } + } + +#undef ELEMENT + + success: + return result; +} -- cgit v1.2.3-18-g5258