From 8ace61933130416a0b8a6b250de681a606439f48 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 28 Jan 2022 11:17:01 +0800 Subject: CNP save point CRF and process descriptors seem to work now. It only remains to implement the set of pending actions before I can work on the driver program. --- src/cnp.c | 362 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 362 insertions(+) create mode 100644 src/cnp.c (limited to 'src/cnp.c') diff --git a/src/cnp.c b/src/cnp.c new file mode 100644 index 0000000..fe8212e --- /dev/null +++ b/src/cnp.c @@ -0,0 +1,362 @@ +#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