summaryrefslogtreecommitdiff
path: root/src/cnp.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cnp.c')
-rw-r--r--src/cnp.c362
1 files changed, 362 insertions, 0 deletions
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 <stdio.h>
+#include <string.h>
+#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;
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-09-19 17:06:41 +0000