Eric Lee / smarc-fsl-linux-kernel

08 Jul, 2008

1 commit

01 Jul, 2006

1 commit

09 Oct, 2005

1 commit

  • dd0fc66fb   [PATCH] gfp flags annotations - part 1 ... Browse Code »

    - 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
    Signed-off-by: Linus Torvalds

    Al Viro
     

05 Oct, 2005

1 commit

24 Jun, 2005

1 commit

  • df3fb93ad   [LIB]: Knuth-Morris-Pratt textsearch algorithm ... Browse Code »

    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
    Signed-off-by: David S. Miller

    Thomas Graf