File	Date	Author	Commit
build-aux	2021-06-14	Barry Schwartz	[c5ce91] Simplified the .hgignore
dsats2	2019-06-30	Barry Schwartz	[d0d919] Clean out dead code.
m4	2019-06-27	Barry Schwartz	[dafb71] Use MATS2 Integers. So far I am using it for po...
tests	2021-06-14	Barry Schwartz	[c5ce91] Simplified the .hgignore
.dir-locals.el	2018-09-13	Barry Schwartz	[750563] At least it can be compiled. Needs tests.
.hgignore	2021-06-14	Barry Schwartz	[c5ce91] Simplified the .hgignore
AUTHORS	2018-10-05	Barry Schwartz	[c3ac81] Enforce GNU package layout.
COPYING	2018-10-04	Barry Schwartz	[63f694] I had forgotten to include COPYING.
ChangeLog	2018-10-05	Barry Schwartz	[c3ac81] Enforce GNU package layout.
INSTALL	2018-10-05	Barry Schwartz	[c3ac81] Enforce GNU package layout.
Makefile.am	2019-06-30	Barry Schwartz	[d0d919] Clean out dead code.
Makefile.in	2021-06-14	Barry Schwartz	[c5ce91] Simplified the .hgignore
NEWS	2018-10-05	Barry Schwartz	[c3ac81] Enforce GNU package layout.
README	2018-10-05	Barry Schwartz	[c3ac81] Enforce GNU package layout.
aclocal.m4	2021-06-14	Barry Schwartz	[c5ce91] Simplified the .hgignore
configure	2021-06-14	Barry Schwartz	[c5ce91] Simplified the .hgignore
configure.ac	2019-06-27	Barry Schwartz	[dafb71] Use MATS2 Integers. So far I am using it for po...
dsats2-bitstring_maps.pc.in	2018-11-06	Barry Schwartz	[0e5ef1] Update the pkg-config file.

Read Me

# An implementation of immutable bitstring maps in ATS2/Postiats

Licensed GPL3 or later.

Immutable maps from strings of bits, such as machine integers, to
key-value pairs.

The implementation employs array mapped tries and might be used to
implement such things as integer maps and hashless string
maps. However, bitstring maps perform best when the keys are more
evenly distributed, and so are suitable, in particular, for ideal hash
trees, which are maps that use hashes of ‘unlimited’ length.

(In practice, one may use the same hash function repeatedly, but with
different seed values, and at some point guarantee termination by
using the bits of the key instead of a hash.)

## References.

  Bagwell, Phil. Ideal hash trees. 2001.

  Bagwell, Phil. Fast and space efficient trie searches. 2000.

## NOTE/WARNING: Regarding POPCOUNT instructions.

The implementation uses population counts (counts of the number of
1-bits in an integer) and so, if possible, one ought to enable
compiler options to emit POPCOUNT instructions. Otherwise a POPCOUNT
subroutine might be called or inline code used instead.

If you are using GCC and building just for the machine on which you
are compiling, the ‘-march=native’ option likely will suffice. On
AMD64, if you want to build for a wider range of processors, you can
use the ‘-mpopcnt’ option. Only quite old AMD64 processors do not have
POPCOUNT instructions.