#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <time.h>

typedef struct _node{
    int data;
    struct _node *prev;
    struct _node *next;
} node;

void insert(node **head, int data) {
    node *new_node = (node *) malloc(sizeof(node));

    new_node->data = data;
    new_node->next = *head;
    new_node->prev = NULL;
    if (*head != NULL) {
        (*head)->prev = new_node;
    }
    *head = new_node;
    return;
}

void pop(node **head, int to_delete) {
    node *curr = *head;
    node *prev = NULL;
    node *nxt;
    while (curr != NULL) {
        nxt = curr->next;
        if ((curr)->data == to_delete) {
            if (prev != NULL) {
                prev->next = nxt;
            }
            if (nxt != NULL) {
                nxt->prev = prev;
            }
            if (curr == *head) {
                *head = nxt;
            }
            free(curr);
            return;
        }
        prev = curr;
        curr = nxt;
    }
    return;
}

void insert_after(node **head, node *target, int data) {
    node *new_node = (node *) malloc(sizeof(node));
    new_node->prev = NULL;
    new_node->next = NULL;
    new_node->data = data;

    node *next = target->next;

    if (next != NULL) {
        next->prev = target;
    }

    new_node->prev = target;
    new_node->next = next;
    target->next = new_node;
    return;
}

void print_list(node *head) {
    node *curr = head;
    node *prev = NULL;
    node *nxt;

    while (curr != NULL) {
        printf("%d ", curr->data);
        nxt = curr->next;
        prev = curr;
        curr = nxt;
    }
    printf("\n");
}


double bench_insert_after() {
    node *head = NULL;
    node *targets[10000];
    int j = 0;
    int x;
    srandom(0);
    for (int i = 0; i < 100000; i++) {
        x = random();
        insert(&head, x);
        if (x % 10 == 0 && j < 10000) {
            targets[j] = head;
            j++;
        }
    }
    clock_t begin = clock();
    for  (int i = 0; i < j; i++) {
        insert_after(&head, targets[i], random());
    }
    clock_t end = clock();
    return (double)(end - begin) / CLOCKS_PER_SEC;
}

double bench_pop(){
    node *head = NULL;
    node *targets[10000];
    int j = 0;
    int x;
    srandom(0);
    for (int i = 0; i < 100000; i++) {
        x = random();
        insert(&head, x);
        if (x % 10 == 0 && j < 10000) {
            targets[j] = head;
            j++;
        }
    }
    clock_t begin = clock();
    for  (int i = 0; i < j; i++) {
        pop(&head, targets[i]->data);
    }
    clock_t end = clock();
    return (double)(end - begin) / CLOCKS_PER_SEC;
}

double bench_insert(){
    node *head = NULL;
    srandom(0);
    clock_t begin = clock();
    for (int i = 0; i < 100000; i++) {
        insert(&head, random());
    }
    clock_t end = clock();
    return (double)(end - begin) / CLOCKS_PER_SEC;
}


int main() {
    printf("%g\n", bench_insert());
    printf("%g\n", bench_pop());
    printf("%g\n", bench_insert_after());
    return 0;
}