Changeset 6099 for pjproject/trunk/pjlib/src/pj/timer.c

Timestamp:

Nov 6, 2019 6:17:53 AM (4 years ago)

Author:

riza

Message:

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

File:

• pjproject/trunk/pjlib/src/pj/timer.c (modified) (20 diffs)

pjproject/trunk/pjlib/src/pj/timer.c

@@ -51 +51 @@
  * the timer heap will simply remove the destroyed entry (and print log)
  * and resume normally.
- * This setting only works if PJ_TIMER_HEAP_USE_COPY is enabled.
+ * This setting only works if PJ_TIMER_USE_COPY is enabled.
  */
-#define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_HEAP_USE_COPY? 0: 0)
+#define ASSERT_IF_ENTRY_DESTROYED (PJ_TIMER_USE_COPY? 0: 0)
 
 
@@ -63 +63 @@
 };
 
-#if PJ_TIMER_HEAP_USE_COPY
+#if PJ_TIMER_USE_COPY
 
 /* Duplicate/copy of the timer entry. */
 typedef struct pj_timer_entry_dup
 {
+#if PJ_TIMER_USE_LINKED_LIST
+    /**
+    * Standard list members.
+    */
+    PJ_DECL_LIST_MEMBER(struct pj_timer_entry_dup);
+#endif
+
     /**
      * The duplicate copy.
@@ -141 +148 @@
      */
     pj_timer_entry_dup **heap;
+
+#if PJ_TIMER_USE_LINKED_LIST
+    /**
+    * If timer heap uses linked list, then this will represent the head of
+    * the list.
+    */
+    pj_timer_entry_dup head_list;
+#endif
 
     /**
@@ -289 +304 @@
 {
     pj_timer_entry_dup *removed_node = ht->heap[slot];
-    
+
     // Return this timer id to the freelist.
     push_freelist( ht, GET_FIELD(removed_node, _timer_id) );
@@ -321 +336 @@
     GET_FIELD(removed_node, _timer_id) = -1;
 
+#if !PJ_TIMER_USE_LINKED_LIST
     // Only try to reheapify if we're not deleting the last entry.
     
@@ -344 +360 @@
         }
     }
-    
+#else
+    pj_list_erase(removed_node);
+#endif
+
     return removed_node;
 }
@@ -352 +371 @@
     // All the containers will double in size from max_size_
     size_t new_size = ht->max_size * 2;
+#if PJ_TIMER_USE_COPY
     pj_timer_entry_dup *new_timer_dups = 0;
+#endif
     pj_timer_id_t *new_timer_ids;
     pj_size_t i;
     pj_timer_entry_dup **new_heap = 0;
+
+#if PJ_TIMER_USE_LINKED_LIST
+    pj_timer_entry_dup *tmp_dup = NULL;
+    pj_timer_entry_dup *new_dup;
+#endif
     
     PJ_LOG(6,(THIS_FILE, "Growing heap size from %d to %d",
@@ -366 +392 @@
         return PJ_ENOMEM;
     
-#if PJ_TIMER_HEAP_USE_COPY
+#if PJ_TIMER_USE_COPY
     // Grow the array of timer copies.
     
@@ -387 +413 @@
     memcpy(new_heap, ht->heap, ht->max_size * sizeof(pj_timer_entry *));
 #endif
+
+#if PJ_TIMER_USE_LINKED_LIST
+    tmp_dup = ht->head_list.next;
+    pj_list_init(&ht->head_list);
+    for (; tmp_dup != &ht->head_list; tmp_dup = tmp_dup->next)
+    {
+        int slot = ht->timer_ids[GET_FIELD(tmp_dup, _timer_id)];
+        new_dup = new_heap[slot];
+        pj_list_push_back(&ht->head_list, new_dup);
+    }
+#endif
+
     ht->heap = new_heap;
     
@@ -417 +455 @@
     pj_timer_entry_dup *timer_copy;
 
+#if PJ_TIMER_USE_LINKED_LIST
+    pj_timer_entry_dup *tmp_node = NULL;
+#endif
+
     if (ht->cur_size + 2 >= ht->max_size) {
         pj_status_t status = grow_heap(ht);
@@ -424 +466 @@
 
     timer_copy = GET_TIMER(ht, new_node);
-#if PJ_TIMER_HEAP_USE_COPY    
+#if PJ_TIMER_USE_COPY
     // Create a duplicate of the timer entry.
     pj_bzero(timer_copy, sizeof(*timer_copy));
@@ -430 +472 @@
     timer_copy->entry = new_node;
 #endif
+
+#if PJ_TIMER_USE_LINKED_LIST
+    pj_list_init(timer_copy);
+#endif
+
     timer_copy->_timer_value = *future_time;
 
-    reheap_up( ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size));
+#if !PJ_TIMER_USE_LINKED_LIST
+    reheap_up(ht, timer_copy, ht->cur_size, HEAP_PARENT(ht->cur_size));
+#else
+    if (ht->cur_size == 0) {
+        pj_list_push_back(&ht->head_list, timer_copy);
+    } else if (PJ_TIME_VAL_GTE(*future_time,
+                               ht->head_list.prev->_timer_value))
+    {
+        /* Insert the max value to the end of the list. */
+        pj_list_insert_before(&ht->head_list, timer_copy);
+    } else {
+        tmp_node = ht->head_list.next;
+        while (tmp_node->next != &ht->head_list &&
+               PJ_TIME_VAL_GT(*future_time, tmp_node->_timer_value))
+        {
+            tmp_node = tmp_node->next;
+        }
+        if (PJ_TIME_VAL_LT(*future_time, tmp_node->_timer_value)) {
+            pj_list_insert_before(tmp_node, timer_copy);
+        } else {
+            pj_list_insert_after(tmp_node, timer_copy);
+        }
+    }
+    copy_node(ht, new_node->_timer_id-1, timer_copy);
+#endif
     ht->cur_size++;
 
@@ -547 +618 @@
         return PJ_ENOMEM;
 
-#if PJ_TIMER_HEAP_USE_COPY
+#if PJ_TIMER_USE_COPY
     // Create the timer entry copies array.
     ht->timer_dups = (pj_timer_entry_dup*)
@@ -567 +638 @@
         ht->timer_ids[i] = -((pj_timer_id_t) (i + 1));
 
+#if PJ_TIMER_USE_LINKED_LIST
+    pj_list_init(&ht->head_list);
+#endif
+
     *p_heap = ht;
     return PJ_SUCCESS;
@@ -610 +685 @@
     entry->user_data = user_data;
     entry->cb = cb;
-#if !PJ_TIMER_HEAP_USE_COPY
+#if !PJ_TIMER_USE_COPY
     entry->_grp_lock = NULL;
 #endif
@@ -772 +847 @@
 {
     pj_time_val now;
+    pj_time_val min_time_node = {0,0};
     unsigned count;
+    pj_timer_id_t slot = 0;
 
     PJ_ASSERT_RETURN(ht, 0);
@@ -786 +863 @@
     pj_gettickcount(&now);
 
+    if (ht->cur_size) {
+#if PJ_TIMER_USE_LINKED_LIST
+        slot = ht->timer_ids[GET_FIELD(ht->head_list.next, _timer_id)];
+#endif
+        min_time_node = ht->heap[slot]->_timer_value;
+    }
+
     while ( ht->cur_size && 
-            PJ_TIME_VAL_LTE(ht->heap[0]->_timer_value, now) &&
+            PJ_TIME_VAL_LTE(min_time_node, now) &&
             count < ht->max_entries_per_poll ) 
     {
-        pj_timer_entry_dup *node = remove_node(ht, 0);
+        pj_timer_entry_dup *node = remove_node(ht, slot);
         pj_timer_entry *entry = GET_ENTRY(node);
         /* Avoid re-use of this timer until the callback is done. */
@@ -835 +919 @@
         /* Now, the timer is really free for re-use. */
         ///push_freelist(ht, node_timer_id);
+
+        if (ht->cur_size) {
+#if PJ_TIMER_USE_LINKED_LIST
+            slot = ht->timer_ids[GET_FIELD(ht->head_list.next, _timer_id)];
+#endif
+            min_time_node = ht->heap[slot]->_timer_value;
+        }
     }
     if (ht->cur_size && next_delay) {
@@ -880 +971 @@
 
     if (ht->cur_size) {
+#if PJ_TIMER_USE_LINKED_LIST
+        pj_timer_entry_dup *tmp_dup;
+#else
         unsigned i;
+#endif
         pj_time_val now;
 
@@ -889 +984 @@
         pj_gettickcount(&now);
 
-        for (i=0; i<(unsigned)ht->cur_size; ++i) {
+#if !PJ_TIMER_USE_LINKED_LIST
+        for (i=0; i<(unsigned)ht->cur_size; ++i)
+        {
             pj_timer_entry_dup *e = ht->heap[i];
+#else
+        for (tmp_dup = ht->head_list.next; tmp_dup != &ht->head_list;
+             tmp_dup = tmp_dup->next)
+        {
+            pj_timer_entry_dup *e = tmp_dup;
+#endif
+
             pj_time_val delta;