Update README to explicitly state that functions must be invertible (fix #16)

[junction.git] / README.md

diff --git a/README.md b/README.md
index 1bf35aceebc94ba2b779e949fd071cf53ff22fdd..47295f3a20cc3f5e89fa716dfa102e10ea0d91f3 100644 (file)
--- a/README.md
+++ b/README.md
@@ -1,7 +1,8 @@
-Junction is a library of concurrent data structures in C++. It contains three hash map implementations:
+Junction is a library of concurrent data structures in C++. It contains several hash map implementations:
 
+    junction::ConcurrentMap_Crude
     junction::ConcurrentMap_Linear
-    junction::ConcurrentMap_LeapFrog
+    junction::ConcurrentMap_Leapfrog
     junction::ConcurrentMap_Grampa
 
 [CMake](https://cmake.org/) and [Turf](https://github.com/preshing/turf) are required. See the blog post [New Concurrent Hash Maps for C++](http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/) for more information.
@@ -96,6 +97,15 @@ Many header files in Turf, and some in Junction, are configurable using preproce
 
 The `JUNCTION_USERCONFIG` variable works in a similar way. As an example, take a look at the Python script `junction/samples/MapScalabilityTests/TestAllMaps.py`. This script invokes `cmake` several times, passing a different `junction_userconfig.h.in` file each time. That's how it builds the same test application using different map implementations.
 
+## Rules and Behavior
+
+Currently, Junction maps only work with integer or pointer-sized keys. The hash function must be invertible, so that every key has a unique hash. Otherwise, A Junction map is a lot like a big array of `std::atomic<>` variables, where the key is an index into the array. More precisely:
+
+* All of a Junction map's member functions, together with its `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion.
+* If an `assign` [happens before](http://preshing.com/20130702/the-happens-before-relation/) a `get` with the same key, the `get` will return the value it inserted, except if another operation changes the value in between. Any [synchronizing operation](http://preshing.com/20130823/the-synchronizes-with-relation/) will establish this relationship.
+* For Linear, Leapfrog and Grampa maps, `assign` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed.
+* In the current version, you must not `assign` while concurrently using an `Iterator`.
+
 ## Feedback
 
 If you have any feedback on improving these steps, feel free to [open an issue](https://github.com/preshing/junction/issues) on GitHub, or send a direct message using the [contact form](http://preshing.com/contact/) on my blog.