úÎ’—†÷O      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMN SafeÖ#A typeclass for hash tables in the OV monad. The operations on these hash tables are typically both key- and value-strict.)Creates a new, default-sized hash table. O(1).'Creates a new hash table sized to hold n elements. O(n). Generalized update. Given a key k, and a user function f, calls:6`f Nothing` if the key did not exist in the hash table`f (Just v)` otherwiseIf the user function returns  (Nothing, _)L, then the value is deleted from the hash table. Otherwise the mapping for k2 is inserted or replaced with the provided value.1Returns the second part of the tuple returned by f.As >, except that the action can perform additional side effects.\Inserts a key/value mapping into a hash table, replacing any existing mapping for that key.O(n) worst case, O(1) amortized./Deletes a key-value mapping from a hash table. O(n) worst case, O(1) amortized..Looks up a key-value mapping in a hash table. O(n) worst case, (O(1) for cuckoo hash), O(1) amortized.@A strict fold over the key-value records of a hash table in the O monad. O(n). BA side-effecting map over the key-value records of a hash table. O(n). SLooks up the index of a key-value mapping in a hash table suitable for passing to  . Returns the next key-value mapping stored at the given index or at a greater index. The index, key, and value of the next record are returned. ˜Computes the overhead (in words) per key-value mapping. Used for debugging, etc; time complexity depends on the underlying hash table implementation. O(n). 4Create a hash table from a list of key-value pairs. O(n).FCreate a hash table from a list of key-value pairs, with a size hint. O(n).7Given a hash table, produce a list of key-value pairs. O(n).       None ËPQRSNoneD!˜TCache line size, in bytes UVWXYZ[\]^_V`NoneD" abcdefghijkl None#­m default valuenew sizenumber of elements to copy old arraynopqrsmtuvwxyz{|}~€‚ƒ„…†‡ NoneD%ŖˆLWhat you have to mask an integer index by to tell if it's cacheline-aligned‰Š‹ŒˆŽ‘’“”•–—˜ None&(™š›œ™žŸ  None D@ߥ(Returns 0 if x is positive, -1 otherwiseĸAbs of an integer, branchlessŖ Returns 0xfff..fff (aka -1) if a == b, 0 otherwise.¤3Returns 0xfff..fff (aka -1) if a == b, 0 otherwise.Ĩ˙^Search through a mutable vector for a given int value, cache-line aligned. If the start index is cache-line aligned, and there is more than a cache-line's room between the start index and the end of the vector, we will search the cache-line all at once using an efficient branchless bit-twiddling technique. Otherwise, we will use a typical loop.Ļ˙iSearch through a mutable vector for one of two given int values, cache-line aligned. If the start index is cache-line aligned, and there is more than a cache-line's room between the start index and the end of the vector, we will search the cache-line all at once using an efficient branchless bit-twiddling technique. Otherwise, we will use a typical loop.§˙kSearch through a mutable vector for one of three given int values, cache-line aligned. If the start index is cache-line aligned, and there is more than a cache-line's room between the start index and the end of the vector, we will search the cache-line all at once using an efficient branchless bit-twiddling technique. Otherwise, we will use a typical loop.Ĩvector to search start indexvalue to search for7dest index where it can be found, or "-1" if not foundĻvector to search start indexvalue to search forvalue 2 to search for7dest index where it can be found, or "-1" if not found§vector to search start indexvalue to search forvalue 2 to search forvalue 3 to search for7dest index where it can be found, or "-1" if not found¨ŠĒĢŦ­ĄĸŖ¤ŽĨĻ§NoneDOŧ ¯O2-element array, stores how many entries and deleted entries are in the table.3An open addressing hash table using linear probing.,See the documentation for this function in Data.HashTable.Class#v:new.,See the documentation for this function in Data.HashTable.Class#v:newSized.,See the documentation for this function in Data.HashTable.Class#v:delete.,See the documentation for this function in Data.HashTable.Class#v:lookup.,See the documentation for this function in Data.HashTable.Class#v:insert.,See the documentation for this function in Data.HashTable.Class#v:mutate.,See the documentation for this function in Data.HashTable.Class#v:mutateST.,See the documentation for this function in Data.HashTable.Class#v:foldM.,See the documentation for this function in Data.HashTable.Class#v:mapM_.,See the documentation for this function in &Data.HashTable.Class#v:computeOverhead.  °ą˛ŗ´ĩļˇ¸šē¯ģŧŊžNoneD`Š ŋ8in buckets, total size is numElemsInCacheLine * _size!A cuckoo hash table.",See the documentation for this function in Data.HashTable.Class#v:new.#,See the documentation for this function in Data.HashTable.Class#v:newSized.$,See the documentation for this function in Data.HashTable.Class#v:insert.Ā,See the documentation for this function in &Data.HashTable.Class#v:computeOverhead.',See the documentation for this function in Data.HashTable.Class#v:delete.(,See the documentation for this function in Data.HashTable.Class#v:lookup.),See the documentation for this function in Data.HashTable.Class#v:foldM.*,See the documentation for this function in Data.HashTable.Class#v:mapM_.+)Find index of given key in the hashtable.,AFind the next entry in the hashtable starting at the given index.Á hash tableare we updating?keycache line start address 1cache line start address 2hash1hash2 hash table hash code 1 hash code 2 cache line 1 cache line 2keyvalue !"#$%&'()*+, !"#'($%&*)+,ÃÄŋÅÆĮČÉ!ĘNoneDQVlŪ /A linear hash table.0,See the documentation for this function in Data.HashTable.Class#v:new.1,See the documentation for this function in Data.HashTable.Class#v:newSized.2,See the documentation for this function in Data.HashTable.Class#v:delete.3,See the documentation for this function in Data.HashTable.Class#v:lookup.4,See the documentation for this function in Data.HashTable.Class#v:insert.7,See the documentation for this function in Data.HashTable.Class#v:mapM_.8,See the documentation for this function in Data.HashTable.Class#v:foldM.9,See the documentation for this function in &Data.HashTable.Class#v:computeOverhead.Ë,See the documentation for this function in "Data.HashTable.Class#v:lookupIndex. /0123456789 /0123456789ĖÍÎĪĐ/ŅNoneEV†Y</A type alias for our hash tables, which run in ST", to set the state token type to Ō Ķ (aka  RealWorld) so that we can use them in Ķ.=,A type alias for the linear hash table. See Data.HashTable.ST.Linear.>,A type alias for the cuckoo hash table. See Data.HashTable.ST.Cuckoo.?OA type alias for a basic open addressing hash table using linear probing. See Data.HashTable.ST.Basic.@+See the documentation for this function in Data.HashTable.Class#v:new.A,See the documentation for this function in Data.HashTable.Class#v:newSized.B+See the documentation for this function in Data.HashTable.Class#v:insert.C+See the documentation for this function in Data.HashTable.Class#v:delete.D+See the documentation for this function in Data.HashTable.Class#v:lookup.E+See the documentation for this function in "Data.HashTable.Class#v:lookupIndex.F+See the documentation for this function in "Data.HashTable.Class#v:nextByIndex.G+See the documentation for this function in Data.HashTable.Class#v:mutateST.H+See the documentation for this function in Data.HashTable.Class#v:mutate.I,See the documentation for this function in Data.HashTable.Class#v:fromList.J,See the documentation for this function in +Data.HashTable.Class#v:fromListWithSizeHint.K+See the documentation for this function in Data.HashTable.Class#v:toList.L+See the documentation for this function in Data.HashTable.Class#v:foldM.M+See the documentation for this function in Data.HashTable.Class#v:mapM_.N,See the documentation for this function in &Data.HashTable.Class#v:computeOverhead.<=>?@ABCDEFGHIJKLMN?>=<@ABCDHGIJKMLNEFÔ   !"  #$%&'()*+,-./01234567./089:;<=>?@ABCDEF G H I J K L M N O P Q   R        S H T U V W X(YZ [ 1 \ ] ^ _ ` a b c d e f g h i j k l i m n o p q r s t u v w x y z { | }~€‚ƒƒ„… †‡VWˆ†‰Š… ‹‡VWŒˆ… Žˆ+‘’“”•)hashtables-1.2.3.0-2LQ0FkSAE89EHxnrdh3b87Data.HashTable.ClassData.HashTable.ST.BasicData.HashTable.ST.CuckooData.HashTable.ST.LinearData.HashTable.IOData.HashTable.Internal.Array Data.HashTable.Internal.IntArray$Data.HashTable.Internal.UnsafeTricks%Data.HashTable.Internal.Linear.BucketData.HashTable.Internal.Utils2Data.HashTable.Internal.CheapPseudoRandomBitStream!Data.HashTable.Internal.CacheLine HashTablenewnewSizedmutatemutateSTinsertdeletelookupfoldMmapM_ lookupIndex nextByIndexcomputeOverheadfromListfromListWithSizeHinttoList$fShowHashTable$fHashTableHashTable $fMonoidSlot$fSemigroupSlot $fShowSlot$fShowSlotFindResponse IOHashTableLinearHashTableCuckooHashTableBasicHashTablemutateIObaseGHC.STST(primitive-0.6.2.0-EI3NK1Xfv9zEcRtyXK2EwZData.Primitive.Array MutableArraynewArray readArray writeArray cacheLineSizeElemIntArrayprimWordToElem elemToInt elemToInt#elemMasklengthtoPtrIAKey emptyRecord deletedRecord keyIsEmpty keyIsDeletedtoKeyfromKeymakeEmptyVectorwriteDeletedElement TombStone EmptyElementDeletedElement expandArrayBucketbucketSplitSizenewBucketArraynelemsAndOverheadInWords emptyWithSize newBucketSizeexpandBucketArray growBucketTosnocsizeelemAtBucket_ _bucketSize _highwater_keys_valuescacheLineIntMaskGHC.IO unsafeIOToSTwordSizenumElemsInCacheLinecacheLineIntBits whichBucket nextBestPrimebumpSizeshiftLshiftRLiShiftLiShiftRLnextHighestPowerOf2log2highestBitMask forceSameType BitStream newBitStream getNextBitgetNBits _curRandom _bitsLeft _randomPossign#bl_abs#mask#maskcacheLineSearchcacheLineSearch2cacheLineSearch3 prefetchRead prefetchWriteforwardSearch2forwardSearch3advanceByCacheLineSizeisCacheLineAlignedmaskw#_loadSlotFindResponse _slotFound_slotB0_slotB1Slot_slot HashTable__size_hashesHTdelete' cuckooOrFail_rng _maxAttempts_level _splitptr_bucketsControl.Monad.Primitive PrimStateghc-prim GHC.TypesIO