delta/linux.git - git.kernel.org: pub/scm/linux/kernel/git/torvalds/linux.git

	Commit message (Collapse)	Author	Age	Files	Lines
*	textsearch: ts_kmp: support case insensitive searching in Knuth-Morris-Pratt ↵	Joonwoo Park	2008-07-08	1	-8/+21
\| \| \| \| \| \| \| \| \| \|	algorithm Add support for case insensitive search to Knuth-Morris-Pratt algorithm. Signed-off-by: Joonwoo Park <joonwpark81@gmail.com> Signed-off-by: Patrick McHardy <kaber@trash.net> Signed-off-by: David S. Miller <davem@davemloft.net>
*	Remove obsolete #include <linux/config.h>	Jörn Engel	2006-06-30	1	-1/+0
\| \| \| \| \|	Signed-off-by: Jörn Engel <joern@wohnheim.fh-wedel.de> Signed-off-by: Adrian Bunk <bunk@stusta.de>
*	[PATCH] gfp flags annotations - part 1	Al Viro	2005-10-08	1	-1/+1
\| \| \| \| \| \| \| \| \| \| \| \|	- added typedef unsigned int __nocast gfp_t; - replaced __nocast uses for gfp flags with gfp_t - it gives exactly the same warnings as far as sparse is concerned, doesn't change generated code (from gcc point of view we replaced unsigned int with typedef) and documents what's going on far better. Signed-off-by: Al Viro <viro@zeniv.linux.org.uk> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
*	[TEXTSEARCH]: fix sparse gfp nocast warnings	Randy Dunlap	2005-10-04	1	-1/+1
\| \| \| \| \| \| \| \|	Fix nocast sparse warnings: include/linux/textsearch.h:165:57: warning: implicit cast to nocast type Signed-off-by: Randy Dunlap <rdunlap@xenotime.net> Signed-off-by: David S. Miller <davem@davemloft.net>
*	[LIB]: Knuth-Morris-Pratt textsearch algorithm	Thomas Graf	2005-06-23	1	-0/+145
	Implements a linear-time string-matching algorithm due to Knuth, Morris, and Pratt [1]. Their algorithm avoids the explicit computation of the transition function DELTA altogether. Its matching time is O(n), for n being length(text), using just an auxiliary function PI[1..m], for m being length(pattern), precomputed from the pattern in time O(m). The array PI allows the transition function DELTA to be computed efficiently "on the fly" as needed. Roughly speaking, for any state "q" = 0,1,...,m and any character "a" in SIGMA, the value PI["q"] contains the information that is independent of "a" and is needed to compute DELTA("q", "a") [2]. Since the array PI has only m entries, whereas DELTA has O(m\|SIGMA\|) entries, we save a factor of \|SIGMA\| in the preprocessing time by computing PI rather than DELTA. [1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press [2] See finite automation theory Signed-off-by: Thomas Graf <tgraf@suug.ch> Signed-off-by: David S. Miller <davem@davemloft.net>