1 /*
2 * Copyright (c) 2017 Fastly Inc., Ltd.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20 * IN THE SOFTWARE.
21 */
22 #ifndef h2o__timerwheel_h
23 #define h2o__timerwheel_h
24
25 #include "h2o/linklist.h"
26
27 #define H2O_TIMERWHEEL_BITS_PER_WHEEL 5
28 #define H2O_TIMERWHEEL_SLOTS_PER_WHEEL (1 << H2O_TIMERWHEEL_BITS_PER_WHEEL)
29
30 typedef struct st_h2o_timerwheel_t h2o_timerwheel_t;
31
32 struct st_h2o_timerwheel_entry_t;
33
34 typedef void (*h2o_timerwheel_cb)(struct st_h2o_timerwheel_entry_t *entry);
35
36 typedef struct st_h2o_timerwheel_entry_t {
37 h2o_linklist_t _link;
38 uint64_t expire_at; /* absolute expiration time*/
39 h2o_timerwheel_cb cb;
40 } h2o_timerwheel_entry_t;
41
42 /**
43 * initializes a timer
44 */
45 static void h2o_timerwheel_init_entry(h2o_timerwheel_entry_t *entry, h2o_timerwheel_cb cb);
46 /**
47 * activates a timer
48 */
49 void h2o_timerwheel_link_abs(h2o_timerwheel_t *ctx, h2o_timerwheel_entry_t *entry, uint64_t at);
50 /**
51 * disactivates a timer
52 */
53 static void h2o_timerwheel_unlink(h2o_timerwheel_entry_t *entry);
54 /**
55 * returns whether a timer is active
56 */
57 static int h2o_timerwheel_is_linked(h2o_timerwheel_entry_t *entry);
58
59 /**
60 * creates a timerwheel
61 */
62 h2o_timerwheel_t *h2o_timerwheel_create(size_t num_wheels, uint64_t now);
63 /**
64 * destroys a timerwheel
65 */
66 void h2o_timerwheel_destroy(h2o_timerwheel_t *ctx);
67 /**
68 * display the contents of the timerwheel
69 */
70 void h2o_timerwheel_dump(h2o_timerwheel_t *ctx);
71 /**
72 * validates the timerwheel and returns the result as a boolean value
73 */
74 int h2o_timerwheel_validate(h2o_timerwheel_t *ctx);
75 /**
76 * find out the time ramaining until the next timer triggers
77 */
78 uint64_t h2o_timerwheel_get_wake_at(h2o_timerwheel_t *ctx);
79 /**
80 * collects the expired entries and returns them back to `expired`. Application must call h2o_timer_run to fire them.
81 */
82 void h2o_timerwheel_get_expired(h2o_timerwheel_t *ctx, uint64_t now, h2o_linklist_t *expired);
83 /**
84 * runs the expired timers
85 */
86 size_t h2o_timerwheel_run(h2o_timerwheel_t *ctx, uint64_t now);
87
88 /* inline definitions */
89
h2o_timerwheel_init_entry(h2o_timerwheel_entry_t * entry,h2o_timerwheel_cb cb)90 inline void h2o_timerwheel_init_entry(h2o_timerwheel_entry_t *entry, h2o_timerwheel_cb cb)
91 {
92 *entry = (h2o_timerwheel_entry_t){{NULL, NULL}, 0, cb};
93 }
94
h2o_timerwheel_is_linked(h2o_timerwheel_entry_t * entry)95 inline int h2o_timerwheel_is_linked(h2o_timerwheel_entry_t *entry)
96 {
97 return h2o_linklist_is_linked(&entry->_link);
98 }
99
h2o_timerwheel_unlink(h2o_timerwheel_entry_t * entry)100 inline void h2o_timerwheel_unlink(h2o_timerwheel_entry_t *entry)
101 {
102 if (h2o_linklist_is_linked(&entry->_link))
103 h2o_linklist_unlink(&entry->_link);
104 }
105
106 #endif
107