DIRECTORY Hash, Basics, IO, Rope, RopeHash; HashImpl: CEDAR PROGRAM IMPORTS Basics, IO, Rope, RopeHash EXPORTS Hash = BEGIN OPEN Hash; rebuildLimit: INT = 3; NewTable: PUBLIC PROC[nBuckets: INT _ 16] RETURNS [table: Table] = BEGIN size: INT _ 16; table _ NEW[TableRec]; table.hashDivide _ 128*128; table.hashDivide _ table.hashDivide*128*8; table.hashMask _ 17B; WHILE (size < nBuckets) DO size _ size*2; table.hashMask _ table.hashMask*2 + 1; table.hashDivide _ table.hashDivide/2; ENDLOOP; table.nEntries _ 0; table.buckets _ NEW[Buckets[size]]; table.firstEntry _ NIL; RETURN [table]; END; Hash: PROC[table: Table, name: Rope.ROPE] RETURNS [CARDINAL] = BEGIN val: INT; val _ RopeHash.FromRope[rope: name]; RETURN [Basics.BITAND[table.hashMask, Basics.LowHalf[val]]]; END; Find: PUBLIC PROC[table: Table, name: Rope.ROPE] RETURNS [entry: Entry] = BEGIN index: CARDINAL _ Hash[table, name]; entry _ table.buckets[index]; WHILE entry # NIL DO IF Rope.Equal[name, entry.name] THEN RETURN [entry]; entry _ entry.nextInBucket; ENDLOOP; IF table.nEntries > (rebuildLimit*table.buckets.length) THEN IF table.buckets.length < 16384 THEN BEGIN Rebuild[table]; index _ Hash[table, name]; END; entry _ NEW[EntryRec]; entry.name _ name; entry.clientData _ NIL; entry.nextInBucket _ table.buckets[index]; table.buckets[index] _ entry; table.nEntries _ table.nEntries + 1; entry.nextOverall _ table.firstEntry; table.firstEntry _ entry; RETURN [entry]; END; Rebuild: PROC[table: Table] = BEGIN old: REF Buckets _ table.buckets; entry, next: Entry; index: CARDINAL; table.buckets _ NEW[Buckets[4*old.length]]; table.hashDivide _ table.hashDivide/4; table.hashMask _ (table.hashMask * 4) + 3; FOR i:CARDINAL IN [0..old.length) DO entry _ old[i]; WHILE (entry # NIL) DO next _ entry.nextInBucket; index _ Hash[table, entry.name]; entry.nextInBucket _ table.buckets[index]; table.buckets[index] _ entry; entry _ next; ENDLOOP; ENDLOOP; END; Enumerate: PUBLIC PROC[table: Table, pattern: Rope.ROPE, proc: EnumProc, clientData: REF ANY _ NIL, errorStream: IO.STREAM _ NIL] = BEGIN prefix: Rope.ROPE _ NIL; postfix: Rope.ROPE _ NIL; length: INT _ Rope.Length[pattern]; pos, next, last: INT; oldPos: INT _ 0; c: CHARACTER; gotRange: BOOLEAN _ FALSE; gotAny: BOOLEAN _ TRUE; gotStar: BOOLEAN _ FALSE; entry: Entry; stream: IO.STREAM; IF length > 0 THEN BEGIN IF Rope.Fetch[pattern, 0] = '* THEN BEGIN pattern _ Rope.Substr[pattern, 1, length-1]; length _ length-1; gotStar _ TRUE; END; END; WHILE TRUE DO pos _ Rope.SkipTo[pattern, oldPos, "\\<"]; prefix _ Rope.Concat[prefix, Rope.Substr[pattern, oldPos, pos-oldPos]]; oldPos _ pos + 1; IF pos = length THEN EXIT; IF pos >= length-1 THEN BEGIN IF errorStream # NIL THEN IO.PutF[errorStream, "Can't end pattern with \"%c\".\n", IO.char[Rope.Fetch[pattern, length-1]]]; RETURN; END; c _ Rope.Fetch[pattern, pos]; IF c = '< THEN EXIT; oldPos _ pos+2; prefix _ Rope.Concat[prefix, Rope.Substr[pattern, pos+1, 1]]; ENDLOOP; IF pos < length THEN BEGIN pos _ Rope.SkipTo[pattern, oldPos, ">"]; IF pos < length THEN BEGIN ENABLE ANY => BEGIN IF errorStream # NIL THEN IO.PutRope[errorStream, "Syntax error in range specifier.\n"]; GOTO quit; END; stream _ IO.RIS[Rope.Substr[pattern, oldPos, pos-oldPos]]; next _ IO.GetInt[stream]; IF IO.GetChar[stream] # ': THEN BEGIN IF errorStream # NIL THEN IO.PutRope[errorStream, "Missing \":\" in range.\n"]; RETURN; END; last _ IO.GetInt[stream]; gotRange _ TRUE; END ELSE BEGIN IF errorStream # NIL THEN IO.PutRope[errorStream, "Missing \">\" in range.\n"]; RETURN; END; oldPos _ pos+1; WHILE TRUE DO pos _ Rope.SkipTo[pattern, oldPos, "\\"]; postfix _ Rope.Concat[postfix, Rope.Substr[pattern, oldPos, pos-oldPos]]; IF pos = length THEN EXIT; IF pos >= length-1 THEN BEGIN IF errorStream # NIL THEN IO.PutRope[errorStream, "Can't end pattern in \"\\\"\n."]; RETURN; END; postfix _ Rope.Concat[postfix, Rope.Substr[pattern, pos+1, 1]]; oldPos _ pos+2; ENDLOOP; END; WHILE gotAny DO IF gotRange THEN BEGIN pattern _ IO.PutFR["%s%d%s", IO.rope[prefix], IO.int[next], IO.rope[postfix]]; IF next > last THEN next _ next-1 ELSE IF next < last THEN next _ next+1 ELSE gotAny _ FALSE; END ELSE BEGIN gotAny _ FALSE; pattern _ prefix; END; IF gotStar THEN BEGIN entry _ table.firstEntry; WHILE entry # NIL DO IF (length=0 OR (Rope.Find[entry.name, pattern, 0] >= 0)) AND (entry.clientData # NIL) THEN proc[entry, clientData]; entry _ entry.nextOverall; ENDLOOP; END ELSE BEGIN entry _ Find[table, pattern]; IF entry.clientData # NIL THEN proc[entry, clientData] ELSE IF errorStream # NIL THEN IO.PutF[errorStream, "%s isn't in table.\n", IO.rope[pattern]]; END; ENDLOOP; RETURN; EXITS quit => RETURN; END; Stats: PUBLIC PROC[table: Table, stream: IO.STREAM] = BEGIN count: ARRAY[0..10) OF INT; overflow: INT _ 0; max: INT _ 0; j: INT; entry: Entry; FOR i:CARDINAL IN [0..10) DO count[i] _ 0 ENDLOOP; FOR i:CARDINAL IN [0..table.buckets.length) DO j _ 0; entry _ table.buckets[i]; WHILE entry # NIL DO j _ j+1; entry _ entry.nextInBucket; ENDLOOP; IF j < 10 THEN count[j] _ count[j] + 1 ELSE overflow _ overflow + 1; IF j > max THEN max _ j; ENDLOOP; FOR i:CARDINAL IN [0..10) DO IO.PutF[stream, "Number of buckets with %d entries: %d.\n", IO.int[i], IO.int[count[i]]]; ENDLOOP; IO.PutF[stream, "Number of buckets with > 9 entries: %d.\n", IO.int[overflow]]; IO.PutF[stream, "Largest bucket has %d entries.\n", IO.int[max]]; END; END. ´FILE: HashImpl.mesa Last edited by Ousterhout, May 10, 1983 10:53 am Barth, February 14, 1986 3:21:36 pm PST Christian LeCocq May 16, 1986 11:54:40 am PDT The following constant gives the ratio of entries to buckets at which we decide that a hash table is too full and rebuild it with a larger size. Round the size up to the next power of two. This is a private procedure to compute a hash table bucket index based on a rope. i: INT _ 0; FOR j: INT IN [0..Rope.Length[name]) DO i _ (10*i) + (Rope.Fetch[name, j] - '0); ENDLOOP; val _ ((i*1103515245) + 12345) / table.hashDivide; See if the entry is already in the table. The entry wasn't found. Before allocating a new entry, see if we're overloading the buckets. If so, then make a bigger table. This is a private procedure that rebuilds a hash table, making it four times larger than it used to be. Check for the star that means we do pattern matching. Strip off the prefix (everything in the string up to the "<"). Grab up the range. Grab up the postfix (everything in the string after the ">"). Be sure to ignore any backslashes. First of all, generate a pattern to test. Now either look it up or test it against all entries in the table. Ê á˜Jšœ™Jšœ0™0šœ'™'Icode™-—J˜šÏk ˜ J˜J˜Jšœ˜J˜Jšœ ˜ —J˜JšÏnœœ˜šœ˜J˜Jšœ˜J˜Jšœ˜—š˜J˜—J˜Jšœœ˜J˜Jšœ™J˜Jšœœ˜J˜J˜š žœœœœœ˜BJ˜Jš˜Jšœœ˜J˜Jšœœ˜J˜Jšœ+™+J˜J˜J˜*J˜šœ˜J˜J˜&J˜&šœ˜J˜——J˜Jšœœ˜#Jšœœ˜Jšœ ˜Jšœ˜—J˜J˜š žœœœœœ˜>J˜JšœQ™QJ˜Jš˜Jšœœ™Jšœœ˜ J™šœœœ™'J™(Jšœ™—J™J™2Jšœ$˜$Jšœ œ'˜™>J˜šœœ˜ J˜*J˜GJ˜Jšœœœ˜šœ˜Jš˜šœœ˜Jšœ6œ&˜a—Jšœ˜Jšœ˜—J˜Jšœœœ˜J˜J˜=Jšœ˜—J˜Jšœ™J˜šœ˜Jš˜J˜(šœ˜Jš˜šœœ˜ Jš˜šœœ˜Jšœ<˜>—Jšœ˜ Jšœ˜J˜—Jšœ œœ+˜:Jšœœ˜šœœ˜Jš˜šœœ˜Jšœ3˜5—Jšœ˜Jšœ˜—Jšœœ˜Jšœœ˜Jš˜—š˜Jš˜šœœ˜Jšœ3˜5—Jšœ˜Jšœ˜—J˜—˜Jšœ=™=Jšœ"™"—˜šœœ˜ J˜)J˜IJšœœœ˜šœ˜Jš˜šœœ˜Jšœ8˜:—Jšœ˜Jšœ˜—J˜?J˜Jšœ˜—Jšœ˜J˜—šœ˜J˜Jšœ)™)J˜šœ ˜Jš˜Jš œ œœœœ˜NJšœ œ˜!Jšœœ œ˜&Jšœ œ˜Jš˜—š˜Jš˜Jšœ œ˜J˜Jšœ˜J˜—JšœB™BJ˜šœ ˜Jš˜J˜šœ œ˜šœœ+œœ˜VJšœ˜—J˜Jšœ˜—Jš˜—š˜Jš˜J˜Jšœœœ˜6šœœœ˜Jšœ*œ˜?—Jšœ˜—Jšœ˜—Jšœ˜š˜Jšœœ˜—Jšœ˜—J˜J˜Jš žœœœœœ˜5˜Jš˜Jšœœœœ˜Jšœ œ˜Jšœœ˜ Jšœœ˜J˜ J˜Jš œœœ œœ˜2šœœœ˜.J˜J˜šœ œ˜J˜J˜Jšœ˜—Jšœœ˜&Jšœ˜Jšœ œ ˜Jšœ˜—J˜šœœœ ˜Jšœ9œ œ˜YJšœ˜—Jšœ:œ˜OJšœ2œ˜AJšœ˜J˜—Jšœ˜J˜˜J˜——…—P#å