102  PART 18: THE HASH TABLE  TEX82 §256

256. The hash table. Control sequences are stored and retrieved by means of a fairly standard hash table algorithm called the method of “coalescing lists” (cf. Algorithm 6.4C in The Art of Computer Programming). Once a control sequence enters the table, it is never removed, because there are complicated situations involving where the removal of a control sequence at the end of a group would be a mistake preventable only by the introduction of a complicated reference-count mechanism.

The actual sequence of letters forming a control sequence identifier is stored in the str pool array together with all the other strings. An auxiliary array hash consists of items with two halfword fields per word. The first of these, called next (p), points to the next identifier belonging to the same coalesced list as the identifier corresponding to p; and the other, called text (p), points to the str start entry for p’s identifier. If position p of the hash table is empty, we have text (p) = 0; if position p is either empty or the end of a coalesced hash list, we have next (p) = 0. An auxiliary pointer variable called hash used is maintained in such a way that all locations p ≥ hash used are nonempty. The global variable cs count tells how many multiletter control sequences have been defined, if statistics are being kept.

A global boolean variable called no new control sequence is set to true during the time that new hash table entries are forbidden.

define next (#) ≡ hash[#].lh { link for coalesced lists }

define text (#) ≡ hash[#].rh { string number for control sequence name }

define hash is full ≡ (hash used = hash base) { test if all positions are occupied }

define font id text (#) ≡ text (font id base + #) { a frozen font identifier’s name } ⟨ Global variables 13 ⟩ +≡ hash: array [hash base . . undefined control sequence − 1] of two halves ; { the hash table } hash used : pointer ; { allocation pointer for hash } no new control sequence: boolean; { are new identifiers legal? } cs count : integer ; { total number of known identifiers }

257. ⟨ Set initial values of key variables 21 ⟩ +≡ no new control sequence ← true; { new identifiers are usually forbidden } next (hash base) ← 0; text (hash base) ← 0; for k ← hash base + 1 to undefined control sequence − 1 do hash[k] ← hash[hash base];

§259  TEX82  PART 18: THE HASH TABLE 103

258. ⟨ Initialize table entries (done by only) 164 ⟩ +≡ hash used ← frozen control sequence; { nothing is used } cs count ← 0; eq type(frozen dont expand ) ← dont expand ; text (frozen dont expand ) ← ; 259. Here is the subroutine that searches the hash table for an identifier that matches a given string of length l > 1 appearing in buffer [j . . (j + l − 1)]. If the identifier is found, the corresponding hash table address is returned. Otherwise, if the global variable no new control sequence is true, the dummy address undefined control sequence is returned. Otherwise the identifier is inserted into the hash table and its location is returned. function id lookup(j, l : integer ): pointer ; { search the hash table }

label found ; { go here if you found it } var h: integer ; { hash code }

d: integer ; { number of characters in incomplete current string } p: pointer ; { index in hash array } k: pointer ; { index in buffer array }

begin ⟨ Compute the hash code h 261 ⟩; p ← h + hash base; { we start searching here; note that 0 ≤ h < hash prime } loop begin if text (p) > 0 then

if length(text (p)) = l then

if str eq buf (text (p), j) then goto found ; if next (p) = 0 then

begin if no new control sequence then p ← undefined control sequence else ⟨ Insert a new control sequence after p, then make p point to it 260 ⟩; goto found ; end;

p ← next (p);

end; found : id lookup ← p;

end;

260. ⟨ Insert a new control sequence after p, then make p point to it 260 ⟩ ≡

begin if text (p) > 0 then

begin repeat if hash is full then overflow ( ␣ , hash size);

decr (hash used ); until text (hash used ) = 0; { search for an empty location in hash } next (p) ← hash used ; p ← hash used ; end;

str room(l); d ← cur length; while pool ptr > str start [str ptr ] do

begin decr (pool ptr ); str pool [pool ptr + l] ← str pool [pool ptr ]; end; { move current string up to make room for another }

for k ← j to j + l − 1 do append char (buffer [k]); text (p) ← make string ; pool ptr ← pool ptr + d; stat incr (cs count ); tats end

This code is used in section 259.

261. The value of hash prime should be roughly 85% of hash size, and it should be a prime number. The theory of hashing tells us to expect fewer than two table probes, on the average, when the search is successful. [See J. S. Vitter, Journal of the ACM 30 (1983), 231–258.] ⟨ Compute the hash code h 261 ⟩ ≡

h ← buffer [j];

for k ← j + 1 to j + l − 1 do begin h ← h + h + buffer [k]; while h ≥ hash prime do h ← h − hash prime; end

This code is used in section 259.

262. Single-character control sequences do not need to be looked up in a hash table, since we can use the character code itself as a direct address. The procedure print cs prints the name of a control sequence, given a pointer to its address in eqtb. A space is printed after the name unless it is a single nonletter or an active character. This procedure might be invoked with invalid data, so it is “extra robust.” The individual characters must be printed one at a time using print , since they may be unprintable. ⟨ Basic printing procedures 57 ⟩ +≡ procedure print cs (p : integer ); { prints a purported control sequence }

begin if p < hash base then { single character }

if p ≥ single base then if p = null cs then

begin print esc( ); print esc( ); end

else begin print esc(p − single base); if cat code(p − single base) = letter then print char ( ␣ ); end

else if p < active base then print esc( )

else print (p − active base) else if p ≥ undefined control sequence then print esc( )

else if (text (p) < 0) ∨ (text (p) ≥ str ptr ) then print esc( )

else begin print esc(text (p)); print char ( ␣ );

end; end;

263. Here is a similar procedure; it avoids the error checks, and it never prints a space after the control sequence. ⟨ Basic printing procedures 57 ⟩ +≡ procedure sprint cs (p : pointer ); { prints a control sequence }

begin if p < hash base then if p < single base then print (p − active base) else if p < null cs then print esc(p − single base)

else begin print esc( ); print esc( );

end else print esc(text (p)); end; 264. We need to put TEX’s “primitive” control sequences into the hash table, together with their command code (which will be the eq type) and an operand (which will be the equiv ). The primitive procedure does this, in a way that no TEX user can. The global value cur val contains the new eqtb pointer after primitive has acted.

init procedure primitive(s : str number ; c : quarterword ; o : halfword ); var k: pool pointer ; { index into str pool }

j: small number ; { index into buffer }

l: small number ; { length of the string } begin if s < 256 then cur val ← s + single base else begin k ← str start [s]; l ← str start [s + 1] − k; { we will move s into the (empty) buffer }

for j ← 0 to l − 1 do buffer [j] ← so(str pool [k + j]);

cur val ← id lookup(0, l); { no new control sequence is false }

flush string ; text (cur val ) ← s; { we don’t want to have the string twice } end;

eq level (cur val ) ← level one; eq type(cur val ) ← c; equiv (cur val ) ← o; end; tini 265. Many of TEX’s primitives need no equiv , since they are identifiable by their eq type alone. These primitives are loaded into the hash table as follows: ⟨ Put each of TEX’s primitives into the hash table 226 ⟩ +≡

primitive( ␣ , ex space, 0); primitive( , ital corr , 0); primitive( , accent , 0); primitive( , advance, 0); primitive( , after assignment , 0); primitive( , after group, 0); primitive( , begin group, 0); primitive( , char num, 0); primitive( , cs name, 0); primitive( , delim num, 0); primitive( , divide, 0); primitive( , end cs name, 0); primitive( , end group, 0); text (frozen end group) ← ; eqtb[frozen end group] ← eqtb[cur val ]; primitive( , expand after , 0); primitive( , def font , 0); primitive( , assign font dimen, 0); primitive( , halign, 0); primitive( , hrule, 0); primitive( , ignore spaces , 0); primitive( , insert , 0); primitive( , mark , 0); primitive( , math accent , 0); primitive( , math char num, 0); primitive( , math choice, 0); primitive( , multiply , 0); primitive( , no align, 0); primitive( , no boundary , 0); primitive( , no expand , 0); primitive( , non script , 0); primitive( , omit , 0); primitive( , set shape, 0); primitive( , break penalty , 0); primitive( , set prev graf , 0); primitive( , radical , 0); primitive( , read to cs , 0); primitive( , relax , 256); { cf. scan file name } text (frozen relax ) ← ; eqtb[frozen relax ] ← eqtb[cur val ]; primitive( , set box , 0); primitive( , the, 0); primitive( , toks register , 0); primitive( , vadjust , 0); primitive( , valign, 0); primitive( , vcenter , 0); primitive( , vrule, 0); 266. Each primitive has a corresponding inverse, so that it is possible to display the cryptic numeric contents of eqtb in symbolic form. Every call of primitive in this program is therefore accompanied by some straightforward code that forms part of the print cmd chr routine below. ⟨ Cases of print cmd chr for symbolic printing of primitives 227 ⟩ +≡ accent : print esc( ); advance: print esc( ); after assignment : print esc( ); after group: print esc( ); assign font dimen: print esc( ); begin group: print esc( ); break penalty : print esc( ); char num: print esc( ); cs name: print esc( ); def font : print esc( ); delim num: print esc( ); divide: print esc( ); end cs name: print esc( ); end group: print esc( ); ex space: print esc( ␣ ); expand after : print esc( ); halign: print esc( ); hrule: print esc( ); ignore spaces : print esc( ); insert : print esc( ); ital corr : print esc( ); mark : print esc( ); math accent : print esc( ); math char num: print esc( ); math choice: print esc( ); multiply : print esc( ); no align: print esc( ); no boundary : print esc( ); no expand : print esc( ); non script : print esc( ); omit : print esc( ); radical : print esc( ); read to cs : print esc( ); relax : print esc( ); set box : print esc( ); set prev graf : print esc( ); set shape: print esc( ); the: print esc( ); toks register : print esc( ); vadjust : print esc( ); valign: print esc( ); vcenter : print esc( ); vrule: print esc( ); 267. We will deal with the other primitives later, at some point in the program where their eq type and equiv values are more meaningful. For example, the primitives for math mode will be loaded when we consider the routines that deal with formulas. It is easy to find where each particular primitive was treated by looking in the index at the end; for example, the section where entered eqtb is listed under ‘ primitive’. (Primitives consisting of a single nonalphabetic character, like ‘ ’, are listed under ‘Single-character primitives’.)

Meanwhile, this is a convenient place to catch up on something we were unable to do before the hash table was defined: ⟨ Print the font identifier for font (p) 267 ⟩ ≡

print esc(font id text (font (p)))

This code is used in sections 174 and 176.