Add support for ICE/STUN/TURN in res_rtp_asterisk and chan_sip.
[asterisk/asterisk.git] / res / pjproject / pjlib / src / pj / timer.c
1 /* $Id$ */
2 /* 
3  * The PJLIB's timer heap is based (or more correctly, copied and modied)
4  * from ACE library by Douglas C. Schmidt. ACE is an excellent OO framework
5  * that implements many core patterns for concurrent communication software.
6  * If you're looking for C++ alternative of PJLIB, then ACE is your best
7  * solution.
8  *
9  * You may use this file according to ACE open source terms or PJLIB open
10  * source terms. You can find the fine ACE library at:
11  *  http://www.cs.wustl.edu/~schmidt/ACE.html
12  *
13  * ACE is Copyright (C)1993-2006 Douglas C. Schmidt <d.schmidt@vanderbilt.edu>
14  *
15  * GNU Public License:
16  * This program is free software; you can redistribute it and/or modify
17  * it under the terms of the GNU General Public License as published by
18  * the Free Software Foundation; either version 2 of the License, or
19  * (at your option) any later version.
20  *
21  * This program is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
24  * GNU General Public License for more details.
25  *
26  * You should have received a copy of the GNU General Public License
27  * along with this program; if not, write to the Free Software
28  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
29  */
30 #include <pj/timer.h>
31 #include <pj/pool.h>
32 #include <pj/os.h>
33 #include <pj/string.h>
34 #include <pj/assert.h>
35 #include <pj/errno.h>
36 #include <pj/lock.h>
37
38 #define HEAP_PARENT(X)  (X == 0 ? 0 : (((X) - 1) / 2))
39 #define HEAP_LEFT(X)    (((X)+(X))+1)
40
41
42 #define DEFAULT_MAX_TIMED_OUT_PER_POLL  (64)
43
44
45 /**
46  * The implementation of timer heap.
47  */
48 struct pj_timer_heap_t
49 {
50     /** Pool from which the timer heap resize will get the storage from */
51     pj_pool_t *pool;
52
53     /** Maximum size of the heap. */
54     pj_size_t max_size;
55
56     /** Current size of the heap. */
57     pj_size_t cur_size;
58
59     /** Max timed out entries to process per poll. */
60     unsigned max_entries_per_poll;
61
62     /** Lock object. */
63     pj_lock_t *lock;
64
65     /** Autodelete lock. */
66     pj_bool_t auto_delete_lock;
67
68     /**
69      * Current contents of the Heap, which is organized as a "heap" of
70      * pj_timer_entry *'s.  In this context, a heap is a "partially
71      * ordered, almost complete" binary tree, which is stored in an
72      * array.
73      */
74     pj_timer_entry **heap;
75
76     /**
77      * An array of "pointers" that allows each pj_timer_entry in the
78      * <heap_> to be located in O(1) time.  Basically, <timer_id_[i]>
79      * contains the slot in the <heap_> array where an pj_timer_entry
80      * with timer id <i> resides.  Thus, the timer id passed back from
81      * <schedule_entry> is really an slot into the <timer_ids> array.  The
82      * <timer_ids_> array serves two purposes: negative values are
83      * treated as "pointers" for the <freelist_>, whereas positive
84      * values are treated as "pointers" into the <heap_> array.
85      */
86     pj_timer_id_t *timer_ids;
87
88     /**
89      * "Pointer" to the first element in the freelist contained within
90      * the <timer_ids_> array, which is organized as a stack.
91      */
92     pj_timer_id_t timer_ids_freelist;
93
94     /** Callback to be called when a timer expires. */
95     pj_timer_heap_callback *callback;
96
97 };
98
99
100
101 PJ_INLINE(void) lock_timer_heap( pj_timer_heap_t *ht )
102 {
103     if (ht->lock) {
104         pj_lock_acquire(ht->lock);
105     }
106 }
107
108 PJ_INLINE(void) unlock_timer_heap( pj_timer_heap_t *ht )
109 {
110     if (ht->lock) {
111         pj_lock_release(ht->lock);
112     }
113 }
114
115
116 static void copy_node( pj_timer_heap_t *ht, int slot, pj_timer_entry *moved_node )
117 {
118     PJ_CHECK_STACK();
119
120     // Insert <moved_node> into its new location in the heap.
121     ht->heap[slot] = moved_node;
122     
123     // Update the corresponding slot in the parallel <timer_ids_> array.
124     ht->timer_ids[moved_node->_timer_id] = slot;
125 }
126
127 static pj_timer_id_t pop_freelist( pj_timer_heap_t *ht )
128 {
129     // We need to truncate this to <int> for backwards compatibility.
130     pj_timer_id_t new_id = ht->timer_ids_freelist;
131     
132     PJ_CHECK_STACK();
133
134     // The freelist values in the <timer_ids_> are negative, so we need
135     // to negate them to get the next freelist "pointer."
136     ht->timer_ids_freelist =
137         -ht->timer_ids[ht->timer_ids_freelist];
138     
139     return new_id;
140     
141 }
142
143 static void push_freelist (pj_timer_heap_t *ht, pj_timer_id_t old_id)
144 {
145     PJ_CHECK_STACK();
146
147     // The freelist values in the <timer_ids_> are negative, so we need
148     // to negate them to get the next freelist "pointer."
149     ht->timer_ids[old_id] = -ht->timer_ids_freelist;
150     ht->timer_ids_freelist = old_id;
151 }
152
153
154 static void reheap_down(pj_timer_heap_t *ht, pj_timer_entry *moved_node,
155                         size_t slot, size_t child)
156 {
157     PJ_CHECK_STACK();
158
159     // Restore the heap property after a deletion.
160     
161     while (child < ht->cur_size)
162     {
163         // Choose the smaller of the two children.
164         if (child + 1 < ht->cur_size
165             && PJ_TIME_VAL_LT(ht->heap[child + 1]->_timer_value, ht->heap[child]->_timer_value))
166             child++;
167         
168         // Perform a <copy> if the child has a larger timeout value than
169         // the <moved_node>.
170         if (PJ_TIME_VAL_LT(ht->heap[child]->_timer_value, moved_node->_timer_value))
171         {
172             copy_node( ht, slot, ht->heap[child]);
173             slot = child;
174             child = HEAP_LEFT(child);
175         }
176         else
177             // We've found our location in the heap.
178             break;
179     }
180     
181     copy_node( ht, slot, moved_node);
182 }
183
184 static void reheap_up( pj_timer_heap_t *ht, pj_timer_entry *moved_node,
185                        size_t slot, size_t parent)
186 {
187     // Restore the heap property after an insertion.
188     
189     while (slot > 0)
190     {
191         // If the parent node is greater than the <moved_node> we need
192         // to copy it down.
193         if (PJ_TIME_VAL_LT(moved_node->_timer_value, ht->heap[parent]->_timer_value))
194         {
195             copy_node(ht, slot, ht->heap[parent]);
196             slot = parent;
197             parent = HEAP_PARENT(slot);
198         }
199         else
200             break;
201     }
202     
203     // Insert the new node into its proper resting place in the heap and
204     // update the corresponding slot in the parallel <timer_ids> array.
205     copy_node(ht, slot, moved_node);
206 }
207
208
209 static pj_timer_entry * remove_node( pj_timer_heap_t *ht, size_t slot)
210 {
211     pj_timer_entry *removed_node = ht->heap[slot];
212     
213     // Return this timer id to the freelist.
214     push_freelist( ht, removed_node->_timer_id );
215     
216     // Decrement the size of the heap by one since we're removing the
217     // "slot"th node.
218     ht->cur_size--;
219     
220     // Set the ID
221     removed_node->_timer_id = -1;
222
223     // Only try to reheapify if we're not deleting the last entry.
224     
225     if (slot < ht->cur_size)
226     {
227         int parent;
228         pj_timer_entry *moved_node = ht->heap[ht->cur_size];
229         
230         // Move the end node to the location being removed and update
231         // the corresponding slot in the parallel <timer_ids> array.
232         copy_node( ht, slot, moved_node);
233         
234         // If the <moved_node->time_value_> is great than or equal its
235         // parent it needs be moved down the heap.
236         parent = HEAP_PARENT (slot);
237         
238         if (PJ_TIME_VAL_GTE(moved_node->_timer_value, ht->heap[parent]->_timer_value))
239             reheap_down( ht, moved_node, slot, HEAP_LEFT(slot));
240         else
241             reheap_up( ht, moved_node, slot, parent);
242     }
243     
244     return removed_node;
245 }
246
247 static void grow_heap(pj_timer_heap_t *ht)
248 {
249     // All the containers will double in size from max_size_
250     size_t new_size = ht->max_size * 2;
251     pj_timer_id_t *new_timer_ids;
252     pj_size_t i;
253     
254     // First grow the heap itself.
255     
256     pj_timer_entry **new_heap = 0;
257     
258     new_heap = (pj_timer_entry**) 
259                pj_pool_alloc(ht->pool, sizeof(pj_timer_entry*) * new_size);
260     memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry*));
261     //delete [] this->heap_;
262     ht->heap = new_heap;
263     
264     // Grow the array of timer ids.
265     
266     new_timer_ids = 0;
267     new_timer_ids = (pj_timer_id_t*)
268                     pj_pool_alloc(ht->pool, new_size * sizeof(pj_timer_id_t));
269     
270     memcpy( new_timer_ids, ht->timer_ids, ht->max_size * sizeof(pj_timer_id_t));
271     
272     //delete [] timer_ids_;
273     ht->timer_ids = new_timer_ids;
274     
275     // And add the new elements to the end of the "freelist".
276     for (i = ht->max_size; i < new_size; i++)
277         ht->timer_ids[i] = -((pj_timer_id_t) (i + 1));
278     
279     ht->max_size = new_size;
280 }
281
282 static void insert_node(pj_timer_heap_t *ht, pj_timer_entry *new_node)
283 {
284     if (ht->cur_size + 2 >= ht->max_size)
285         grow_heap(ht);
286     
287     reheap_up( ht, new_node, ht->cur_size, HEAP_PARENT(ht->cur_size));
288     ht->cur_size++;
289 }
290
291
292 static pj_status_t schedule_entry( pj_timer_heap_t *ht,
293                                    pj_timer_entry *entry, 
294                                    const pj_time_val *future_time )
295 {
296     if (ht->cur_size < ht->max_size)
297     {
298         // Obtain the next unique sequence number.
299         // Set the entry
300         entry->_timer_id = pop_freelist(ht);
301         entry->_timer_value = *future_time;
302         insert_node( ht, entry);
303         return 0;
304     }
305     else
306         return -1;
307 }
308
309
310 static int cancel( pj_timer_heap_t *ht, 
311                    pj_timer_entry *entry, 
312                    int dont_call)
313 {
314   long timer_node_slot;
315
316   PJ_CHECK_STACK();
317
318   // Check to see if the timer_id is out of range
319   if (entry->_timer_id < 0 || (pj_size_t)entry->_timer_id > ht->max_size)
320     return 0;
321
322   timer_node_slot = ht->timer_ids[entry->_timer_id];
323
324   if (timer_node_slot < 0) // Check to see if timer_id is still valid.
325     return 0;
326
327   if (entry != ht->heap[timer_node_slot])
328     {
329       pj_assert(entry == ht->heap[timer_node_slot]);
330       return 0;
331     }
332   else
333     {
334       remove_node( ht, timer_node_slot);
335
336       if (dont_call == 0)
337         // Call the close hook.
338         (*ht->callback)(ht, entry);
339       return 1;
340     }
341 }
342
343
344 /*
345  * Calculate memory size required to create a timer heap.
346  */
347 PJ_DEF(pj_size_t) pj_timer_heap_mem_size(pj_size_t count)
348 {
349     return /* size of the timer heap itself: */
350            sizeof(pj_timer_heap_t) + 
351            /* size of each entry: */
352            (count+2) * (sizeof(pj_timer_entry*)+sizeof(pj_timer_id_t)) +
353            /* lock, pool etc: */
354            132;
355 }
356
357 /*
358  * Create a new timer heap.
359  */
360 PJ_DEF(pj_status_t) pj_timer_heap_create( pj_pool_t *pool,
361                                           pj_size_t size,
362                                           pj_timer_heap_t **p_heap)
363 {
364     pj_timer_heap_t *ht;
365     pj_size_t i;
366
367     PJ_ASSERT_RETURN(pool && p_heap, PJ_EINVAL);
368
369     *p_heap = NULL;
370
371     /* Magic? */
372     size += 2;
373
374     /* Allocate timer heap data structure from the pool */
375     ht = PJ_POOL_ALLOC_T(pool, pj_timer_heap_t);
376     if (!ht)
377         return PJ_ENOMEM;
378
379     /* Initialize timer heap sizes */
380     ht->max_size = size;
381     ht->cur_size = 0;
382     ht->max_entries_per_poll = DEFAULT_MAX_TIMED_OUT_PER_POLL;
383     ht->timer_ids_freelist = 1;
384     ht->pool = pool;
385
386     /* Lock. */
387     ht->lock = NULL;
388     ht->auto_delete_lock = 0;
389
390     // Create the heap array.
391     ht->heap = (pj_timer_entry**)
392                pj_pool_alloc(pool, sizeof(pj_timer_entry*) * size);
393     if (!ht->heap)
394         return PJ_ENOMEM;
395
396     // Create the parallel
397     ht->timer_ids = (pj_timer_id_t *)
398                     pj_pool_alloc( pool, sizeof(pj_timer_id_t) * size);
399     if (!ht->timer_ids)
400         return PJ_ENOMEM;
401
402     // Initialize the "freelist," which uses negative values to
403     // distinguish freelist elements from "pointers" into the <heap_>
404     // array.
405     for (i=0; i<size; ++i)
406         ht->timer_ids[i] = -((pj_timer_id_t) (i + 1));
407
408     *p_heap = ht;
409     return PJ_SUCCESS;
410 }
411
412 PJ_DEF(void) pj_timer_heap_destroy( pj_timer_heap_t *ht )
413 {
414     if (ht->lock && ht->auto_delete_lock) {
415         pj_lock_destroy(ht->lock);
416         ht->lock = NULL;
417     }
418 }
419
420 PJ_DEF(void) pj_timer_heap_set_lock(  pj_timer_heap_t *ht,
421                                       pj_lock_t *lock,
422                                       pj_bool_t auto_del )
423 {
424     if (ht->lock && ht->auto_delete_lock)
425         pj_lock_destroy(ht->lock);
426
427     ht->lock = lock;
428     ht->auto_delete_lock = auto_del;
429 }
430
431
432 PJ_DEF(unsigned) pj_timer_heap_set_max_timed_out_per_poll(pj_timer_heap_t *ht,
433                                                           unsigned count )
434 {
435     unsigned old_count = ht->max_entries_per_poll;
436     ht->max_entries_per_poll = count;
437     return old_count;
438 }
439
440 PJ_DEF(pj_timer_entry*) pj_timer_entry_init( pj_timer_entry *entry,
441                                              int id,
442                                              void *user_data,
443                                              pj_timer_heap_callback *cb )
444 {
445     pj_assert(entry && cb);
446
447     entry->_timer_id = -1;
448     entry->id = id;
449     entry->user_data = user_data;
450     entry->cb = cb;
451
452     return entry;
453 }
454
455 PJ_DEF(pj_status_t) pj_timer_heap_schedule( pj_timer_heap_t *ht,
456                                             pj_timer_entry *entry, 
457                                             const pj_time_val *delay)
458 {
459     pj_status_t status;
460     pj_time_val expires;
461
462     PJ_ASSERT_RETURN(ht && entry && delay, PJ_EINVAL);
463     PJ_ASSERT_RETURN(entry->cb != NULL, PJ_EINVAL);
464
465     /* Prevent same entry from being scheduled more than once */
466     PJ_ASSERT_RETURN(entry->_timer_id < 1, PJ_EINVALIDOP);
467
468     pj_gettickcount(&expires);
469     PJ_TIME_VAL_ADD(expires, *delay);
470     
471     lock_timer_heap(ht);
472     status = schedule_entry(ht, entry, &expires);
473     unlock_timer_heap(ht);
474
475     return status;
476 }
477
478 PJ_DEF(int) pj_timer_heap_cancel( pj_timer_heap_t *ht,
479                                   pj_timer_entry *entry)
480 {
481     int count;
482
483     PJ_ASSERT_RETURN(ht && entry, PJ_EINVAL);
484
485     lock_timer_heap(ht);
486     count = cancel(ht, entry, 1);
487     unlock_timer_heap(ht);
488
489     return count;
490 }
491
492 PJ_DEF(unsigned) pj_timer_heap_poll( pj_timer_heap_t *ht, 
493                                      pj_time_val *next_delay )
494 {
495     pj_time_val now;
496     unsigned count;
497
498     PJ_ASSERT_RETURN(ht, 0);
499
500     if (!ht->cur_size && next_delay) {
501         next_delay->sec = next_delay->msec = PJ_MAXINT32;
502         return 0;
503     }
504
505     count = 0;
506     pj_gettickcount(&now);
507
508     lock_timer_heap(ht);
509     while ( ht->cur_size && 
510             PJ_TIME_VAL_LTE(ht->heap[0]->_timer_value, now) &&
511             count < ht->max_entries_per_poll ) 
512     {
513         pj_timer_entry *node = remove_node(ht, 0);
514         ++count;
515
516         unlock_timer_heap(ht);
517         if (node->cb)
518             (*node->cb)(ht, node);
519         lock_timer_heap(ht);
520     }
521     if (ht->cur_size && next_delay) {
522         *next_delay = ht->heap[0]->_timer_value;
523         PJ_TIME_VAL_SUB(*next_delay, now);
524         if (next_delay->sec < 0 || next_delay->msec < 0)
525             next_delay->sec = next_delay->msec = 0;
526     } else if (next_delay) {
527         next_delay->sec = next_delay->msec = PJ_MAXINT32;
528     }
529     unlock_timer_heap(ht);
530
531     return count;
532 }
533
534 PJ_DEF(pj_size_t) pj_timer_heap_count( pj_timer_heap_t *ht )
535 {
536     PJ_ASSERT_RETURN(ht, 0);
537
538     return ht->cur_size;
539 }
540
541 PJ_DEF(pj_status_t) pj_timer_heap_earliest_time( pj_timer_heap_t * ht,
542                                                  pj_time_val *timeval)
543 {
544     pj_assert(ht->cur_size != 0);
545     if (ht->cur_size == 0)
546         return PJ_ENOTFOUND;
547
548     lock_timer_heap(ht);
549     *timeval = ht->heap[0]->_timer_value;
550     unlock_timer_heap(ht);
551
552     return PJ_SUCCESS;
553 }
554