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/cnp.c | 361 -------------------------------------------------------------- 1 file changed, 361 deletions(-) (limited to 'src/cnp.c') diff --git a/src/cnp.c b/src/cnp.c index fe8212e..d9a4978 100644 --- a/src/cnp.c +++ b/src/cnp.c @@ -1,362 +1 @@ -#include -#include -#include "util.h" -#include "list.h" #include "cnp.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 - -} - -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