src/sys/netinet/tcp_lro.c
/*
 * The tcp_lro_sort() routine is comparable to qsort(), except it has
 * a worst case complexity limit of O(MIN(N,64)*N), where N is the
 * number of elements to sort and 64 is the number of sequence bits
 * available. The algorithm is bit-slicing the 64-bit sequence number,
 * sorting one bit at a time from the most significant bit until the
 * least significant one, skipping the constant bits. This is
 * typically called a radix sort.
 */
The tcp_lro_sort() routine is comparable to qsort(), except it has
a worst case complexity limit of O(MIN(N,64)*N), where N is the
number of elements to sort and 64 is the number of sequence bits
available. The algorithm is bit-slicing the 64-bit sequence number,
sorting one bit at a time from the most significant bit until the
least significant one, skipping the constant bits. This is
typically called a radix sort.
The tcp_lro_sort () routine is comparable to qsort () except it has a worst case complexity limit of O ( MIN ( N 64 ) * N ) where N is the number of elements to sort and 64 is the number of sequence bits available . The algorithm is bit - slicing the 64 - bit sequence number sorting one bit at a time from the most significant bit until the least significant one skipping the constant bits . This is typically called a radix sort .
static void
tcp_lro_sort(struct lro_mbuf_sort *parray, uint32_t size)
{
	struct lro_mbuf_sort temp;
	uint64_t ones;
	uint64_t zeros;
	uint32_t x;
	uint32_t y;
repeat:
	if (size <= 12) {
		for (x = 1; x < size; x++) {
			temp = parray[x];
			for (y = x; y > 0 && temp.seq < parray[y - 1].seq; y--)
				parray[y] = parray[y - 1];
			parray[y] = temp;
		}
		return;
	}
	ones = 0;
	zeros = 0;
	for (x = 0; x != size; x++) {
		ones |= parray[x].seq;
		zeros |= ~parray[x].seq;
	}
	ones &= zeros;
	if (ones == 0)
		return;
	ones = tcp_lro_msb_64(ones);
	for (x = y = 0; y != size; y++) {
		if (parray[y].seq & ones)
			continue;
		temp = parray[x];
		parray[x] = parray[y];
		parray[y] = temp;
		x++;
	}
	KASSERT(x != 0 && x != size, ("Memory is corrupted\n"));
	tcp_lro_sort(parray, x);
	parray += x;
	size -= x;
	goto repeat;
}
static void tcp_lro_sort ( struct lro_mbuf_sort * parray , uint32_t size ) { struct lro_mbuf_sort temp ; uint64_t ones ; uint64_t zeros ; uint32_t x ; uint32_t y ; repeat : if ( size <= 12 ) { for ( x = 1 ; x < size ; x ++ ) { temp = parray [ x ] ; for ( y = x ; y > 0 && temp . seq < parray [ y - 1 ] . seq ; y -- ) parray [ y ] = parray [ y - 1 ] ; parray [ y ] = temp ; } return ; } ones = 0 ; zeros = 0 ; for ( x = 0 ; x != size ; x ++ ) { ones |= parray [ x ] . seq ; zeros |= ~ parray [ x ] . seq ; } ones &= zeros ; if ( ones == 0 ) return ; ones = tcp_lro_msb_64 ( ones ) ; for ( x = y = 0 ; y != size ; y ++ ) { if ( parray [ y ] . seq & ones ) continue ; temp = parray [ x ] ; parray [ x ] = parray [ y ] ; parray [ y ] = temp ; x ++ ; } KASSERT ( x != 0 && x != size , ( " \n " ) ) ; tcp_lro_sort ( parray , x ) ; parray += x ; size -= x ; goto repeat ; }
The tcp_lro_sort() routine is comparable to qsort(), except it has
 a worst case complexity limit of O(MIN(N,64)*N), where N is the
 number of elements to sort and 64 is the number of sequence bits
 available.
The tcp_lro_sort () routine is comparable to qsort () except it has a worst case complexity limit of O ( MIN ( N 64 ) * N ) where N is the number of elements to sort and 64 is the number of sequence bits available .
/* for small arrays insertion sort is faster */ /* compute sequence bits which are constant */ /* compute bits which are not constant into "ones" */ /* pick the most significant bit which is not constant */ /*
	 * Move entries having cleared sequence bits to the beginning
	 * of the array:
	 */ /* skip set bits */ /* swap entries */ /* sort zeros */ /* sort ones */