1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <unistd.h>
5 #include <errno.h>
6 #include "logger.h"
7 #include "fast_timer.h"
8
fast_timer_init(FastTimer * timer,const int slot_count,const int64_t current_time)9 int fast_timer_init(FastTimer *timer, const int slot_count,
10 const int64_t current_time)
11 {
12 int bytes;
13 if (slot_count <= 0 || current_time <= 0) {
14 return EINVAL;
15 }
16
17 timer->slot_count = slot_count;
18 timer->base_time = current_time; //base time for slot 0
19 timer->current_time = current_time;
20 bytes = sizeof(FastTimerSlot) * slot_count;
21 timer->slots = (FastTimerSlot *)malloc(bytes);
22 if (timer->slots == NULL) {
23 return errno != 0 ? errno : ENOMEM;
24 }
25 memset(timer->slots, 0, bytes);
26 return 0;
27 }
28
fast_timer_destroy(FastTimer * timer)29 void fast_timer_destroy(FastTimer *timer)
30 {
31 if (timer->slots != NULL) {
32 free(timer->slots);
33 timer->slots = NULL;
34 }
35 }
36
37 #define TIMER_GET_SLOT_INDEX(timer, expires) \
38 (((expires) - timer->base_time) % timer->slot_count)
39
40 #define TIMER_GET_SLOT_POINTER(timer, expires) \
41 (timer->slots + TIMER_GET_SLOT_INDEX(timer, expires))
42
fast_timer_add(FastTimer * timer,FastTimerEntry * entry)43 int fast_timer_add(FastTimer *timer, FastTimerEntry *entry)
44 {
45 FastTimerSlot *slot;
46
47 slot = TIMER_GET_SLOT_POINTER(timer, entry->expires >
48 timer->current_time ? entry->expires : timer->current_time);
49 entry->next = slot->head.next;
50 if (slot->head.next != NULL) {
51 slot->head.next->prev = entry;
52 }
53 entry->prev = &slot->head;
54 slot->head.next = entry;
55 entry->rehash = false;
56 return 0;
57 }
58
fast_timer_modify(FastTimer * timer,FastTimerEntry * entry,const int64_t new_expires)59 int fast_timer_modify(FastTimer *timer, FastTimerEntry *entry,
60 const int64_t new_expires)
61 {
62 if (new_expires == entry->expires) {
63 return 0;
64 }
65
66 if (new_expires < entry->expires) {
67 fast_timer_remove(timer, entry);
68 entry->expires = new_expires;
69 return fast_timer_add(timer, entry);
70 }
71
72 entry->rehash = TIMER_GET_SLOT_INDEX(timer, new_expires) !=
73 TIMER_GET_SLOT_INDEX(timer, entry->expires);
74 entry->expires = new_expires; //lazy move
75 return 0;
76 }
77
fast_timer_remove(FastTimer * timer,FastTimerEntry * entry)78 int fast_timer_remove(FastTimer *timer, FastTimerEntry *entry)
79 {
80 if (entry->prev == NULL) {
81 return ENOENT; //already removed
82 }
83
84 if (entry->next != NULL) {
85 entry->next->prev = entry->prev;
86 entry->prev->next = entry->next;
87 entry->next = NULL;
88 }
89 else {
90 entry->prev->next = NULL;
91 }
92
93 entry->prev = NULL;
94 return 0;
95 }
96
fast_timer_slot_get(FastTimer * timer,const int64_t current_time)97 FastTimerSlot *fast_timer_slot_get(FastTimer *timer, const int64_t current_time)
98 {
99 if (timer->current_time >= current_time) {
100 return NULL;
101 }
102
103 return TIMER_GET_SLOT_POINTER(timer, timer->current_time++);
104 }
105
fast_timer_timeouts_get(FastTimer * timer,const int64_t current_time,FastTimerEntry * head)106 int fast_timer_timeouts_get(FastTimer *timer, const int64_t current_time,
107 FastTimerEntry *head)
108 {
109 FastTimerSlot *slot;
110 FastTimerEntry *entry;
111 FastTimerEntry *first;
112 FastTimerEntry *last;
113 FastTimerEntry *tail;
114 int count;
115
116 head->prev = NULL;
117 head->next = NULL;
118 if (timer->current_time >= current_time) {
119 return 0;
120 }
121
122 first = NULL;
123 last = NULL;
124 tail = head;
125 count = 0;
126 while (timer->current_time < current_time) {
127 slot = TIMER_GET_SLOT_POINTER(timer, timer->current_time++);
128 entry = slot->head.next;
129 while (entry != NULL) {
130 if (entry->expires >= current_time) { //not expired
131 if (first != NULL) {
132 first->prev->next = entry;
133 entry->prev = first->prev;
134
135 tail->next = first;
136 first->prev = tail;
137 tail = last;
138 first = NULL;
139 }
140 if (entry->rehash) {
141 last = entry;
142 entry = entry->next;
143
144 last->rehash = false;
145 fast_timer_remove(timer, last);
146 fast_timer_add(timer, last);
147 continue;
148 }
149 }
150 else { //expired
151 count++;
152 if (first == NULL) {
153 first = entry;
154 }
155 }
156
157 last = entry;
158 entry = entry->next;
159 }
160
161 if (first != NULL) {
162 first->prev->next = NULL;
163
164 tail->next = first;
165 first->prev = tail;
166 tail = last;
167 first = NULL;
168 }
169 }
170
171 if (count > 0) {
172 tail->next = NULL;
173 }
174
175 return count;
176 }
177
178