Ignore:
Timestamp:
Nov 6, 2019 6:17:53 AM (13 months ago)
Author:
riza
Message:

Close #2249: Use sorted linked list for timer implementation.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • pjproject/trunk/pjlib/src/pj/timer.c

    r6067 r6099  
    5151 * the timer heap will simply remove the destroyed entry (and print log) 
    5252 * and resume normally. 
    53  * This setting only works if PJ_TIMER_HEAP_USE_COPY is enabled. 
     53 * This setting only works if PJ_TIMER_USE_COPY is enabled. 
    5454 */ 
    55 #define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_HEAP_USE_COPY? 0: 0) 
     55#define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_USE_COPY? 0: 0) 
    5656 
    5757 
     
    6363}; 
    6464 
    65 #if PJ_TIMER_HEAP_USE_COPY 
     65#if PJ_TIMER_USE_COPY 
    6666 
    6767/* Duplicate/copy of the timer entry. */ 
    6868typedef struct pj_timer_entry_dup 
    6969{ 
     70#if PJ_TIMER_USE_LINKED_LIST 
     71    /** 
     72    * Standard list members. 
     73    */ 
     74    PJ_DECL_LIST_MEMBER(struct pj_timer_entry_dup); 
     75#endif 
     76 
    7077    /** 
    7178     * The duplicate copy. 
     
    141148     */ 
    142149    pj_timer_entry_dup **heap; 
     150 
     151#if PJ_TIMER_USE_LINKED_LIST 
     152    /** 
     153    * If timer heap uses linked list, then this will represent the head of 
     154    * the list. 
     155    */ 
     156    pj_timer_entry_dup head_list; 
     157#endif 
    143158 
    144159    /** 
     
    289304{ 
    290305    pj_timer_entry_dup *removed_node = ht->heap[slot]; 
    291      
     306 
    292307    // Return this timer id to the freelist. 
    293308    push_freelist( ht, GET_FIELD(removed_node, _timer_id) ); 
     
    321336    GET_FIELD(removed_node, _timer_id) = -1; 
    322337 
     338#if !PJ_TIMER_USE_LINKED_LIST 
    323339    // Only try to reheapify if we're not deleting the last entry. 
    324340     
     
    344360        } 
    345361    } 
    346      
     362#else 
     363    pj_list_erase(removed_node); 
     364#endif 
     365 
    347366    return removed_node; 
    348367} 
     
    352371    // All the containers will double in size from max_size_ 
    353372    size_t new_size = ht->max_size * 2; 
     373#if PJ_TIMER_USE_COPY 
    354374    pj_timer_entry_dup *new_timer_dups = 0; 
     375#endif 
    355376    pj_timer_id_t *new_timer_ids; 
    356377    pj_size_t i; 
    357378    pj_timer_entry_dup **new_heap = 0; 
     379 
     380#if PJ_TIMER_USE_LINKED_LIST 
     381    pj_timer_entry_dup *tmp_dup = NULL; 
     382    pj_timer_entry_dup *new_dup; 
     383#endif 
    358384     
    359385    PJ_LOG(6,(THIS_FILE, "Growing heap size from %d to %d", 
     
    366392        return PJ_ENOMEM; 
    367393     
    368 #if PJ_TIMER_HEAP_USE_COPY 
     394#if PJ_TIMER_USE_COPY 
    369395    // Grow the array of timer copies. 
    370396     
     
    387413    memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry *)); 
    388414#endif 
     415 
     416#if PJ_TIMER_USE_LINKED_LIST 
     417    tmp_dup = ht->head_list.next; 
     418    pj_list_init(&ht->head_list); 
     419    for (; tmp_dup != &ht->head_list; tmp_dup = tmp_dup->next) 
     420    { 
     421        int slot = ht->timer_ids[GET_FIELD(tmp_dup, _timer_id)]; 
     422        new_dup = new_heap[slot]; 
     423        pj_list_push_back(&ht->head_list, new_dup); 
     424    } 
     425#endif 
     426 
    389427    ht->heap = new_heap; 
    390428     
     
    417455    pj_timer_entry_dup *timer_copy; 
    418456 
     457#if PJ_TIMER_USE_LINKED_LIST 
     458    pj_timer_entry_dup *tmp_node = NULL; 
     459#endif 
     460 
    419461    if (ht->cur_size + 2 >= ht->max_size) { 
    420462        pj_status_t status = grow_heap(ht); 
     
    424466 
    425467    timer_copy = GET_TIMER(ht, new_node); 
    426 #if PJ_TIMER_HEAP_USE_COPY     
     468#if PJ_TIMER_USE_COPY 
    427469    // Create a duplicate of the timer entry. 
    428470    pj_bzero(timer_copy, sizeof(*timer_copy)); 
     
    430472    timer_copy->entry = new_node; 
    431473#endif 
     474 
     475#if PJ_TIMER_USE_LINKED_LIST 
     476    pj_list_init(timer_copy); 
     477#endif 
     478 
    432479    timer_copy->_timer_value = *future_time; 
    433480 
    434     reheap_up( ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size)); 
     481#if !PJ_TIMER_USE_LINKED_LIST 
     482    reheap_up(ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size)); 
     483#else 
     484    if (ht->cur_size == 0) { 
     485        pj_list_push_back(&ht->head_list, timer_copy); 
     486    } else if (PJ_TIME_VAL_GTE(*future_time, 
     487                               ht->head_list.prev->_timer_value)) 
     488    { 
     489        /* Insert the max value to the end of the list. */ 
     490        pj_list_insert_before(&ht->head_list, timer_copy); 
     491    } else { 
     492        tmp_node = ht->head_list.next; 
     493        while (tmp_node->next != &ht->head_list && 
     494               PJ_TIME_VAL_GT(*future_time, tmp_node->_timer_value)) 
     495        { 
     496            tmp_node = tmp_node->next; 
     497        } 
     498        if (PJ_TIME_VAL_LT(*future_time, tmp_node->_timer_value)) { 
     499            pj_list_insert_before(tmp_node, timer_copy); 
     500        } else { 
     501            pj_list_insert_after(tmp_node, timer_copy); 
     502        } 
     503    } 
     504    copy_node(ht, new_node->_timer_id-1, timer_copy); 
     505#endif 
    435506    ht->cur_size++; 
    436507 
     
    547618        return PJ_ENOMEM; 
    548619 
    549 #if PJ_TIMER_HEAP_USE_COPY 
     620#if PJ_TIMER_USE_COPY 
    550621    // Create the timer entry copies array. 
    551622    ht->timer_dups = (pj_timer_entry_dup*) 
     
    567638        ht->timer_ids[i] = -((pj_timer_id_t) (i + 1)); 
    568639 
     640#if PJ_TIMER_USE_LINKED_LIST 
     641    pj_list_init(&ht->head_list); 
     642#endif 
     643 
    569644    *p_heap = ht; 
    570645    return PJ_SUCCESS; 
     
    610685    entry->user_data = user_data; 
    611686    entry->cb = cb; 
    612 #if !PJ_TIMER_HEAP_USE_COPY 
     687#if !PJ_TIMER_USE_COPY 
    613688    entry->_grp_lock = NULL; 
    614689#endif 
     
    772847{ 
    773848    pj_time_val now; 
     849    pj_time_val min_time_node = {0,0}; 
    774850    unsigned count; 
     851    pj_timer_id_t slot = 0; 
    775852 
    776853    PJ_ASSERT_RETURN(ht, 0); 
     
    786863    pj_gettickcount(&now); 
    787864 
     865    if (ht->cur_size) { 
     866#if PJ_TIMER_USE_LINKED_LIST 
     867        slot = ht->timer_ids[GET_FIELD(ht->head_list.next, _timer_id)]; 
     868#endif 
     869        min_time_node = ht->heap[slot]->_timer_value; 
     870    } 
     871 
    788872    while ( ht->cur_size &&  
    789             PJ_TIME_VAL_LTE(ht->heap[0]->_timer_value, now) && 
     873            PJ_TIME_VAL_LTE(min_time_node, now) && 
    790874            count < ht->max_entries_per_poll )  
    791875    { 
    792         pj_timer_entry_dup *node = remove_node(ht, 0); 
     876        pj_timer_entry_dup *node = remove_node(ht, slot); 
    793877        pj_timer_entry *entry = GET_ENTRY(node); 
    794878        /* Avoid re-use of this timer until the callback is done. */ 
     
    835919        /* Now, the timer is really free for re-use. */ 
    836920        ///push_freelist(ht, node_timer_id); 
     921 
     922        if (ht->cur_size) { 
     923#if PJ_TIMER_USE_LINKED_LIST 
     924            slot = ht->timer_ids[GET_FIELD(ht->head_list.next, _timer_id)]; 
     925#endif 
     926            min_time_node = ht->heap[slot]->_timer_value; 
     927        } 
    837928    } 
    838929    if (ht->cur_size && next_delay) { 
     
    880971 
    881972    if (ht->cur_size) { 
     973#if PJ_TIMER_USE_LINKED_LIST 
     974        pj_timer_entry_dup *tmp_dup; 
     975#else 
    882976        unsigned i; 
     977#endif 
    883978        pj_time_val now; 
    884979 
     
    889984        pj_gettickcount(&now); 
    890985 
    891         for (i=0; i<(unsigned)ht->cur_size; ++i) { 
     986#if !PJ_TIMER_USE_LINKED_LIST 
     987        for (i=0; i<(unsigned)ht->cur_size; ++i) 
     988        { 
    892989            pj_timer_entry_dup *e = ht->heap[i]; 
     990#else 
     991        for (tmp_dup = ht->head_list.next; tmp_dup != &ht->head_list; 
     992             tmp_dup = tmp_dup->next) 
     993        { 
     994            pj_timer_entry_dup *e = tmp_dup; 
     995#endif 
     996 
    893997            pj_time_val delta; 
    894998 
Note: See TracChangeset for help on using the changeset viewer.