qsort.h File Reference

#include "macros.h"

Go to the source code of this file.

Macros
#define	AV_QSORT(p, num, type, cmp)
	Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input that requires O(n^2) time but this is very unlikely to happen with non constructed input.
#define	AV_MSORT(p, tmp, num, type, cmp)
	Merge sort, this sort requires a temporary buffer and is stable, its worst case time is O(n log n)

Macro Definition Documentation

AV_QSORT

#define AV_QSORT	(		p,
			num,
			type,
			cmp )

Quicksort This sort is fast, and fully inplace but not stable and it is possible to construct input that requires O(n^2) time but this is very unlikely to happen with non constructed input.

Definition at line 33 of file qsort.h.

Referenced by calculate_blur(), clean_mean(), ff_huff_build_tree(), ff_tx_decompose_length(), ff_tx_init_subtx(), ff_vlc_init_sparse(), filter_frame(), get_median_factor(), get_next_color(), load_rgb_float32_frame(), magy_huffman_compute_bits(), mjpegenc_huffman_compute_bits(), mode02(), mode03(), mode04(), sab_diamond_search(), sbr_make_f_master(), sbr_make_f_tablelim(), update_model1_to_4(), and update_model2_to_6().

AV_MSORT

#define AV_MSORT	(		p,
			tmp,
			num,
			type,
			cmp )

Value:

    do {\
    unsigned i, j, step;\
    for(step=1; step<(num); step+=step){\
        for(i=0; i<(num); i+=2*step){\
            unsigned a[2] = {i, i+step};\
            unsigned end = FFMIN(i+2*step, (num));\
            for(j=i; a[0]<i+step && a[1]<end; j++){\
                int idx= cmp(p+a[0], p+a[1]) > 0;\
                tmp[j] = p[ a[idx]++ ];\
            }\
            if(a[0]>=i+step) a[0] = a[1];\
            for(; j<end; j++){\
                tmp[j] = p[ a[0]++ ];\
            }\
        }\
        FFSWAP(type*, p, tmp);\
    }\
} while (0)

Merge sort, this sort requires a temporary buffer and is stable, its worst case time is O(n log n)

Parameters

p	must be a lvalue pointer, this function may exchange it with tmp
tmp	must be a lvalue pointer, this function may exchange it with p

Definition at line 103 of file qsort.h.