filehash/ffdb_pagepool.c
static void
_ffdb_slist_merge_sort (ffdb_slh_t* head)
{
  ffdb_sbkt_t *p, *q, *e, *tail;
  int insize, nmerges, psize, qsize, i;

  if (FFDB_SLIST_EMPTY(head))
    return;

  /* First time merge two elements */
  insize = 1;

  while (1) {
    p = FFDB_SLIST_FIRST(head);
    FFDB_SLIST_FIRST(head) = 0;
    tail = 0;

    /* count number of merges we do in this pass */
    nmerges = 0; 
    while (p) {
      nmerges++;
      /* there merges to be done */
      q = p;
      psize = 0;
      for (i = 0; i < insize; i++) {
	psize++;
	q = FFDB_SLIST_NEXT(q,sl);
	if (!q) break;
      }

      /* if q has not fallen off end, we have two lists to merge */
      qsize = insize;
      
      /* now we have two lists: merge them */
      while (psize > 0 || (qsize > 0 && q)) {
	  
	  /* decide whether next element of merge comes from q or q */
	  if (psize == 0) {
	    /* p is empty, e must come from q */
	    e = q;
	    q = FFDB_SLIST_NEXT(q,sl);
	    qsize--;
	  }
	  else if (qsize == 0 || !q) {
	    /* q is empty, e must come from p */
	    e = p;
	    p = FFDB_SLIST_NEXT(p,sl);
	    psize--;
	  }
	  else if (_ffdb_sbkt_cmp (p, q) <= 0) {
	    /* First element of p is lower (or same)
	     * e must be from p */
	    e = p;
	    p = FFDB_SLIST_NEXT(p,sl);
	    psize--;
	  }
	  else {
	    /* First element of q is lower (or same)
	     * e must be from q */
	    e = q;
	    q = FFDB_SLIST_NEXT(q,sl);
	    qsize--;
	  }
	  
	  /* add the next element to the merged list */
	  if (tail) {
	    FFDB_SLIST_INSERT_AFTER(tail,e,sl);
	  }
	  else {
	    FFDB_SLIST_FIRST(head) = e;
	  }
	  
	  /* assign tail to the new one */
	  tail = e;
	}

	/* Now p has stepped 'insize' places along, and q has too */
	p = q;
    }
    
    /* Now we finished one pass of the list using merge size of insize
     * We have to set the tail next pointer to zero */
    FFDB_SLIST_NULL_NEXT(tail,sl);

    /* If we have done only one merge, we are done */
    if (nmerges <= 1) /* allowing for nmerges == 0, the empty list case */
      break;

    /* Otherwise repeat, merging list twice the size */
    insize *= 2;
  }
    
  /* When we get here, we are finished */
}
/**
 * Non recursive merge sort of a single linked list according to
 * page number
 */
Non recursive merge sort of a single linked list according to
page number
Non recursive merge sort of a single linked list according to page number
static void
_ffdb_slist_merge_sort (ffdb_slh_t* head)
{
  ffdb_sbkt_t *p, *q, *e, *tail;
  int insize, nmerges, psize, qsize, i;
  if (FFDB_SLIST_EMPTY(head))
    return;
  insize = 1;
  while (1) {
    p = FFDB_SLIST_FIRST(head);
    FFDB_SLIST_FIRST(head) = 0;
    tail = 0;
    nmerges = 0; 
    while (p) {
      nmerges++;
      q = p;
      psize = 0;
      for (i = 0; i < insize; i++) {
	psize++;
	q = FFDB_SLIST_NEXT(q,sl);
	if (!q) break;
      }
      qsize = insize;
      while (psize > 0 || (qsize > 0 && q)) {
	  if (psize == 0) {
	    e = q;
	    q = FFDB_SLIST_NEXT(q,sl);
	    qsize--;
	  }
	  else if (qsize == 0 || !q) {
	    e = p;
	    p = FFDB_SLIST_NEXT(p,sl);
	    psize--;
	  }
	  else if (_ffdb_sbkt_cmp (p, q) <= 0) {
	    e = p;
	    p = FFDB_SLIST_NEXT(p,sl);
	    psize--;
	  }
	  else {
	    e = q;
	    q = FFDB_SLIST_NEXT(q,sl);
	    qsize--;
	  }
	  if (tail) {
	    FFDB_SLIST_INSERT_AFTER(tail,e,sl);
	  }
	  else {
	    FFDB_SLIST_FIRST(head) = e;
	  }
	  tail = e;
	}
	p = q;
    }
    FFDB_SLIST_NULL_NEXT(tail,sl);
    if (nmerges <= 1) 
      break;
    insize *= 2;
  }
}
static void _ffdb_slist_merge_sort ( ffdb_slh_t * head ) { ffdb_sbkt_t * p , * q , * e , * tail ; int insize , nmerges , psize , qsize , i ; if ( FFDB_SLIST_EMPTY ( head ) ) return ; insize = 1 ; while ( 1 ) { p = FFDB_SLIST_FIRST ( head ) ; FFDB_SLIST_FIRST ( head ) = 0 ; tail = 0 ; nmerges = 0 ; while ( p ) { nmerges ++ ; q = p ; psize = 0 ; for ( i = 0 ; i < insize ; i ++ ) { psize ++ ; q = FFDB_SLIST_NEXT ( q , sl ) ; if ( ! q ) break ; } qsize = insize ; while ( psize > 0 || ( qsize > 0 && q ) ) { if ( psize == 0 ) { e = q ; q = FFDB_SLIST_NEXT ( q , sl ) ; qsize -- ; } else if ( qsize == 0 || ! q ) { e = p ; p = FFDB_SLIST_NEXT ( p , sl ) ; psize -- ; } else if ( _ffdb_sbkt_cmp ( p , q ) <= 0 ) { e = p ; p = FFDB_SLIST_NEXT ( p , sl ) ; psize -- ; } else { e = q ; q = FFDB_SLIST_NEXT ( q , sl ) ; qsize -- ; } if ( tail ) { FFDB_SLIST_INSERT_AFTER ( tail , e , sl ) ; } else { FFDB_SLIST_FIRST ( head ) = e ; } tail = e ; } p = q ; } FFDB_SLIST_NULL_NEXT ( tail , sl ) ; if ( nmerges <= 1 ) break ; insize *= 2 ; } }
Non recursive merge sort of a single linked list according to
 page number
Non recursive merge sort of a single linked list according to page number
/* First time merge two elements */ /* count number of merges we do in this pass */ /* there merges to be done */ /* if q has not fallen off end, we have two lists to merge */ /* now we have two lists: merge them */ /* decide whether next element of merge comes from q or q */ /* p is empty, e must come from q */ /* q is empty, e must come from p */ /* First element of p is lower (or same)
	     * e must be from p */ /* First element of q is lower (or same)
	     * e must be from q */ /* add the next element to the merged list */ /* assign tail to the new one */ /* Now p has stepped 'insize' places along, and q has too */ /* Now we finished one pass of the list using merge size of insize
     * We have to set the tail next pointer to zero */ /* If we have done only one merge, we are done */ /* allowing for nmerges == 0, the empty list case */ /* Otherwise repeat, merging list twice the size */ /* When we get here, we are finished */