summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2019-09-18 03:55:23 +0300
committerLinus Torvalds <torvalds@linux-foundation.org>2019-09-18 03:55:23 +0300
commite7345f92c27af003f219ad026d0e629a50b41e5c (patch)
treee4a68d230e460d25e340128e60a7e7efe4165244 /lib
parent6ab8ad31601f29470eb895fd95e5c963e125aa1b (diff)
parent6f51fdfd8229d5358c2d6e272cf73478866e8ddc (diff)
downloadlinux-e7345f92c27af003f219ad026d0e629a50b41e5c.tar.xz
Merge tag 'media/v5.4-1' of git://git.kernel.org/pub/scm/linux/kernel/git/mchehab/linux-media
Pull media updates from Mauro Carvalho Chehab: - a new sensor driver for ov5675 - a new platform driver for Allwinner A10 sensor interface - some new remote controller keymaps - some cosmetic changes at V4L2 core in order to avoid #ifdefs and to merge two core modules into one - removal of bcm2048 radio driver from staging - removal of davinci_vpfe video driver from staging - regression fix since Kernel 5.1 at the legacy VideoBuffer version 1 core - added some documentation for remote controller protocols - pixel format documentation was split on two files - lots of other driver improvements and cleanups * tag 'media/v5.4-1' of git://git.kernel.org/pub/scm/linux/kernel/git/mchehab/linux-media: (321 commits) media: videobuf-core.c: poll_wait needs a non-NULL buf pointer media: sun4i: Make sun4i_csi_formats static media: imx: remove unused including <linux/version.h> media: stm32-dcmi: Delete an unnecessary of_node_put() call in dcmi_probe() media: pvrusb2: qctrl.flag will be uninitlaized if cx2341x_ctrl_query() returns error code media: em28xx: Fix exception handling in em28xx_alloc_urbs() media: don't do a 31 bit shift on a signed int media: use the BIT() macro media: ov9650: add a sanity check media: aspeed-video: address a protential usage of an unitialized var media: vicodec: make life easier for static analyzers media: remove include stdarg.h from some drivers v4l2-core: fix coding style for the two new c files media: v4l2-core: Remove BUG() from i2c and spi helpers media: v4l2-core: introduce a helper to unregister a i2c subdev media: v4l2-core: introduce a helper to unregister a spi subdev media: v4l2-core: move i2c helpers out of v4l2-common.c media: v4l2-core: move spi helpers out of v4l2-common.c media: v4l2-core: Module re-organization media: usbvision: Remove dead code ...
Diffstat (limited to 'lib')
-rw-r--r--lib/sort.c34
1 files changed, 28 insertions, 6 deletions
diff --git a/lib/sort.c b/lib/sort.c
index cf408aec3733..d54cf97e9548 100644
--- a/lib/sort.c
+++ b/lib/sort.c
@@ -144,6 +144,18 @@ static void do_swap(void *a, void *b, size_t size, swap_func_t swap_func)
swap_func(a, b, (int)size);
}
+typedef int (*cmp_func_t)(const void *, const void *);
+typedef int (*cmp_r_func_t)(const void *, const void *, const void *);
+#define _CMP_WRAPPER ((cmp_r_func_t)0L)
+
+static int do_cmp(const void *a, const void *b,
+ cmp_r_func_t cmp, const void *priv)
+{
+ if (cmp == _CMP_WRAPPER)
+ return ((cmp_func_t)(priv))(a, b);
+ return cmp(a, b, priv);
+}
+
/**
* parent - given the offset of the child, find the offset of the parent.
* @i: the offset of the heap element whose parent is sought. Non-zero.
@@ -171,12 +183,13 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
}
/**
- * sort - sort an array of elements
+ * sort_r - sort an array of elements
* @base: pointer to data to sort
* @num: number of elements
* @size: size of each element
* @cmp_func: pointer to comparison function
* @swap_func: pointer to swap function or NULL
+ * @priv: third argument passed to comparison function
*
* This function does a heapsort on the given array. You may provide
* a swap_func function if you need to do something more than a memory
@@ -188,9 +201,10 @@ static size_t parent(size_t i, unsigned int lsbit, size_t size)
* O(n*n) worst-case behavior and extra memory requirements that make
* it less suitable for kernel use.
*/
-void sort(void *base, size_t num, size_t size,
- int (*cmp_func)(const void *, const void *),
- void (*swap_func)(void *, void *, int size))
+void sort_r(void *base, size_t num, size_t size,
+ int (*cmp_func)(const void *, const void *, const void *),
+ void (*swap_func)(void *, void *, int size),
+ const void *priv)
{
/* pre-scale counters for performance */
size_t n = num * size, a = (num/2) * size;
@@ -238,12 +252,12 @@ void sort(void *base, size_t num, size_t size,
* average, 3/4 worst-case.)
*/
for (b = a; c = 2*b + size, (d = c + size) < n;)
- b = cmp_func(base + c, base + d) >= 0 ? c : d;
+ b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d;
if (d == n) /* Special case last leaf with no sibling */
b = c;
/* Now backtrack from "b" to the correct location for "a" */
- while (b != a && cmp_func(base + a, base + b) >= 0)
+ while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0)
b = parent(b, lsbit, size);
c = b; /* Where "a" belongs */
while (b != a) { /* Shift it into place */
@@ -252,4 +266,12 @@ void sort(void *base, size_t num, size_t size,
}
}
}
+EXPORT_SYMBOL(sort_r);
+
+void sort(void *base, size_t num, size_t size,
+ int (*cmp_func)(const void *, const void *),
+ void (*swap_func)(void *, void *, int size))
+{
+ return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func);
+}
EXPORT_SYMBOL(sort);