doc: Doxygen-friendly CuckooCache comments

ch4ot1c · ch4ot1c · commit 7aad3b68e7e1 · 2019-10-10T15:47:39.000-04:00
diff --git a/src/cuckoocache.h b/src/cuckoocache.h
@@ -14,42 +14,40 @@
 #include <vector>
 
 
-/** namespace CuckooCache provides high performance cache primitives
+/** High-performance cache primitives.
  *
  * Summary:
  *
- * 1) bit_packed_atomic_flags is bit-packed atomic flags for garbage collection
+ * 1. @ref bit_packed_atomic_flags is bit-packed atomic flags for garbage collection
  *
- * 2) cache is a cache which is performant in memory usage and lookup speed. It
- * is lockfree for erase operations. Elements are lazily erased on the next
- * insert.
+ * 2. @ref cache is a cache which is performant in memory usage and lookup speed. It
+ * is lockfree for erase operations. Elements are lazily erased on the next insert.
  */
 namespace CuckooCache
 {
-/** bit_packed_atomic_flags implements a container for garbage collection flags
+/** @ref bit_packed_atomic_flags implements a container for garbage collection flags
  * that is only thread unsafe on calls to setup. This class bit-packs collection
  * flags for memory efficiency.
  *
- * All operations are std::memory_order_relaxed so external mechanisms must
+ * All operations are `std::memory_order_relaxed` so external mechanisms must
  * ensure that writes and reads are properly synchronized.
  *
- * On setup(n), all bits up to n are marked as collected.
+ * On setup(n), all bits up to `n` are marked as collected.
  *
  * Under the hood, because it is an 8-bit type, it makes sense to use a multiple
  * of 8 for setup, but it will be safe if that is not the case as well.
- *
  */
 class bit_packed_atomic_flags
 {
     std::unique_ptr<std::atomic<uint8_t>[]> mem;
 
 public:
-    /** No default constructor as there must be some size */
+    /** No default constructor, as there must be some size. */
     bit_packed_atomic_flags() = delete;
 
     /**
      * bit_packed_atomic_flags constructor creates memory to sufficiently
-     * keep track of garbage collection information for size entries.
+     * keep track of garbage collection information for `size` entries.
      *
      * @param size the number of elements to allocate space for
      *
@@ -68,7 +66,7 @@ class bit_packed_atomic_flags
     };
 
     /** setup marks all entries and ensures that bit_packed_atomic_flags can store
-     * at least size entries
+     * at least `b` entries.
      *
      * @param b the number of elements to allocate space for
      * @post bit_set, bit_unset, and bit_is_set function properly forall x. x <
@@ -84,19 +82,18 @@ class bit_packed_atomic_flags
 
     /** bit_set sets an entry as discardable.
      *
-     * @param s the index of the entry to bit_set.
+     * @param s the index of the entry to bit_set
      * @post immediately subsequent call (assuming proper external memory
      * ordering) to bit_is_set(s) == true.
-     *
      */
     inline void bit_set(uint32_t s)
     {
         mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed);
     }
 
-    /**  bit_unset marks an entry as something that should not be overwritten
+    /** bit_unset marks an entry as something that should not be overwritten.
      *
-     * @param s the index of the entry to bit_unset.
+     * @param s the index of the entry to bit_unset
      * @post immediately subsequent call (assuming proper external memory
      * ordering) to bit_is_set(s) == false.
      */
@@ -105,26 +102,26 @@ class bit_packed_atomic_flags
         mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed);
     }
 
-    /** bit_is_set queries the table for discardability at s
+    /** bit_is_set queries the table for discardability at `s`.
      *
-     * @param s the index of the entry to read.
-     * @returns if the bit at index s was set.
+     * @param s the index of the entry to read
+     * @returns true if the bit at index `s` was set, false otherwise
      * */
     inline bool bit_is_set(uint32_t s) const
     {
         return (1 << (s & 7)) & mem[s >> 3].load(std::memory_order_relaxed);
     }
 };
 
-/** cache implements a cache with properties similar to a cuckoo-set
+/** @ref cache implements a cache with properties similar to a cuckoo-set.
  *
- *  The cache is able to hold up to (~(uint32_t)0) - 1 elements.
+ *  The cache is able to hold up to `(~(uint32_t)0) - 1` elements.
  *
  *  Read Operations:
- *      - contains(*, false)
+ *      - contains() for `erase=false`
  *
  *  Read+Erase Operations:
- *      - contains(*, true)
+ *      - contains() for `erase=true`
  *
  *  Erase Operations:
  *      - allow_erase()
@@ -141,10 +138,10 @@ class bit_packed_atomic_flags
  *
  * User Must Guarantee:
  *
- * 1) Write Requires synchronized access (e.g., a lock)
- * 2) Read Requires no concurrent Write, synchronized with the last insert.
- * 3) Erase requires no concurrent Write, synchronized with last insert.
- * 4) An Erase caller must release all memory before allowing a new Writer.
+ * 1. Write requires synchronized access (e.g. a lock)
+ * 2. Read requires no concurrent Write, synchronized with last insert.
+ * 3. Erase requires no concurrent Write, synchronized with last insert.
+ * 4. An Erase caller must release all memory before allowing a new Writer.
  *
  *
  * Note on function names:
@@ -177,7 +174,7 @@ class cache
     mutable std::vector<bool> epoch_flags;
 
     /** epoch_heuristic_counter is used to determine when an epoch might be aged
-     * & an expensive scan should be done.  epoch_heuristic_counter is
+     * & an expensive scan should be done. epoch_heuristic_counter is
      * decremented on insert and reset to the new number of inserts which would
      * cause the epoch to reach epoch_size when it reaches zero.
      */
@@ -194,24 +191,25 @@ class cache
     uint32_t epoch_size;
 
     /** depth_limit determines how many elements insert should try to replace.
-     * Should be set to log2(n)*/
+     * Should be set to log2(n).
+     */
     uint8_t depth_limit;
 
     /** hash_function is a const instance of the hash function. It cannot be
      * static or initialized at call time as it may have internal state (such as
      * a nonce).
-     * */
+     */
     const Hash hash_function;
 
     /** compute_hashes is convenience for not having to write out this
      * expression everywhere we use the hash values of an Element.
      *
      * We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a
-     *  manner which preserves as much of the hash's uniformity as possible.  Ideally
+     *  manner which preserves as much of the hash's uniformity as possible. Ideally
      *  this would be done by bitmasking but the size is usually not a power of two.
      *
      * The naive approach would be to use a mod -- which isn't perfectly uniform but so
-     *  long as the hash is much larger than size it is not that bad.  Unfortunately,
+     *  long as the hash is much larger than size it is not that bad. Unfortunately,
      *  mod/division is fairly slow on ordinary microprocessors (e.g. 90-ish cycles on
      *  haswell, ARM doesn't even have an instruction for it.); when the divisor is a
      *  constant the compiler will do clever tricks to turn it into a multiply+add+shift,
@@ -223,10 +221,10 @@ class cache
      *  somewhat complicated and the result is still slower than other options:
      *
      * Instead we treat the 32-bit random number as a Q32 fixed-point number in the range
-     *  [0,1) and simply multiply it by the size.  Then we just shift the result down by
-     *  32-bits to get our bucket number.  The result has non-uniformity the same as a
+     *  [0, 1) and simply multiply it by the size. Then we just shift the result down by
+     *  32-bits to get our bucket number. The result has non-uniformity the same as a
      *  mod, but it is much faster to compute. More about this technique can be found at
-     *  http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
+     *  http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ .
      *
      * The resulting non-uniformity is also more equally distributed which would be
      *  advantageous for something like linear probing, though it shouldn't matter
@@ -237,8 +235,8 @@ class cache
      *  32*32->64 multiply, which means the operation is reasonably fast even on a
      *  typical 32-bit processor.
      *
-     * @param e the element whose hashes will be returned
-     * @returns std::array<uint32_t, 8> of deterministic hashes derived from e
+     * @param e The element whose hashes will be returned
+     * @returns Deterministic hashes derived from `e` uniformly mapped onto the range [0, size)
      */
     inline std::array<uint32_t, 8> compute_hashes(const Element& e) const
     {
@@ -252,14 +250,14 @@ class cache
                  (uint32_t)(((uint64_t)hash_function.template operator()<7>(e) * (uint64_t)size) >> 32)}};
     }
 
-    /* end
-     * @returns a constexpr index that can never be inserted to */
+    /** invalid returns a special index that can never be inserted to
+     * @returns the special constexpr index that can never be inserted to */
     constexpr uint32_t invalid() const
     {
         return ~(uint32_t)0;
     }
 
-    /** allow_erase marks the element at index n as discardable. Threadsafe
+    /** allow_erase marks the element at index `n` as discardable. Threadsafe
      * without any concurrent insert.
      * @param n the index to allow erasure of
      */
@@ -268,7 +266,7 @@ class cache
         collection_flags.bit_set(n);
     }
 
-    /** please_keep marks the element at index n as an entry that should be kept.
+    /** please_keep marks the element at index `n` as an entry that should be kept.
      * Threadsafe without any concurrent insert.
      * @param n the index to prioritize keeping
      */
@@ -336,7 +334,7 @@ class cache
      *
      * @param new_size the desired number of elements to store
      * @returns the maximum number of elements storable
-     **/
+     */
     uint32_t setup(uint32_t new_size)
     {
         // depth_limit must be at least one otherwise errors can occur.
@@ -360,7 +358,7 @@ class cache
      * negligible compared to the size of the elements.
      *
      * @param bytes the approximate number of bytes to use for this data
-     * structure.
+     * structure
      * @returns the maximum number of elements storable (see setup()
      * documentation for more detail)
      */
@@ -376,18 +374,19 @@ class cache
      * It drops the last tried element if it runs out of depth before
      * encountering an open slot.
      *
-     * Thus
+     * Thus:
      *
+     * ```
      * insert(x);
      * return contains(x, false);
+     * ```
      *
      * is not guaranteed to return true.
      *
      * @param e the element to insert
      * @post one of the following: All previously inserted elements and e are
      * now in the table, one previously inserted element is evicted from the
      * table, the entry attempted to be inserted is evicted.
-     *
      */
     inline void insert(Element e)
     {
@@ -416,9 +415,9 @@ class cache
             /** Swap with the element at the location that was
             * not the last one looked at. Example:
             *
-            * 1) On first iteration, last_loc == invalid(), find returns last, so
+            * 1. On first iteration, last_loc == invalid(), find returns last, so
             *    last_loc defaults to locs[0].
-            * 2) On further iterations, where last_loc == locs[k], last_loc will
+            * 2. On further iterations, where last_loc == locs[k], last_loc will
             *    go to locs[k+1 % 8], i.e., next of the 8 indices wrapping around
             *    to 0 if needed.
             *
@@ -439,17 +438,19 @@ class cache
         }
     }
 
-    /* contains iterates through the hash locations for a given element
+    /** contains iterates through the hash locations for a given element
      * and checks to see if it is present.
      *
      * contains does not check garbage collected state (in other words,
      * garbage is only collected when the space is needed), so:
      *
+     * ```
      * insert(x);
      * if (contains(x, true))
      *     return contains(x, false);
      * else
      *     return true;
+     * ```
      *
      * executed on a single thread will always return true!
      *
@@ -458,7 +459,7 @@ class cache
      * contains returns a bool set true if the element was found.
      *
      * @param e the element to check
-     * @param erase
+     * @param erase whether to attempt setting the garbage collect flag
      *
      * @post if erase is true and the element is found, then the garbage collect
      * flag is set
diff --git a/src/test/cuckoocache_tests.cpp b/src/test/cuckoocache_tests.cpp
@@ -10,11 +10,11 @@
 
 /** Test Suite for CuckooCache
  *
- *  1) All tests should have a deterministic result (using insecure rand
+ *  1. All tests should have a deterministic result (using insecure rand
  *  with deterministic seeds)
- *  2) Some test methods are templated to allow for easier testing
+ *  2. Some test methods are templated to allow for easier testing
  *  against new versions / comparing
- *  3) Results should be treated as a regression test, i.e., did the behavior
+ *  3. Results should be treated as a regression test, i.e., did the behavior
  *  change significantly from what was expected. This can be OK, depending on
  *  the nature of the change, but requires updating the tests to reflect the new
  *  expected behavior. For example improving the hit rate may cause some tests
@@ -82,9 +82,9 @@ static double test_cache(size_t megabytes, double load)
  *
  * Examples:
  *
- * 1) at load 0.5, we expect a perfect hit rate, so we multiply by
+ * 1. at load 0.5, we expect a perfect hit rate, so we multiply by
  * 1.0
- * 2) at load 2.0, we expect to see half the entries, so a perfect hit rate
+ * 2. at load 2.0, we expect to see half the entries, so a perfect hit rate
  * would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the
  * normalized hit rate.
  *

Original file line number	Diff line number	Diff line change
`@@ -14,42 +14,40 @@`
`14`	`14`	`#include <vector>`
`15`	`15`
`16`	`16`
`17`		`-/** namespace CuckooCache provides high performance cache primitives`
	`17`	`+/** High-performance cache primitives.`
`18`	`18`	`*`
`19`	`19`	`* Summary:`
`20`	`20`	`*`
`21`		`- * 1) bit_packed_atomic_flags is bit-packed atomic flags for garbage collection`
	`21`	`+ * 1. @ref bit_packed_atomic_flags is bit-packed atomic flags for garbage collection`
`22`	`22`	`*`
`23`		`- * 2) cache is a cache which is performant in memory usage and lookup speed. It`
`24`		`- * is lockfree for erase operations. Elements are lazily erased on the next`
`25`		`- * insert.`
	`23`	`+ * 2. @ref cache is a cache which is performant in memory usage and lookup speed. It`
	`24`	`+ * is lockfree for erase operations. Elements are lazily erased on the next insert.`
`26`	`25`	`*/`
`27`	`26`	`namespace CuckooCache`
`28`	`27`	`{`
`29`		`-/** bit_packed_atomic_flags implements a container for garbage collection flags`
	`28`	`+/** @ref bit_packed_atomic_flags implements a container for garbage collection flags`
`30`	`29`	`* that is only thread unsafe on calls to setup. This class bit-packs collection`
`31`	`30`	`* flags for memory efficiency.`
`32`	`31`	`*`
`33`		`- * All operations are std::memory_order_relaxed so external mechanisms must`
	`32`	+ * All operations are `std::memory_order_relaxed` so external mechanisms must
`34`	`33`	`* ensure that writes and reads are properly synchronized.`
`35`	`34`	`*`
`36`		`- * On setup(n), all bits up to n are marked as collected.`
	`35`	+ * On setup(n), all bits up to `n` are marked as collected.
`37`	`36`	`*`
`38`	`37`	`* Under the hood, because it is an 8-bit type, it makes sense to use a multiple`
`39`	`38`	`* of 8 for setup, but it will be safe if that is not the case as well.`
`40`		`- *`
`41`	`39`	`*/`
`42`	`40`	`class bit_packed_atomic_flags`
`43`	`41`	`{`
`44`	`42`	`std::unique_ptr<std::atomic<uint8_t>[]> mem;`
`45`	`43`
`46`	`44`	`public:`
`47`		`- /** No default constructor as there must be some size */`
	`45`	`+ /** No default constructor, as there must be some size. */`
`48`	`46`	`bit_packed_atomic_flags() = delete;`
`49`	`47`
`50`	`48`	`/**`
`51`	`49`	`* bit_packed_atomic_flags constructor creates memory to sufficiently`
`52`		`- * keep track of garbage collection information for size entries.`
	`50`	+ * keep track of garbage collection information for `size` entries.
`53`	`51`	`*`
`54`	`52`	`* @param size the number of elements to allocate space for`
`55`	`53`	`*`
`@@ -68,7 +66,7 @@ class bit_packed_atomic_flags`
`68`	`66`	`};`
`69`	`67`
`70`	`68`	`/** setup marks all entries and ensures that bit_packed_atomic_flags can store`
`71`		`- * at least size entries`
	`69`	+ * at least `b` entries.
`72`	`70`	`*`
`73`	`71`	`* @param b the number of elements to allocate space for`
`74`	`72`	`* @post bit_set, bit_unset, and bit_is_set function properly forall x. x <`
`@@ -84,19 +82,18 @@ class bit_packed_atomic_flags`
`84`	`82`
`85`	`83`	`/** bit_set sets an entry as discardable.`
`86`	`84`	`*`
`87`		`- * @param s the index of the entry to bit_set.`
	`85`	`+ * @param s the index of the entry to bit_set`
`88`	`86`	`* @post immediately subsequent call (assuming proper external memory`
`89`	`87`	`* ordering) to bit_is_set(s) == true.`
`90`		`- *`
`91`	`88`	`*/`
`92`	`89`	`inline void bit_set(uint32_t s)`
`93`	`90`	`{`
`94`	`91`	`mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed);`
`95`	`92`	`}`
`96`	`93`
`97`		`- /** bit_unset marks an entry as something that should not be overwritten`
	`94`	`+ /** bit_unset marks an entry as something that should not be overwritten.`
`98`	`95`	`*`
`99`		`- * @param s the index of the entry to bit_unset.`
	`96`	`+ * @param s the index of the entry to bit_unset`
`100`	`97`	`* @post immediately subsequent call (assuming proper external memory`
`101`	`98`	`* ordering) to bit_is_set(s) == false.`
`102`	`99`	`*/`
`@@ -105,26 +102,26 @@ class bit_packed_atomic_flags`
`105`	`102`	`mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed);`
`106`	`103`	`}`
`107`	`104`
`108`		`- /** bit_is_set queries the table for discardability at s`
	`105`	+ /** bit_is_set queries the table for discardability at `s`.
`109`	`106`	`*`
`110`		`- * @param s the index of the entry to read.`
`111`		`- * @returns if the bit at index s was set.`
	`107`	`+ * @param s the index of the entry to read`
	`108`	+ * @returns true if the bit at index `s` was set, false otherwise
`112`	`109`	`* */`
`113`	`110`	`inline bool bit_is_set(uint32_t s) const`
`114`	`111`	`{`
`115`	`112`	`return (1 << (s & 7)) & mem[s >> 3].load(std::memory_order_relaxed);`
`116`	`113`	`}`
`117`	`114`	`};`
`118`	`115`
`119`		`-/** cache implements a cache with properties similar to a cuckoo-set`
	`116`	`+/** @ref cache implements a cache with properties similar to a cuckoo-set.`
`120`	`117`	`*`
`121`		`- * The cache is able to hold up to (~(uint32_t)0) - 1 elements.`
	`118`	+ * The cache is able to hold up to `(~(uint32_t)0) - 1` elements.
`122`	`119`	`*`
`123`	`120`	`* Read Operations:`
`124`		`- * - contains(*, false)`
	`121`	+ * - contains() for `erase=false`
`125`	`122`	`*`
`126`	`123`	`* Read+Erase Operations:`
`127`		`- * - contains(*, true)`
	`124`	+ * - contains() for `erase=true`
`128`	`125`	`*`
`129`	`126`	`* Erase Operations:`
`130`	`127`	`* - allow_erase()`
`@@ -141,10 +138,10 @@ class bit_packed_atomic_flags`
`141`	`138`	`*`
`142`	`139`	`* User Must Guarantee:`
`143`	`140`	`*`
`144`		`- * 1) Write Requires synchronized access (e.g., a lock)`
`145`		`- * 2) Read Requires no concurrent Write, synchronized with the last insert.`
`146`		`- * 3) Erase requires no concurrent Write, synchronized with last insert.`
`147`		`- * 4) An Erase caller must release all memory before allowing a new Writer.`
	`141`	`+ * 1. Write requires synchronized access (e.g. a lock)`
	`142`	`+ * 2. Read requires no concurrent Write, synchronized with last insert.`
	`143`	`+ * 3. Erase requires no concurrent Write, synchronized with last insert.`
	`144`	`+ * 4. An Erase caller must release all memory before allowing a new Writer.`
`148`	`145`	`*`
`149`	`146`	`*`
`150`	`147`	`* Note on function names:`
`@@ -177,7 +174,7 @@ class cache`
`177`	`174`	`mutable std::vector<bool> epoch_flags;`
`178`	`175`
`179`	`176`	`/** epoch_heuristic_counter is used to determine when an epoch might be aged`
`180`		`- * & an expensive scan should be done. epoch_heuristic_counter is`
	`177`	`+ * & an expensive scan should be done. epoch_heuristic_counter is`
`181`	`178`	`* decremented on insert and reset to the new number of inserts which would`
`182`	`179`	`* cause the epoch to reach epoch_size when it reaches zero.`
`183`	`180`	`*/`
`@@ -194,24 +191,25 @@ class cache`
`194`	`191`	`uint32_t epoch_size;`
`195`	`192`
`196`	`193`	`/** depth_limit determines how many elements insert should try to replace.`
`197`		`- * Should be set to log2(n)*/`
	`194`	`+ * Should be set to log2(n).`
	`195`	`+ */`
`198`	`196`	`uint8_t depth_limit;`
`199`	`197`
`200`	`198`	`/** hash_function is a const instance of the hash function. It cannot be`
`201`	`199`	`* static or initialized at call time as it may have internal state (such as`
`202`	`200`	`* a nonce).`
`203`		`- * */`
	`201`	`+ */`
`204`	`202`	`const Hash hash_function;`
`205`	`203`
`206`	`204`	`/** compute_hashes is convenience for not having to write out this`
`207`	`205`	`* expression everywhere we use the hash values of an Element.`
`208`	`206`	`*`
`209`	`207`	`* We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a`
`210`		`- * manner which preserves as much of the hash's uniformity as possible. Ideally`
	`208`	`+ * manner which preserves as much of the hash's uniformity as possible. Ideally`
`211`	`209`	`* this would be done by bitmasking but the size is usually not a power of two.`
`212`	`210`	`*`
`213`	`211`	`* The naive approach would be to use a mod -- which isn't perfectly uniform but so`
`214`		`- * long as the hash is much larger than size it is not that bad. Unfortunately,`
	`212`	`+ * long as the hash is much larger than size it is not that bad. Unfortunately,`
`215`	`213`	`* mod/division is fairly slow on ordinary microprocessors (e.g. 90-ish cycles on`
`216`	`214`	`* haswell, ARM doesn't even have an instruction for it.); when the divisor is a`
`217`	`215`	`* constant the compiler will do clever tricks to turn it into a multiply+add+shift,`
`@@ -223,10 +221,10 @@ class cache`
`223`	`221`	`* somewhat complicated and the result is still slower than other options:`
`224`	`222`	`*`
`225`	`223`	`* Instead we treat the 32-bit random number as a Q32 fixed-point number in the range`
`226`		`- * [0,1) and simply multiply it by the size. Then we just shift the result down by`
`227`		`- * 32-bits to get our bucket number. The result has non-uniformity the same as a`
	`224`	`+ * [0, 1) and simply multiply it by the size. Then we just shift the result down by`
	`225`	`+ * 32-bits to get our bucket number. The result has non-uniformity the same as a`
`228`	`226`	`* mod, but it is much faster to compute. More about this technique can be found at`
`229`		`- * http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/`
	`227`	`+ * http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ .`
`230`	`228`	`*`
`231`	`229`	`* The resulting non-uniformity is also more equally distributed which would be`
`232`	`230`	`* advantageous for something like linear probing, though it shouldn't matter`
`@@ -237,8 +235,8 @@ class cache`
`237`	`235`	`* 32*32->64 multiply, which means the operation is reasonably fast even on a`
`238`	`236`	`* typical 32-bit processor.`
`239`	`237`	`*`
`240`		`- * @param e the element whose hashes will be returned`
`241`		`- * @returns std::array<uint32_t, 8> of deterministic hashes derived from e`
	`238`	`+ * @param e The element whose hashes will be returned`
	`239`	+ * @returns Deterministic hashes derived from `e` uniformly mapped onto the range [0, size)
`242`	`240`	`*/`
`243`	`241`	`inline std::array<uint32_t, 8> compute_hashes(const Element& e) const`
`244`	`242`	`{`
`@@ -252,14 +250,14 @@ class cache`
`252`	`250`	`(uint32_t)(((uint64_t)hash_function.template operator()<7>(e) * (uint64_t)size) >> 32)}};`
`253`	`251`	`}`
`254`	`252`
`255`		`- /* end`
`256`		`- * @returns a constexpr index that can never be inserted to */`
	`253`	`+ /** invalid returns a special index that can never be inserted to`
	`254`	`+ * @returns the special constexpr index that can never be inserted to */`
`257`	`255`	`constexpr uint32_t invalid() const`
`258`	`256`	`{`
`259`	`257`	`return ~(uint32_t)0;`
`260`	`258`	`}`
`261`	`259`
`262`		`- /** allow_erase marks the element at index n as discardable. Threadsafe`
	`260`	+ /** allow_erase marks the element at index `n` as discardable. Threadsafe
`263`	`261`	`* without any concurrent insert.`
`264`	`262`	`* @param n the index to allow erasure of`
`265`	`263`	`*/`
`@@ -268,7 +266,7 @@ class cache`
`268`	`266`	`collection_flags.bit_set(n);`
`269`	`267`	`}`
`270`	`268`
`271`		`- /** please_keep marks the element at index n as an entry that should be kept.`
	`269`	+ /** please_keep marks the element at index `n` as an entry that should be kept.
`272`	`270`	`* Threadsafe without any concurrent insert.`
`273`	`271`	`* @param n the index to prioritize keeping`
`274`	`272`	`*/`
`@@ -336,7 +334,7 @@ class cache`
`336`	`334`	`*`
`337`	`335`	`* @param new_size the desired number of elements to store`
`338`	`336`	`* @returns the maximum number of elements storable`
`339`		`- **/`
	`337`	`+ */`
`340`	`338`	`uint32_t setup(uint32_t new_size)`
`341`	`339`	`{`
`342`	`340`	`// depth_limit must be at least one otherwise errors can occur.`
`@@ -360,7 +358,7 @@ class cache`
`360`	`358`	`* negligible compared to the size of the elements.`
`361`	`359`	`*`
`362`	`360`	`* @param bytes the approximate number of bytes to use for this data`
`363`		`- * structure.`
	`361`	`+ * structure`
`364`	`362`	`* @returns the maximum number of elements storable (see setup()`
`365`	`363`	`* documentation for more detail)`
`366`	`364`	`*/`
`@@ -376,18 +374,19 @@ class cache`
`376`	`374`	`* It drops the last tried element if it runs out of depth before`
`377`	`375`	`* encountering an open slot.`
`378`	`376`	`*`
`379`		`- * Thus`
	`377`	`+ * Thus:`
`380`	`378`	`*`
	`379`	+ * ```
`381`	`380`	`* insert(x);`
`382`	`381`	`* return contains(x, false);`
	`382`	+ * ```
`383`	`383`	`*`
`384`	`384`	`* is not guaranteed to return true.`
`385`	`385`	`*`
`386`	`386`	`* @param e the element to insert`
`387`	`387`	`* @post one of the following: All previously inserted elements and e are`
`388`	`388`	`* now in the table, one previously inserted element is evicted from the`
`389`	`389`	`* table, the entry attempted to be inserted is evicted.`
`390`		`- *`
`391`	`390`	`*/`
`392`	`391`	`inline void insert(Element e)`
`393`	`392`	`{`
`@@ -416,9 +415,9 @@ class cache`
`416`	`415`	`/** Swap with the element at the location that was`
`417`	`416`	`* not the last one looked at. Example:`
`418`	`417`	`*`
`419`		`- * 1) On first iteration, last_loc == invalid(), find returns last, so`
	`418`	`+ * 1. On first iteration, last_loc == invalid(), find returns last, so`
`420`	`419`	`* last_loc defaults to locs[0].`
`421`		`- * 2) On further iterations, where last_loc == locs[k], last_loc will`
	`420`	`+ * 2. On further iterations, where last_loc == locs[k], last_loc will`
`422`	`421`	`* go to locs[k+1 % 8], i.e., next of the 8 indices wrapping around`
`423`	`422`	`* to 0 if needed.`
`424`	`423`	`*`
`@@ -439,17 +438,19 @@ class cache`
`439`	`438`	`}`
`440`	`439`	`}`
`441`	`440`
`442`		`- /* contains iterates through the hash locations for a given element`
	`441`	`+ /** contains iterates through the hash locations for a given element`
`443`	`442`	`* and checks to see if it is present.`
`444`	`443`	`*`
`445`	`444`	`* contains does not check garbage collected state (in other words,`
`446`	`445`	`* garbage is only collected when the space is needed), so:`
`447`	`446`	`*`
	`447`	+ * ```
`448`	`448`	`* insert(x);`
`449`	`449`	`* if (contains(x, true))`
`450`	`450`	`* return contains(x, false);`
`451`	`451`	`* else`
`452`	`452`	`* return true;`
	`453`	+ * ```
`453`	`454`	`*`
`454`	`455`	`* executed on a single thread will always return true!`
`455`	`456`	`*`
`@@ -458,7 +459,7 @@ class cache`
`458`	`459`	`* contains returns a bool set true if the element was found.`
`459`	`460`	`*`
`460`	`461`	`* @param e the element to check`
`461`		`- * @param erase`
	`462`	`+ * @param erase whether to attempt setting the garbage collect flag`
`462`	`463`	`*`
`463`	`464`	`* @post if erase is true and the element is found, then the garbage collect`
`464`	`465`	`* flag is set`