2 * Copyright (c) 2015-2020 Red Hat, Inc.
6 * Author: Jan Friesse (jfriesse@redhat.com)
8 * This software licensed under BSD license, the text of which follows:
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions are met:
13 * - Redistributions of source code must retain the above copyright notice,
14 * this list of conditions and the following disclaimer.
15 * - Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
18 * - Neither the name of the Red Hat, Inc. nor the names of its
19 * contributors may be used to endorse or promote products derived from this
20 * software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
31 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
32 * THE POSSIBILITY OF SUCH DAMAGE.
38 #include "timer-list.h"
41 timer_list_init(struct timer_list
*tlist
)
44 memset(tlist
, 0, sizeof(*tlist
));
46 TAILQ_INIT(&tlist
->free_list
);
50 timer_list_entry_time_to_expire(const struct timer_list_entry
*entry
, PRIntervalTime current_time
)
52 PRIntervalTime diff
, half_interval
;
54 diff
= entry
->expire_time
- current_time
;
58 if (diff
> half_interval
) {
66 timer_list_entry_cmp(const struct timer_list_entry
*entry1
,
67 const struct timer_list_entry
*entry2
, PRIntervalTime current_time
)
69 PRIntervalTime diff1
, diff2
;
72 diff1
= timer_list_entry_time_to_expire(entry1
, current_time
);
73 diff2
= timer_list_entry_time_to_expire(entry2
, current_time
);
77 if (diff1
< diff2
) res
= -1;
78 if (diff1
> diff2
) res
= 1;
84 timer_list_heap_index_left(size_t index
)
87 return (2 * index
+ 1);
91 timer_list_heap_index_right(size_t index
)
94 return (2 * index
+ 2);
98 timer_list_heap_index_parent(size_t index
)
101 return ((index
- 1) / 2);
105 timer_list_heap_sift_up(struct timer_list
*tlist
, size_t item_pos
)
108 struct timer_list_entry
*parent_entry
;
109 struct timer_list_entry
*item_entry
;
111 item_entry
= tlist
->entries
[item_pos
];
113 parent_pos
= timer_list_heap_index_parent(item_pos
);
115 while (item_pos
> 0 &&
116 (parent_entry
= tlist
->entries
[parent_pos
],
117 timer_list_entry_cmp(parent_entry
, item_entry
, item_entry
->epoch
) > 0)) {
119 * Swap item and parent
121 tlist
->entries
[parent_pos
] = item_entry
;
122 tlist
->entries
[item_pos
] = parent_entry
;
124 item_pos
= parent_pos
;
125 parent_pos
= timer_list_heap_index_parent(item_pos
);
130 timer_list_heap_sift_down(struct timer_list
*tlist
, size_t item_pos
)
133 size_t left_pos
, right_pos
, smallest_pos
;
134 struct timer_list_entry
*left_entry
;
135 struct timer_list_entry
*right_entry
;
136 struct timer_list_entry
*smallest_entry
;
137 struct timer_list_entry
*tmp_entry
;
142 smallest_pos
= item_pos
;
143 left_pos
= timer_list_heap_index_left(item_pos
);
144 right_pos
= timer_list_heap_index_right(item_pos
);
146 smallest_entry
= tlist
->entries
[smallest_pos
];
148 if (left_pos
< tlist
->size
&&
149 (left_entry
= tlist
->entries
[left_pos
],
150 timer_list_entry_cmp(left_entry
, smallest_entry
, smallest_entry
->epoch
) < 0)) {
151 smallest_entry
= left_entry
;
152 smallest_pos
= left_pos
;
155 if (right_pos
< tlist
->size
&&
156 (right_entry
= tlist
->entries
[right_pos
],
157 timer_list_entry_cmp(right_entry
, smallest_entry
, smallest_entry
->epoch
) < 0)) {
158 smallest_entry
= right_entry
;
159 smallest_pos
= right_pos
;
162 if (smallest_pos
== item_pos
) {
164 * Item is smallest (or has no childs) -> heap property is restored
169 * Swap item with smallest child
171 tmp_entry
= tlist
->entries
[item_pos
];
172 tlist
->entries
[item_pos
] = smallest_entry
;
173 tlist
->entries
[smallest_pos
] = tmp_entry
;
175 item_pos
= smallest_pos
;
181 timer_list_heap_delete(struct timer_list
*tlist
, struct timer_list_entry
*entry
)
185 struct timer_list_entry
*replacement_entry
;
188 entry_pos
= tlist
->size
;
191 * Find the element index
193 for (i
= 0; i
< tlist
->size
; i
++) {
194 if (tlist
->entries
[i
] == entry
) {
200 if (entry_pos
== tlist
->size
) {
208 * Swap element with last element
210 replacement_entry
= tlist
->entries
[tlist
->size
- 1];
211 tlist
->entries
[entry_pos
] = tlist
->entries
[tlist
->size
- 1];
214 * And "remove" last element (= entry)
219 * Up (or down) heapify based on replacement item size
221 cmp_entries
= timer_list_entry_cmp(replacement_entry
, entry
, entry
->epoch
);
223 if (cmp_entries
< 0) {
224 timer_list_heap_sift_up(tlist
, entry_pos
);
225 } else if (cmp_entries
> 0) {
226 timer_list_heap_sift_down(tlist
, entry_pos
);
233 * Check if heap is valid.
234 * - Shape property is always fullfiled because of storage in array
235 * - Check heap property
238 timer_list_debug_is_valid_heap(struct timer_list
*tlist
)
241 size_t left_pos
, right_pos
;
242 struct timer_list_entry
*left_entry
;
243 struct timer_list_entry
*right_entry
;
244 struct timer_list_entry
*cur_entry
;
246 for (i
= 0; i
< tlist
->size
; i
++) {
247 cur_entry
= tlist
->entries
[i
];
249 left_pos
= timer_list_heap_index_left(i
);
250 right_pos
= timer_list_heap_index_right(i
);
252 if (left_pos
< tlist
->size
&&
253 (left_entry
= tlist
->entries
[left_pos
],
254 timer_list_entry_cmp(left_entry
, cur_entry
, cur_entry
->epoch
) < 0)) {
258 if (right_pos
< tlist
->size
&&
259 (right_entry
= tlist
->entries
[right_pos
],
260 timer_list_entry_cmp(right_entry
, cur_entry
, cur_entry
->epoch
) < 0)) {
269 timer_list_insert_into_list(struct timer_list
*tlist
, struct timer_list_entry
*new_entry
)
272 struct timer_list_entry
**new_entries
;
275 * This can overflow and it's not a problem
277 new_entry
->expire_time
= new_entry
->epoch
+ PR_MillisecondsToInterval(new_entry
->interval
);
282 if (tlist
->size
+ 1 > tlist
->allocated
) {
283 new_size
= (tlist
->allocated
+ 1) * 2;
285 new_entries
= realloc(tlist
->entries
, new_size
* sizeof(tlist
->entries
[0]));
287 if (new_entries
== NULL
) {
291 tlist
->allocated
= new_size
;
292 tlist
->entries
= new_entries
;
295 tlist
->entries
[tlist
->size
] = new_entry
;
298 timer_list_heap_sift_up(tlist
, tlist
->size
- 1);
303 struct timer_list_entry
*
304 timer_list_add(struct timer_list
*tlist
, PRUint32 interval
, timer_list_cb_fn func
, void *data1
,
307 struct timer_list_entry
*new_entry
;
309 if (interval
< 1 || interval
> TIMER_LIST_MAX_INTERVAL
|| func
== NULL
) {
313 if (!TAILQ_EMPTY(&tlist
->free_list
)) {
315 * Use free list entry
317 new_entry
= TAILQ_FIRST(&tlist
->free_list
);
318 TAILQ_REMOVE(&tlist
->free_list
, new_entry
, entries
);
323 new_entry
= malloc(sizeof(*new_entry
));
324 if (new_entry
== NULL
) {
329 memset(new_entry
, 0, sizeof(*new_entry
));
330 new_entry
->epoch
= PR_IntervalNow();
331 new_entry
->interval
= interval
;
332 new_entry
->func
= func
;
333 new_entry
->user_data1
= data1
;
334 new_entry
->user_data2
= data2
;
335 new_entry
->is_active
= 1;
337 if (timer_list_insert_into_list(tlist
, new_entry
) != 0) {
338 TAILQ_INSERT_HEAD(&tlist
->free_list
, new_entry
, entries
);
347 timer_list_reschedule(struct timer_list
*tlist
, struct timer_list_entry
*entry
)
351 if (entry
->is_active
) {
352 res
= timer_list_heap_delete(tlist
, entry
);
355 entry
->epoch
= PR_IntervalNow();
356 timer_list_insert_into_list(tlist
, entry
);
361 timer_list_expire(struct timer_list
*tlist
)
364 struct timer_list_entry
*entry
;
367 now
= PR_IntervalNow();
369 while (tlist
->size
> 0 &&
370 (entry
= tlist
->entries
[0],
371 timer_list_entry_time_to_expire(entry
, now
) == 0)) {
375 res
= entry
->func(entry
->user_data1
, entry
->user_data2
);
378 * Move item to free list
380 timer_list_delete(tlist
, entry
);
381 } else if (entry
->is_active
) {
385 res
= timer_list_heap_delete(tlist
, entry
);
389 timer_list_insert_into_list(tlist
, entry
);
395 timer_list_time_to_expire(struct timer_list
*tlist
)
397 struct timer_list_entry
*entry
;
399 if (tlist
->size
== 0) {
400 return (PR_INTERVAL_NO_TIMEOUT
);
403 entry
= tlist
->entries
[0];
405 return (timer_list_entry_time_to_expire(entry
, PR_IntervalNow()));
409 timer_list_time_to_expire_ms(struct timer_list
*tlist
)
411 struct timer_list_entry
*entry
;
414 if (tlist
->size
== 0) {
415 u32
= ~((uint32_t)0);
419 entry
= tlist
->entries
[0];
421 return (PR_IntervalToMilliseconds(timer_list_entry_time_to_expire(entry
, PR_IntervalNow())));
425 timer_list_delete(struct timer_list
*tlist
, struct timer_list_entry
*entry
)
429 if (entry
->is_active
) {
431 * Remove item from heap and move it to free list
433 res
= timer_list_heap_delete(tlist
, entry
);
436 TAILQ_INSERT_HEAD(&tlist
->free_list
, entry
, entries
);
437 entry
->is_active
= 0;
442 timer_list_free(struct timer_list
*tlist
)
444 struct timer_list_entry
*entry
;
445 struct timer_list_entry
*entry_next
;
448 for (i
= 0; i
< tlist
->size
; i
++) {
449 free(tlist
->entries
[i
]);
452 free(tlist
->entries
);
454 entry
= TAILQ_FIRST(&tlist
->free_list
);
456 while (entry
!= NULL
) {
457 entry_next
= TAILQ_NEXT(entry
, entries
);
464 timer_list_init(tlist
);