1/*	$OpenBSD: min_heap.h,v 1.6 2019/04/29 17:11:52 tobias 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
34typedef struct min_heap {
35	struct event **p;
36	size_t n, a;
37} min_heap_t;
38
39static inline void min_heap_ctor(min_heap_t * s);
40static inline void min_heap_dtor(min_heap_t * s);
41static inline void min_heap_elem_init(struct event * e);
42static inline int min_heap_elem_greater(struct event * a, struct event * b);
43static inline int min_heap_empty(min_heap_t * s);
44static inline size_t min_heap_size(min_heap_t * s);
45static inline struct event *min_heap_top(min_heap_t * s);
46static inline int min_heap_reserve(min_heap_t * s, size_t n);
47static inline int min_heap_push(min_heap_t * s, struct event * e);
48static inline struct event *min_heap_pop(min_heap_t * s);
49static inline int min_heap_erase(min_heap_t * s, struct event * e);
50static inline void min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e);
51static inline void min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e);
52
53int
54min_heap_elem_greater(struct event * a, struct event * b)
55{
56	return timercmp(&a->ev_timeout, &b->ev_timeout, >);
57}
58
59void
60min_heap_ctor(min_heap_t * s)
61{
62	s->p = 0;
63	s->n = 0;
64	s->a = 0;
65}
66void min_heap_dtor(min_heap_t * s) {
67	if (s->p)
68		free(s->p);
69}
70void
71min_heap_elem_init(struct event * e)
72{
73	e->min_heap_idx = SIZE_MAX;
74}
75int
76min_heap_empty(min_heap_t * s)
77{
78	return 0 == s->n;
79}
80size_t
81min_heap_size(min_heap_t * s)
82{
83	return s->n;
84}
85struct event *
86min_heap_top(min_heap_t * s)
87{
88	return s->n ? *s->p : 0;
89}
90
91int
92min_heap_push(min_heap_t * s, struct event * e)
93{
94	if (min_heap_reserve(s, s->n + 1))
95		return -1;
96	min_heap_shift_up_(s, s->n++, e);
97	return 0;
98}
99
100struct event *
101min_heap_pop(min_heap_t * s)
102{
103	if (s->n) {
104		struct event *e = *s->p;
105		min_heap_shift_down_(s, 0, s->p[--s->n]);
106		e->min_heap_idx = SIZE_MAX;
107		return e;
108	}
109	return 0;
110}
111
112int
113min_heap_erase(min_heap_t * s, struct event * e)
114{
115	if (e->min_heap_idx != SIZE_MAX) {
116		struct event *last = s->p[--s->n];
117		size_t parent = (e->min_heap_idx - 1) / 2;
118		/*
119		 * we replace e with the last element in the heap.  We might
120		 * need to shift it upward if it is less than its parent, or
121		 * downward if it is greater than one or both its children.
122		 * Since the children are known to be less than the parent,
123		 * it can't need to shift both up and down.
124		 */
125		if (e->min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
126			min_heap_shift_up_(s, e->min_heap_idx, last);
127		else
128			min_heap_shift_down_(s, e->min_heap_idx, last);
129		e->min_heap_idx = SIZE_MAX;
130		return 0;
131	}
132	return -1;
133}
134
135int
136min_heap_reserve(min_heap_t * s, size_t n)
137{
138	if (s->a < n) {
139		struct event **p;
140		size_t a = s->a ? s->a * 2 : 8;
141		if (a < n)
142			a = n;
143		if (!(p = recallocarray(s->p, s->a, a, sizeof *p)))
144			return -1;
145		s->p = p;
146		s->a = a;
147	}
148	return 0;
149}
150
151void
152min_heap_shift_up_(min_heap_t * s, size_t hole_index, struct event * e)
153{
154	size_t parent = (hole_index - 1) / 2;
155	while (hole_index && min_heap_elem_greater(s->p[parent], e)) {
156		s->p[hole_index] = s->p[parent];
157		s->p[hole_index]->min_heap_idx = hole_index;
158		hole_index = parent;
159		parent = (hole_index - 1) / 2;
160	}
161	e->min_heap_idx = hole_index;
162	s->p[hole_index] = e;
163}
164
165void
166min_heap_shift_down_(min_heap_t * s, size_t hole_index, struct event * e)
167{
168	size_t min_child = 2 * (hole_index + 1);
169	while (min_child <= s->n) {
170		if (min_child == s->n ||
171		    min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]))
172			min_child -= 1;
173		if (!(min_heap_elem_greater(e, s->p[min_child])))
174			break;
175		s->p[hole_index] = s->p[min_child];
176		s->p[hole_index]->min_heap_idx = hole_index;
177		hole_index = min_child;
178		min_child = 2 * (hole_index + 1);
179	}
180	min_heap_shift_up_(s, hole_index, e);
181}
182#endif				/* _MIN_HEAP_H_ */
183