nord vpnnord vpn
Ad

Untitled

mail@pastecode.io avatar
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));
}

nord vpnnord vpn
Ad