/src/libevent/minheap-internal.h

Source
/*
 * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson
 *
 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#ifndef MINHEAP_INTERNAL_H_INCLUDED_
#define MINHEAP_INTERNAL_H_INCLUDED_

#include "event2/event-config.h"
#include "evconfig-private.h"
#include "event2/event.h"
#include "event2/event_struct.h"
#include "event2/util.h"
#include "util-internal.h"
#include "mm-internal.h"

typedef struct min_heap
{
  struct event** p;
  size_t 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_empty_(min_heap_t* s);
static inline size_t       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, size_t 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_adjust_(min_heap_t *s, struct event* e);
static inline int      min_heap_erase_(min_heap_t* s, struct event* e);
static inline void       min_heap_shift_up_(min_heap_t* s, size_t hole_index, struct event* e);
static inline void       min_heap_shift_up_unconditional_(min_heap_t* s, size_t hole_index, struct event* e);
static inline void       min_heap_shift_down_(min_heap_t* s, size_t hole_index, struct event* e);

#define min_heap_elem_greater(a, b) \
  (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 = EV_SIZE_MAX; }
int min_heap_empty_(min_heap_t* s) { return 0 == s->n; }
size_t 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, 0, s->p[--s->n]);
    e->ev_timeout_pos.min_heap_idx = EV_SIZE_MAX;
    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 (EV_SIZE_MAX != e->ev_timeout_pos.min_heap_idx)
  {
    struct event *last = s->p[--s->n];
    size_t 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_unconditional_(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 = EV_SIZE_MAX;
    return 0;
  }
  return -1;
}

int min_heap_adjust_(min_heap_t *s, struct event *e)
{
  if (EV_SIZE_MAX == e->ev_timeout_pos.min_heap_idx) {
    return min_heap_push_(s, e);
  } else {
    size_t parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
    /* The position of e has changed; we shift it up or down
     * as needed.  We can't need to do both. */
    if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e))
      min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e);
    else
      min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e);
    return 0;
  }
}

int min_heap_reserve_(min_heap_t* s, size_t n)
{
  if (s->a < n)
  {
    struct event** p;
    size_t 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_unconditional_(min_heap_t* s, size_t hole_index, struct event* e)
{
    size_t parent = (hole_index - 1) / 2;
    do
    {
  (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
  hole_index = parent;
  parent = (hole_index - 1) / 2;
    } while (hole_index && min_heap_elem_greater(s->p[parent], e));
    (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
}

void min_heap_shift_up_(min_heap_t* s, size_t hole_index, struct event* e)
{
    size_t 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, size_t hole_index, struct event* e)
{
    size_t 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;
}

#endif /* MINHEAP_INTERNAL_H_INCLUDED_ */

Line	Count	Source
1		/*
2		* Copyright (c) 2007-2012 Niels Provos and Nick Mathewson
3		*
4		* Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
5		*
6		* Redistribution and use in source and binary forms, with or without
7		* modification, are permitted provided that the following conditions
8		* are met:
9		* 1. Redistributions of source code must retain the above copyright
10		* notice, this list of conditions and the following disclaimer.
11		* 2. Redistributions in binary form must reproduce the above copyright
12		* notice, this list of conditions and the following disclaimer in the
13		* documentation and/or other materials provided with the distribution.
14		* 3. The name of the author may not be used to endorse or promote products
15		* derived from this software without specific prior written permission.
16		*
17		* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18		* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19		* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20		* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21		* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22		* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23		* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24		* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25		* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26		* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27		*/
28		#ifndef MINHEAP_INTERNAL_H_INCLUDED_
29		#define MINHEAP_INTERNAL_H_INCLUDED_
30
31		#include "event2/event-config.h"
32		#include "evconfig-private.h"
33		#include "event2/event.h"
34		#include "event2/event_struct.h"
35		#include "event2/util.h"
36		#include "util-internal.h"
37		#include "mm-internal.h"
38
39		typedef struct min_heap
40		{
41		struct event** p;
42		size_t n, a;
43		} min_heap_t;
44
45		static inline void min_heap_ctor_(min_heap_t* s);
46		static inline void min_heap_dtor_(min_heap_t* s);
47		static inline void min_heap_elem_init_(struct event* e);
48		static inline int min_heap_elt_is_top_(const struct event *e);
49		static inline int min_heap_empty_(min_heap_t* s);
50		static inline size_t min_heap_size_(min_heap_t* s);
51		static inline struct event* min_heap_top_(min_heap_t* s);
52		static inline int min_heap_reserve_(min_heap_t* s, size_t n);
53		static inline int min_heap_push_(min_heap_t* s, struct event* e);
54		static inline struct event* min_heap_pop_(min_heap_t* s);
55		static inline int min_heap_adjust_(min_heap_t s, struct event e);
56		static inline int min_heap_erase_(min_heap_t* s, struct event* e);
57		static inline void min_heap_shift_up_(min_heap_t* s, size_t hole_index, struct event* e);
58		static inline void min_heap_shift_up_unconditional_(min_heap_t* s, size_t hole_index, struct event* e);
59		static inline void min_heap_shift_down_(min_heap_t* s, size_t hole_index, struct event* e);
60
61		#define min_heap_elem_greater(a, b) \
62	0	(evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >))
63
64	0	void min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; } Unexecuted instantiation: event.c:min_heap_ctor_ Unexecuted instantiation: evmap.c:min_heap_ctor_ Unexecuted instantiation: signal.c:min_heap_ctor_ Unexecuted instantiation: select.c:min_heap_ctor_ Unexecuted instantiation: poll.c:min_heap_ctor_ Unexecuted instantiation: epoll.c:min_heap_ctor_ Unexecuted instantiation: signalfd.c:min_heap_ctor_ Unexecuted instantiation: buffer.c:min_heap_ctor_ Unexecuted instantiation: bufferevent.c:min_heap_ctor_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_ctor_
65	0	void min_heap_dtor_(min_heap_t* s) { if (s->p) mm_free(s->p); } Unexecuted instantiation: event.c:min_heap_dtor_ Unexecuted instantiation: evmap.c:min_heap_dtor_ Unexecuted instantiation: signal.c:min_heap_dtor_ Unexecuted instantiation: select.c:min_heap_dtor_ Unexecuted instantiation: poll.c:min_heap_dtor_ Unexecuted instantiation: epoll.c:min_heap_dtor_ Unexecuted instantiation: signalfd.c:min_heap_dtor_ Unexecuted instantiation: buffer.c:min_heap_dtor_ Unexecuted instantiation: bufferevent.c:min_heap_dtor_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_dtor_
66	0	void min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = EV_SIZE_MAX; } Unexecuted instantiation: event.c:min_heap_elem_init_ Unexecuted instantiation: evmap.c:min_heap_elem_init_ Unexecuted instantiation: signal.c:min_heap_elem_init_ Unexecuted instantiation: select.c:min_heap_elem_init_ Unexecuted instantiation: poll.c:min_heap_elem_init_ Unexecuted instantiation: epoll.c:min_heap_elem_init_ Unexecuted instantiation: signalfd.c:min_heap_elem_init_ Unexecuted instantiation: buffer.c:min_heap_elem_init_ Unexecuted instantiation: bufferevent.c:min_heap_elem_init_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_elem_init_
67	0	int min_heap_empty_(min_heap_t* s) { return 0 == s->n; } Unexecuted instantiation: event.c:min_heap_empty_ Unexecuted instantiation: evmap.c:min_heap_empty_ Unexecuted instantiation: signal.c:min_heap_empty_ Unexecuted instantiation: select.c:min_heap_empty_ Unexecuted instantiation: poll.c:min_heap_empty_ Unexecuted instantiation: epoll.c:min_heap_empty_ Unexecuted instantiation: signalfd.c:min_heap_empty_ Unexecuted instantiation: buffer.c:min_heap_empty_ Unexecuted instantiation: bufferevent.c:min_heap_empty_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_empty_
68	0	size_t min_heap_size_(min_heap_t* s) { return s->n; } Unexecuted instantiation: event.c:min_heap_size_ Unexecuted instantiation: evmap.c:min_heap_size_ Unexecuted instantiation: signal.c:min_heap_size_ Unexecuted instantiation: select.c:min_heap_size_ Unexecuted instantiation: poll.c:min_heap_size_ Unexecuted instantiation: epoll.c:min_heap_size_ Unexecuted instantiation: signalfd.c:min_heap_size_ Unexecuted instantiation: buffer.c:min_heap_size_ Unexecuted instantiation: bufferevent.c:min_heap_size_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_size_
69	0	struct event* min_heap_top_(min_heap_t* s) { return s->n ? *s->p : 0; } Unexecuted instantiation: event.c:min_heap_top_ Unexecuted instantiation: evmap.c:min_heap_top_ Unexecuted instantiation: signal.c:min_heap_top_ Unexecuted instantiation: select.c:min_heap_top_ Unexecuted instantiation: poll.c:min_heap_top_ Unexecuted instantiation: epoll.c:min_heap_top_ Unexecuted instantiation: signalfd.c:min_heap_top_ Unexecuted instantiation: buffer.c:min_heap_top_ Unexecuted instantiation: bufferevent.c:min_heap_top_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_top_
70
71		int min_heap_push_(min_heap_t* s, struct event* e)
72	0	{
73	0	if (min_heap_reserve_(s, s->n + 1))
74	0	return -1;
75	0	min_heap_shift_up_(s, s->n++, e);
76	0	return 0;
77	0	} Unexecuted instantiation: event.c:min_heap_push_ Unexecuted instantiation: evmap.c:min_heap_push_ Unexecuted instantiation: signal.c:min_heap_push_ Unexecuted instantiation: select.c:min_heap_push_ Unexecuted instantiation: poll.c:min_heap_push_ Unexecuted instantiation: epoll.c:min_heap_push_ Unexecuted instantiation: signalfd.c:min_heap_push_ Unexecuted instantiation: buffer.c:min_heap_push_ Unexecuted instantiation: bufferevent.c:min_heap_push_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_push_
78
79		struct event* min_heap_pop_(min_heap_t* s)
80	0	{
81	0	if (s->n)
82	0	{
83	0	struct event* e = *s->p;
84	0	min_heap_shift_down_(s, 0, s->p[--s->n]);
85	0	e->ev_timeout_pos.min_heap_idx = EV_SIZE_MAX;
86	0	return e;
87	0	}
88	0	return 0;
89	0	} Unexecuted instantiation: event.c:min_heap_pop_ Unexecuted instantiation: evmap.c:min_heap_pop_ Unexecuted instantiation: signal.c:min_heap_pop_ Unexecuted instantiation: select.c:min_heap_pop_ Unexecuted instantiation: poll.c:min_heap_pop_ Unexecuted instantiation: epoll.c:min_heap_pop_ Unexecuted instantiation: signalfd.c:min_heap_pop_ Unexecuted instantiation: buffer.c:min_heap_pop_ Unexecuted instantiation: bufferevent.c:min_heap_pop_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_pop_
90
91		int min_heap_elt_is_top_(const struct event *e)
92	0	{
93	0	return e->ev_timeout_pos.min_heap_idx == 0;
94	0	} Unexecuted instantiation: event.c:min_heap_elt_is_top_ Unexecuted instantiation: evmap.c:min_heap_elt_is_top_ Unexecuted instantiation: signal.c:min_heap_elt_is_top_ Unexecuted instantiation: select.c:min_heap_elt_is_top_ Unexecuted instantiation: poll.c:min_heap_elt_is_top_ Unexecuted instantiation: epoll.c:min_heap_elt_is_top_ Unexecuted instantiation: signalfd.c:min_heap_elt_is_top_ Unexecuted instantiation: buffer.c:min_heap_elt_is_top_ Unexecuted instantiation: bufferevent.c:min_heap_elt_is_top_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_elt_is_top_
95
96		int min_heap_erase_(min_heap_t* s, struct event* e)
97	0	{
98	0	if (EV_SIZE_MAX != e->ev_timeout_pos.min_heap_idx)
99	0	{
100	0	struct event *last = s->p[--s->n];
101	0	size_t parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
102		/* we replace e with the last element in the heap. We might need to
103		shift it upward if it is less than its parent, or downward if it is
104		greater than one or both its children. Since the children are known
105		to be less than the parent, it can't need to shift both up and
106		down. */
107	0	if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
108	0	min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last);
109	0	else
110	0	min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
111	0	e->ev_timeout_pos.min_heap_idx = EV_SIZE_MAX;
112	0	return 0;
113	0	}
114	0	return -1;
115	0	} Unexecuted instantiation: event.c:min_heap_erase_ Unexecuted instantiation: evmap.c:min_heap_erase_ Unexecuted instantiation: signal.c:min_heap_erase_ Unexecuted instantiation: select.c:min_heap_erase_ Unexecuted instantiation: poll.c:min_heap_erase_ Unexecuted instantiation: epoll.c:min_heap_erase_ Unexecuted instantiation: signalfd.c:min_heap_erase_ Unexecuted instantiation: buffer.c:min_heap_erase_ Unexecuted instantiation: bufferevent.c:min_heap_erase_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_erase_
116
117		int min_heap_adjust_(min_heap_t s, struct event e)
118	0	{
119	0	if (EV_SIZE_MAX == e->ev_timeout_pos.min_heap_idx) {
120	0	return min_heap_push_(s, e);
121	0	} else {
122	0	size_t parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
123	0	/* The position of e has changed; we shift it up or down
124	0	* as needed. We can't need to do both. */
125	0	if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e))
126	0	min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e);
127	0	else
128	0	min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e);
129	0	return 0;
130	0	}
131	0	} Unexecuted instantiation: event.c:min_heap_adjust_ Unexecuted instantiation: evmap.c:min_heap_adjust_ Unexecuted instantiation: signal.c:min_heap_adjust_ Unexecuted instantiation: select.c:min_heap_adjust_ Unexecuted instantiation: poll.c:min_heap_adjust_ Unexecuted instantiation: epoll.c:min_heap_adjust_ Unexecuted instantiation: signalfd.c:min_heap_adjust_ Unexecuted instantiation: buffer.c:min_heap_adjust_ Unexecuted instantiation: bufferevent.c:min_heap_adjust_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_adjust_
132
133		int min_heap_reserve_(min_heap_t* s, size_t n)
134	0	{
135	0	if (s->a < n)
136	0	{
137	0	struct event** p;
138	0	size_t a = s->a ? s->a * 2 : 8;
139	0	if (a < n)
140	0	a = n;
141	0	if (!(p = (struct event*)mm_realloc(s->p, a sizeof *p)))
142	0	return -1;
143	0	s->p = p;
144	0	s->a = a;
145	0	}
146	0	return 0;
147	0	} Unexecuted instantiation: event.c:min_heap_reserve_ Unexecuted instantiation: evmap.c:min_heap_reserve_ Unexecuted instantiation: signal.c:min_heap_reserve_ Unexecuted instantiation: select.c:min_heap_reserve_ Unexecuted instantiation: poll.c:min_heap_reserve_ Unexecuted instantiation: epoll.c:min_heap_reserve_ Unexecuted instantiation: signalfd.c:min_heap_reserve_ Unexecuted instantiation: buffer.c:min_heap_reserve_ Unexecuted instantiation: bufferevent.c:min_heap_reserve_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_reserve_
148
149		void min_heap_shift_up_unconditional_(min_heap_t* s, size_t hole_index, struct event* e)
150	0	{
151	0	size_t parent = (hole_index - 1) / 2;
152	0	do
153	0	{
154	0	(s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
155	0	hole_index = parent;
156	0	parent = (hole_index - 1) / 2;
157	0	} while (hole_index && min_heap_elem_greater(s->p[parent], e));
158	0	(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
159	0	} Unexecuted instantiation: event.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: evmap.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: signal.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: select.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: poll.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: epoll.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: signalfd.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: buffer.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: bufferevent.c:min_heap_shift_up_unconditional_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_shift_up_unconditional_
160
161		void min_heap_shift_up_(min_heap_t* s, size_t hole_index, struct event* e)
162	0	{
163	0	size_t parent = (hole_index - 1) / 2;
164	0	while (hole_index && min_heap_elem_greater(s->p[parent], e))
165	0	{
166	0	(s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
167	0	hole_index = parent;
168	0	parent = (hole_index - 1) / 2;
169	0	}
170	0	(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
171	0	} Unexecuted instantiation: event.c:min_heap_shift_up_ Unexecuted instantiation: evmap.c:min_heap_shift_up_ Unexecuted instantiation: signal.c:min_heap_shift_up_ Unexecuted instantiation: select.c:min_heap_shift_up_ Unexecuted instantiation: poll.c:min_heap_shift_up_ Unexecuted instantiation: epoll.c:min_heap_shift_up_ Unexecuted instantiation: signalfd.c:min_heap_shift_up_ Unexecuted instantiation: buffer.c:min_heap_shift_up_ Unexecuted instantiation: bufferevent.c:min_heap_shift_up_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_shift_up_
172
173		void min_heap_shift_down_(min_heap_t* s, size_t hole_index, struct event* e)
174	0	{
175	0	size_t min_child = 2 * (hole_index + 1);
176	0	while (min_child <= s->n)
177	0	{
178	0	min_child -= min_child == s->n \|\| min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
179	0	if (!(min_heap_elem_greater(e, s->p[min_child])))
180	0	break;
181	0	(s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
182	0	hole_index = min_child;
183	0	min_child = 2 * (hole_index + 1);
184	0	}
185	0	(s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
186	0	} Unexecuted instantiation: event.c:min_heap_shift_down_ Unexecuted instantiation: evmap.c:min_heap_shift_down_ Unexecuted instantiation: signal.c:min_heap_shift_down_ Unexecuted instantiation: select.c:min_heap_shift_down_ Unexecuted instantiation: poll.c:min_heap_shift_down_ Unexecuted instantiation: epoll.c:min_heap_shift_down_ Unexecuted instantiation: signalfd.c:min_heap_shift_down_ Unexecuted instantiation: buffer.c:min_heap_shift_down_ Unexecuted instantiation: bufferevent.c:min_heap_shift_down_ Unexecuted instantiation: bufferevent_ratelim.c:min_heap_shift_down_
187
188		#endif /* MINHEAP_INTERNAL_H_INCLUDED_ */

Coverage Report

Created: 2025-10-28 06:56