lkml.org 
[lkml]   [2020]   [Jan]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Subject[PATCH v5 0/7] lib: rework bitmap_parse
Date
On top of next-20191220.

Similarly to recently revisited bitmap_parselist(), bitmap_parse()
is ineffective and overcomplicated. This series reworks it, aligns
its interface with bitmap_parselist() and makes it simpler to use.

The series also adds a test for the function and fixes usage of it
in cpumask_parse() according to the new design - drops the calculating
of length of an input string.

bitmap_parse() takes the array of numbers to be put into the map in
the BE order which is reversed to the natural LE order for bitmaps.
For example, to construct bitmap containing a bit on the position 42,
we have to put a line '400,0'. Current implementation reads chunk
one by one from the beginning ('400' before '0') and makes bitmap
shift after each successful parse. It makes the complexity of the
whole process as O(n^2). We can do it in reverse direction ('0'
before '400') and avoid shifting, but it requires reverse parsing
helpers.

Tested on arm64 and BE mips.

v1: https://lkml.org/lkml/2019/4/27/597
v2:
- strnchrnul() signature and description changed, ifdeffery and
exporting removed;
- test split for better demonstration of before/after changes;
- minor naming and formatting issues fixed.
v3:
- fix bitmap_clear() misuse.
- opencode in_str() helper.
- simplify while() in bitmap_parse()
v4:
- use isxdigit() where appropriate.
- clean signed-off-by list.
v5:
- remove isxdigit() with hex_to_bin() to avoid cache use by ctype
table.
- rebase on top of next-20191220.

Yury Norov (7):
lib/string: add strnchrnul()
bitops: more BITS_TO_* macros
lib: add test for bitmap_parse()
lib: make bitmap_parse_user a wrapper on bitmap_parse
lib: rework bitmap_parse()
lib: new testcases for bitmap_parse{_user}
cpumask: don't calculate length of the input string

include/linux/bitmap.h | 8 +-
include/linux/bitops.h | 5 +-
include/linux/cpumask.h | 4 +-
include/linux/string.h | 1 +
lib/bitmap.c | 193 +++++++++++++++++------------------
lib/string.c | 17 +++
lib/test_bitmap.c | 102 +++++++++++++++++-
tools/include/linux/bitops.h | 9 +-
8 files changed, 222 insertions(+), 117 deletions(-)

--
2.20.1

\
 
 \ /
  Last update: 2020-01-02 05:32    [W:0.044 / U:0.932 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site