Add support for Alexey Tourbin's QSORT code (#708)

* Add support for Alexey Tourbin's QSORT code

See https://github.com/svpv/qsort

* Add benchmark scripts and compilation mode

Compile with `make O_BENCHMARK=1`, and run benchmarks with e.g.:
  ./misc/test/benchmark.sh ./nnn '/' '/usr/bin' '/usr/lib' > benchdata
You can then plot basic violin graphs with:
  ./misc/test/plot-bench.py benchdata

* Update style, doc, haiku support, fix lint

3 files changed, 67 insertions, 0 deletions

diff --git a/misc/haiku/Makefile b/misc/haiku/Makefile
index 34057df..6ab4544 100644
--- a/misc/haiku/Makefile
+++ b/misc/haiku/Makefile
@@ -18,6 +18,8 @@ O_NOBATCH := 0  # no built-in batch renamer
 O_NOFIFO := 0  # no FIFO previewer support
 O_CTX8 := 0  # enable 8 contexts
 O_ICONS := 0  # support icons
+O_QSORT := 0  # use Alexey Tourbin's QSORT implementation
+O_BENCH := 0  # benchmark mode (stops at first user input)
 
 # convert targets to flags for backwards compatibility
 ifneq ($(filter debug,$(MAKECMDGOALS)),)
@@ -74,6 +76,14 @@ ifeq ($(O_ICONS),1)
 	CPPFLAGS += -DICONS
 endif
 
+ifeq ($(O_QSORT),1)
+	CPPFLAGS += -DTOURBIN_QSORT
+endif
+
+ifeq ($(O_BENCH),1)
+	CPPFLAGS += -DBENCH
+endif
+
 ifeq ($(shell $(PKG_CONFIG) ncursesw && echo 1),1)
 	CFLAGS_CURSES ?= $(shell $(PKG_CONFIG) --cflags ncursesw)
 	LDLIBS_CURSES ?= $(shell $(PKG_CONFIG) --libs   ncursesw)
diff --git a/misc/test/benchmark.sh b/misc/test/benchmark.sh
new file mode 100755
index 0000000..fb56d01
--- /dev/null
+++ b/misc/test/benchmark.sh
@@ -0,0 +1,37 @@
+#!/bin/sh
+#
+# Usage: ./misc/test/benchmark.sh ./nnn /tmp/testdir1 ./testdir2 ...
+#
+# Don't forget to build nnn in benchmark mode: make O_BENCH=1
+
+# Use a test dir filled with genfiles.sh to get interesting output
+# (or maybe /usr/lib/)
+
+LANG=C
+
+TIME_VAL=${TIME_VAL:-"real"}
+
+SAMPLES=${SAMPLES:-100}
+
+EXE=$1
+
+bench_val () {
+    (time "$1" "$2") 2>&1 |\
+    awk '$1=="'"$TIME_VAL"'"{match($2, /[0-9]*\.[0-9]*/) ; print substr($2, RSTART, RLENGTH)}'
+}
+
+bench_dir () {
+    i=$SAMPLES
+    printf "$2"
+    while [ $((i--)) -gt 0 ] ; do
+        printf "\t%s" "$(bench_val "$1" "$2")"
+    done
+    printf "\n"
+}
+
+shift
+
+for dir in "$@" ; do
+    bench_dir "$EXE" "$dir"
+done
+
diff --git a/misc/test/plot-bench.py b/misc/test/plot-bench.py
new file mode 100755
index 0000000..b708fec
--- /dev/null
+++ b/misc/test/plot-bench.py
@@ -0,0 +1,20 @@
+#!/usr/bin/env python3
+#
+# Usage: ./plot-bench.py datafile
+# (where datafile is the output of benchmark.sh)
+
+import matplotlib.pyplot as plt
+import sys
+
+def bench_file_to_lists(infile):
+    return [[float(entry) for entry in line.split('\t')[1:]] for line in infile.readlines()]
+
+def plot_data(data):
+    fig = plt.figure()
+    ax = fig.add_axes([0,0,1,1])
+    ax.violinplot(data)
+    plt.savefig("plot.svg")
+
+filename = sys.argv[1]
+
+plot_data(bench_file_to_lists(open(filename)))