IntHashTableThreaded: CEDAR DEFINITIONS = BEGIN Table: TYPE = REF TableRec; TableRec: PRIVATE TYPE = MONITORED RECORD [ class: Class, size, sizeLimit, inhibitCount: INT, data: REF Seq ]; Seq: TYPE = PRIVATE RECORD [nodes: SEQUENCE max: SeqIndex OF Value]; SeqIndex: TYPE = NAT; Key: TYPE = INT; Value: TYPE = REF; Class: TYPE = RECORD [ GetKey: PROC [Value] RETURNS [Key], SetLink: PROC [from, to: Value], GetLink: PROC [from: Value] RETURNS [to: Value] ]; Create: PROC [mod: SeqIndex _ 17, class: Class] RETURNS [Table]; GetSize: PROC [table: Table] RETURNS [INT]; Fetch: PROC [table: Table, key: Key] RETURNS [found: BOOLEAN, value: Value]; Replace: PROC [table: Table, key: Key, value: Value] RETURNS [BOOLEAN]; Store: PROC [table: Table, key: Key, value: Value] RETURNS [BOOLEAN]; Insert: PROC [table: Table, key: Key, value: Value] RETURNS [BOOLEAN]; Delete: PROC [table: Table, key: Key] RETURNS [BOOLEAN]; Pairs: PROC [table: Table, action: EachPairAction] RETURNS [BOOLEAN]; EachPairAction: TYPE = PROC [key: Key, value: Value] RETURNS [quit: BOOLEAN _ FALSE]; Erase: PROC [table: Table]; END. βIntHashTableThreaded.Mesa Copyright c 1985 by Xerox Corporation. All rights reversed. Adapted from RefTab.mesa by Bertrand Serlet, July 24, 1985 4:20:46 pm PDT Adapted from HashTable.mesa by Mike Spreitzer, October 23, 1985 5:41:07 pm PDT Adapted from HashTable.mesa by Mike Spreitzer, February 5, 1986 4:24:22 pm PST Last Edited by Bertrand Serlet, July 29, 1985 11:42:28 am PDT Last Edited by Widom, July 25, 1985 4:36:47 pm PDT Last Edited by Mike Spreitzer, May 7, 1986 4:00:14 pm PDT Definitions for hashed table abstraction. The keys are INTs, and the values are REF ANYs. The hash bucket links are threaded through the values. Each table is monitored. These tables will grow in size (up to a limit), so as to keep the density (i.e., (# elements in table) / (# hash table buckets)) from growing too large. When these tables grow, they pick as new modulus a prime number at least twice as large as the old modulus. These tables will try to grow when the density exceeds 1.0 and no enumeration (Pairs) is going on. creates new table, whose length is mod. returns number of key-value pairs in table looks up key in table, returns associated value (if any) if found is TRUE, value is value associated with given key if found is FALSE, value is NIL returns TRUE after overwriting old value for existing key-value pair if no previous value for key, returns FALSE without inserting new pair returns TRUE after inserting new pair returns FALSE after overwriting old value for existing key-value pair returns TRUE after inserted new pair if previous value existed for key, returns FALSE without changing value deletes key-value pair associated with given key returns TRUE if deletion actually occurred, FALSE if no such key enumerates pairs currently in symbol table in unspecified order pairs inserted/deleted during enumeration may or may not be seen applies action to each pair until action returns TRUE or no more pairs returns TRUE if some action returns TRUE deletes all key-value pairs in given table Κξ– "cedar" style˜codešœ™Kšœ Οmœ1™