Untitled
unknown
plain_text
7 months ago
6.6 kB
4
Indexable
Never
#include "seq.h" #include <stdlib.h> #include <string.h> #include <errno.h> #include <stdbool.h> #include<stdio.h> typedef struct list list_t; typedef struct abstr abstr_t; struct list { seq_t *node; list_t *prev; list_t *next; }; struct abstr { list_t *elems_l; // start of list list_t *elems_r; // end of list size_t size; char *name; }; struct seq { seq_t *children[3]; abstr_t *abstr; list_t *pos; }; #define SWAP(type, a, b) \ do { \ type tmp = a; \ b = a; \ a = tmp; \ } while(false) ///------------errors------------ static int invalid() { errno = EINVAL; return -1; } static int invalid_input(seq_t *p, char const *s) { if (p == NULL) return invalid(); if (s == NULL) return invalid(); size_t i = 0; while (s[i] != 0) { if (s[i] < '0' || s[i] > '3') return invalid(); i++; } return 0; } ///------------struct management------------ static abstr_t *new_abstr() { abstr_t *x = (abstr_t *) malloc(sizeof(abstr_t)); list_t *l = (list_t *) malloc(sizeof(list_t)); list_t *r = (list_t *) malloc(sizeof(list_t)); if (x == NULL || l == NULL || r == NULL) { if(x) free(x); if(l) free(l); if(r) free(r); errno = ENOMEM; return NULL; } *x = (abstr_t) {.elems_l = l, .elems_r = r}; return x; } static void delete_abstr(abstr_t *x) { if(x->elems_l) free(x->elems_l); if(x->elems_r) free(x->elems_r); if(x->name) free(x->name); if(x) free(x); } static seq_t *new_node() { seq_t *x = (seq_t *) malloc(sizeof(seq_t)); list_t *l = (list_t *) malloc(sizeof(list_t)); abstr_t *a = new_abstr(); if (x == NULL || a == NULL || l == NULL) { if(x) free(x); if(a) free(a); if(l) free(l); errno = ENOMEM; return NULL; } *x = (seq_t) {.pos = l, .abstr = a}; x->children[0] = NULL; x->children[1] = NULL; x->children[2] = NULL; l->next = a->elems_r; l->prev = a->elems_l; a->size = 1; return x; } static void delete_node(seq_t *x) { if (x->abstr == NULL) { //deleting trie root if(x) free(x); return; } x->pos->prev->next = x->pos->next; x->pos->next->prev = x->pos->prev; if (--x->abstr->size == 0) delete_abstr(x->abstr); if(x->pos) free(x->pos); if(x) free(x); } static void delete_subtree(seq_t *x) { for (size_t i = 0; i < 3; i++) { if (x->children[i] != NULL){ delete_subtree(x->children[i]); } } delete_node(x); } static int join_names(abstr_t *a, abstr_t *b) { if (b->name == NULL) return 0; if (a->name == NULL) { a->name = b->name; b->name = NULL; return 0; } if (!strcmp(a->name, b->name)){ if(b->name) free(b->name); return 0; } size_t b_len = strlen(b->name); size_t new_len = strlen(a->name) + b_len; char *new_ptr = realloc(a->name, new_len + 1); if (new_ptr == NULL) { errno = ENOMEM; return -1; } a->name = strncat(new_ptr, b->name, b_len); if(b->name) free(b->name); b->name = NULL; return 0; } static int join_abstr(abstr_t *a, abstr_t *b) { if (a == b) return 0; if (join_names(a, b)) { return -1; } if (a->size < b->size) { SWAP(abstr_t *, a, b); SWAP(char *, a->name, b->name); } for (list_t *ptr = b->elems_l->next; ptr != b->elems_r; ptr = ptr->next) ptr->node->abstr = a; a->elems_r->prev->next = b->elems_l->next; b->elems_l->next->prev = a->elems_r->prev; SWAP(list_t *, a->elems_r, b->elems_r); a->size += b->size; delete_abstr(b); return 1; } static abstr_t *get_abstr(seq_t * p, char const *s){ seq_t *now = p; size_t i = 0; while (s[i] != 0){ now = now->children[(size_t) s[i] - '0']; i++; } return now->abstr; } ///------------OG functions------------ seq_t *seq_new() { seq_t *x = (seq_t *) calloc(1, sizeof(seq_t)); if (x == NULL) { errno = ENOMEM; return NULL; } return x; } void seq_delete(seq_t *p) { if (p == NULL) return; delete_subtree(p); } int seq_valid(seq_t *p, char const *s) { if (invalid_input(p, s)) return -1; seq_t *now = p; size_t i = 0; while(s[i] != 0 && now->children[(size_t) s[i] - '0'] != NULL) { now = now->children[(size_t) s[i] - '0']; i++; } if (s[i] == 0) return 1; return 0; } int seq_add(seq_t *p, char const *s) { if (invalid_input(p, s)) return -1; if (seq_valid(p, s)) return 0; seq_t *now = p, *first_added = NULL; size_t i = 0; while (s[i] != 0) { size_t idx = s[i] - '0'; if (now->children[idx] == NULL) { now->children[idx] = new_node(); if (now->children[idx] == NULL) { if (first_added != NULL) delete_subtree(first_added); return -1; } if (first_added == NULL) first_added = now->children[idx]; } now = now->children[idx]; i++; } return 1; } int seq_remove(seq_t *p, char const *s) { if (invalid_input(p, s)) return -1; if (!seq_valid(p, s)) return 0; seq_t *now = p; size_t i = 0; while (s[i] != 0) { if (now->children[(size_t) s[i] - '0'] == NULL) return 0; now = now->children[(size_t) s[i] - '0']; i++; } delete_subtree(now); return 1; } int seq_set_name(seq_t *p, char const *s, char const *n) { if (invalid_input(p, s)) return -1; if (!seq_valid(p, s)) return 0; size_t len = strlen(s); char *name = (char *) calloc(len + 1, sizeof(char)); if (name == NULL){ if(name) free(name); errno = ENOMEM; return -1; } strcpy(name, n); abstr_t *a = get_abstr(p, s); if(!strcmp(a->name, name)) return 0; a->name = name; return 1; } char const *seq_get_name(seq_t *p, char const *s) { if (invalid_input(p, s)) return NULL; if (!seq_valid(p, s)){ errno = 0; return NULL; } abstr_t * a = get_abstr(p, s); if (a->name == NULL) errno = 0; return a->name; } int seq_equiv(seq_t *p, char const *s1, char const *s2) { if (invalid_input(p, s1) || invalid_input(p, s2)) return -1; if (!seq_valid(p, s1) || !seq_valid(p, s2)) return 0; return join_abstr(get_abstr(p, s1), get_abstr(p, s2)); }