diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/dma-debug.c | 2 | ||||
| -rw-r--r-- | lib/list_sort.c | 102 | ||||
| -rw-r--r-- | lib/string.c | 27 | ||||
| -rw-r--r-- | lib/zlib_inflate/inffast.c | 32 |
5 files changed, 160 insertions, 5 deletions
diff --git a/lib/Makefile b/lib/Makefile index 911b25aed1e7..3b0b4a696db9 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \ bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \ - string_helpers.o gcd.o + string_helpers.o gcd.o list_sort.o ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG diff --git a/lib/dma-debug.c b/lib/dma-debug.c index 7d2f0b33e5a8..ba8b67039d13 100644 --- a/lib/dma-debug.c +++ b/lib/dma-debug.c @@ -587,7 +587,7 @@ out_unlock: return count; } -const struct file_operations filter_fops = { +static const struct file_operations filter_fops = { .read = filter_read, .write = filter_write, }; diff --git a/lib/list_sort.c b/lib/list_sort.c new file mode 100644 index 000000000000..19d11e0bb958 --- /dev/null +++ b/lib/list_sort.c @@ -0,0 +1,102 @@ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/list_sort.h> +#include <linux/slab.h> +#include <linux/list.h> + +/** + * list_sort - sort a list. + * @priv: private data, passed to @cmp + * @head: the list to sort + * @cmp: the elements comparison function + * + * This function has been implemented by Mark J Roberts <mjr@znex.org>. It + * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted + * in ascending order. + * + * The comparison function @cmp is supposed to return a negative value if @a is + * less than @b, and a positive value if @a is greater than @b. If @a and @b + * are equivalent, then it does not matter what this function returns. + */ +void list_sort(void *priv, struct list_head *head, + int (*cmp)(void *priv, struct list_head *a, + struct list_head *b)) +{ + struct list_head *p, *q, *e, *list, *tail, *oldhead; + int insize, nmerges, psize, qsize, i; + + if (list_empty(head)) + return; + + list = head->next; + list_del(head); + insize = 1; + for (;;) { + p = oldhead = list; + list = tail = NULL; + nmerges = 0; + + while (p) { + nmerges++; + q = p; + psize = 0; + for (i = 0; i < insize; i++) { + psize++; + q = q->next == oldhead ? NULL : q->next; + if (!q) + break; + } + + qsize = insize; + while (psize > 0 || (qsize > 0 && q)) { + if (!psize) { + e = q; + q = q->next; + qsize--; + if (q == oldhead) + q = NULL; + } else if (!qsize || !q) { + e = p; + p = p->next; + psize--; + if (p == oldhead) + p = NULL; + } else if (cmp(priv, p, q) <= 0) { + e = p; + p = p->next; + psize--; + if (p == oldhead) + p = NULL; + } else { + e = q; + q = q->next; + qsize--; + if (q == oldhead) + q = NULL; + } + if (tail) + tail->next = e; + else + list = e; + e->prev = tail; + tail = e; + } + p = q; + } + + tail->next = list; + list->prev = tail; + + if (nmerges <= 1) + break; + + insize *= 2; + } + + head->next = list; + head->prev = list->prev; + list->prev->next = head; + list->prev = head; +} + +EXPORT_SYMBOL(list_sort); diff --git a/lib/string.c b/lib/string.c index 9f75b4ec50b8..a1cdcfcc42d0 100644 --- a/lib/string.c +++ b/lib/string.c @@ -667,7 +667,7 @@ EXPORT_SYMBOL(memscan); */ char *strstr(const char *s1, const char *s2) { - int l1, l2; + size_t l1, l2; l2 = strlen(s2); if (!l2) @@ -684,6 +684,31 @@ char *strstr(const char *s1, const char *s2) EXPORT_SYMBOL(strstr); #endif +#ifndef __HAVE_ARCH_STRNSTR +/** + * strnstr - Find the first substring in a length-limited string + * @s1: The string to be searched + * @s2: The string to search for + * @len: the maximum number of characters to search + */ +char *strnstr(const char *s1, const char *s2, size_t len) +{ + size_t l1 = len, l2; + + l2 = strlen(s2); + if (!l2) + return (char *)s1; + while (l1 >= l2) { + l1--; + if (!memcmp(s1, s2, l2)) + return (char *)s1; + s1++; + } + return NULL; +} +EXPORT_SYMBOL(strnstr); +#endif + #ifndef __HAVE_ARCH_MEMCHR /** * memchr - Find a character in an area of memory. diff --git a/lib/zlib_inflate/inffast.c b/lib/zlib_inflate/inffast.c index 05e1559fa156..215447c55261 100644 --- a/lib/zlib_inflate/inffast.c +++ b/lib/zlib_inflate/inffast.c @@ -4,12 +4,25 @@ */ #include <linux/zutil.h> -#include <asm/unaligned.h> -#include <asm/byteorder.h> #include "inftrees.h" #include "inflate.h" #include "inffast.h" +/* Only do the unaligned "Faster" variant when + * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS is set + * + * On powerpc, it won't be as we don't include autoconf.h + * automatically for the boot wrapper, which is intended as + * we run in an environment where we may not be able to deal + * with (even rare) alignment faults. In addition, we do not + * define __KERNEL__ for arch/powerpc/boot unlike x86 + */ + +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS +#include <asm/unaligned.h> +#include <asm/byteorder.h> +#endif + #ifndef ASMINF /* Allow machine dependent optimization for post-increment or pre-increment. @@ -243,6 +256,7 @@ void inflate_fast(z_streamp strm, unsigned start) } } else { +#ifdef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS unsigned short *sout; unsigned long loops; @@ -284,6 +298,20 @@ void inflate_fast(z_streamp strm, unsigned start) } if (len & 1) PUP(out) = PUP(from); +#else /* CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ + from = out - dist; /* copy direct from output */ + do { /* minimum length is three */ + PUP(out) = PUP(from); + PUP(out) = PUP(from); + PUP(out) = PUP(from); + len -= 3; + } while (len > 2); + if (len) { + PUP(out) = PUP(from); + if (len > 1) + PUP(out) = PUP(from); + } +#endif /* !CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS */ } } else if ((op & 64) == 0) { /* 2nd level distance code */ |