Import and use Mesa's hash table

With `perf record`/`perf report` I saw that 30% of the time was spent in
`sqfs_frag_table_find_tail_end` with tar2sqfs for a tarball containing
the Gentoo ebuild repository (many thousands of small files).

The reason was the bucketing hash table in frag_table.c: too many
elements in too few buckets meant lots of walking over the linked lists.

This patch replaces that hash table with the hash table implementation
from Mesa. Its implementation is more complex (is is an open-addressing,
linear-reprobing) hash table, but it is much better suited for the task.

On my 4c/8t Skylake, the time to run tar2sqfs drops from 7.5s to less
than 3s. CPU usage increases from ~207% to ~356%, presumably indicating
an increase in available parallelism due to the removal of the hash
table as a bottleneck. The `perf report` profile with this patch shows
that the time spent in `sqfs_frag_table_find_tail_end` has dropped from
~30% to 0.01%.

Output from ministat:

x before
+ after
    N          Min          Max       Median          Avg        Stddev
x  20        7.476        7.685       7.5725       7.5615   0.051254268
+  20         2.79        2.901        2.846      2.84475    0.03543842
Difference at 95.0% confidence
	-4.71675 +/- 0.0282015
	-62.3785% +/- 0.241477%
	(Student's t, pooled s = 0.0440618)

I imported only the bits of the hash table implementation that were
needed for frag_table.c. Among the changes I made after importing are

    - removed usage of ralloc, Mesa's recursive memory allocator
      - Replaced ralloc -> malloc
		 ralloc_free -> free
                 rzalloc_array -> calloc
      - Removed mem_ctx parameters
      - Added free()s to the appropriate places (valgrind confirms there
	are no leaks)
    - removed _mesa_-prefix from function names

Fixes: #40
Signed-off-by: Matt Turner <mattst88@gmail.com>

1 files changed, 2 insertions, 0 deletions

diff --git a/COPYING.md b/COPYING.md
index 00d539a..b86177e 100644
--- a/COPYING.md
+++ b/COPYING.md
@@ -14,6 +14,8 @@ with the following exceptions:
  - `lib/sqfs/comp/zlib` contains files that have been extracted from the the
    zlib compression library and modified. See `lib/sqfs/comp/zlib/README` for
    details and `licenses/zlib.txt` for details.
+ - `lib/util/hash_table.*` and `lib/util/fast_urem_by_const.h` contain a hash
+   table implementation (MIT license).
 
 The rest of squashfs-tools-ng is released under the terms and conditions of
 the **GNU General Public License version 3 or later**.