← Back to branch summary

~jlukas79/+junk/mysql-server

« back to all changes in this revision

Viewing changes to extra/libevent/min_heap.h

manual merge 6.0-main --> 6.0-bka-review

Show diffs side-by-side

added added

removed removed

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