New hmap and hmapx hash table implementations.
authorBen Pfaff <blp@gnu.org>
Sat, 27 Sep 2008 03:42:01 +0000 (20:42 -0700)
committerBen Pfaff <blp@gnu.org>
Wed, 1 Oct 2008 03:36:03 +0000 (20:36 -0700)
commitc1e75ee809efd2f4bfd9ebcc1c2b0689c1da0e4c
tree71a47ff8cdb79146106c13fea4808b41a56e6b1d
parentbe412d7b78faa1598408c8b9f35375f3918e8274
New hmap and hmapx hash table implementations.

These new hash table implementations should yield better performance
than the older one, for at least two reasons.  First, they are based
on "separate chaining" rather than "open addressing", and thus do not
suffer from clustering, which is likely to be an issue with the hash
functions that we have been using.  Second, they are carefully written
to generate simple code that should inline well.

Also, move the existing hash functions into a new pair of files,
src/lib/hash-functions.[ch].  This allows users of the new hash tables
to use them without including the older hash table header.
12 files changed:
src/libpspp/automake.mk
src/libpspp/hash-functions.c [new file with mode: 0644]
src/libpspp/hash-functions.h [new file with mode: 0644]
src/libpspp/hash.c
src/libpspp/hash.h
src/libpspp/hmap.c [new file with mode: 0644]
src/libpspp/hmap.h [new file with mode: 0644]
src/libpspp/hmapx.c [new file with mode: 0644]
src/libpspp/hmapx.h [new file with mode: 0644]
tests/automake.mk
tests/libpspp/hmap-test.c [new file with mode: 0644]
tests/libpspp/hmapx-test.c [new file with mode: 0644]