• Yury Norov's avatar
    lib: rework bitmap_parse() · 2d626158
    Yury Norov authored
    bitmap_parse() is ineffective and full of opaque variables and opencoded
    parts.  It leads to hard understanding and usage of it.  This rework
    includes:
    
    - remove bitmap_shift_left() call from the cycle.  Now it makes the
      complexity of the algorithm as O(nbits^2).  In the suggested approach
      the input string is parsed in reverse direction, so no shifts needed;
    
    - relax requirement on a single comma and no white spaces between
      chunks.  It is considered useful in scripting, and it aligns with
      bitmap_parselist();
    
    - split bitmap_parse() to small readable helpers;
    
    - make an explicit calculation of the end of input line at the
      beginning, so users of the bitmap_parse() won't bother doing this.
    
    Link: http://lkml.kernel.org/r/20200102043031.30357-6-yury.norov@gmail.comSigned-off-by: default avatarYury Norov <yury.norov@gmail.com>
    Cc: Amritha Nambiar <amritha.nambiar@intel.com>
    Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
    Cc: Arnaldo Carvalho de Melo <acme@redhat.com>
    Cc: Chris Wilson <chris@chris-wilson.co.uk>
    Cc: Kees Cook <keescook@chromium.org>
    Cc: Matthew Wilcox <willy@infradead.org>
    Cc: Miklos Szeredi <mszeredi@redhat.com>
    Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
    Cc: Steffen Klassert <steffen.klassert@secunet.com>
    Cc: "Tobin C . Harding" <tobin@kernel.org>
    Cc: Vineet Gupta <vineet.gupta1@synopsys.com>
    Cc: Will Deacon <will.deacon@arm.com>
    Cc: Willem de Bruijn <willemb@google.com>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    2d626158
bitmap.c 37.9 KB