DIRECTORYCountedVM USING [Handle],IO USING [STREAM],Rope USING [ROPE];BitTableLookup: CEDAR DEFINITIONS =BEGINROPE: TYPE = Rope.ROPE;STREAM: TYPE = IO.STREAM;Create: PROC [size: INT] RETURNS [table: Table];NumberHashFunctions: PROC [] RETURNS [numberHashFunctions: INT];Read: PROC [in: STREAM] RETURNS [table: Table];Write: PROC [table: Table, out: STREAM];Insert: PROC [table: Table, word: REF TEXT];Lookup: PROC [table: Table, word: REF TEXT] RETURNS [member: BOOLEAN];RowContents: TYPE = PACKED ARRAY [0..4096) OF BOOL;RowPointer: TYPE = LONG POINTER TO RowContents;RowPrime: CARDINAL = 4093; -- Prime less than 4096.Table: TYPE = REF TableContents;TableContents: TYPE = MACHINE DEPENDENT RECORD[vmHandle: CountedVM.Handle,bits: SEQUENCE rowSize: CARDINAL OF RowPointer];FailureTypes: TYPE = {TooLarge, BadTable};Failed: ERROR[ why: FailureTypes ];END.CHANGE LOGCreated by Nix on September 15, 1983 10:36 am    BitTableLookup.mesa - interface for space efficient set membership test, useful for implementing sleazy spelling checkers.-- Last Edited by-- Nix on October 27, 1983 1:15 pmBeach, February 13, 1985 10:15:07 pm PSTCreates a table with the given number of bits of capacity.   The number of bits should be a prime number that is approximately 20 times the number of words in the given table.ERRORS: Raises Failed[TableTooLarge] if the table size is greater than 1,048,576 bits; tables of this size suffice to hold 50,000 items while maintaining a probability of ~0.001 that non-members will erroneously be called members.Returns the number of hash functions used by the lookup/insertion procedure.Reads in a Table from the given stream.  ERRORS: Raises Failed[BadTable] if it detects that the stream does not contain a valid bit table.Writes out a Table to the given stream.Inserts the word into the given Table.Looks up the word in the Table and returns TRUE iff it thinks that the word is in there.  If the word actually was in the Table, then this will always return TRUE.  However if the word actually was not in the table then it may erroneously return TRUE, although this won't happen very often.The representation of the bit table.ErrorsThere are currently two kinds of errors:TooLarge: raised by Create when asked to create a bit table that is larger than implementation restrictions currently allow (currently raised at about 1,000,000 bits).BadTable: raised by Read when it finds that the stream does not contain a valid table.Êv  ˜ šœ¯™¯J™(—J˜ šÏk	˜	Jšœ
œ
˜Jšœœœ˜Jšœœœ˜—J˜ JšÏbœœœ˜#Jš˜Jšœœœ˜Jšœœœœ˜J˜ J˜ šÏnœœœœ˜0Jšœ¯™¯Jšœæ™æ—J˜ šŸœœœœ˜@JšœL™LJ™ —šŸœœœœ˜/Jšœ)™)Jšœa™aJ˜ —šŸœœœ˜(Jšœ'™'J˜ —šŸœœœœ˜,Jšœ&™&—J˜ J˜ šŸœœœœœ
œ˜FJšœ¢™¢J™ J™ —J™$J™ Jšœœœœœœ˜3Jš	œœœœœ˜/Jšœ
œ	Ïc˜3J˜ Jšœœœ˜ š	œœœ	œœ˜/J˜Jšœœ
œœ˜0—J˜ J˜ J˜ J˜ Jšœ™J™ Jšœœ˜*J˜ šœœ˜#šœ(™(Jšœ§™§JšœV™V——J˜ Jšœ˜J˜ Jšœ˜
J˜ Jšœ.˜.— …—    ¼  L  