用伸展树汇总多个传输的最近超时

3775  /* Add the timeout, will replace any previous value for this timer. */3776  multi_set_timeout(data, &set, eid);3777  DEBUGASSERT(timeouts->first < EXPIRE_LAST);37783779  if(Curl_timeouts_has(data)) {3780    /* data has already a timeout registered. If the first timer3781     * was NOT the one we just set AND is still the first one,3782     * nothing changed from the timeouts point of view. The3783     * set timer triggers after the one already registered. Leave. */3784    if((prev_id != eid) && (prev_id == timeouts->first))3785      return;37863787    /* Since this is an updated time, we must remove data from3788     * timeouts and then add it again. */3789    Curl_timeouts_remove(&multi->timeouts, data);3790  }37913792  /* Insert the new timer expiry since it is our local minimum. */3793  Curl_timeouts_add(&multi->timeouts, data,3794                    timeouts->offset_us[timeouts->first]);

190  if(root) {191    root = splay(key, root);192    DEBUGASSERT(root);193    if(key == root->key) {194      /* There already exists a node in the tree with the same key.195         Append the new node to the `same` list. */196      struct Curl_tree **panchor = &root->same;197      while(*panchor)198        panchor = &(*panchor)->same;199      *panchor = node;200      return root; /* the root node always stays the same */

222void Curl_timeouts_add(struct Curl_timeouts *timeouts,223                       struct Curl_easy *data,224                       timediff_t offset_us)225{226  struct Curl_tree *node = &data->state.timeouts.splaynode;227  DEBUGASSERT(!node->registered);228  timeouts->tree = splayinsert(offset_us, timeouts->tree,229                               node, data->mid);230}

112  for(;;) {113    if(key < root->key) {114      /* key is somewhere in root->smaller branch */115      if(!root->smaller)  /* which is empty, done */116        break;117      if(key < root->smaller->key) {118        /* key is somewhere in root->smaller->smaller, make a "Zig step" */119        y = root->smaller;120        root->smaller = y->larger;121        y->larger = root;122        root = y;123        if(!root->smaller)124          break;125      }126      /* Making root->smaller the new root, the old root is no longer127       * referenced. Remember it in the N tree's `r`ight/larger side.128       * Everything in old root is smaller than what the right side129       * of N already has, so it gets added to r->smaller. */130      r->smaller = root;131      r = root;132      root = root->smaller;

64int Curl_timeouts_next_ms(struct Curl_timeouts *timeouts,65                          const struct curltime *pnow,66                          timediff_t *pexpire_offset_us,67                          uint32_t *pmid)68{69  if(timeouts->tree) { /* splay the lowest key to the root */70    timeouts->tree = splay(TIMEDIFF_T_MIN, timeouts->tree);71  }7273  if(timeouts->tree) {74    timediff_t elapsed_us = Curl_timeouts_offset_us(timeouts, pnow);75    timediff_t delta_us = timeouts->tree->key - elapsed_us;76    if(pmid)77      *pmid = timeouts->tree->id;78    if(pexpire_offset_us)79      *pexpire_offset_us = timeouts->tree->key;80    if(delta_us > 0) { /* expires in the future */81      timediff_t ms = curlx_us_to_ceil_ms(delta_us);82      return (ms > INT_MAX) ? INT_MAX : (int)ms;83    }84    else /* has expired */85      return 0;

252  /* find smallest */253  root = splay(TIMEDIFF_T_MIN, root);254  DEBUGASSERT(root);255  if(key < root->key) {256    /* even the smallest is too big */257    *removed = NULL;258    return root;259  }260261  /* FIRST! Check if there is a list with identical keys */262  if(root->same) {263    x = root->same;264    DEBUGASSERT(x->key == root->key);265    /* 'x' becomes the new root node */266    x->larger = root->larger;267    x->smaller = root->smaller;268    root->same = NULL;269    root->registered = FALSE;270    *removed = root;271    return x; /* new root */

3145static CURLMcode add_next_timeout(const struct curltime *pnow,3146                                  struct Curl_multi *multi,3147                                  struct Curl_easy *data)3148{3149  struct expire_timers *timeouts = &data->state.timeouts;3150  timediff_t now_us = Curl_timeouts_offset_us(&multi->timeouts, pnow);31513152  while(timeouts->first < EXPIRE_LAST) {3153    if(timeouts->offset_us[timeouts->first] <= now_us)  /* already expired */3154      timeouts->first = timeouts->next[timeouts->first];3155    else /* timeouts are sorted, first is first in the future now */3156      break;3157  }31583159  if(timeouts->first < EXPIRE_LAST) {3160    /* Insert this node again into the splay. Keep the timer in the list in3161       case we need to recompute future timers. */3162    Curl_timeouts_add(&multi->timeouts, data,3163                      timeouts->offset_us[timeouts->first]);3164  }3165  return CURLM_OK;

3179  while(Curl_timeouts_remove_expired(&multi->timeouts, ts, &mid)) {3180    /* Check if there is one (more) expired timer to deal with! This function3181       extracts a matching node if there is one */3182    data = Curl_multi_get_easy(multi, mid);3183    if(!data) {3184      DEBUGASSERT(0);3185      continue;3186    }3187#ifdef CURLVERBOSE3188    if(CURL_TRC_TIMER_is_verbose(data)) {3189      if(data->state.timeouts.first < EXPIRE_LAST) {3190        CURL_TRC_TIMER(data, data->state.timeouts.first, "has expired");3191      }3192    }3193#endif3194    (void)add_next_timeout(ts, multi, data);3195    Curl_multi_mark_dirty(data);