Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	lib/libevent/min_heap.h	Lines:	42	46	91.3 %
Date:	2017-11-13	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	✓✓	469799532	return timercmp(&a->ev_timeout, &b->ev_timeout, >);
57			}
58
59		414	void min_heap_ctor(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
60	✓✓	423	void min_heap_dtor(min_heap_t* s) { if(s->p) free(s->p); }
61		366072	void min_heap_elem_init(struct event* e) { e->min_heap_idx = -1; }
62		127716	int min_heap_empty(min_heap_t* s) { return 0u == s->n; }
63		12433764	unsigned min_heap_size(min_heap_t* s) { return s->n; }
64	✓✓	13212160	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	✗✓	18361512	if(min_heap_reserve(s, s->n + 1))
69			return -1;
70		9180756	min_heap_shift_up_(s, s->n++, e);
71		9180756	return 0;
72		9180756	}
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	✓✗	18361512	if(((unsigned int)-1) != e->min_heap_idx)
89			{
90		9180756	struct event *last = s->p[--s->n];
91		9180756	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	✓✓✓✓	15107071	if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
98		702611	min_heap_shift_up_(s, e->min_heap_idx, last);
99			else
100		8478145	min_heap_shift_down_(s, e->min_heap_idx, last);
101		9180756	e->min_heap_idx = -1;
102			return 0;
103			}
104			return -1;
105		9180756	}
106
107			int min_heap_reserve(min_heap_t* s, unsigned n)
108			{
109	✓✓	30795276	if(s->a < n)
110			{
111			struct event** p;
112	✓✓	432	unsigned a = s->a ? s->a * 2 : 8;
113	✗✓	162	if(a < n)
114			a = n;
115	✗✓	162	if(!(p = (struct event*)realloc(s->p, a sizeof *p)))
116			return -1;
117		162	s->p = p;
118		162	s->a = a;
119	✓✗	162	}
120		15397638	return 0;
121		15397638	}
122
123			void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
124			{
125		36723024	unsigned parent = (hole_index - 1) / 2;
126	✓✓✓✓	102442278	while(hole_index && min_heap_elem_greater(s->p[parent], e))
127			{
128		7249515	(s->p[hole_index] = s->p[parent])->min_heap_idx = hole_index;
129			hole_index = parent;
130		7249515	parent = (hole_index - 1) / 2;
131			}
132		18361512	(s->p[hole_index] = e)->min_heap_idx = hole_index;
133		18361512	}
134
135			void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
136			{
137		16956290	unsigned min_child = 2 * (hole_index + 1);
138	✓✓	99771786	while(min_child <= s->n)
139			{
140	✓✓	128872858	min_child -= min_child == s->n \|\| min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
141	✓✓	42958487	if(!(min_heap_elem_greater(e, s->p[min_child])))
142			break;
143		41407748	(s->p[hole_index] = s->p[min_child])->min_heap_idx = hole_index;
144			hole_index = min_child;
145		41407748	min_child = 2 * (hole_index + 1);
146			}
147		8478145	min_heap_shift_up_(s, hole_index, e);
148		8478145	}
149
150			#endif /* _MIN_HEAP_H_ */