Function td_list_sort

src/list_sort.c:131–182

* td_list_sort - sort a list * @head: the list to sort * @cmp: the elements comparison function * * This function implements "merge sort", which has O(nlog(n)) * complexity. * * The comparison function @cmp must return a negative value if @a * should sort before @b, and a positive value if @a should sort after * @b. If @a and @b are equivalent, and their original relative * ordering is t

 * ordering is to be preserved, @cmp must return 0.
 */
void td_list_sort(struct td_list_head *head,
    int (*cmp)(const struct td_list_head *a, const struct td_list_head *b))
{
  struct td_list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
							-- last slot is a sentinel */
  unsigned int lev;  /* index into part[] */
  unsigned int max_lev = 0;
  struct td_list_head *list;

  if (td_list_empty(head))
    return;

  memset(part, 0, sizeof(part));

  head->prev->next = NULL;
  list = head->next;

  /*@
    @ loop invariant \valid_function(cmp);
    @*/
  while (list) {
    struct td_list_head *cur = list;
    list = list->next;
    cur->next = NULL;

    /*@
      @ loop invariant \valid_function(cmp);
      @*/
    for (lev = 0; part[lev]; lev++) {
      cur = merge(cmp, part[lev], cur);
      part[lev] = NULL;
    }
    if (lev > max_lev) {
      if (lev >= MAX_LIST_LENGTH_BITS)
      {
	// list passed to td_list_sort() too long for efficiency
	lev--;
      }
      max_lev = lev;
    }
    part[lev] = cur;
  }

  /*@
    @ loop invariant \valid_function(cmp);
    @*/
  for (lev = 0; lev < max_lev; lev++)
    if (part[lev])
      list = merge(cmp, part[lev], list);

  merge_and_restore_back_links(cmp, head, part[max_lev], list);
}