;;; -*- Mode:gate; Fonts:(HL12 HL12I HL12B CPTFONTB HL12BI HL12B HL12I ) -*- =Node: Introduction to Hash Tables =Text: 3INTRODUCTION TO HASH TABLES* A hash table is a Lisp object that works something like a property list. Each hash table has a set of 1entries*, each of which associates a particular 1key* with a particular 1value* (or sequence of values). The basic functions that deal with hash tables can create entries, delete entries, and find the value that is associated with a given key. Finding the value is very fast even if there are many entries, because hashing is used; this is an important advantage of hash tables over property lists. Hashing is explained in 4(MANLISTSTR-3)Hash Primitive*. A given hash table stores a fixed number of values for each key; by default, there is only one value. Each time you specify a new value or sequence of values, the old one(s) are lost. There are three standard kinds of hash tables, which differ in how they compare keys: with 2eq*, with 2eql* or with 2equal*. In other words, there are hash tables which hash on Lisp 1objects* (using 2eq* or 2eql*) and there are hash tables which hash on trees (using 2equal*). You can also create a nonstandard hash table with any comparison function you like, as long as you also provide a suitable hash function. Any two objects which would be regarded as the same by the comparison function should produce the same hash code under the hash function. See the 2:compare-function* and 2:hash-function* keywords under 2make-hash-table*, below. The following discussion refers to the 2eq* kind of hash table; the other kinds are described later, and work analogously. 2eq* hash tables are created with the function 2make-hash-table*, which takes various options. New entries are added to hash tables with the 2puthash* function. To look up a key and find the associated value(s), the 2gethash* function is used. To remove an entry, use 2remhash*. Here is a simple example. 3(setq a (make-hash-table))* 3(puthash 'color 'brown a)* 3(puthash 'name 'fred a)* 3(gethash 'color a) => brown* 3(gethash 'name a) => fred* In this example, the symbols 2color* and 2name* are being used as keys, and the symbols 2brown* and 2fred* are being used as the associated values. The hash table remembers one value for each key, since we did not specify otherwise, and has two items in it, one of which associates from 2color* to 2brown*, and the other of which associates from 2name* to 2fred*. Keys do not have to be symbols; they can be any Lisp object. Likewise values can be any Lisp object. Since 2eq* does not work reliably on numbers (except for fixnums), they should not be used as keys in an 2eq* hash table. Use an 2eql* hash table if you want to hash on numeric values. When a hash table is first created, it has a 1size*, which is the number of entries it has room for. But hash tables which are nearly full become slow to search, so if more than a certain fraction of the entries become in use, the hash table is automatically made larger, and the entries are 1rehashed* (new hash values are recomputed, and everything is rearranged so that the fast hash lookup still works). This is transparent to the caller; it all happens automatically. The 2describe* function (see 4(MISCELL-1)Poking Around in the Lisp World*) prints a variety of useful information when applied to a hash table. This hash table facility is similar to the hasharray facility of Interlisp, and some of the function names are the same. However, it is 1not* compatible. The exact details and the order of arguments are designed to be consistent with the rest of Zetalisp rather than with Interlisp. For instance, the order of arguments to 2maphash* is different, we do not have the Interlisp ``system hash table'', and we do not have the Interlisp restriction that keys and values may not be 2nil*. Note, however, that the order of arguments to 2gethash*, 2puthash*, and 2remhash* is not consistent with the Zetalisp's 2get*, 2putprop*, and 2remprop*, either. This is an unfortunate result of the haphazard historical development of Lisp. Hash tables are implemented as instances of the flavor 2hash-table*. The internals of a hash table are subject to change without notice. Hash tables should be manipulated only with the functions and operations described below. =Node: Hash Table Functions =Text: 3HASH TABLE FUNCTIONS make-hash-table* &rest 1options* 3make-equal-hash-table* &rest 1options* These functions create new hash tables. 2make-equal-hash-table* creates an 2equal* hash table. 2make-hash-table* normally creates an 2eq* hash table, but this can be overridden by keywords as described below. Valid option keywords are: 2:size* Sets the initial size of the hash table, in entries, as a fixnum. The default is 64. The actual size is rounded up from the size you specify to the next size that is good for the hashing algorithm. The number of entries you can actually store in the hash table before it is rehashed is at least the actual size times the rehash threshold (see below). 2:test* This keyword is the Common Lisp way to specify the kind of hashing desired. The value must be 2eq*, 2eql* or 2equal*. The one specified is used as the compare function and an appropriate hash function is chosen automatically to go with it. 2:compare-function* Specifies a function of two arguments which compares two keys to see if they count as the same for retrieval from this table. For reasonable results, this function should be an equivalence relation. The default is 2eq*. For 2make-equal-hash-table* the default is 2equal*; that is the only difference between that function and 2make-hash-table*. 2:hash-function* Specifies a function of one argument which, given a key, computes its hash code. The hash code may be any Lisp object. The purpose of the hash function is to map equivalent keys into identical objects: if two keys would cause the compare function to return non-2nil*, the hash function must produce identical (2eq*) hash codes for them. For an 2eq* hash table, the key itself is a suitable hash code, so no hash function is needed. Then this option's value should be 2nil* (2identity* would also work, but slower). 2nil* is the default in 2make-hash-table*. 2make-equal-hash-table* specifies an appropriate function which uses 2sxhash*. 2:number-of-values* A positive integer which specifies how many values to associate with each key. The default is one. 2:area* Specifies the area in which the hash table should be created. This is just like the 2:area* option to 2make-array* (see 4(ARRAYS-1)Constructing Arrays*). Defaults to 2nil* (i.e. 2default-cons-area*). 2:rehash-function* Specifies the function to be used for rehashing when the table becomes full. Defaults to the internal rehashing function that does the usual thing. If you want to write your own rehashing function, you must know all the internals of how hash tables work. These internals are not documented here, as the best way to learn them is to read the source code. 2:rehash-size* Specifies how much to increase the size of the hash table when it becomes full. This can be a fixnum which is the number of entries to add, or it can be a float which is the ratio of the new size to the old size. The default is 21.3*, which causes the table to be made 30% bigger each time it has to grow. 2:rehash-threshold* Sets a maximum fraction of the entries which can be in use before the hash table is made larger and rehashed. The default is 20.7s0*. Alternately, an integer may be specified. It is the exact number of filled entries at which a rehash should be done. When the rehash happens, if the threshold is an integer it is increased in the same proportion as the table has grown. 2:rehash-before-cold* If non-2nil*, this hash table should be rehashed (if that is necessary due to garbage collection) by 2disk-save*. This avoids a delay for rehashing the hash table the first time it is referenced after booting the saved band. 2:actual-size* Specifies exactly the size for the hash table. Hash tables used by the microcode for flavor method lookup must be a power of two in size. This differs from 2:size* in that 2:size* is rounded up to a nearly prime number, but 2:actual-size* is used exactly as specified. 2:actual-size* overrides 2:size.* 3hash-table-p* 1object* 2t* if 1object* is a hash table. 3(hash-table-p 1object*)* is equivalent to 3(typep 1object* 'hash-table)* The following functions are equivalent to sending appropriate messages to the hash table. 3gethash* 1key* 1hash-table* &optional 1default-value* Finds the entry in 1hash-table* whose key is 1key*, and return the associated value. If there is no such entry, returns 1default-value*. Returns also a second value, which is 2t* if an entry was found or 2nil* if there is no entry for 1key* in this table. Returns also a third value, a list which overlays the hash table entry. Its car is the key; the remaining elements are the values in the entry. This is how you can access values other than the first, if the hash table contains more than one value per entry. 3puthash* 1key* 1value* 1hash-table* &rest 1extra-values* Creates an entry associating 1key* to 1value*; if there is already an entry for 1key*, then replace the value of that entry with 1value*. Returns 1value*. The hash table automatically grows if necessary. If the hash table associates more than one value with each key, the remaining values in the entry are taken from 1extra-values*. 3remhash* 1key* 1hash-table* Removes any entry for 1key* in 1hash-table*. Returns 2t* if there was an entry or 2nil* if there was not. 3swaphash* 1key* 1value* 1hash-table* &rest 1extra-values* This specifies new value(s) for 1key* like 2puthash*, but returns values describing the previous state of the entry, just like 2gethash*. It returns the previous (replaced) associated value as the first value, and returns 2t* as the second value if the entry existed previously. 3maphash* 1function* 1hash-table* &rest 1extra-args* For each occupied entry in 1hash-table*, call 1function*. The arguments passed to 1function* are the key of the entry, the value(s) of the entry (however many there are), and the 1extra-args* (however many there are). If the hash table has more than one value per key, all the values, in order, are supplied as successive arguments. 3maphash-return* 1function* 1hash-table* Like 2maphash*, but accumulates and returns a list of all the values returned by 1function* when it is applied to the items in the hash table. 3clrhash* 1hash-table* Removes all the entries from 1hash-table*. Returns the hash table itself. 3hash-table-count* 1hash-table* Returns the number of filled entries in hash-table. =Node: Hash Table Operations =Text: 3HASH TABLE OPERATIONS* Hash tables are instances, and support the following operations: 3:size* 1Operation on 2hash-table** Returns the number of entries in the hash table. Note that the hash table is rehashed when only a fraction of this many (the rehash threshold) are full. 3:filled-entries* 1Operation on 2hash-table** Returns the number of entries that are currently occupied. 3:get-hash* 1key* 1Operation on 2hash-table** 3:put-hash* 1key* &rest 1values* 1Operation on 2hash-table** 3:swap-hash* 1key* &rest 1values* 1Operation on 2hash-table** 3:rem-hash* 1key* 1Operation on 2hash-table** 3:map-hash* 1function* &rest 1extra-args* 1Operation on 2hash-table** 3:map-hash-return* 1function* 1Operation on 2hash-table** 3:clear-hash* 1Operation on 2hash-table** 3:filled-entries* 1Operation on 2hash-table** Are equivalent to the functions 2gethash*, 2puthash*, 2swaphash*, 2remhash*, 2maphash*, 2maphash-return*, 2clrhash* and 2hash-table-count* except that the hash table need not be specified as an argument because it is the object that receives the message. Those functions (documented in the previous section) actually work by invoking these operations. 3:modify-hash* 1key* 1function* &rest 1additional-args* 1Operation on 2hash-table** Passes the value associated with 1key* in the table to 1function*; whatever 1function* returns is stored in the table as the new value for 1key*. Thus, the hash association for 1key* is both examined and updated according to 1function*. The arguments passed to 1function* are 1key*, the value associated with 1key*, a flag (2t* if 1key* is actually found in the hash table), and the 1additional-args* that you specify. If the hash table stores more than one value per key, only the first value is examined and updated. =Node: Hash Tables and the Garbage Collector =Text: 3HASH TABLES AND THE GARBAGE COLLECTOR* The 2eq* type hash tables actually hash on the address of the representation of the object. 2equal* hash tables do so too, if given keys containing unusual objects (other than symbols, numbers, strings and lists of the above). When the copying garbage collector changes the addresses of objects, it lets the hash facility know so that the next 2gethash* will rehash the table based on the new object addresses. There may eventually be an option to 2make-hash-table* which tells it to make a ``non-GC-protecting'' hash table. This is a special kind of hash table with the property that if one of its keys becomes garbage, i.e. is an object not known about by anything other than the hash table, then the entry for that key will be removed silently from the table. When this option exists it will be documented in this section. =Node: Hash Primitive =Text: 3HASH PRIMITIVE* 1Hashing* is a technique used in algorithms to provide fast retrieval of data in large tables. A function, known as the 1hash function*, takes an object that might be used as a key, and produces a number associated with that key. This number, or some function of it, can be used to specify where in a table to look for the datum associated with the key. It is always possible for two different objects to hash to the same value; that is, for the hash function to return the same number for two distinct objects. Good hash functions are designed to minimize this by evenly distributing their results over the range of possible numbers. However, hash table algorithms must still deal with this problem by providing a secondary search, sometimes known as a 1rehash*. For more information, consult a textbook on computer algorithms. 3sxhash* 1tree* &optional 1ok-to-use-address* 2sxhash* computes a hash code of a tree, and returns it as a fixnum. A property of 2sxhash* is that 2(equal 1x y*)* always implies 2(= (sxhash 1x*) (sxhash 1y*))*. The number returned by 2sxhash* is always a non-negative fixnu. 2sxhash* tries to compute its hash code in such a way that common permutations of an object, such as interchanging two elements of a list or changing one character in a string, always change the hash code. Here is an example of how to use 2sxhash* in maintaining hash tables of trees: 3(defun knownp (x &aux i bkt) ;2look up x in the table** 3 (setq i (abs (remainder (sxhash x) 176)))* 3 ;The remainder should be reasonably randomized.* 3 (setq bkt (aref table i))* 3 ;bkt is thus a list of all those expressions that* 3 ;hash into the same number as does x.* 3 (memq x bkt))* For an ``intern'' for trees, one could write: 3(defun sintern (x &aux bkt i tem)* 3 (setq i (abs (remainder (sxhash x) 2n-1)))* 3 ;2n-1 stands for a power of 2 minus one.* 3 ;This is a good choice to randomize the* 3 ;result of the remainder operation.* 3 (setq bkt (aref table i))* 3 (cond ((setq tem (memq x bkt))* 3 (car tem))* 3 (t (aset (cons x bkt) table i)* 3 x)))* If 2sxhash* is given a named structure or a flavor instance, or if such an object is part of a tree that is 2sxhash*'ed, it asks the object to supply its own hash code by performing the 2:sxhash* operation if the object supports it. This should return a suitable nonnegative hash code. The easiest way to compute one is usually by applying 2sxhash* to one or more of the components of the structure or the instance variables of the instance. For named structures and flavor instances that do not handle the 2:sxhash* operation, and other unusual kinds of objects, 2sxhash* can optionally use the object's address as its hash code, if you specify a non-2nil* second argument. If you use this option, you must be prepared to deal with hash codes changing due to garbage collection. 2sxhash* provides what is called ``hashing on 2equal*''; that is, two objects that are 2equal* are considered to be ``the same'' by 2sxhash*. If two strings differ only in alphabetic case, 2sxhash* returns the same thing for both of them, making it suitable for 2equalp* hashing as well in some cases. Therefore, 2sxhash* is useful for retrieving data when two keys that are not the same object but are 2equal* are considered the same. If you consider two such keys to be different, then you need ``hashing on 2eq*'', where two different objects are always considered different. In some Lisp implementations, there is an easy way to create a hash function that hashes on 2eq*, namely, by returning the virtual address of the storage associated with the object. But in other implementations, of which Zetalisp is one, this doesn't work, because the address associated with an object can be changed by the relocating garbage collector. The hash tables created by 2make-hash-table* deal with this problem by using the appropriate subprimitives so that they interface correctly with the garbage collector. If you need a hash table that hashes on 2eq*, it is already provided; if you need an 2eq* hash function for some other reason, you must build it yourself, either using the provided 2eq* hash table facility or carefully using subprimitives. =Node: Introduction to Resources =Text: 3INTRODUCTION TO RESOURCES* Storage allocation is handled differently by different computer systems. In many languages, the programmer must spend a lot of time thinking about when variables and storage units are allocated and deallocated. In Lisp, freeing of allocated storage is normally done automatically by the Lisp system; when an object is no longer accessible to the Lisp environment, the garbage collector reuses its storage for some other object. This relieves the programmer of a great burden, and makes writing programs much easier. However, automatic freeing of storage incurs an expense: more computer resources must be devoted to the garbage collector. If a program is designed to allocate temporary storage, which is then left as garbage, more of the computer must be devoted to the collection of garbage; this expense can be high. In some cases, the programmer may decide that it is worth putting up with the inconvenience of having to free storage under program control, rather than letting the system do it automatically, in order to prevent a great deal of overhead from the garbage collector. It usually is not worth worrying about freeing of storage when the units of storage are very small things such as conses or small arrays. Numbers are not a problem, either; fixnums and short floats do not occupy storage, and the system has a special way of garbage-collecting the other kinds of numbers with low overhead. But when a program allocates and then gives up very large objects at a high rate (or large objects at a very high rate), it can be worthwhile to keep track of that one kind of object manually. Within the Lisp Machine system, there are several programs that are in this position. The Chaosnet software allocates and frees ``packets'', which are moderately large, at a very high rate. The window system allocates and frees certain kinds of windows, which are very large, moderately often. Both of these programs manage their objects manually, keeping track of when they are no longer used. When we say that a program ``manually frees'' storage, it does not really mean that the storage is freed in the same sense that the garbage collector frees storage. Instead, a list of unused objects is kept. When a new object is desired, the program first looks on the list to see if there is one around already, and if there is it uses it. Only if the list is empty does it actually allocate a new one. When the program is finished with the object, it returns it to this list. The functions and special forms in this section perform the above function. The set of objects forming each such list is called a 1resource*; for example, there might be a Chaosnet packet resource. 2defresource* defines a new resource; 2allocate-resource* allocates one of the objects; 2deallocate-resource* frees one of the objects (putting it back on the list); and 2using-resource* temporarily allocates an object and then frees it. =Node: Defining Resources =Text: 3DEFINING RESOURCES defresource* 1Macro* The 2defresource* special form is used to define a new resource. The form looks like this: 3(defresource 1name* 1parameters** 3 1doc-string** 3 1keyword* 1value** 3 1keyword* 1value** 3 ...)* 1name* should be a symbol; it is the name of the resource and gets a 2defresource* property of the internal data structure representing the resource. 1parameters* is a lambda-list giving names and default values (if 2&optional* is used) of parameters to an object of this type. For example, if one had a resource of two-dimensional arrays to be used as temporary storage in a calculation, the resource would typically have two parameters, the number of rows and the number of columns. In the simplest case 1parameters* is 2()*. The documentation string is recorded for 2(documentation 1name* 'resource)* to access. It may be omitted. The keyword options control how the objects of the resource are made and kept track of. The following keywords are allowed: 2:constructor* The 1value* is either a form or the name of a function. It is responsible for making an object, and will be used when someone tries to allocate an object from the resource and no suitable free objects exist. If the 1value* is a form, it may access the parameters as variables. If it is a function, it is given the internal data structure for the resource and any supplied parameters as its arguments; it will need to default any unsupplied optional parameters. This keyword is required. 2:free-list-size* The 1value* is the number of objects which the resource data structure should have room, initially, to remember. This is not a hard limit, since the data structure will be made bigger if necessary. 2:initial-copies* The 1value* is a number (or 2nil* which means 0). This many objects will be made as part of the evaluation of the 2defresource*; thus is useful to set up a pool of free objects during loading of a program. The default is to make no initial copies. If initial copies are made and there are 1parameters*, all the parameters must be 2&optional* and the initial copies will have the default values of the parameters. 2:initializer* The 1value* is a form or a function as with 2:constructor*. In addition to the parameters, a form here may access the variable 2object* (in the current package). A function gets the object as its second argument, after the data structure and before the parameters. The purpose of the initializer function or form is to clean up the contents of the object before each use. It is called or evaluated each time an object is allocated, whether just constructed or being reused. 2:finder* The 1value* is a form or a function as with 2:constructor* and sees the same arguments. If this option is specified, the resource system does not keep track of the objects. Instead, the finder must do so. It will be called inside a 2without-interrupts* and must find a usable object somehow and return it. 2:matcher* The 1value* is a form or a function as with 2:constructor*. In addition to the parameters, a form here may access the variable 2object* (in the current package). A function gets the object as its second argument, after the data structure and before the parameters. The job of the matcher is to make sure that the object matches the specified parameters. If no matcher is supplied, the system will remember the values of the parameters (including optional ones that defaulted) that were used to construct the object, and will assume that it matches those particular values for all time. The comparison is done with 2equal* (not 2eq*). The matcher is called inside a 2without-interrupts*. 2:checker* The job of the checker is to determine whether the object is safe to allocate. The 1value* is a form or a function, as above. In addition to the parameters, a form here may access the variables 2object* and 2in-use-p* (in the current package). A function receives these as its second and third arguments, after the data structure and before the parameters. If no checker is supplied, the default checker looks only at 2in-use-p*; if the object has been allocated and not freed it is not safe to allocate, otherwise it is. The checker is called inside a 2without-interrupts*. If these options are used with forms (rather than functions), the forms get compiled into functions as part of the expansion of 2defresource*. The functions, whether user-provided or generated from forms, are given names like 2(:property 1resource-name** 2si:resource-constructor)*; these names are not guaranteed not to change in the future. Most of the options are not used in typical cases. Here is an example: 3(defresource two-dimensional-array (rows columns)* 3 :constructor (make-array (list rows columns)))* Suppose the array was usually going to be 100 by 100, and you wanted to preallocate one during loading of the program so that the first time you needed an array you wouldn't have to spend the time to create one. You might simply put 3(using-resource (foo two-dimensional-array 100 100)* 3 )* after your 2defresource*, which would allocate a 100 by 100 array and then immediately free it. Alternatively you could write: 3(defresource two-dimensional-array* 3 (&optional (rows 100) (columns 100))* 3 :constructor (make-array (list rows columns))* 3 :initial-copies 1)* Here is an example of how you might use the 2:matcher* option. Suppose you wanted to have a resource of two-dimensional arrays, as above, except that when you allocate one you don't care about the exact size, as long as it is big enough. Furthermore you realize that you are going to have a lot of different sizes and if you always allocated one of exactly the right size, you would allocate a lot of different arrays and would not reuse a pre-existing array very often. So you might write: 3(defresource sloppy-two-dimensional-array (rows columns)* 3 :constructor (make-array (list rows columns))* 3 :matcher (and ( (array-dimension-n 1 object) rows)* 3 ( (array-dimension-n 2 object) columns)))* =Node: Allocating Resource Objects =Text: 3ALLOCATING RESOURCE OBJECTS allocate-resource* 1resource-name* &rest 1parameters* Allocates an object from the resource specified by 1resource-name*. The various forms and/or functions given as options to 2defresource*, together with any 1parameters* given to 2allocate-resource*, control how a suitable object is found and whether a new one has to be constructed or an old one can be reused. Note that the 2using-resource* special form is usually what you want to use, rather than 2allocate-resource* itself; see below. 3deallocate-resource* 1resource-name* 1resource-object* Frees the object 1resource-object*, returning it to the free-object list of the resource specified by 1resource-name*. 3using-resource* 1(variable* 1resource* 1parameters...)* 1body...* 1Macro* The 1body* forms are evaluated sequentially with 1variable* bound to an object allocated from the resource named 1resource*, using the given 1parameters*. The 1parameters* (if any) are evaluated, but 1resource* is not. 2using-resource* is often more convenient than calling 2allocate-resource* and 2deallocate-resource*. Furthermore it is careful to free the object when the body is exited, whether it returns normally or via 2throw*. This is done by using 2unwind-protect*; see 4(FLOWCTL-2)Dynamic Non-Local Exits*. Here is an example of the use of resources: 3(defresource huge-16b-array (&optional (size 1000))* 3 :constructor (make-array size :type 'art-16b))* 3(defun do-complex-computation (x y)* 3 (using-resource (temp-array huge-16b-array)* 3 ... ;2Within the body, the array can be used.** 3 (aset 5 temp-array i)* 3 ...)) ;2The array is deallocated at the end.* deallocate-whole-resource* 1resource-name* Frees all objects in 1resource-name*. This is like doing 2deallocate-resource* on each one individually. This function is often useful in warm-boot initializations. 3map-resource* 1function* 1resource-name* &rest 1extra-args* Calls function on each object created in 1resource-name*. Each time function is called, it receives three fixed arguments, plus whatever 1extra-args* were specified. The three fixed arguments are an object of the resource; 2t* if the object is currently allocated (``in use''); and the resource data structure itself. 3clear-resource* 1resource-name* Forgets all of the objects being remembered by the resource specified by 1resource-name*. Future calls to 2allocate-resource* will create new objects. This function is useful if something about the resource has been changed incompatibly, such that the old objects are no longer usable. If an object of the resource is in use when 2clear-resource* is called, an error will be signaled when that object is deallocated. =Node: Accessing the Resource Data Structure =Text: 3ACCESSING THE RESOURCE DATA STRUCTURE* The constructor, initializer, matcher and checker functions receive the internal resource data structure as an argument. This is a named structure array whose elements record the objects both free and allocated, and whose array leader contains sundry other information. This structure should be accessed using the following primitives: 3si:resource-object* 1resource-structure* 1index* Returns the 1index*'th object remembered by the resource. Both free and allocated objects are remembered. 3si:resource-in-use-p* 1resource-structure* 1index* Returns 2t* if the 1index*'th object remembered by the resource has been allocated and not deallocated. Simply defined resources will not reallocate an object in this state. 3si:resource-parameters* 1resource-structure* 1index* Returns the list of parameters from which the 1index*'th object was originally created. 3si:resource-n-objects* 1resource-structure* Returns the number of objects currently remembered by the resource. This will include all objects ever constructed, unless 2clear-resource* has been used. 3si:resource-parametizer* 1resource-structure* Returns a function, created by 2defresource*, which accepts the supplied parameters as arguments, and returns a complete list of parameter values, including defaults for the optional ones. =Node: Fast Pseudo-Resources =Text: 3FAST PSEUDO-RESOURCES* When small temporary data structures are allocated so often that they amount to a considerable drain of storage space, an ordinary resource may be unacceptably slow. Here is a simple technique that provides in such cases nearly all the benefit of a resource while costing nearly nothing. The function 2read* uses it to allocate a buffer for reading tokens of input. 3(defvar buffer-for-reuse nil)* 3(defsubst get-buffer ()* 3 (or (do (old)* 3 ((%store-conditional (locf buffer-for-reuse)* 3 (setq old buffer-for-reuse)* 3 nil)* 3 old))* 3 (construct-new-buffer))))* 3(defsubst free-buffer (buffer)* 3 (setq buffer-for-reuse buffer))* To allocate a buffer for use, do 2(get-buffer)*. To free it when you are done with it, call 2free-buffer*. It is assumed that 2construct-new-buffer* is the function which can create a new buffer when there is none available for reuse. This technique keeps track of at most one buffer which has been freed and may be reused. It is not effective in this simple form when more than one buffer is needed at any given time by one application. In the case of 2read*, only one token is being read in at any time. It is safe for more than one process to call 2read* because 2get-buffer* is designed to guarantee that a request cannot get a buffer already handed out and not freed. Likewise, nothing terrible happens if there is an error inside 2read* and 2read* is called recursively within the debugger. The only problem is that multiple buffers will be allocated, which means that some of them will be lost. But the cost of this is minor in the cases where this technique is applicable. For example, if two processes are reading files, process switching will probably happen a few times a second, each time costing one buffer not reused. This is insignificant compared to the storage used up for other purposes by reading large amounts of data.