XEROX HASHBUFFER 2 4 1 HASHBUFFER 1 4 By: Christopher Lane (Lane@Sumex-Aim.Stanford.Edu) Requires: HASH HASHBUFFER facilitates combining together a hash file with a hash array in order to improve hash file performance when the same keys are accessed multiple times. This module also defines two functions for moving large amounts of hashed data between hash files and hash arrays. This module defines a small set of functions to use in place of the hash file functions. When a hash file is opened, a hash array is created, of a complimentary size. When requests for keys are made, the hash array is searched first, and if the value is found, it is returned. If the value is not found, the hash file is searched. If a value is found there, it is stored in the hash array and returned. If a value is not found, an empty marker is put into the hash array so that the hash file is not searched again. (OPENHASHBUFFER FILE [ACCESS MINKEYS OVERFLOW HASHBITSFN EQUIVFN]) [Function] Opens an existing hash file as a hash buffer and returns a hash buffer datum which must be given to other hash buffer functions; only the FILE argument is required. The MINKEYS argument is used for the size of the hash array, if not supplied the size of the hash file is used. Setting MINKEYS smaller than the size of the hash file allows a fast, small hash array window onto a larger, slower hash file. The OVERFLOW, HASHBITSFN and EQUIVFN arguments are passed onto HASHARRAY. (CREATEHASHBUFFER FILE [VALUETYPE ITEMLENGTH #ENTRIES OVERFLOW HASHBITSFN EQUIVFN]) Similar to OPENHASHBUFFER except that it creates a new hash file. The FILE, VALUETYPE and ITEMLENGTH arguments are passed onto CREATEHASHFILE. The OVERFLOW, HASHBITSFN and EQUIVFN arguments are passed onto HASHARRAY. The #ENTRIES argument is used for both the hash fIle and hash array. (CLOSEHASHBUFFER HASHBUFFER [FILEONLY?]) [Function] Closes a hash buffer, closing the hash file and setting the hash array to NIL so that it can be reclaimed. If FILEONLY? is non-NIL then only the hash file will be closed, the hash array will be left alone. (GETHASHBUFFER KEY HASHBUFFER) [Function] Gets the value for KEY from the hash buffer. (PUTHASHBUFFER KEY VALUE HASHBUFFER) [Function] Stores VALUE under KEY in the hash buffer. If the hash file is opened for input only, then putting a key to the hash buffer will only put the key in the hash array, not the hash file. If the hash file is open for output, then putting a key into the hash buffer will put it in the hash array and the hash file. If VALUE is NIL, then a delete is performed. The following functions move large amounts of data between hash arrays and hash files: (HASHARRAY.TO.HASHFILE HASHARRAY HASHFILE [TESTFN]) [Function] Uses MAPHASH to move the contents of HASHARRY into a hash file. If HASHFILE is a file name, CREATEHASHFILE is called on the name. If HASHFILE is an open hash file pointer, it is used and left open. TESTFN, if supplied, is called just before each PUTHASHFILE on the (KEY VALUE HASHARRAY HASHFILE). If the TESTFN returns NIL, the key and value will not be copied to the file. (HASHFILE.TO.HASHARRAY HASHFILE HASHARRAY [TESTFN]) [Function] Uses MAPHASHFILE to move the contents of HASHFILE into a hash array. The HASHARRAY argument is optional, if not supplied a new hash array is created of the appropriate size. TESTFN, if supplied, is called just before each PUTHASH on the (KEY VALUE HASHFILE HASHARRAY). If the TESTFN returns NIL, the key and value will not be copied to the array. (LIST ((PAGE NIL (PAPERSIZE LETTER STARTINGPAGE# 112) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD CENTERED) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO NIL) (174 36 288 36) NIL) (HEADING NIL (HEADINGTYPE RUNNINGHEAD) (84 744 528 36) NIL) (TEXT NIL NIL (84 96 456 600) NIL))) (PAGE NIL (PAPERSIZE NIL . LETTER) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD CENTERED) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO NIL) (174 36 288 36) NIL) (HEADING NIL (HEADINGTYPE RUNNINGHEAD) (84 744 528 36) NIL) (TEXT NIL NIL (84 96 456 600) NIL))) (PAGE NIL (PAPERSIZE NIL . LETTER) (0 0 612 792) ((FOLIO NIL (PARALOOKS (QUAD CENTERED) CHARLOOKS (SUPERSCRIPT 0 INVISIBLE OFF SELECTPOINT OFF PROTECTED OFF SIZE 10 FAMILY MODERN OVERLINE OFF STRIKEOUT OFF UNDERLINE OFF EXPANSION REGULAR SLOPE REGULAR WEIGHT MEDIUM INVERTED OFF USERINFO NIL STYLE NIL) FORMATINFO NIL) (174 36 288 36) NIL) (HEADING NIL (HEADINGTYPE RUNNINGHEAD) (84 744 528 36) NIL) (TEXT NIL NIL (84 96 456 600) NIL)))))1ÈÈ(È(È (È(ŠŠ8(ŠŠ8DÈÈ PAGEHEADING RUNNINGHEAD(È TERMINAL MODERN  HELVETICA MODERN MODERN MODERNLOGOMODERN   HRULE.GETFNMODERN  HRULE.GETFNMODERN  HRULE.GETFNMODERN   HRULE.GETFNMODERN  HRULE.GETFNMODERN 4 #  Ï NŠnu  9 /    : J" L  &W :*   5   ]*  5 Ò­zº