FFmpeg
Macros
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. 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.

◆ 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
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.

tmp
static uint8_t tmp[11]
Definition: aes_ctr.c:28
step
trying all byte sequences megabyte in length and selecting the best looking sequence will yield cases to try But a word about which is also called distortion Distortion can be quantified by almost any quality measurement one chooses the sum of squared differences is used but more complex methods that consider psychovisual effects can be used as well It makes no difference in this discussion First step
Definition: rate_distortion.txt:58
type
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf type
Definition: writing_filters.txt:86
cmp
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:262
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:41
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:256
FFMIN
#define FFMIN(a, b)
Definition: macros.h:49