Attachment #291 for ticket #336




    return(n);
}


void
list_sort (List l, ListCmpF f)
{
/*  Note: Time complexity O(n^2).
 */
    ListNode *pp, *ppPrev, *ppPos, pTmp;
    ListIterator it;

    ListNode p, q, e, tail, head;
    int insize, nmerges, psize, qsize, i;

    assert(l != NULL);
    assert(f != NULL);
    list_mutex_lock(&l->mutex);
    assert(l->magic == LIST_MAGIC);
    head = l->head;
    if (l->count > 1) {
        insize=1;
        while(1) {
           p = head;
           head = NULL;
           tail = NULL;


           nmerges = 0;
           while(p) {
              nmerges++;
              q = p;

              psize=0;
              for (i = 0; i < insize; i++) {
                psize++;
                q = q->next;

                if (!q) break;
              }
              qsize = insize;
              while (psize > 0 || (qsize > 0 && q)) {
                 if (psize == 0) {
                    e = q;
                    q = q->next;
                    qsize--;
                 } else if (qsize == 0 || !q ) {
                    e = p;
                    p = p->next;
                    psize--;
                 } else if (f(p->data,q->data) < 0) {
                    e = p;
                    p = p->next;
                    psize--;
                 } else {
                    e = q;
                    q = q->next;
                    qsize--;
                 }
                 if (tail) {
                    tail->next = e;
                 } else {
                    head = e;
                 }
                 tail = e;
              }
              p = q;

           }
           tail->next = NULL;
           if(nmerges <= 1) {
              l->head = head;
              l->tail = &tail;
              for (it=l->iNext; it; it=it->iNext) {
                  assert(it->magic == LIST_MAGIC);
                  it->pos = it->list->head;
                  it->prev = &it->list->head;
              }

              list_mutex_unlock(&l->mutex);
              return;
           }
           insize *=2;
        }
    }
    list_mutex_unlock(&l->mutex);
    return;

Return to ticket 336

Lines 529-574 list_flush (List l) Link Here

(-)a/src/common/list.c (-30 / +68 lines)
529	return(n);	529	return(n);
530	}	530	}
531		531
532
533	void	532	void
534	list_sort (List l, ListCmpF f)	533	list_sort (List l, ListCmpF f)
535	{	534	{
536	/* Note: Time complexity O(n^2).
537	*/
538	ListNode pp, ppPrev, *ppPos, pTmp;	535	ListNode pp, ppPrev, *ppPos, pTmp;
539	ListIterator i;	536	ListIterator it;
		537
		538	ListNode p, q, e, tail, head;
		539	int insize, nmerges, psize, qsize, i;
540		540
541	assert(l != NULL);	541	assert(l != NULL);
542	assert(f != NULL);	542	assert(f != NULL);
543	list_mutex_lock(&l->mutex);	543	list_mutex_lock(&l->mutex);
544	assert(l->magic == LIST_MAGIC);	544	assert(l->magic == LIST_MAGIC);
		545	head = l->head;
545	if (l->count > 1) {	546	if (l->count > 1) {
546	ppPrev = &l->head;	547	insize=1;
547	pp = &(*ppPrev)->next;	548	while(1) {
548	while (*pp) {	549	p = head;
549	if (f((pp)->data, (ppPrev)->data) < 0) {	550	head = NULL;
550	ppPos = &l->head;	551	tail = NULL;
551	while (f((pp)->data, (ppPos)->data) >= 0)	552
552	ppPos = &(*ppPos)->next;	553
553	pTmp = (*pp)->next;	554	nmerges = 0;
554	(pp)->next = ppPos;	555	while(p) {
555	ppPos = pp;	556	nmerges++;
556	*pp = pTmp;	557	q = p;
557	if (ppPrev == ppPos)	558
558	ppPrev = &(*ppPrev)->next;	559	psize=0;
559	}	560	for (i = 0; i < insize; i++) {
560	else {	561	psize++;
561	ppPrev = pp;	562	q = q->next;
562	pp = &(*pp)->next;	563
563	}	564	if (!q) break;
564	}	565	}
565	l->tail = pp;	566	qsize = insize;
566		567	while (psize > 0 \|\| (qsize > 0 && q)) {
567	for (i=l->iNext; i; i=i->iNext) {	568	if (psize == 0) {
568	assert(i->magic == LIST_MAGIC);	569	e = q;
569	i->pos = i->list->head;	570	q = q->next;
570	i->prev = &i->list->head;	571	qsize--;
571	}	572	} else if (qsize == 0 \|\| !q ) {
		573	e = p;
		574	p = p->next;
		575	psize--;
		576	} else if (f(p->data,q->data) < 0) {
		577	e = p;
		578	p = p->next;
		579	psize--;
		580	} else {
		581	e = q;
		582	q = q->next;
		583	qsize--;
		584	}
		585	if (tail) {
		586	tail->next = e;
		587	} else {
		588	head = e;
		589	}
		590	tail = e;
		591	}
		592	p = q;
		593
		594	}
		595	tail->next = NULL;
		596	if(nmerges <= 1) {
		597	l->head = head;
		598	l->tail = &tail;
		599	for (it=l->iNext; it; it=it->iNext) {
		600	assert(it->magic == LIST_MAGIC);
		601	it->pos = it->list->head;
		602	it->prev = &it->list->head;
		603	}
		604
		605	list_mutex_unlock(&l->mutex);
		606	return;
		607	}
		608	insize *=2;
		609	}
572	}	610	}
573	list_mutex_unlock(&l->mutex);	611	list_mutex_unlock(&l->mutex);
574	return;	612	return;