<> <> <> <> 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.