1*9034ec65Schristos /* $NetBSD: minheap-internal.h,v 1.5 2020/05/25 20:47:33 christos Exp $ */
22b3787f6Schristos
32b3787f6Schristos /*
42b3787f6Schristos * Copyright (c) 2007-2012 Niels Provos and Nick Mathewson
52b3787f6Schristos *
62b3787f6Schristos * Copyright (c) 2006 Maxim Yegorushkin <maxim.yegorushkin@gmail.com>
72b3787f6Schristos *
82b3787f6Schristos * Redistribution and use in source and binary forms, with or without
92b3787f6Schristos * modification, are permitted provided that the following conditions
102b3787f6Schristos * are met:
112b3787f6Schristos * 1. Redistributions of source code must retain the above copyright
122b3787f6Schristos * notice, this list of conditions and the following disclaimer.
132b3787f6Schristos * 2. Redistributions in binary form must reproduce the above copyright
142b3787f6Schristos * notice, this list of conditions and the following disclaimer in the
152b3787f6Schristos * documentation and/or other materials provided with the distribution.
162b3787f6Schristos * 3. The name of the author may not be used to endorse or promote products
172b3787f6Schristos * derived from this software without specific prior written permission.
182b3787f6Schristos *
192b3787f6Schristos * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
202b3787f6Schristos * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
212b3787f6Schristos * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
222b3787f6Schristos * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
232b3787f6Schristos * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
242b3787f6Schristos * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
252b3787f6Schristos * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
262b3787f6Schristos * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
272b3787f6Schristos * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
282b3787f6Schristos * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
292b3787f6Schristos */
302b3787f6Schristos #ifndef MINHEAP_INTERNAL_H_INCLUDED_
312b3787f6Schristos #define MINHEAP_INTERNAL_H_INCLUDED_
322b3787f6Schristos
332b3787f6Schristos #include "event2/event-config.h"
342b3787f6Schristos #include "evconfig-private.h"
352b3787f6Schristos #include "event2/event.h"
362b3787f6Schristos #include "event2/event_struct.h"
372b3787f6Schristos #include "event2/util.h"
382b3787f6Schristos #include "util-internal.h"
392b3787f6Schristos #include "mm-internal.h"
402b3787f6Schristos
412b3787f6Schristos typedef struct min_heap
422b3787f6Schristos {
432b3787f6Schristos struct event** p;
442b3787f6Schristos unsigned n, a;
452b3787f6Schristos } min_heap_t;
462b3787f6Schristos
472b3787f6Schristos static inline void min_heap_ctor_(min_heap_t* s);
482b3787f6Schristos static inline void min_heap_dtor_(min_heap_t* s);
492b3787f6Schristos static inline void min_heap_elem_init_(struct event* e);
502b3787f6Schristos static inline int min_heap_elt_is_top_(const struct event *e);
512b3787f6Schristos static inline int min_heap_empty_(min_heap_t* s);
522b3787f6Schristos static inline unsigned min_heap_size_(min_heap_t* s);
532b3787f6Schristos static inline struct event* min_heap_top_(min_heap_t* s);
542b3787f6Schristos static inline int min_heap_reserve_(min_heap_t* s, unsigned n);
552b3787f6Schristos static inline int min_heap_push_(min_heap_t* s, struct event* e);
562b3787f6Schristos static inline struct event* min_heap_pop_(min_heap_t* s);
572b3787f6Schristos static inline int min_heap_adjust_(min_heap_t *s, struct event* e);
582b3787f6Schristos static inline int min_heap_erase_(min_heap_t* s, struct event* e);
592b3787f6Schristos static inline void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e);
602b3787f6Schristos static inline void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e);
612b3787f6Schristos static inline void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e);
622b3787f6Schristos
632b3787f6Schristos #define min_heap_elem_greater(a, b) \
642b3787f6Schristos (evutil_timercmp(&(a)->ev_timeout, &(b)->ev_timeout, >))
652b3787f6Schristos
min_heap_ctor_(min_heap_t * s)662b3787f6Schristos void min_heap_ctor_(min_heap_t* s) { s->p = 0; s->n = 0; s->a = 0; }
min_heap_dtor_(min_heap_t * s)672b3787f6Schristos void min_heap_dtor_(min_heap_t* s) { if (s->p) mm_free(s->p); }
min_heap_elem_init_(struct event * e)682b3787f6Schristos void min_heap_elem_init_(struct event* e) { e->ev_timeout_pos.min_heap_idx = -1; }
min_heap_empty_(min_heap_t * s)692b3787f6Schristos int min_heap_empty_(min_heap_t* s) { return 0u == s->n; }
min_heap_size_(min_heap_t * s)702b3787f6Schristos unsigned min_heap_size_(min_heap_t* s) { return s->n; }
min_heap_top_(min_heap_t * s)712b3787f6Schristos struct event* min_heap_top_(min_heap_t* s) { return s->n ? *s->p : 0; }
722b3787f6Schristos
min_heap_push_(min_heap_t * s,struct event * e)732b3787f6Schristos int min_heap_push_(min_heap_t* s, struct event* e)
742b3787f6Schristos {
752b3787f6Schristos if (min_heap_reserve_(s, s->n + 1))
762b3787f6Schristos return -1;
772b3787f6Schristos min_heap_shift_up_(s, s->n++, e);
782b3787f6Schristos return 0;
792b3787f6Schristos }
802b3787f6Schristos
min_heap_pop_(min_heap_t * s)812b3787f6Schristos struct event* min_heap_pop_(min_heap_t* s)
822b3787f6Schristos {
832b3787f6Schristos if (s->n)
842b3787f6Schristos {
852b3787f6Schristos struct event* e = *s->p;
862b3787f6Schristos min_heap_shift_down_(s, 0u, s->p[--s->n]);
872b3787f6Schristos e->ev_timeout_pos.min_heap_idx = -1;
882b3787f6Schristos return e;
892b3787f6Schristos }
902b3787f6Schristos return 0;
912b3787f6Schristos }
922b3787f6Schristos
min_heap_elt_is_top_(const struct event * e)932b3787f6Schristos int min_heap_elt_is_top_(const struct event *e)
942b3787f6Schristos {
952b3787f6Schristos return e->ev_timeout_pos.min_heap_idx == 0;
962b3787f6Schristos }
972b3787f6Schristos
min_heap_erase_(min_heap_t * s,struct event * e)982b3787f6Schristos int min_heap_erase_(min_heap_t* s, struct event* e)
992b3787f6Schristos {
1002b3787f6Schristos if (-1 != e->ev_timeout_pos.min_heap_idx)
1012b3787f6Schristos {
1022b3787f6Schristos struct event *last = s->p[--s->n];
1032b3787f6Schristos unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
1042b3787f6Schristos /* we replace e with the last element in the heap. We might need to
1052b3787f6Schristos shift it upward if it is less than its parent, or downward if it is
1062b3787f6Schristos greater than one or both its children. Since the children are known
1072b3787f6Schristos to be less than the parent, it can't need to shift both up and
1082b3787f6Schristos down. */
1092b3787f6Schristos if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], last))
1102b3787f6Schristos min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, last);
1112b3787f6Schristos else
1122b3787f6Schristos min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, last);
1132b3787f6Schristos e->ev_timeout_pos.min_heap_idx = -1;
1142b3787f6Schristos return 0;
1152b3787f6Schristos }
1162b3787f6Schristos return -1;
1172b3787f6Schristos }
1182b3787f6Schristos
min_heap_adjust_(min_heap_t * s,struct event * e)1192b3787f6Schristos int min_heap_adjust_(min_heap_t *s, struct event *e)
1202b3787f6Schristos {
1212b3787f6Schristos if (-1 == e->ev_timeout_pos.min_heap_idx) {
1222b3787f6Schristos return min_heap_push_(s, e);
1232b3787f6Schristos } else {
1242b3787f6Schristos unsigned parent = (e->ev_timeout_pos.min_heap_idx - 1) / 2;
1252b3787f6Schristos /* The position of e has changed; we shift it up or down
1262b3787f6Schristos * as needed. We can't need to do both. */
1272b3787f6Schristos if (e->ev_timeout_pos.min_heap_idx > 0 && min_heap_elem_greater(s->p[parent], e))
1282b3787f6Schristos min_heap_shift_up_unconditional_(s, e->ev_timeout_pos.min_heap_idx, e);
1292b3787f6Schristos else
1302b3787f6Schristos min_heap_shift_down_(s, e->ev_timeout_pos.min_heap_idx, e);
1312b3787f6Schristos return 0;
1322b3787f6Schristos }
1331b6f2cd4Schristos }
1342b3787f6Schristos
min_heap_reserve_(min_heap_t * s,unsigned n)1352b3787f6Schristos int min_heap_reserve_(min_heap_t* s, unsigned n)
1362b3787f6Schristos {
1372b3787f6Schristos if (s->a < n)
1382b3787f6Schristos {
1392b3787f6Schristos struct event** p;
1402b3787f6Schristos unsigned a = s->a ? s->a * 2 : 8;
1412b3787f6Schristos if (a < n)
1422b3787f6Schristos a = n;
1432b3787f6Schristos if (!(p = (struct event**)mm_realloc(s->p, a * sizeof *p)))
1442b3787f6Schristos return -1;
1452b3787f6Schristos s->p = p;
1462b3787f6Schristos s->a = a;
1472b3787f6Schristos }
1482b3787f6Schristos return 0;
1492b3787f6Schristos }
1502b3787f6Schristos
min_heap_shift_up_unconditional_(min_heap_t * s,unsigned hole_index,struct event * e)1512b3787f6Schristos void min_heap_shift_up_unconditional_(min_heap_t* s, unsigned hole_index, struct event* e)
1522b3787f6Schristos {
1532b3787f6Schristos unsigned parent = (hole_index - 1) / 2;
1542b3787f6Schristos do
1552b3787f6Schristos {
1562b3787f6Schristos (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
1572b3787f6Schristos hole_index = parent;
1582b3787f6Schristos parent = (hole_index - 1) / 2;
1592b3787f6Schristos } while (hole_index && min_heap_elem_greater(s->p[parent], e));
1602b3787f6Schristos (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
1612b3787f6Schristos }
1622b3787f6Schristos
min_heap_shift_up_(min_heap_t * s,unsigned hole_index,struct event * e)1632b3787f6Schristos void min_heap_shift_up_(min_heap_t* s, unsigned hole_index, struct event* e)
1642b3787f6Schristos {
1652b3787f6Schristos unsigned parent = (hole_index - 1) / 2;
1662b3787f6Schristos while (hole_index && min_heap_elem_greater(s->p[parent], e))
1672b3787f6Schristos {
1682b3787f6Schristos (s->p[hole_index] = s->p[parent])->ev_timeout_pos.min_heap_idx = hole_index;
1692b3787f6Schristos hole_index = parent;
1702b3787f6Schristos parent = (hole_index - 1) / 2;
1712b3787f6Schristos }
1722b3787f6Schristos (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
1732b3787f6Schristos }
1742b3787f6Schristos
min_heap_shift_down_(min_heap_t * s,unsigned hole_index,struct event * e)1752b3787f6Schristos void min_heap_shift_down_(min_heap_t* s, unsigned hole_index, struct event* e)
1762b3787f6Schristos {
1772b3787f6Schristos unsigned min_child = 2 * (hole_index + 1);
1782b3787f6Schristos while (min_child <= s->n)
1792b3787f6Schristos {
1802b3787f6Schristos min_child -= min_child == s->n || min_heap_elem_greater(s->p[min_child], s->p[min_child - 1]);
1812b3787f6Schristos if (!(min_heap_elem_greater(e, s->p[min_child])))
1822b3787f6Schristos break;
1832b3787f6Schristos (s->p[hole_index] = s->p[min_child])->ev_timeout_pos.min_heap_idx = hole_index;
1842b3787f6Schristos hole_index = min_child;
1852b3787f6Schristos min_child = 2 * (hole_index + 1);
1862b3787f6Schristos }
1872b3787f6Schristos (s->p[hole_index] = e)->ev_timeout_pos.min_heap_idx = hole_index;
1882b3787f6Schristos }
1892b3787f6Schristos
1902b3787f6Schristos #endif /* MINHEAP_INTERNAL_H_INCLUDED_ */
191