3、libevent【最小堆minheap】
程序员文章站
2024-02-13 16:52:10
...
最小堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。libevent的最小堆是通过数组的形式实现的，索引从0开始，下面的图片表示堆与索引的关系，该索引与数组下标是相同的，其中最小堆即为索引0的元素不大于1和2的元素，1的元素不大于3和4的，2的元素不大于5和6的元素。
min_heap_shift_up_ 插入元素后向上调整
min_heap_shift_down_ 元素向下调整（删除元素）
1、堆定义
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
首先，就是该最小堆的结构体，p表示堆的内容，n表示堆现在的大小，a表示堆总的分配空间的大小（包括还没使用的）。
2、堆的构造
static inline void min_heap_ctor(min_heap_t* s);
void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
堆的所有操作使用的都是内联函数，构造函数很简单，就是将结构体的内容全部用0初始化。
3、堆的析构
static inline void min_heap_dtor(min_heap_t* s);
void min_heap_dtor(min_heap_t* s) { if (s->p) mm_free(s->p); }
堆的析构也很简单，就是单纯的判断一下是否为堆分配过空间，如果分配过，就释放。
4、堆的内容初始化
static inline void min_heap_elem_init(struct event* e);
void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
该函数对堆的内容，也就是结构体中p所指向的数组成员的初始化。将该元素的索引min_heap_idx置为-1。
5、判断堆是否为空
static inline int min_heap_empty(min_heap_t* s);
int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
通过判断成员n是否为0。
6、判断堆的大小
static inline unsigned min_heap_size(min_heap_t* s);
unsigned min_heap_size(min_heap_t* s) { return s->n; }
成员n表示堆的大小。
7、堆的顶点元素
static inline struct event* min_heap_top(min_heap_t* s);
struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
p指向的第一个元素即为顶点元素
8、向堆中添加元素
static inline int min_heap_push(min_heap_t* s, struct event* e);
int min_heap_push(min_heap_t* s, struct event* e)
{
if (min_heap_reserve(s, s->n + 1))
return -1;
min_heap_shift_up_(s, s->n++, e);
return 0;
}
该函数包含调用了两个函数接口，其中min_heap_reserve定义如下：
static inline int min_heap_reserve(min_heap_t* s, unsigned n);
int min_heap_reserve(min_heap_t* s, unsigned n)
{
if (s->a < n)
{
struct event** p;
unsigned a = s->a ? s->a * 2 : 8;
if (a < n)
a = n;
if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
该函数很简单，n表示堆的元素的个数，首先判断元素a（堆总大小）是否小于n，如果小于，表示堆的空间不够用了，需要分配新的空间，通过realloc分配更大的空间，当原来堆为空时，默认分配8个元素的空间；当原来堆不为空，分配原来两倍的空间。
即在min_heap_push函数中，先判断需不需要分配更大的空间，然后调用min_heap_shift_up_，该函数定义如下：
static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
{
unsigned parent = (hole_index - 1) / 2;
while (hole_index && min_heap_elem_greater(s->p[parent], e))
{
(s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
int min_heap_elem_greater(struct event *a, struct event *b)
{
return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);
}
该函数的意思是将索引为hole_index的元素e根据大小尝试向上移动。即先将新加入的元素默认为树的最后一个元素，然后通过该函数，将新加入的元素通过最小堆原则，即父不大于子的原则，向上移动到合适的位置。首先获取该节点的父节点，通过判断该节点的父节点是否大于该节点，如果大于，需要将父节点与本节点交换位置。并再次获取现在位置的父节点，继续判断，直到满足hole_index为0，即该节点已经为顶点节点，或者该节点的父节点不大于该节点为止。然后将当前的索引赋值给新加入的元素
9、从堆中拿出顶点元素
static inline struct event* min_heap_pop(min_heap_t* s);
struct event* min_heap_pop(min_heap_t* s)
{
if (s->n)
{
struct event* e = *s->p;
min_heap_shift_down_(s, 0u, s->p[--s->n]);
e->ev_timeout_pos.min_heap_idx = -1;
return e;
}
return 0;
}
从堆中拿出顶点元素后，需要将堆重新排列，组成新的堆。该函数使用的策略为先将最后一个元素升级为顶点元素，然后对该元素尝试向下移动，其中min_heap_shift_down_即实现尝试向下移动的功能。
static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{
unsigned min_child = 2 * (hole_index + 1);
while (min_child <= s->n)
{
min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
if (!(min_heap_elem_greater(e, s->p[min_child])))
break;
(s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
该函数尝试将索引为hole_index的元素e向下移动到合适的位置。该函数首先获取该节点的右子节点，然后通过获取它的两个子节点的最小值。min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);该语句有一点复杂。首先，该语句先判断min_child==s->n，该判断如果相等，表示索引为hole_index的节点没有右子节点，其左子节点即为该堆的最后一个元素，那么||判断直接为真，min_child-=1来获取该左节点；如果min_child！=s->n，再通过判断右子节点是否大于左子节点，如果大于，||为真，min_child-=1获取该左子节点；否则表示右子节点小，min_child不需要减1。然后通过min_heap_elem_greater(e, s->p[min_child])判断该节点是否小于其最小的子节点，如果大于，需要将该节点与其子节点换位，并继续与之后的子节点做相同的处理。直到移动到合适的位置。
然后在min_heap_pop函数中返回顶点元素。
10、判断某元素是否为顶点元素
static inline int min_heap_elt_is_top(const struct event *e);
int min_heap_elt_is_top(const struct event *e)
{
return e->ev_timeout_pos.min_heap_idx == 0;
}
通过判断该元素的索引是否为0
11、删除某个元素
static inline int min_heap_erase(min_heap_t* s, struct event* e);
int min_heap_erase(min_heap_t* s, struct event* e)
{
if (-1 != e->ev_timeout_pos.min_heap_idx)
{
struct event *last = s->p[--s->n];
unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
/* we replace e with the last element in the heap. We might need to
shift it upward if it is less than its parent, or downward if it is
greater than one or both its children. Since the children are known
to be less than the parent, it can't need to shift both up and
down. */
if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);
else
min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
e->ev_timeout_pos.min_heap_idx = -1;
return 0;
}
return -1;
}
首先判断该元素的索引是否有效，如果有效，将该元素与最后一个元素换位置（实际上还并没有真正交换，只是通过下面的处理，可以看出是将最后一个元素提到要删除的元素位置，并进行处理）。判断该元素的父节点与最后一个元素的关系，如果父节点大，需要尝试将最后一个元素向上移动（当前要将最后一个元素的位置按照删除的元素的位置处理）；否则，尝试将最后一个节点向下移动。
可以看到，该函数几乎和min_heap_shift_up_是一样的，参数也是一样的，表示将位于hole_index的元素e向上移动，唯一的区别是，该函数先处理一遍循环再判断，原因很简单，在min_heap_erase_函数中已经判断过了if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))，所以第一次执行不需要判断了。
案例：
//test.cpp:提取的libevent定时器代码，定时循环10次，根据参数也可一直启动定时器
#ifndef MY_TIMER_H
#define MY_TIMER_H
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#include <unistd.h>
#include <iostream>
#define mm_malloc(sz) malloc(sz)
#define mm_calloc(n, sz) calloc((n), (sz))
#define mm_strdup(s) strdup(s)
#define mm_realloc(p, sz) realloc((p), (sz))
#define mm_free(p) free(p)
#define evutil_timercmp(tvp, uvp, cmp) \
(((tvp)->tv_sec == (uvp)->tv_sec) ? \
((tvp)->tv_usec cmp (uvp)->tv_usec) : \
((tvp)->tv_sec cmp (uvp)->tv_sec))
#define evutil_timersub(tvp, uvp, vvp) \
do { \
(vvp)->tv_sec = (tvp)->tv_sec - (uvp)->tv_sec; \
(vvp)->tv_usec = (tvp)->tv_usec - (uvp)->tv_usec; \
if ((vvp)->tv_usec < 0) { \
(vvp)->tv_sec--; \
(vvp)->tv_usec += 1000000; \
} \
} while (0)
#define evutil_timeradd(tvp, uvp, vvp) \
do { \
(vvp)->tv_sec = (tvp)->tv_sec + (uvp)->tv_sec; \
(vvp)->tv_usec = (tvp)->tv_usec + (uvp)->tv_usec; \
if ((vvp)->tv_usec >= 1000000) { \
(vvp)->tv_sec++; \
(vvp)->tv_usec -= 1000000; \
} \
} while (0)
struct event
{
/* for managing timeouts */
union {
//TAILQ_ENTRY(event) ev_next_with_common_timeout;
int min_heap_idx;
} ev_timeout_pos;
unsigned int timer_id;
struct timeval ev_interval;
struct timeval ev_timeout;
int ev_exe_num;
void (*ev_callback)(void *arg);
void *ev_arg;
int ev_res; /* result passed to event callback */
int ev_flags;
};
static inline void gettime(struct timeval *tm);
void gettime(struct timeval *tm)
{
gettimeofday(tm, NULL);
}
typedef struct min_heap
{
struct event** p;
unsigned n, a;
} min_heap_t;
static inline void min_heap_ctor(min_heap_t* s);
static inline void min_heap_dtor(min_heap_t* s);
static inline void min_heap_elem_init(struct event* e);
static inline int min_heap_elt_is_top(const struct event *e);
static inline int min_heap_elem_greater(struct event *a, struct event *b);
static inline int min_heap_empty(min_heap_t* s);
static inline unsigned min_heap_size(min_heap_t* s);
static inline struct event* min_heap_top(min_heap_t* s);
static inline int min_heap_reserve(min_heap_t* s, unsigned n);
static inline int min_heap_push(min_heap_t* s, struct event* e);
static inline struct event* min_heap_pop(min_heap_t* s);
static inline int min_heap_erase(min_heap_t* s, struct event* e);
static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
int min_heap_elem_greater(struct event *a, struct event *b)
{
return evutil_timercmp(&a->ev_timeout, &b->ev_timeout, >);
}
void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
void min_heap_dtor(min_heap_t* s) { if (s->p) mm_free(s->p); }
void min_heap_elem_init(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
unsigned min_heap_size(min_heap_t* s) { return s->n; }
struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
int min_heap_push(min_heap_t* s, struct event* e)
{
if (min_heap_reserve(s, s->n + 1))
return -1;
min_heap_shift_up_(s, s->n++, e);
return 0;
}
struct event* min_heap_pop(min_heap_t* s)
{
if (s->n)
{
struct event* e = *s->p;
min_heap_shift_down_(s, 0u, s->p[--s->n]);
e->ev_timeout_pos.min_heap_idx = -1;
return e;
}
return 0;
}
int min_heap_elt_is_top(const struct event *e)
{
return e->ev_timeout_pos.min_heap_idx == 0;
}
int min_heap_erase(min_heap_t* s, struct event* e)
{
if (-1 != e->ev_timeout_pos.min_heap_idx)
{
struct event *last = s->p[--s->n];
unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
/* we replace e with the last element in the heap. We might need to
shift it upward if it is less than its parent, or downward if it is
greater than one or both its children. Since the children are known
to be less than the parent, it can't need to shift both up and
down. */
if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
min_heap_shift_up_(s, e->ev_timeout_pos.min_heap_idx, last);
else
min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
e->ev_timeout_pos.min_heap_idx = -1;
return 0;
}
return -1;
}
int min_heap_reserve(min_heap_t* s, unsigned n)
{
if (s->a < n)
{
struct event** p;
unsigned a = s->a ? s->a * 2 : 8;
if (a < n)
a = n;
if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
return -1;
s->p = p;
s->a = a;
}
return 0;
}
void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
{
unsigned parent = (hole_index - 1) / 2;
while (hole_index && min_heap_elem_greater(s->p[parent], e))
{
(s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = parent;
parent = (hole_index - 1) / 2;
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
{
unsigned min_child = 2 * (hole_index + 1);
while (min_child <= s->n)
{
min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
if (!(min_heap_elem_greater(e, s->p[min_child])))
break;
(s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
hole_index = min_child;
min_child = 2 * (hole_index + 1);
}
(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}
#define LIMIT_TIMER 1 //有限次数定时器
#define CYCLE_TIMER 2 //循环定时器
class Timer
{
public:
Timer();
virtual ~Timer();
/**************************************
* input: interval: 每次执行的时间隔间, 单位是毫秒。
* fun arg : 回调函数以及参数。
* flag : 循环定时器还是有限次数定时器，如果是相对定时器
* exe_num : 只有在有限次数定时器才有效，表示执行的次数。最少为1次
* return: 生成定时器的ID
**************************************/
unsigned int timer_add(int interval, void (*fun)(void*), void *arg, int flag = CYCLE_TIMER,
int exe_num = 0);
/***************************************
* description:
* 去掉已经加入的定时器，比如产生定时器的母体已经消亡了，在消亡之间要将其删除。
* 相对定时器在任务完成后会Timer会自己释放掉。
***************************************/
bool timer_remove(unsigned int timer_id);
/***************************************
* description: Timer属于被动对象，没有自己的执行线程，属于被调用者。这样主要是为了避免产生线程同步。
* 定时器的循环处理函数，由定时器的拥有者进行循环调用。它的最小时间间隔决定了定时器的精度。
***************************************/
int timer_process();
private:
struct min_heap _min_heap;
unsigned int _timer_id;
};
#endif // MY_TIMER_H
Timer::Timer() :
_timer_id(0)
{
min_heap_ctor(&_min_heap);
}
Timer::~Timer()
{
for (unsigned int i = 0; i < _min_heap.n; i++)
{
if(_min_heap.p[i])
free(_min_heap.p[i]);
}
min_heap_dtor(&_min_heap);
}
unsigned int Timer::timer_add(int interval, void(*fun)(void*), void *arg,
int flag /* = CYCLE_TIMER */, int exe_num /* = 0 */)
{
struct event * ev = (struct event*) malloc(sizeof(struct event));
min_heap_elem_init(ev);
if (NULL == ev)
return 0xffffffff;
struct timeval now;
gettime(&now);
ev->ev_interval.tv_sec = interval / 1000;
ev->ev_interval.tv_usec = (interval % 1000) * 1000;
evutil_timeradd(&now, &(ev->ev_interval), &(ev->ev_timeout));
ev->ev_flags = flag;
ev->ev_callback = fun;
ev->ev_arg = arg;
ev->ev_exe_num = exe_num;
ev->timer_id = _timer_id++;
min_heap_push(&_min_heap, ev);
return ev->timer_id;
}
bool Timer::timer_remove(unsigned int timer_id)
{
for (unsigned int i = 0; i < _min_heap.n; i++)
{
if (timer_id == _min_heap.p[i]->timer_id)
{
struct event * e = _min_heap.p[i];
min_heap_erase(&_min_heap, _min_heap.p[i]);
if(e)
free(e);
return true;
}
}
return false;
}
int Timer::timer_process()
{
struct event *event;
struct timeval now;
while ((event = min_heap_top(&_min_heap)) != NULL)
{
gettime(&now);
if (evutil_timercmp(&now, &(event->ev_timeout), < ))
break;
min_heap_pop(&_min_heap);
event->ev_callback(event->ev_arg);
if (event->ev_flags == CYCLE_TIMER
|| (event->ev_flags == LIMIT_TIMER && --event->ev_exe_num > 0))
{
evutil_timeradd(&(event->ev_timeout), &(event->ev_interval), &(event->ev_timeout));
min_heap_push(&_min_heap, event);
}
else
{
free(event);
}
}
return 0;
}
using namespace std;
static void fun(void *arg)
{
//int *id = (int *) arg;
//cout << *id << endl;
struct timeval tv;
gettimeofday(&tv, NULL);
printf("second: %ld ", tv.tv_sec + tv.tv_usec / 1000); // 秒
time_t timep;
time (&timep);
printf("%s\n", asctime(gmtime(&timep)));
}
int main()
{
Timer t;
int id1 = 100;
t.timer_add(1000, fun, &id1, LIMIT_TIMER, 10);//ms
//int id2 = 101;
//t.timer_add(5000, fun, &id2);
//int id3 = 102;
//t.timer_add(3000, fun, &id3);
while (true)
{
t.timer_process();
sleep(1);
}
system("pause");
return 0;
}
sudo g++ -g test.cpp -o test.linux -Wal
sudo ./test.linux
上一篇： Python学习：批量裁剪图片数据
下一篇： Python实现多文件批量裁剪