HashTable: CEDAR DEFINITIONS = BEGIN Table: TYPE = REF TableRec; TableRec: PRIVATE TYPE = MONITORED RECORD [ hash: HashProc, equal: EqualProc, size, sizeLimit, inhibitCount: INT, data: REF Seq ]; Seq: TYPE = PRIVATE RECORD [nodes: SEQUENCE max: SeqIndex OF Node]; Node: TYPE = PRIVATE REF NodeRep; NodeRep: TYPE = PRIVATE RECORD [key: Key, value: Value, next: Node]; SeqIndex: TYPE = NAT; Key: TYPE = REF; Value: TYPE = REF; HashProc: TYPE = PROC [Key] RETURNS [CARDINAL]; EqualProc: TYPE = PROC [Key, Key] RETURNS [BOOL]; Create: PROC [mod: SeqIndex _ 17, equal: EqualProc _ NIL, hash: HashProc _ NIL] RETURNS [Table]; RopeEqual, RopeEqualModCase: EqualProc; HashRope, HashRopeModCase: HashProc; 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. BHashTable.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 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, November 18, 1985 3:31:15 pm PST Definitions for hashed REF table abstraction. Hash and Equality functions are given. Each table is monitored. RefTab is a particular case of this interface, when defaults are used. Particular Hash and Equality functions are provided to produce behavior equivalent to SymTab. 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. The required relation between hashProc and equalProc is that 2 equal keys (equalProc returns TRUE on them) must have the same hash key. equal defaults to pointer equality, and hash defaults to a magic Xor on key adress. Some EqualProcs that clients may find commonly useful. Some HashProcs that clients may find commonly useful. 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™