// minheap.h
#ifndef _MINHEAP_H
#define _MINHEAP_H

#include <stdint.h>
#include <stdlib.h>
#include <pthread.h>


typedef struct timer_entry_s timer_entry_t;
typedef void (*timer_handler_pt)(timer_entry_t *ev);

#define TIMER_TIMEOUT (1 << 0)
#define TIMER_DELETE (1 << 1)
struct min_heap_s;
struct timer_entry_s
{
    struct min_heap *heap;
    uint32_t time;
    int min_heap_idx;
    timer_handler_pt handler;
    void *privdata;
};

typedef struct min_heap
{
    timer_entry_t **elements;
    uint32_t size;
    uint32_t capacity; // n 為實(shí)際元素個(gè)數(shù)  a 為容量
    pthread_mutex_t mtx;
} min_heap_t;

void min_heap_create(min_heap_t *heap);
void min_heap_destroy(min_heap_t *heap);
void min_heap_elem_init(timer_entry_t *elem);
int min_heap_elt_is_top(const timer_entry_t *elem);
int min_heap_is_empty(min_heap_t *heap);
unsigned min_heap_size(min_heap_t *heap);
timer_entry_t *min_heap_top(min_heap_t *heap);
int min_heap_ensure_capacity(min_heap_t *heap, unsigned n);
int min_heap_push(min_heap_t *heap, timer_entry_t *elem);
void min_heap_adjust(min_heap_t *heap, timer_entry_t *elem);
timer_entry_t *min_heap_pop(min_heap_t *heap);
int min_heap_delete(min_heap_t *heap, timer_entry_t *elem);
void min_heap_shift_up(min_heap_t *heap, unsigned int index, timer_entry_t *elem);
void min_heap_shift_down(min_heap_t *heap, unsigned int index, timer_entry_t *elem);

#endif // _MINHEAP_H

// minheap.c
#include "minheap.h"

#define min_heap_elem_greater(a, b) \
    ((a)->time > (b)->time)

int min_heap_left(min_heap_t *heap, int index)
{
    index = (index << 1) + 1;
    if (index >= heap->size)
    {
        return -1;
    }
    return index;
}

int min_heap_right(min_heap_t *heap, int index)
{
    index = (index << 1) + 2;
    if (index >= heap->size)
    {
        return -1;
    }
    return index;
}

void min_heap_create(min_heap_t *heap)
{
    heap->elements = 0;
    heap->size = 0;
    heap->capacity = 0;
}
void min_heap_destroy(min_heap_t *heap)
{
    if (heap->elements)
    {
        free(heap->elements);
    }
}
void min_heap_elem_init(timer_entry_t *elem) 
{ 
    memset(elem, 0, sizeof(timer_entry_t));
    elem->min_heap_idx = -1; 
}
int min_heap_is_empty(min_heap_t *heap) 
{ 
    return 0 == heap->size; 
}
unsigned min_heap_size(min_heap_t *heap) 
{ 
    return heap->size; 
}
timer_entry_t *min_heap_top(min_heap_t *heap) 
{
    if (heap->size)
    {
        return heap->elements[0];
    }
    return NULL;
}

int min_heap_push(min_heap_t *heap, timer_entry_t *elem)
{
    if (min_heap_ensure_capacity(heap, heap->size + 1))
    {
        return -1;
    }

    min_heap_shift_up(heap, heap->size, elem);
    heap->size++;
    return 0;
}

void min_heap_adjust(min_heap_t *heap, timer_entry_t *elem)
{
    min_heap_shift_down(heap, elem->min_heap_idx, elem);
}

timer_entry_t *min_heap_pop(min_heap_t *heap)
{
    if (heap->size <= 0)
    {
        return NULL;
    }

    timer_entry_t *root = heap->elements[0];
    timer_entry_t *last = heap->elements[heap->size - 1];
    heap->size--;
    heap->elements[heap->size] = NULL;
    min_heap_shift_down(heap, 0, last);
    root->min_heap_idx = -1;
    return root;
}

int min_heap_elt_is_top(const timer_entry_t *elem)
{
    return elem->min_heap_idx == 0;
}

int min_heap_delete(min_heap_t *heap, timer_entry_t *elem)
{
    if (heap->size <= 0)
    {
        return -1;
    }
    if (elem->min_heap_idx < 0)
    {
        return 0;
    }

    timer_entry_t *last = heap->elements[heap->size - 1];
    heap->size--;
    heap->elements[heap->size] = NULL;
    min_heap_shift_down(heap, elem->min_heap_idx, last);
    elem->min_heap_idx = -1;
    return 0;
}

int min_heap_ensure_capacity(min_heap_t *heap, unsigned n)
{
    if (heap->capacity < n)
    {
        timer_entry_t **p;
        unsigned a = heap->capacity ? heap->capacity * 2 : 8;
        if (a < n)
            a = n;
        if (!(p = (timer_entry_t **)realloc(heap->elements, a * sizeof *p)))
            return -1;
        heap->elements = p;
        heap->capacity = a;
    }
    return 0;
}

void min_heap_shift_up(min_heap_t *heap, uint32_t index, timer_entry_t *elem)
{

    while (index > 0)
    {
        uint32_t pindex = (index - 1) >> 1; // 父節(jié)點(diǎn)計(jì)算公式
        timer_entry_t *parent = heap->elements[pindex];
        if (parent->time <= elem->time) // 加等號(hào)讓后面添加的在后面執(zhí)行
        {
            break;
        }
        // 如果父節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)大，那么交換，將父節(jié)點(diǎn)放在index位置
        heap->elements[index] = parent;
        heap->elements[index]->min_heap_idx = index;

        index = pindex;
    }
    heap->elements[index] = elem;
    heap->elements[index]->min_heap_idx = index;

    return;
}

void min_heap_shift_down(min_heap_t *heap, unsigned int index, timer_entry_t *elem)
{
    int half = heap->size >> 1; // 葉子節(jié)點(diǎn)計(jì)算公式
    // 第一個(gè)葉子節(jié)點(diǎn)的索引 == 非葉子節(jié)點(diǎn)的數(shù)量
    // 第一個(gè)葉子節(jié)點(diǎn)之后的節(jié)點(diǎn)全部為葉子節(jié)點(diǎn)
    while (index < half)
    {
        // index 的子節(jié)點(diǎn)有兩種情況撮抓，只有左節(jié)點(diǎn)和同時(shí)有兩個(gè)子節(jié)點(diǎn)
        int left_index = (index << 1) + 1;
        int right_index = (index << 1) + 2;
        timer_entry_t *left = heap->elements[left_index];
        timer_entry_t *child = left;
        int child_index = left_index;
        if ((right_index < heap->size) && (heap->elements[right_index]->time < child->time))
        {
            child = heap->elements[right_index];
            child_index = right_index;
        }

        if (elem->time < child->time)
        {
            break;
        }

        // 將子節(jié)點(diǎn)存到index 的位置
        heap->elements[index] = child;
        heap->elements[index]->min_heap_idx = index;
        index = child_index;
    }
    heap->elements[index] = elem;
    heap->elements[index]->min_heap_idx = index;
}

// mh-timer.h///////////////////////// 鎖未完善赁炎，另一個(gè)線程刪除定時(shí)器的時(shí)候如果定時(shí)器已經(jīng)執(zhí)行了，te 被釋放了會(huì)有問題//////////////////////////////////////////////////////////////////
#ifndef _MINHEAP_TIMER_H
#define _MINHEAP_TIMER_H

#if defined(__APPLE__)
#include <AvailabilityMacros.h>
#include <sys/time.h>
#include <mach/task.h>
#include <mach/mach.h>
#else
#include <time.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <pthread.h>

#include "minheap.h"

static uint32_t
current_time()
{
    uint32_t t;
#if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
    struct timespec ti;
    clock_gettime(CLOCK_MONOTONIC, &ti);
    t = (uint32_t)ti.tv_sec * 1000;
    t += ti.tv_nsec / 1000000;
#else
    struct timeval tv;
    gettimeofday(&tv, NULL);
    t = (uint32_t)tv.tv_sec * 1000;
    t += tv.tv_usec / 1000;
#endif
    return t;
}

void init_timer(min_heap_t *min_heap)
{
    min_heap_create(min_heap);
    pthread_mutex_init(&min_heap->mtx, NULL);
}

timer_entry_t *add_timer(min_heap_t *min_heap, uint32_t msec, timer_handler_pt callback, void *privdata)
{
    timer_entry_t *te = (timer_entry_t *)malloc(sizeof(*te));
    if (!te)
    {
        return NULL;
    }
    min_heap_elem_init(te);
    te->handler = callback;
    te->time = current_time() + msec;
    te->privdata = privdata;
    te->heap = min_heap;

    pthread_mutex_lock(&min_heap->mtx);
    if (0 != min_heap_push(min_heap, te))
    {
        pthread_mutex_unlock(&min_heap->mtx);
        free(te);
        return NULL;
    }
    pthread_mutex_unlock(&min_heap->mtx);
    printf("[add timer] %p, time = %u now = %u\n", te, te->time, current_time());
    return te;
}

int del_timer(min_heap_t *min_heap, timer_entry_t *elem)
{
    int ret = 0;
    pthread_mutex_lock(&min_heap->mtx);
    ret = min_heap_delete(min_heap, elem);
    pthread_mutex_unlock(&min_heap->mtx);
    
    return ret;
}

int find_nearest_expire_timer(min_heap_t *min_heap)
{
    pthread_mutex_lock(&min_heap->mtx);
    timer_entry_t *te = min_heap_top(min_heap);
    if (!te)
    {
        pthread_mutex_unlock(&min_heap->mtx);
        return -1;
    }
    int diff = (int)te->time - (int)current_time();
    pthread_mutex_unlock(&min_heap->mtx);
    return diff > 0 ? diff : 0;
}

void expire_timer(min_heap_t *min_heap)
{
    uint32_t cur = current_time();
    for (;;)
    {
        pthread_mutex_lock(&min_heap->mtx);
        timer_entry_t *te = min_heap_top(min_heap);
        if (!te)
        {
            pthread_mutex_unlock(&min_heap->mtx);
            break;
        }

        if (te->time > cur)
        {
            pthread_mutex_unlock(&min_heap->mtx);
            break;
        }
        min_heap_pop(min_heap);
        pthread_mutex_unlock(&min_heap->mtx);
        te->handler(te);
        printf("[del timer] %p\n", te);
        free(te);
        te = NULL;
    }
}

#endif // _MINHEAP_TIMER_H

// mh-timer.c

#include <stdio.h>
#include <unistd.h>
#include <sys/epoll.h>
#include "mh-timer.h"

uint32_t count = 1;

void hello_world(timer_entry_t *te)
{
    if (count == 1)
    {
        count = te->time;
    }
    if (te->time < count)
    {
        printf("hello world time = %u, count = %d\n", te->time, (int)te->privdata);
        printf("dtwdebug >>>>>>>>>>>>>>>> error\n");
        exit(1);
    }
    printf("hello world time = %u, count = %d\n", te->time, (int)te->privdata);
    count = te->time;
    // add_timer(te->heap, 1000, hello_world, te->privdata);
    // del_timer(te->min_heap_idx, te);
    return;
}

int main()
{
    min_heap_t min_heap;
    init_timer(&min_heap);

    // timer_entry_t *te1 = add_timer(&min_heap, 100, hello_world, 100);
    // timer_entry_t *te2 = add_timer(&min_heap, 5000, hello_world, 5000);
    // timer_entry_t *te3 = add_timer(&min_heap, 20000, hello_world, 20000);
    // timer_entry_t *te4 = add_timer(&min_heap, 5000, hello_world, 5000);
    // timer_entry_t *te5 = add_timer(&min_heap, 6000, hello_world, 6000);
    // timer_entry_t *te6 = add_timer(&min_heap, 4000, hello_world, 4000);
    // timer_entry_t *te7 = add_timer(&min_heap, 3000, hello_world, 3000);
    // timer_entry_t *te8 = add_timer(&min_heap, 2500, hello_world, 2500);
    // timer_entry_t *te9 = add_timer(&min_heap, 150, hello_world, 160);
    // timer_entry_t *te10 = add_timer(&min_heap, 770, hello_world, 770);
    // timer_entry_t *te11 = add_timer(&min_heap, 5689, hello_world, 5689);
    // timer_entry_t *te12 = add_timer(&min_heap, 5800, hello_world, 5800);
    // timer_entry_t *te13 = add_timer(&min_heap, 60000, hello_world, 60000);
    // timer_entry_t *te14 = add_timer(&min_heap, 30000, hello_world, 30000);
    // timer_entry_t *te15 = add_timer(&min_heap, 25000, hello_world, 25000);
    // timer_entry_t *te16 = add_timer(&min_heap, 800, hello_world, 800);

    // 設(shè)置種子為當(dāng)前時(shí)間
    srand((unsigned int)time(NULL));

    for (int i = 0; i < 2000; i++)
    {
        // 生成100到25000之間的隨機(jī)數(shù)
        int random_number = 1000 + rand() % (25000 - 1000 + 1);
        add_timer(&min_heap, random_number, hello_world, random_number);
    }

    int epfd = epoll_create(1);
    struct epoll_event events[512];

    for (;;)
    {
        int nearest = find_nearest_expire_timer(&min_heap);
        int n = epoll_wait(epfd, events, 512, nearest);
        for (int i = 0; i < n; i++)
        {
            //
        }
        expire_timer(&min_heap);
    }
    return 0;
}

// gcc mh-timer.c minheap.c -o mh -I./