Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libevent/min_heap.h	Lines:	42	46	91.3 %
Date:	2017-11-07	Branches:	29	34	85.3 %


/*	$OpenBSD: min_heap.h,v 1.3 2014/10/29 22:47:29 bluhm Exp $	*/

/*
 * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
 * All rights reserved.
 *
 * 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 _MIN_HEAP_H_
#define _MIN_HEAP_H_

#include "event.h"

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_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 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) free(s->p); }
void min_heap_elem_init(struct event* e) { e->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->min_heap_idx = -1;
        return e;
    }
    return 0;
}

int min_heap_erase(min_heap_t* s, struct event* e)
{
    if(((unsigned int)-1) != e->min_heap_idx)
    {
        struct event *last = s->p[--s->n];
        unsigned parent = (e->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->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
             min_heap_shift_up_(s, e->min_heap_idx, last);
        else
             min_heap_shift_down_(s, e->min_heap_idx, last);
        e->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**)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])->min_heap_idx = hole_index;
        hole_index = parent;
        parent = (hole_index - 1) / 2;
    }
    (s->p[hole_index] = e)->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])->min_heap_idx = hole_index;
        hole_index = min_child;
        min_child = 2 * (hole_index + 1);
	}
    min_heap_shift_up_(s, hole_index,  e);
}

#endif /* _MIN_HEAP_H_ */


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: min_heap.h,v 1.3 2014/10/29 22:47:29 bluhm Exp $ */
2
3			/*
4			* Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
5			* All rights reserved.
6			*
7			* Redistribution and use in source and binary forms, with or without
8			* modification, are permitted provided that the following conditions
9			* are met:
10			* 1. Redistributions of source code must retain the above copyright
11			* notice, this list of conditions and the following disclaimer.
12			* 2. Redistributions in binary form must reproduce the above copyright
13			* notice, this list of conditions and the following disclaimer in the
14			* documentation and/or other materials provided with the distribution.
15			* 3. The name of the author may not be used to endorse or promote products
16			* derived from this software without specific prior written permission.
17			*
18			* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19			* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20			* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21			* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22			* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23			* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24			* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25			* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26			* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27			* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28			*/
29			#ifndef _MIN_HEAP_H_
30			#define _MIN_HEAP_H_
31
32			#include "event.h"
33
34			typedef struct min_heap
35			{
36			struct event** p;
37			unsigned n, a;
38			} min_heap_t;
39
40			static inline void min_heap_ctor(min_heap_t* s);
41			static inline void min_heap_dtor(min_heap_t* s);
42			static inline void min_heap_elem_init(struct event* e);
43			static inline int min_heap_elem_greater(struct event a, struct event b);
44			static inline int min_heap_empty(min_heap_t* s);
45			static inline unsigned min_heap_size(min_heap_t* s);
46			static inline struct event* min_heap_top(min_heap_t* s);
47			static inline int min_heap_reserve(min_heap_t* s, unsigned n);
48			static inline int min_heap_push(min_heap_t* s, struct event* e);
49			static inline struct event* min_heap_pop(min_heap_t* s);
50			static inline int min_heap_erase(min_heap_t* s, struct event* e);
51			static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
52			static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
53
54			int min_heap_elem_greater(struct event a, struct event b)
55			{
56	✓✓	790505860	return timercmp(&a->ev_timeout, &b->ev_timeout, >);
57			}
58
59		1436	void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
60	✓✓	808	void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
61		648410	void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
62		251206	int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
63		20817990	unsigned min_heap_size(min_heap_t* s) { return s->n; }
64	✓✓	22468548	struct event* min_heap_top(min_heap_t* s) { return s->n ? *s->p : 0; }
65
66			int min_heap_push(min_heap_t* s, struct event* e)
67			{
68	✗✓	30598924	if(min_heap_reserve(s, s->n + 1))
69			return -1;
70		15299462	min_heap_shift_up_(s, s->n++, e);
71		15299462	return 0;
72		15299462	}
73
74			struct event* min_heap_pop(min_heap_t* s)
75			{
76			if(s->n)
77			{
78			struct event* e = *s->p;
79			min_heap_shift_down_(s, 0u, s->p[--s->n]);
80			e->min_heap_idx = -1;
81			return e;
82			}
83			return 0;
84			}
85
86			int min_heap_erase(min_heap_t* s, struct event* e)
87			{
88	✓✗	30598372	if(((unsigned int)-1) != e->min_heap_idx)
89			{
90		15299186	struct event *last = s->p[--s->n];
91		15299186	unsigned parent = (e->min_heap_idx - 1) / 2;
92			/* we replace e with the last element in the heap. We might need to
93			shift it upward if it is less than its parent, or downward if it is
94			greater than one or both its children. Since the children are known
95			to be less than the parent, it can't need to shift both up and
96			down. */
97	✓✓✓✓	25078522	if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
98		1164921	min_heap_shift_up_(s, e->min_heap_idx, last);
99			else
100		14134265	min_heap_shift_down_(s, e->min_heap_idx, last);
101		15299186	e->min_heap_idx = -1;
102			return 0;
103			}
104			return -1;
105		15299186	}
106
107			int min_heap_reserve(min_heap_t* s, unsigned n)
108			{
109	✓✓	51416914	if(s->a < n)
110			{
111			struct event** p;
112	✓✓	1326	unsigned a = s->a ? s->a * 2 : 8;
113	✗✓	573	if(a < n)
114			a = n;
115	✗✓	573	if(!(p = (struct event*)realloc(s->p, a sizeof *p)))
116			return -1;
117		573	s->p = p;
118		573	s->a = a;
119	✓✗	573	}
120		25708457	return 0;
121		25708457	}
122
123			void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
124			{
125		61197296	unsigned parent = (hole_index - 1) / 2;
126	✓✓✓✓	169906328	while(hole_index && min_heap_elem_greater(s->p[parent], e))
127			{
128		11878850	(s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
129			hole_index = parent;
130		11878850	parent = (hole_index - 1) / 2;
131			}
132		30598648	(s->p[hole_index] = e)->min_heap_idx = hole_index;
133		30598648	}
134
135			void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
136			{
137		28268530	unsigned min_child = 2 * (hole_index + 1);
138	✓✓	168478064	while(min_child <= s->n)
139			{
140	✓✓	218062108	min_child -= min_child == s->n \|\| min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
141	✓✓	72688813	if(!(min_heap_elem_greater(e, s->p[min_child])))
142			break;
143		70104767	(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
144			hole_index = min_child;
145		70104767	min_child = 2 * (hole_index + 1);
146			}
147		14134265	min_heap_shift_up_(s, hole_index, e);
148		14134265	}
149
150			#endif /* _MIN_HEAP_H_ */