FFmpeg  4.0
Macros
qsort.h File Reference
#include "common.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. More...
 
#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) More...
 

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_codes(), clean_mean(), ff_huff_build_tree(), ff_init_vlc_sparse(), ff_mjpeg_encode_huffman_close(), ff_mjpegenc_huffman_compute_bits(), get_median_factor(), get_next_color(), get_palette_frame(), huff_build(), huff_build10(), huff_build12(), magy_huffman_compute_bits(), mode02(), mode03(), mode04(), sab_diamond_search(), sbr_make_f_master(), and sbr_make_f_tablelim().

◆ 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)
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:90
#define FFMIN(a, b)
Definition: common.h:96
static av_always_inline int cmp(MpegEncContext *s, const int x, const int y, const int subx, const int suby, const int size, const int h, int ref_index, int src_index, me_cmp_func cmp_func, me_cmp_func chroma_cmp_func, const int flags)
compares a block (either a full macroblock or a partition thereof) against a proposed motion-compensa...
Definition: motion_est.c:260
cl_device_type type
static uint8_t tmp[11]
Definition: aes_ctr.c:26

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

Parameters
pmust be a lvalue pointer, this function may exchange it with tmp
tmpmust be a lvalue pointer, this function may exchange it with p

Definition at line 103 of file qsort.h.