{Begin SubSec WHEREIS Package}
{Title WHEREIS Package}
{Text

{index WHEREIS package}

{Tag WHEREISpackage}

The WHEREIS package extends the function {fn WHEREIS} ({PageRef Fn WHEREIS}) such that, when asked about a given name as a function, {fn WHEREIS} will consult not only the commands of files that have been noticed by the file package ({PageRef Tag FilePkg}) but also a collection of hashfile databases ({PageRef Tag Hashfile}) that associates function names with filenames.


{FnDef {FnName WHEREIS} {FnArgs NAME TYPE FILES FN}
{Text
Behaves exactly like the definition on {PageRef Fn WHEREIS} unless {arg TYPE}={lisp FNS} (or {lisp NIL}) and {arg FILES}={lisp T}.  In this case, {fn WHEREIS} will consult, in addition to the files on {var FILELST}, the hashfiles that are on the value of {index WHEREIS.HASH Var}{var WHEREIS.HASH} (initially {lisp <LISP>LIBRARY>WHEREIS.HASH}).
}}


Note:  Most system functions call {fn WHEREIS} with {arg FILES}={lisp T}, so loading this package automatically makes the information contained in the {fn WHEREIS} database available throughout the system.

Information may be added to a WHEREIS hashfile by creating new databases.  It is often useful to have a separate database for large user systems.  explicitly calling the following function:

{FnDef {FnName WHEREISNOTICE} {FnArgs FILEGROUP NEWFLG DATABASEFILE}
{Text
Inserts the information about all of the functions on the files in {arg FILEGROUP} into the {fn WHEREIS} data base contained on {arg DATABASEFILE}.  If {arg DATABASEFILE} is {lisp NIL}, the first entry on {var WHEREIS.HASH} is used.

{arg FILEGROUP} is given as a filegroup argument to {fn DIRECTORY} ({PageRef Fn DIRECTORY}), so {lisp &}, {lisp $}, etc. may be used. To avoid analysing compiled files also, {arg FILEGROUP} should specify an extension. e.g. <LISP>LIBRARY>*. or <PROJECT>*.LSP.

If {arg NEWFLG} is non-{lisp NIL}, a new version of {arg DATABASEFILE} will be created containing the database for the functions specified in {arg FILEGROUP}.  If {arg NEWFLG} is a number, the hash file will be created with {arg NEWFLG} entries.  Otherwise, it will be created to allow 20000 entries.

Example:
The following sequence of actions will cause all of the files on the PROJECT directory to be noticed by the WHEREIS package.

(WHEREISNOTICE '<PROJECT>*. T '<PROJECT>PROJECTWHEREIS.HASH)
(SETQ WHEREIS.HASH (CONS '<PROJECT>PROJECTWHEREIS.HASH WHEREIS.HASH))
}}

}{End SubSec WHEREIS Package}


{Begin SubSec Hash Files}
{Title Hash Files}
{Text

{index *BEGIN* hash file facility}

{Tag Hashfile}


The hash file facility permits information associated with string or atom "keys" to be stored on and retrieved from files.  The information (or "values") associated with the keys in a file may be numbers, strings, or arbitary  Interlisp expressions.  The associations are maintained by a hashing scheme that minimizes the number of file operations it takes to access a value from its key.

A hashfile is created by the function {fn CREATEHASHFILE}:  

{FnDef {FnName CREATEHASHFILE} {FnArgs FILE}
{Text
A new version of {arg FILE} is opened and initialized as a hashfile. After being initialized, {arg FILE} is left open and {fn CREATEHASHFILE} returns as its value a "hashfile datum," a handle on the hashfile that may be used as an argument for most of the functions described below.
}}

{FnDef {FnName OPENHASHFILE} {FnArgs FILE ACCESS}
{Text
Re-opens the previously existing hashfile {arg FILE}.  {arg ACCESS} may be {lisp INPUT} (or {lisp NIL}), in which case {arg FILE} is opened for reading only, or {lisp BOTH}, in which case {arg FILE} is open for both input and output.  Causes an error {lisp NOT A HASHFILE},{index NOT A HASHFILE Error} if {arg FILE} is not recognized as a hashfile.

If {arg ACCESS} is {lisp BOTH} and {arg FILE} is a hashfile open for reading only, {fn OPENHASHFILE} attempts to close it and re-open it for writing. Otherwise, if {arg FILE} designates an already open hashfile, {fn OPENHASHFILE} is a no-op.

{fn OPENHASHFILE} returns a hashfile datum.
}}

{FnDef {FnName HASHFILEP} {FnArgs X}
{Text
Returns {arg X} if {arg X} is a hashfile datum (i.e., a value returned by {fn CREATEHASHFILE} or {fn OPENHASHFILE}).  If {arg X} is {lisp NIL}, returns {var SYSHASHFILE}{index SYSHASHFILE Var} if it is a hashfile datum.  If {arg X} is the name of an open hashfile, returns the corresponding hashfile datum.  Otherwise, returns {lisp NIL}.
}}

The following functions require an open hashfile as an argument, i.e. an object for which {fn HASHFILEP} is non-{lisp NIL}. 

{FnDef {FnName PUTHASHFILE} {FnArgs KEY VALUE HASHFILE}
{Text
Puts {arg VALUE} in {arg HASHFILE}, indexed under {arg KEY}.  If {arg VALUE} is {lisp NIL}, any previous entry for {arg KEY} is deleted. 
}}

{FnDef {FnName GETHASHFILE} {FnArgs KEY HASHFILE}
{Text
Returns the value corresponding to {arg KEY} in {arg HASHFILE}. }}

{FnDef {FnName HASHFILEPROP} {FnArgs HASHFILE PROP}
{Text
Returns the value of the {arg PROP} property of {arg HASHFILE}.  The recognized {arg PROP}s and the values returned are:

{Begin LabeledList The recognized PROPs}

{Label {lisp NAME}}
{Item
The full name of the file.
}

{Label {lisp ACCESS}}
{Item
{lisp BOTH} if file is open for writing, {lisp INPUT} if it is read-only.
}

{End LabeledList The recognized PROPs}

}}


{FnDef {FnName CLOSEHASHFILE} {FnArgs HASHFILE}
{Text
Closes the hash file and clears any internal buffers associated with it.
}}

{FnDef {FnName MAPHASHFILE} {FnArgs HASHFILE MAPFN}
{Text
For each entry in {arg HASHFILE}, performs {lisp ({arg MAPFN} {arg KEY} (GETHASHFILE {arg KEY} {arg HASHFILE}))}.  If {arg MAPFN} is a function of only one argument, performs {lisp ({arg MAPFN} {arg KEY})} thereby avoiding the call to {fn GETHASHFILE} needed to obtain the value.  {arg KEY} is temporary, as for {fn GETHASHFILE}.  {arg VALUE} is also temporary, for {lisp STRING}, {lisp NUMBER}, and {lisp SYMBOLTABLE} files. 
}}


{FnDef {FnName REHASHFILE} {FnArgs HASHFILE}
{Text
After many insertions and deletions much of the space in a hashfile may be unusable.  {fn REHASHFILE} reclaims that space by rehashing all the keys.}}


{FnDef {FnName COPYHASHFILE} {FnArgs HASHFILE NEWNAME FN }
{Text
Calls {fn CREATEHASHFILE} to open {arg NEWNAME} as a hashfile, then maps through all the keys in {arg HASHFILE}, doing the equivalent of:

{lispcode
(PUTHASHFILE
   {arg KEY}
   (GETHASHFILE {arg KEY} {arg HASHFILE})
   {arg NEWHASHFILE})}

for each key {arg KEY}.  In essence, {fn COPYHASHFILE} copies {arg HASHFILE} to {arg NEWNAME}.

If {arg FN} is given, then it is applied to the successive values of {arg HASHFILE}, the old {arg HASHFILE}, and the new hashfile, and the value returned is used as the value in the new file.  In effect,

{lispcode
(PUTHASHFILE
   {arg KEY}
   ({arg FN} (GETHASHFILE {arg KEY} {arg HASHFILE})
       {arg HASHFILE}
       {arg NEWHASHFILE})
   {arg NEWHASHFILE})}

is evaluated for each key.  Thus, the user can intervene as each key is processed in order to copy information associated with the key.
}}


{FnDef {FnName HASHFILESPLST} {FnArgs HASHFILE}
{Text
Returns a "generator" for the keys in {arg HASHFILE} that is acceptable as an argument to {fn FIXSPELL} ({PageRef Fn FIXSPELL}).{index generators for spelling correction}{index spelling correction on hash files}  Thus, {lisp (FIXSPELL BADWORD 70 (HASHFILESPLST {arg HASHFILE}))} will spelling correct a word using the keys in {arg HASHFILE}.
}}


{FnDef {FnName LOOKUPHASHFILE} {FnArgs KEY VALUE HASHFILE CALLTYPE}
{Text
A generalized entry for inserting and retrieving values; provides certain options not available with {fn GETHASHFILE} or {fn PUTHASHFILE}.  {fn LOOKUPHASHFILE} looks up {arg KEY} in {arg HASHFILE}.  {arg CALLTYPE} is an atom or a list of atoms.  These keywords are interpreted as follows:

{Begin LabeledList CALLTYPEs}

{Indent 15percent}

{Label {lisp RETRIEVE}}
{Text
If {arg KEY} is found, then if {arg CALLTYPE} is or contains {lisp RETRIEVE}, the old value is returned from {fn LOOKUPHASHFILE}; otherwise returns {lisp T}.
}

{Name {lisp DELETE}}
{Text
If {arg CALLTYPE} is or contains {lisp DELETE}, the value associated with {arg KEY} is deleted from the file. 
}

{Name {lisp REPLACE}}
{Text
If {arg CALLTYPE} is or contains {lisp REPLACE}, the old value is replaced with {arg VALUE}.
}

{Name {lisp INSERT}}
{Text
If {arg CALLTYPE} is or contains {lisp INSERT}, {fn LOOKUPHASHFILE} inserts value as the value associated with {arg KEY}.
}


{End LabeledList CALLTYPEs}


If {arg KEY} is not found, {fn LOOKUPHASHFILE} returns {lisp NIL}.
}}



Examples:


To either return an old value or insert a new value in the file if one does not already exist, perform
{lisp (LOOKUPHASHFILE {arg KEY} {arg NEWVALUE} {arg HASHFILE} '(INSERT RETRIEVE))}.
The value returned will be {lisp NIL} if {arg NEWVALUE} was inserted, or the old value if {arg KEY} was found. 

To merely check whether {arg KEY} exists in the file without actually retrieving its value (which may be expensive for the more general valuetypes), perform {lisp (LOOKUPHASHFILE {arg KEY} NIL {arg HASHFILE} NIL)}.

The function {fn PUTHASHFILE} could be defined as:

{lispcode
(LAMBDA (KEY VALUE HASHFILE)
    (if VALUE=NIL
      then (LOOKUPHASHFILE KEY NIL HASHFILE 'DELETE)
      else (LOOKUPHASHFILE KEY VALUE HASHFILE '(INSERT REPLACE))
           VALUE))}


And {fn GETHASHFILE} could be defined as:

{lispcode
(LAMBDA (KEY HASHFILE)
    (LOOKUPHASHFILE KEY NIL HASHFILE 'RETRIEVE))}

{note HASH is a new implementation of the hashfile package which works in both Interlisp-10 and Interlisp-D. It is written in Interlisp and operating on streams of bytes. This package implements the interfaces documented in the Interlisp Reference Manual (and marked as Interlisp-10 specific) as well as those of the original implementation used in EMYCIN based systems, and will be referred to as the EMYCIN package. This document only deals with differences between the various packages. Users should consult the Interlisp Reference Manual and the EMYCIN documentation for details.
Hashfiles are created by calling CREATEHASHFILE. A "HashFile", as referenced in this document, is the datum returned by CREATEHASHFILE or OPENHASHFILE, currently an array record containing the hashfile name, and the number of slots in the file, the used slots and other details. All other functions with hashfile arguments use this datum. A NIL hashfile argument refers to SYSHASHFILE. Keys are strings or atoms, as in the other systems.
Interlisp-10 hashfiles came in several flavors, according to the values stored in them. This system only supports the most general EXPR type of hashfiles; the VALUETYPE and ITEMLENGTH arguments are ignored. This distinction is generally invisible to the user.
Two key hashing is supported in this system. The functions that manipulate 'secret pages' do not exist in this implementation.
When running in Interlisp-10, HASH will load the DFOR10.COM package from the LispUsers directory.
Functions
The functions implemented are:
hashfiledata[hashfile] (EMYCIN)
clearhashfiles[close,release] (EMYCIN)
collectkeys[hashfile,double,mkstring] (EMYCIN)


 Global Variables


The variables used by the system of interest to the user.
HASHTEXTCHAR  ^A  The character separating two key hashkeys.
HASHFILERDTBL  ORIG  The hashfile read table.
HFGROWTHFACTOR  3  The ration of total slots to used slots when a hashfile is created.
REHASHGAG  NIL  Flags whether to print message when rehashing; initially off.
HASHFILEDEFAULTSIZE  512  Size used when #Entries is omited.
HASHLOADFACTOR  .875  The ratio, used slots/total slots, at which the system rehashes the file, initially 7/8.
SYSHASHFILE  NIL  The current hashfile.

Implementation

The hashfile package views files as a sequence of bytes, randomly accessible. No notice is made of pages and it is assumed that the host computer buffers I/O suffieciently.
Hash files consist of a layer of pointers followed by ascii data. Pointers are 3 bytes wide, preceeded by a status byte. The pointers point to key PNAMES in the data section, where each key is followed by its value. Deleted key pointers are reused, deleted data space is not, so rehashing is required if many items have been "replaced".
The data section starts at 4*HASHFILE:SIZE + 9, and consists of alternating keys and values. As deleted data is not re-written, files should not be accessed directly.

When a key hashes into a used slot, a probe value is added to it to find the next slot to search. The probe value is a small prime derived from the original hash key.

Limitations

Due to the pointer size, only hashfiles of < 6 million intial entries can be created, though these can grow to 14 million entries before automatic rehashing exceeds the pointer limit. The total file length is limited to 16 million bytes. No range checking is done for these limits. 

{index *END* hash file facility} 


}{End SubSec Hash Files}


%GACHA

NILNILHGACHA

NILNIL
¶GACHA

NILNIL
GACHA

NILNILGACHA

NILNILbGACHA

NILNIL
GACHA

NILNILGACHA

NILNIL GACHA

NILNIL'GACHA

NILNIL/GACHA

NILNIL
GACHA

NILNIL
GACHA

NILNILGACHA

NILNIL
GACHA

NILNIL
GACHA

NILNIL:GACHA

NILNIL=GACHA

NILNIL.GACHA

NILNILWGACHA

NILNILNGACHA

NILNIL=GACHA

NILNILoGACHA

NILNIL(GACHA

NILNIL
GACHA

NILNILGACHA

NILNIL
GACHA

NILNIL­GACHA

NILNIL
QGACHA

NILNIL§GACHA

NILNIL
GACHA

NILNIL§GACHA

NILNIL
GACHA

NILNILGACHA

NILNIL
GACHA

NILNIL
GACHA

NILNIL
GACHA

NILNIL"GACHA

NILNIL
GACHA

NILNIL
GACHA

NILNILGACHA

NILNIL
GACHA

NILNIL
GACHA
2ŽUz¸